Highlights We focus on the use of branch-and-price in a dynamic decision making environment to investigate its potential as a solution methodology for operational problems. We introduce and consider a dynamic variant of the vehicle routing problem with roaming delivery locations, and develop an iterative re-optimization framework to solve it. We propose and employ methods that make efficient use of the information collected during the solution of previous optimization problems in order to produce solutions quickly during the operational stage. Our computational results demonstrate the potential of branch-and-price for solving operational problems and the benefits of re-using previously collected information.

    Abstract Branch-and-price has established itself as an effective solution methodology for a wide variety of planning problems. We investigate its potential as a solution methodology for solving operational problems. Specifically, we explore its potential in the context of a dynamic variant of the vehicle routing problem with roaming delivery locations, in which customer itineraries may change during the execution of a planned delivery schedule, which, in turn, may cause the planned delivery schedule to become suboptimal or even infeasible. We propose an iterative solution framework in which an active delivery schedule is re-optimized whenever a customer itinerary update is revealed. We use a branch-and-price algorithm for solving the planning problem (to obtain an initial delivery schedule) as well as the re-optimization problems (to obtain modified delivery schedules). As the re-optimization problems are solved during the execution of the (active) delivery schedule, it is critical to produce solutions quickly. This is accomplished by re-using, suitably modified, columns generated during preceding branch-and-price solves. The results of our computational experiments demonstrate the viability of using branch-and-price for solving operational problems and the benefit (necessity) of re-using information from previous solves.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    An iterative re-optimization framework for the dynamic vehicle routing problem with roaming delivery locations


    Beteiligte:


    Erscheinungsdatum :

    2019-08-08


    Format / Umfang :

    29 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Vehicle routing with roaming delivery locations

    Reyes, Damián / Savelsbergh, Martin / Toriello, Alejandro | Elsevier | 2017


    A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations

    Ozbaygin, Gizem / Ekin Karasan, Oya / Savelsbergh, Martin et al. | Elsevier | 2017


    Dynamic vehicle routing problem with drone resupply for same-day delivery

    Pina-Pardo, Juan C. / Silva, Daniel F. / Smith, Alice E. et al. | Elsevier | 2024


    Iterative Local-Search Heuristic for Weighted Vehicle Routing Problem

    Wang, Xinyu / Shao, Shuai / Tang, Jiafu | IEEE | 2021


    An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem

    Archetti, C. / Speranza, M.G. / Savelsbergh, M.W.P. | British Library Online Contents | 2008