Решение задачи динамической маршрутизации методом роя частиц

Введение

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

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

Это привело к разработке модели управления транспортной системой, которая также называется динамическим управлением, где некоторые данные зависят от времени. Это особенно выгодно в связи с последними достижениями в области ИКТ, благодаря которым автопарком можно управлять в режиме реального времени.

При совместном использовании такие устройства, как географические информационные системы (ГИС), системы глобального позиционирования (GPS), датчики транспортного потока и сотовые теле-

Глава написана Мостефа Редуан Кхоаджи, Летицией Джордан и Эль Газали Талби.

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

В этой главе мы изучаем динамическое расширение обычной задачи маршрутизации транспортных средств и ее решение путем метаэврис- тической парадигмы. Введенная в 1995 году Кеннеди и Эберхартом [KEN 95], эта парадигма представляет собой оптимизацию методом роя частиц.

В разделе 4.2 мы описываем задачу динамической маршрутизации транспортного средства, ее моделирование и сопутствующие проблемы. В разделе 4.3 введем метаэвристический метод роя частиц и в разделе 4.4 опишем способ его адаптации для решения задач. В разделе 4.5 предоставим численные результаты и анализ. Раздел 4.6 содержит заключения и перспективу.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >