Информационная система "Конференции"

Тезисы докладов

Вычислительная математика

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

Известны попытки повысить качество планирования за счет включения в постановку задачи элементов неопределенности (ЭН), таких, как возможность возникновения транспортных пробок, что дает возможность оптимизации с учетом рисков опозданий. Однако оптимизационные задачи с ЭН значительно сложнее для решения, поскольку вычисление значения целевой функции подразумевает необходимость вычисления одного или нескольких интегралов по функциям плотности вероятности возможных исходов. Также возрастают объемы необходимых исходных данных и требования к их точности. Если для решения классической ЗК достаточно знать расстояния между точками как константу, то при учете ЭН расстояния представляют собой случайные величины, возможно нестационарные. А поскольку оптимизации подвергаются в т.ч. и такие трудно визуализируемые величины, как взвешенные суммарные риски опоздания в заданные временные окна, то ошибки и погрешности, содержащиеся в исходных данных трудно выявить по внешнему виду полученного маршрута.

В качестве промежуточного варианта рассматривается разновидность постановки ЗК с временными окнами, в которой время проезда между пунктами является детерминированной величиной, зависящей от времени. Для решения предлагается использовать метаэвристические подходы, такие как метод итерационной локальной оптимизации(ILS), генетические алгоритмы(GA), Scatter Search(SS).

Литература

1. Аксенов В.В. Задача оптимизации маршрута транспортного средства. В кн.: Труды VIII Международного научно-технического семинара "Современные технологии в задачах управления, автоматики и обработки информации". Сентябрь 2007 г., Алушта. - Тула: Изд-во ТулГУ, 2007, с. 3-4.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:48:14)