Проблема с переоформлением автомобиля

Задача перепланирования транспортных средств (VRSP) представляет собой задачу комбинаторной оптимизации и целочисленного программирования, направленную на обслуживание клиентов в поездке после изменения расписания, такого как поломка транспортного средства или серьезная задержка. Предложено Ли, Мирчандани и Боренштейном в 2007 году: ^[1] ВРСП является важной проблемой в сфере транспорта и логистики.

Определение оптимального решения - это NP-полная задача комбинаторной оптимизации. ^{[ нужна ссылка ]}, поэтому на практике для поиска приемлемо хороших решений для VRSP используются эвристические и детерминированные методы.

Обзор

Существует несколько вариантов и специализаций проблемы переоформления транспортных средств:

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

Хотя VRSP связан с проблемой планирования транспортных средств с одним депо и проблемой планирования транспортных средств с несколькими депо , существует значительная разница в требованиях к времени выполнения, поскольку VRSP необходимо решать практически в реальном времени, чтобы обеспечить перепланирование во время операций, в то время как SDVSP и MDVSP обычно решаются с использованием длительных методов линейного программирования. ^[2]

Еще одна область применения VRSP — перевозки грузов с целью изменения расписания маршрутов при существенном изменении спроса. ^[3]

См. также

Ссылки

^ Ли, Цзин-Цюань; Мирчандани, Питу Б.; Боренштейн, Денис (2007). «Задача переоформления транспортных средств: Модель и алгоритмы» . Сети . 50 (3): 211–229. дои : 10.1002/net.20199 .
^ Пепин, Анн-Софи; Десольнье, Ги; Герц, Ален; Хейсман, Деннис (февраль 2009 г.). «Сравнение пяти эвристик для задачи планирования движения транспортных средств с несколькими депо». Журнал планирования . 12 (1): 17–30. дои : 10.1007/s10951-008-0072-x . S2CID 34169965 .
^ Сплиет, Реми; Габор, Адриана Ф.; Деккер, Роммерт (март 2014 г.). «Проблема переоформления транспортного средства» . Компьютеры и исследования операций . 43 : 129–136. дои : 10.1016/j.cor.2013.09.009 . HDL : 1765/17350 .

Внешние ссылки

Optibus — коммерческая SaaS-платформа для решения VRSP в режиме реального времени.
Ecolane – Коммерческое программное обеспечение для транспорта, реагирующего на спрос

[LiMirchandani2007-1] Ли, Цзин-Цюань; Мирчандани, Питу Б.; Боренштейн, Денис (2007). «Задача переоформления транспортных средств: Модель и алгоритмы» . Сети . 50 (3): 211–229. дои : 10.1002/net.20199 .

[PepinDesaulniers2009-2] Пепин, Анн-Софи; Десольнье, Ги; Герц, Ален; Хейсман, Деннис (февраль 2009 г.). «Сравнение пяти эвристик для задачи планирования движения транспортных средств с несколькими депо». Журнал планирования . 12 (1): 17–30. дои : 10.1007/s10951-008-0072-x . S2CID 34169965 .

[3] Сплиет, Реми; Габор, Адриана Ф.; Деккер, Роммерт (март 2014 г.). «Проблема переоформления транспортного средства» . Компьютеры и исследования операций . 43 : 129–136. дои : 10.1016/j.cor.2013.09.009 . HDL : 1765/17350 .

[1]

[2]

[3]