The VNS Approach for a Consistent Capacitated Vehicle Routing Problem Under the Shift Length Constraints

Igor Kulachenko, Polina Kononova

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

We consider a new real-world application of vehicle routing planning in a finite time horizon. A company has a set of capacitated vehicles in some depots and must serve a set of clients. There is a frequency for each client stating how often this client must be visited. Time intervals between two consecutive visits must be the same but the visiting schedule is flexible. To get some competitive advantage, the company tries to increase its service quality. To this end, each client should be visited by one driver only. The goal is to minimize the total length of vehicles’ paths over the planning horizon under the frequency constraints and driver shift length constraints. We present an integer linear programming model for this new consistent capacitated vehicle routing problem. To find near-optimal solutions, we design the Variable Neighborhood Search metaheuristic with eleven neighborhood structures. The driver shift length and capacity constraints are penalized and included into the objective function. Empirical results for real test instances from Orenburg region in Russia with up to 900 clients and four weeks in the planning horizon are discussed.

Язык оригиналаанглийский
Название основной публикацииMathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers
РедакторыIgor Bykadorov, Vitaly Strusevich, Tatiana Tchemisova
ИздательSpringer Gabler
Страницы51-67
Число страниц17
ISBN (печатное издание)9783030333935
DOI
СостояниеОпубликовано - 1 янв 2019
Событие18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 - Ekaterinburg, Российская Федерация
Продолжительность: 8 июл 201912 июл 2019

Серия публикаций

НазваниеCommunications in Computer and Information Science
Том1090 CCIS
ISSN (печатное издание)1865-0929
ISSN (электронное издание)1865-0937

Конференция

Конференция18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019
СтранаРоссийская Федерация
ГородEkaterinburg
Период08.07.201912.07.2019

Fingerprint Подробные сведения о темах исследования «The VNS Approach for a Consistent Capacitated Vehicle Routing Problem Under the Shift Length Constraints». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Kulachenko, I., & Kononova, P. (2019). The VNS Approach for a Consistent Capacitated Vehicle Routing Problem Under the Shift Length Constraints. В I. Bykadorov, V. Strusevich, & T. Tchemisova (Ред.), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers (стр. 51-67). (Communications in Computer and Information Science; Том 1090 CCIS). Springer Gabler. https://doi.org/10.1007/978-3-030-33394-2_5