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

Есть два основных компонента в предлагаемом методе решений:

  • 1. Планировщик событий собирает новые заказы, полученные в ходе рабочего дня. Он использует эту информацию, чтобы определить задачи (образцы) в качестве частично статической ЗМТС. Кроме того, он управляет организацией заданий для водителей транспортных средств.
  • 2. Компонент ОАМРЧ (Оптимизация адаптивного метода роя частиц) используется в качестве эвристики для решения части образцов ЗМТС. Эти образцы создаются заранее планировщиком событий.

Такая схема решения была принята Мотеманни в [MON 05], а также Хэрземом [НОU 06] и Хэншером [HAN 07].

Далее мы подробнее опишем эти два компонента.

Планировщик событий

Планировщик событий выступает в качестве интерфейса для поступления новых запросов и алгоритма оптимизации. Основываясь на принципе разделения рабочего дня на несколько периодов времени (временных срезов), а также общем размере издержек в «отрезке времени» новых заказов, планировщик генерирует частичные образцы и последовательно запускает для них алгоритм ОАМРЧ. Решения, найденные в ходе поиска, будут использованы для планирования назначения транспортных средств для обслуживания клиентов.

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

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

Кроме того, транспортные средства возвращаются в депо, если и только если:

  • — все клиенты обслуживаются до конца рабочего дня;
  • — транспортное средство использовало всю свою вместимость.

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

Псевдоалгоритм планировщика событий описан в Алгоритме 4.1. Изначально все Невыполненные запросы содержат запросы, известные с предыдущего дня. Временная переменная устанавливается в нулевое положение, а транспортные средства расположены в депо. Процесс моделирования осуществляется в сочетании с резолюцией. Частичный образец, содержащий Невыполненные запросы, генерируется и решается с помощью алгоритма, описанного в разделе 4.4.3. Таким образом, транспортные средства назначаются обслуживать клиентов в соответствии с решением Частичного образца, и запросы могут быть обработаны в течение интервала времени [Время; Время + Ts].

Наконец, обновляются все Невыполненные запросы и остаточная емкость транспортных средств. Эти операции повторяются до тех пор, пока все клиенты не будут обслужены (Невыполненные запросы = 0), затем транспортные средства возвращаются в депо, как в конечный пункт назначения.

Алгоритм 4.1. Процедура планирования событий_

  • Time.- 0;
  • — Транспортные средства находятся в депо;
  • Невыполненные запросы:= известные запросы с прошедшего дня (все заказы, полученные после Гс0);

До тех пор пока (Невыполненные запросы ф 0) выполняется

  • Частичный образец:- образец запроса из Невыполненных запросов;
  • — Выполняется АОМРЧ для Частичного образца;
  • Общие запросы:= запросы с временным окном Р( е [Время, Время + Тф
  • — Назначение транспортных средств на обслуживание запросов из набора Общих запросов;
  • Невыполненные запросы:= Невыполненные запросы Общие запросы,
  • Невыполненные запросы:^ Невыполненные запросы^) {запросы, прибывшие в течение последнего отрезка времени};
  • Время := Время + Т$
  • — Обновление позиции, вместимости и времени пути транспортных средств;

Заканчивается, как только

— Команда транспортных средств возвращается в депо

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