Проблема перепланирования автомобиля - Vehicle rescheduling problem - Wikipedia
В проблема перепланирования транспортных средств (VRSP) это комбинаторная оптимизация и целочисленное программирование проблема с поиском обслуживания клиентов в поездке после изменения расписания, например, поломки автомобиля или серьезной задержки. Предложено Ли, Мирчандани и Боренштейном в 2007 г.[1] ВРСП - важная проблема в сфере транспорта и логистики.
Определение оптимального решения - это НП-полный проблема в комбинаторная оптимизация, поэтому на практике эвристические и детерминированные методы используются для поиска приемлемо хороших решений для VRSP.
Обзор
Существует несколько разновидностей и специализаций проблемы перепланирования транспортных средств:
- Проблема перепланирования транспортного средства в одном депо (SDVRSP): необходимо перенести несколько рейсов из-за задержки, поломки транспортного средства или по любой другой причине. Цель состоит в том, чтобы найти оптимальное изменение графика существующего парка, используя, возможно, дополнительные автомобили из депо, чтобы минимизировать задержки и эксплуатационные расходы. В варианте с одним депо есть только одно депо, которое содержит все дополнительные автомобили и в котором каждое транспортное средство начинает и заканчивает свой график.
- Проблема перепланирования транспортных средств с несколькими депо (MDVRSP): аналогична SDVRSP, за исключением того, что вводятся дополнительные депо. У каждого депо есть ограничения по вместимости, а также различные дополнительные транспортные средства. Обычно графики движения транспортных средств имеют дополнительное ограничение, которое требует, чтобы каждое транспортное средство возвращалось в депо, с которого оно начало свое расписание.
- Проблема изменения расписания открытых транспортных средств (OVRSP): Транспортные средства не должны возвращаться в депо.
Хотя VRSP относится к Проблема планирования одного депо и Проблема планирования нескольких депо, существует значительная разница в требованиях к среде выполнения, так как VRSP необходимо решать в режиме, близком к реальному времени, чтобы можно было перепланировать во время операций, в то время как SDVSP и MDVSP обычно решаются с использованием методов длительного линейного программирования.[2]
Еще одна сфера применения VRSP - это транспортировка товаров с целью перепланирования маршрутов при значительном изменении спроса.[3]
Смотрите также
- Комбинаторная оптимизация
- Проблема с маршрутизацией автомобиля
- Основы транспортировки / Составление расписания и планирование
Рекомендации
- ^ Ли, Цзин-Цюань; Mirchandani, Pitu B .; Боренштейн, Денис (2007). «Проблема перепланирования транспортных средств: модель и алгоритмы». Сети. 50 (3): 211–229. Дои:10.1002 / нетто.20199.
- ^ Пепин, Анн-Софи; Desaulniers, Guy; Герц, Ален; Хейсман, Деннис (февраль 2009 г.). «Сравнение пяти эвристик для задачи планирования транспортных средств с несколькими депо». Журнал планирования. 12 (1): 17–30. Дои:10.1007 / s10951-008-0072-х.
- ^ Сплит, Реми; Габор, Адриана Ф .; Деккер, Роммерт (март 2014 г.). «Проблема перепланирования автомобиля». Компьютеры и исследования операций. 43: 129–136. Дои:10.1016 / j.cor.2013.09.009. HDL:1765/17350.