Том 22, номер 6, 2015 г., Стр. 55–77
УДК 519.85
Хмелёв А. В.
Трёхфазный алгоритм оптимизации автопарка и маршрутов транспортных средств
Аннотация:
Рассматривается задача оптимизации автопарка и маршрутов транспортных средств в предположении, что каждый клиент имеет временное окно для его обслуживания. Водители транспортных средств работают посменно. Каждая смена имеет начало, конец и определённое число перерывов для отдыха. Построена математическая модель в терминах частично-целочисленного линейного программирования. Разработан трёхфазный алгоритм локального поиска с эффективной процедурой просмотра окрестности. Численные эксперименты на тестах одной из новосибирских транспортных компаний показали эффективность разработанного подхода и значительное снижение издержек.
Табл. 2, ил. 4, библиогр. 13.
Ключевые слова: задача маршрутизации, временнґое окно, рабочая смена, перерыв, локальный поиск, оптимизация автопарка.
DOI: 10.17377/daio.2015.22.496
Хмелёв Алексей Владимирович 1
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: avhmel@gmail.com
Статья поступила 3 июня 2015 г.
Исправленный вариант — 11 августа 2015 г.
Литература
[1] Кочетов Ю. А., Хмелёв А. В. Гибридный алгоритм локального поиска для задачи маршрутизации транспортных средств с неоднородным автопарком // Дискрет. анализ и исслед. операций. 2015. T. 22, № 5. C. 5–29.
[2] Bent R., van Hentenryck P. A two-stage hybrid local search for the vehicle routing problem with time windows // Transp. Sci. 2004. Vol. 38, No. 4. P. 515–530.
[3] Bostel N., Dejax P., Guez P., Tricoire F. Multiperiod planning and routing on a rolling horizon for field force optimization logistics // The vehicle routing problem: Latest advances and new challenges. Vol. 43. New York: Springer-Verl., 2008. P. 503–525.
[4] Bräysy O., Gendreau M. Vehicle routing problem with time windows. Part I: Route constraction and local search algorithms // Transp. Sci. 2005. Vol. 39. P. 104–118.
[5] Bräysy O., Gendreau M. Vehicle routing problem with time windows. Part II: Metaheuristics // Transp. Sci. 2005. Vol. 39, No. 1. P. 119–139.
[6] Gagliardi J.-Ph., Renaud J., Ruiz A., Coehlo C. L. The vehicle routing problem with pauses // Tech. Rep. 2014–22, CIRRELT, Montreal, QC, Canada, 2014.
[7] Gehring H., Homberger J. Parallelization of a two-phase metaheuristic for routing problems with time windows // Asia-Pac. J. Oper. Res. 2001. Vol. 18, No. 1. P. 35–47.
[8] Goel A. Vehicle scheduling and routing with drivers’ working hours // Transp. Sci. 2009. Vol. 43, No. 1. P. 17–26.
[9] Goel A., Archetti C., Savelsbergh M. Truck driver scheduling in Australia // Comput. Oper. Res. 2012. Vol. 39, No. 5. P. 1122–1132.
[10] Goel A., Vidal T. Hours of service regulations in road freight transport: An optimization-based international assessment // Transp. Sci. 2014. Vol. 48, No. 3. P. 391–412.
[11] Mladenovic N., Hansen P. Variable neighborhood search // Comput. Oper. Res. 1997. Vol. 24, No. 11. P. 1097–1100.
[12] Nagata Yu., Bräysy O. A powerful route minimization heuristic for the vehicle routing problem with time windows // Oper. Res. Lett. 2009. Vol. 37, No. 5. P. 333–338.
[13] Sahoo S., Kim S., Kim B.-I., Kraas B., Popov A., Jr. Routing optimization for waste management // Interfaces. 2005. Vol. 35, No. 1. P. 24–36.
[14] Vidal T., Crainic T. G., Gendreau M., Prins C. A unified solution framework for multi-attribute vehicle routing problems // Eur. J. Oper. Res. 2014. Vol. 234, No. 3. P. 658–673.
