Задачи маршрутизации транспортных средств

В этом разделе мы рассматриваем, в первую очередь, задачу маршрутизации транспортного средства в статическом варианте, а уже затем в динамическом варианте.

Задача статической маршрутизации транспортного средства

Задача маршрутизации транспортного средства (ЗМТС) является задачей оптимизации, которая была сформулирована Данцигом и Рам- сером в 1959 году [ДАН 59]. Она состоит из определения маршрута путем минимизации его стоимости, набора маршрутов для ограниченного числа транспорта, начальной и конечной точек, находящихся в депо, таким образом, что каждый клиент посещается транспортным средством только один раз, и суммы запросов от клиентов на маршрут, не превышающей вместимость транспортного средства, которое обслуживает этот маршрут.

Более формально, ЗМТС может быть смоделирована следующим образом:

Пусть G= (С, Е) будет графом, где С= {с0, с1? с2,..., сп} — это набор транспортных средств с вершиной с0, рассматриваемой как депо,

Е = {(с/5 Cj) | с{, Cj е С} - это набор дуг, иС' = С {с0} — набор городов и клиентов.

Каждая дуга связана с неотрицательной стоимостью dy. Это можно интерпретировать как стоимость поездки или времени пути между с;-

и Сумы предполагаем, что у нас есть т идентичных транспортных средств одинаковой мощности. ЗМТС состоит в определении набора маршрутов с минимальной стоимостью (то есть расстоянием) так, что:

  • — каждый город С посещен один раз одним транспортным средством;
  • — все маршруты начинаются и кончаются в депо;
  • — определенные условия будут выполнены. Эти условия определяют различные варианты проблемы.

Эта проблема может быть выражена следующим образом:

где:

  • п — число вершин;
  • т — число транспортных средств;
  • dy — стоимость или расстояние между вершинами ci и су-.
  • 1, если сегмент (с,-, с у) покрывается транспортным Ху = < средством к

О в противном случае.

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

В случае планирования маршрута транспортного средства в статическом режиме, как правило, принято считать, что [LAR 00]:

  • — вся необходимая информация (т.е. данные задачи) известна планировщику перед началом процесса планирования;
  • — эта информация не меняется после того, как маршруты спланированы;
  • — эта информация включает в себя все атрибуты клиентов, такие как географическое положение, время обслуживания, каждый запрос клиента (то есть количество, которое будет собрано либо доставлено). Кроме того, информация о времени пути между клиентами, которые будут обслужены, должна быть известна или измерима планировщиком.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >