Адаптация метаэвристики ОМРЧ для задачи динамической маршрутизации транспортного средства

Описание частиц

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

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

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

Решение задачи динамической маршрутизации методом роя частиц 153 Rk:0, Cj, с2, ..., Cj,..., сп, ся+1).

Начальной точкой маршрута является депо (с0 = сп+1). Для моделирования мы присваиваем каждому клиенту ct следующую информацию:

(Xj, Y(): координаты клиента c-v

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

Tf время обслуживания клиента ct (время, когда он был обслужен).

Маршрут Rk обслуживается транспортным средством vy. Для каждого транспортного средства Vj мы имеем следующую информацию:

{Xj, Yj): координаты транспортного средства Vj на покрываемой области;

Сару: остаточная вместимость транспортного средства vj,

Disty: пройденное расстояние транспортного средства vy .

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

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