English
!

Архив публикаций

Тезисы

XV-ая конференция

Метод решения некоторых задач маршрутизации, основанный на упрощении маршрута до кратчайшего пути с ограничением

Павлов Д.В.

Институт машиноведения им. А.А. Благонравова РАН, лаборатория биомеханики, Россия, 117334, Москва, ул. Бардина, д.4, Тел: 135-5523, E-mail: Iteration@inbox.ru

1  стр.

Самой известной NP-трудной задачей маршрутизации является задача коммивояжера и ее общий случай – задача о развозке товара. В задаче коммивояжера необходимо объехать заданное множество из n городов наиболее эффективным образом, т. е. нужно составить кратчайший элементарный цикл, проходящий через каждый город по одному разу. Существует много подходов к решению задачи коммивояжера, однако в случае дополнительных ограничений на маршрут большинство из них не эффективны. Если расстояния между пунктами не статичны, а зависят от параметра времени, моделируя городские пробки, то задача значительно усложняется. Другой вариацией является задача о развозке, в которой необходимо сформировать несколько элементарных маршрутов от склада к клиентам и развести все заказы при помощи ограниченного парка машин.

Для точного или приближенного решения данных задач, часто применяется метод ветвей и границ. В первую очередь эффективность этого метода определяется эффективностью процедуры нижней границы. Процедура нижней границы это метод оценки целевой функции задачи снизу (для задач на поиск минимума). Под эффективностью процедуры понимается соотношение точности оценки снизу и времени выполнения. Если процедура оценки не NP-трудная, то определяющее значение имеет точность нижней границы.

В 1971 Хелд и Карп предложили использовать кратчайший остов графа для оценки тура коммивояжера снизу. Заметим, что расстояния между вершинами графа можно изменить, прибавляя к вершинам графа некоторые числа – “дополнительные расстояния”, при этом сам тур коммивояжера не изменится. В тоже время релаксация тура – кратчайший остов может значительно изменить структуру и стать похожей на тур коммивояжера. Эта идея оказалась очень продуктивной, однако она не работает в случае задачи коммивояжера с параметром времени или в случае задачи о развозке. В этих случаях было предложено использовать другую релаксацию тура – кратчайший цикл, проходящий ровно через n вершин графа. При этом цикл не должен содержать подциклов малой длины (т.е. три-четыре соседних пункта в маршруте не могут попарно совпадать). В иностранной литературе такой маршрут принято называть k-SPPRC релаксацией, ее не сложно построить с помощью алгоритма динамического программирования.

В докладе рассматриваются некоторые модификации k-SPPRC цикла как оценке нижней границы для задачи коммивояжера и задачи о развозке товара. В частности, k-SPPRC цикл, обязательно проходящий через вершины выпуклой оболочки исходного множества вершин. Точность такой оценки заметно возрастает, а принцип построения не меняется. На базе данных процедур нижней границы строится алгоритм ветвей и границ для точного либо приближенного решения задачи о развозке товара и задачи коммивояжера.

Было выполнено множество вычислительных экспериментов, вся информация о которых приводится в докладе. Для задачи о развозке точность нижней границы составляет 97-98%, что позволяет решать задачи на множестве 40-50 городов. Для задачи коммивояжера точность нижней границы составляет примерно 98.5-99%, что позволяет решать задачи на множестве до 100 городов. В случае дополнительных ограничений на маршрут, алгоритм может быть еще более эффективным. Кроме того, был реализован полноценный программный комплекс автоматизации планирования маршрутов.



© 2004 Дизайн Лицея Информационных технологий №1533