Задачу по оптимизации маршрута легко представить в виде сети, так как каждое перемещение из пункта отправки в пункт прибытия является направленным и представляет собой дугу, а сами пункты в таком случае, представляют вершины сети (сетью называется ориентированный граф, в котором существует лишь одна вершина, не имеющая входящих дуг, и лишь одна вершина, не имеющая выходящих дуг).
Карта, приведенная на рисунке 25, по своей сути сама является сетью, но сеть удобнее представлять в упрощенном виде, не соблюдая масштабов и пропорций, а указывая только связи между вершинами:
Рисунок 26. Сеть поставленной задачи по оптимизации маршрута
Пункты пронумерованы в порядке «слева-направо, сверху-вниз». Стрелки на концах дуг указывают направления, в которых может происходить перемещение транспорта из одного пункта в другой. В целях упрощения расчетов будем считать, что перемещение обратно в пункт 1 из пунктов 2, 3 и 4 невозможно (так как не соответствует требованиям задачи); также невозможен выезд из пункта 15 (так как цель уже достигнута). Рядом с каждой дугой указана ее характеристика (в данном случае – расстояние между пунктами в километрах).
Для решения задач оптимизации маршрута разработаны несколько методов: метод полного перебора вариантов, метод ветвей и границ, метод Дейкстры и т.д. Но для выполнения вручную они требуют значительных затрат времени, а для автоматизированного решения – специальных программных средств.
Практически любую сетевую задачу оптимизации маршрута движения можно решить с помощью методов линейного программирования. В качестве переменных в данной задаче принимаются передвижения по дугам. Например, передвижение из пункта 2 в пункт 4 будет обозначено переменной X2-4 , а переезд из пункта 4 в пункт 2 – переменной X2-4. Таким образом, дуге с двумя стрелками на концах будут соответствовать две переменные, дуге с одной стрелкой – одна переменная. Переменные в этой задаче – булевого (двоичного) типа, они принимают значение 0, если перемещение по дуге состоялось, и значение 1, если перемещения не было.
Таким образом, выезд транспортного средства из пункта 1 может быть описан в следующем виде:
.
Так как переменная булева, то лишь одна из трех переменных примет значение 1. Например, если X1-3 = 1, то транспортное средство переместится из пункта 1 в пункт 3.
Проезд через остальные пункты будет обеспечен уравнениями следующего вида (пример ‑ уравнение для пятого пункта):
.
По этому условию количество выездов из 5 пункта (во 2, 3, 7 или 8 пункт) равно количеству въездов в него (из 2, 3, 7 или 8 пункта). В левой, как и в правой части уравнения, лишь одна переменная может принять значение 1. Например, X5-8 = 1 и X3-5 = 1, таким образом, в пятый пункт транспорт прибыл из третьего, а уедет – в восьмой. Для простоты реализации этих уравнений в «Поиске решения» перенесем переменные из правой части в левую:
.
Достижение конечного (пятнадцатого) пункта будет реализовано следующим уравнением:
.
Целевая функция данной задачи представляет собой пройденное расстояние, находимое как сумма произведений расстояний между пунктами на количество переездов между ними (0 или 1):
.
В структурном виде данная задача записывается следующим образом:
где n – количество вершин сети (или номер конечного пункта назначения), Сi-j – вес дуги i-j (расстояние от i-го пункта до j-го пункта).
Сетевая модель в матричной форме приведена в таблице 36.
Анализ результатов решения задачи
Задача решалась в табличном процессоре Microsoft Excel с использованием надстройки Solver («Поиск решения»). В результате решения следующие переменные приняли значение 1: X1-4, X4-7, X7-9, X9-12 и X12-15. Значение целевой функции составило 43,6 км.
Оптимальный маршрут 1-4-7-9-12-15 протяженностью 43,6 км представлен выделенной линией на рисунках 27 и 28.
Рисунок 27. Сеть поставленной задачи с указанием оптимального маршрута
Рисунок 28. Карта автодорожной сети с указанием оптимального маршрута
.
.
.
.
.
