Geum.ru

И. Д. Салмин московский инженерно-физический институт (государственный университет) постановка задачи коммивояжера с временными окнами и ее решение

Вид материалаРешение
Подобный материал:

УДК 004.4(06) Технологии разработки программных систем


В.В. АКСЁНОВ, И.Д. САЛМИН

Московский инженерно-физический институт (государственный университет)


ПОСТАНОВКА ЗАДАЧИ КОММИВОЯЖЕРА
С ВРЕМЕННЫМИ ОКНАМИ И ЕЕ РЕШЕНИЕ


В докладе представлена постановка задачи коммивояжера с временными окнами, описаны разработанные точный и приближенные методы нахождения ее решения.


В настоящее время эффективность решения транспортно-логистических задач имеет большое практическое значение. Классической задачей данного направления является задача коммивояжера (ЗК) [1,2,3]. В докладе рассматривается одна из разновидностей ЗК - задача коммивояжера с временными окнами (ЗКВО), в которой введены дополнительные ограничения на время доставки груза потребителям.

В ЗКВО требуется проложить маршрут движения автомобиля, развозящего заказы потребителям. Все заказы изначально загружены в машину на складе, который является исходной точкой маршрута. Для каждого потребителя задан промежуток времени, в течение которого он должен быть посещен машиной. Также заданы матрицы расстояний и времени проезда между потребителями. Требуется найти маршрут посещения потребителей, обладающий по возможности наивысшим качеством.

Если в маршруте машина прибывает к потребителю до начала интервала его обслуживания, то она ожидает его начала, после чего начинается разгрузка.

Если машина прибывает к потребителю после завершения временного интервала, маршрут либо считается недопустимым (задача с жесткими временными окнами), либо подвергается дополнительному штрафу за опоздание (задача с нежесткими, или мягкими временными окнами).

Перечислим характеристики маршрута, определяющие его качество:

Суммарная длина маршрута (Length).

Суммарное время движения по маршруту без учета времени простоя (MoveTime).

Суммарное время простоя в ожидании открытия клиентов (WaitTime).

Суммарное опоздание - для задачи с нежесткими временными окнами (LateTime).

Тогда целевая функция решаемой задачи примет следующий вид:

Min F = C1* Length + C2* MoveTime + C3* WaitTime + C4* LateTime

Также как и ЗК, ЗКВО является NP-сложной задачей. Более того, для ЗКВО даже нахождение допустимого решения уже является NP-сложной задачей.

Для решения ЗКВО с жесткими временными окнами был реализован метод нахождения оптимального решения, основанный на методе ветвей и границ. Ветвление состоит в выборе очередной точки маршрута (маршрут строится последовательно). Для расчета оценки нижней границы целевой функции адаптирован алгоритм Литла[2,3,4]. Реализованный метод позволяет за несколько секунд находить оптимальные решения задач размерностью 12-19 точек.

Для решения задач большей размерности разработан и реализован эвристический метод решения ЗКВО, основанный на алгоритме локального спуска. В нем были использованы 3 типа операций, задающих окрестность соседних решений[3,5] :
  • перестановка точки в другое место маршрута
  • замена местами в маршруте двух точек
  • инвертирование последовательности посещения фрагмента маршрута.

Разработанные методы позволяют решать ЗКВО, возникающие в логистической практике. Результаты работы в настоящее время используются в компании ЭРМАСОФТ Менеджмент.


Список литературы

  1. Салмин И.Д. Математические методы решения оптимизационных задач. М.: МИФИ, 2004. - 156 с.
  2. Литл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере. – “Экономика и математические методы” Т.1, вып. 1, 1965.
  3. Мудров В.И.. Задача о коммивояжере. – “Знание”, математика кибернетика №10, 1969. 64 с.
  4. Coy S. P., Golden B. L., Runger G. C., and Wasil E. A., “Using Experimental Design to Find E_ective ParameterSettings for Heuristics,” Journal of Heuristics 7, 77–97 (2000)
  5. Dumas Y., Desrosiers J., Gelinas E., and Solomon M. M., “An Optimal Algorithm for the Traveling Salesman Problem with Time Windows,” Operations Research 43, 367–371 (1995).




ISBN 5-7262-0633-9. НАУЧНАЯ СЕССИЯ МИФИ-2006. Том 2