Route Minimization Heuristic for the Vehicle Routing Problem with Multiple Pauses

Alexey Khmelev

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

    Аннотация

    In this work we introduce the vehicle routing problem with multiple pauses, where the fleet is heterogeneous in terms of capacity and drivers availability. Each shift has a time interval when the driver is available and a set of breaks that needs to be scheduled in the route during this shift. The objective is to minimize the number of vehicles and the travel distance. To tackle large instances, we develop a three-phase local search algorithm taking multiple breaks into account by introducing an ejection pool and randomized variable neighborhood descent as local improvement procedure. For effective break scheduling, we develop a special dynamic programming routine. Computational experiments are done on the data set provided by a delivery company situated in Novosibirsk, Russia. The instances contain 1000 customers and 30 vehicles. Experiments show effectiveness of our algorithm. It substantially reduces the fleet and travel distance.

    Язык оригиналаанглийский
    Название основной публикацииOPERATIONS RESEARCH PROCEEDINGS 2015
    РедакторыKF Doerner, Ljubic, G Pflug, G Tragler
    ИздательSpringer International Publishing AG
    Страницы265-271
    Число страниц7
    ISBN (печатное издание)978-3-319-42901-4
    DOI
    СостояниеОпубликовано - 8 мар 2017
    СобытиеOperations Research Conference (OR) - Vienna, Австрия
    Продолжительность: 1 сен 20154 сен 2015

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

    НазваниеOperations Research Proceedings
    ИздательSPRINGER INTERNATIONAL PUBLISHING AG
    ISSN (печатное издание)0721-5924

    Конференция

    КонференцияOperations Research Conference (OR)
    СтранаАвстрия
    ГородVienna
    Период01.09.201504.09.2015

    Цитировать