Определение маршрутов методом совмещенных планов
Составляем оптимальный план возврата порожняка под погрузку:
Таблица 23. Оптимальный план возврата порожняка
Составляем матрицу совмещенных планов. Выделим отдельным цветом добавленные в матрицу совмещенные планы:
Таблица 24. Матрица совмещенных планов
Строим маршруты движения автомобилей непосредственно на матрице совмещенных планов. Вначале выбираем маятниковые маршруты, после кольцевые.
Маятниковые маршруты определяются клетками с двойной нагрузкой, при этом выбираем наименьшее из значений (в тоннах). В нашем случае клеток с двойной нагрузкой две:
Таблица 25. Выбор маятниковых маршрутов
Итак, маятниковые маршруты:
1) А1-Б1-А1, на котором необходимо развезти 126 тонн;
2) А4-Б3-А4, на котором необходимо развезти 72 тонны.
Удаляем из матрицы клетки с двойной загрузкой и составляем кольцевые маршруты:
Кольцевые маршруты составляем по следующему принципу: все нечетные вершины должны лежать в «груженых» клетках, а четные - в клетках с порожняком. Для удобства будем отмечать каждый четырехзвенный маршрут отдельным цветом.
1) Кольцевой маршрут А2-Б2-А3-Б5-А2 на 81 тонну. Исключаем данный маршрут и ищем новые маршруты.
Таблица 26. Четырехзвенный кольцевой маршрут
2) Кольцевой маршрут А5-Б3-А1-Б8-А5 на 54 тонны. Исключаем данный четырехзвенный маршрут и ищем новые маршруты.
Таблица 27. Четырехзвенный кольцевой маршрут
3) Кольцевой маршрут А5-Б1-А1-Б7-А5 на 54 тонны. Удаляем его из рассмотрения.
Таблица 28. Четырехзвенный кольцевой маршрут
Поиск четырехзвенных маршрутов завершен. Осуществляем поиск шестизвенных маршрутов:
4) Маршрут А5-Б1-А1-Б7-А6-Б5-А5 на 54 тонны. Исключаем его из рассмотрения:
Таблица 29. Шестизвенный кольцевой маршрут
|
Б1 |
Б2 |
Б3 |
Б4 |
Б5 |
Б6 |
Б7 |
||
|
А1 |
5 (81) |
1 |
7 |
8 |
4 |
2 |
14 81 |
|
|
А2 |
5 |
13 27 |
8 |
6 (27) |
3 |
1 |
7 |
|
|
А3 |
12 |
4 (27) |
14 |
13 |
11 27 |
4 |
12 |
|
|
А4 |
16 |
7 |
15 |
15 27 |
13 |
5 (27) |
15 |
|
|
А5 |
9 81 |
1 |
13 |
6 |
1 (81) |
1 |
4 |
|
|
А6 |
3 |
1 |
5 |
3 |
8 54 |
10 27 |
3 (81) |
Имеем следующую матрицу.
Таблица 30. Заключительный поиск кольцевых маршрутов
Осталось развести 6 точек по 27 тонн в каждую, а также осталось 6 клеток с 27 тоннами порожняка. В данном случае остался единственный замкнутый маршрут из 12 звеньев, который полностью удовлетворит запросы всех потребителей в грузах.
Маршрут выглядит следующим образом:
Таблица 31. 12-звенный кольцевой маршрут
|
Б1 |
Б2 |
Б3 |
Б4 |
Б5 |
Б6 |
Б7 |
Б8 |
||
|
А1 |
5 (27) |
1 |
7 |
8 |
4 |
2 |
14 27 |
15 |
|
|
А2 |
5 |
13 27 |
8 |
6 (27) |
3 |
1 |
7 |
3 |
|
|
А3 |
12 |
4 (27) |
14 |
13 |
11 27 |
4 |
12 |
10 |
|
|
А4 |
16 |
7 |
15 |
15 27 |
13 |
5 (27) |
15 |
12 |
|
|
А5 |
9 27 |
1 |
13 |
6 |
1 (27) |
1 |
4 |
1 |
|
|
А6 |
3 |
1 |
5 |
3 |
8 |
10 27 |
3 (27) |
2 |
А5-Б1-А1-Б7-А6-Б6-А4-Б4-А2-Б2-А3-Б5-А5 на 27 тонн.
Проверяем, весь ли груз таким образом будет доставлен потребителям. Имеем: 126+72+(81+54+54)*2+54*3+27*6=900, таким образом, маршруты полностью удовлетворят запросы потребителей.
