Abstract We study a dynamic vehicle routing problem where stochastic customers request urgent deliveries characterized by restricted time windows. The aim is to use a fleet of vehicles to maximize the number of served requests and minimize the traveled distance. The problem is known in the literature as the same-day delivery problem, and it is of high importance because it models a number of real-world applications, including the delivery of online purchases. We solve the same-day delivery problem by proposing a novel branch-and-regret algorithm in which sampled scenarios are used to anticipate future events and an adaptive large neighborhood search is iteratively invoked to optimize routing plans. The branch-and-regret is equipped with four innovation elements: a new way to model the subproblem, a new policy to generate scenarios, new consensus functions, and a new branching scheme Extensive computational experiments on a large variety of instances prove the outstanding performance of the branch-and-regret, also in comparison with recent literature, in terms of served requests, traveled distance, and computational effort.

    Highlights We study the same-day delivery problem. Stochastic customers request urgent deliveries within restricted time windows. We propose a novel branch-and-regret algorithm. Sampled scenarios are used to anticipate future events. Computational experiments prove the outstanding performance of the branch-and-regret.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    A branch-and-regret algorithm for the same-day delivery problem


    Beteiligte:


    Erscheinungsdatum :

    2023-07-13




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    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



    Regret, Valuation, and Inaction Inertia

    Arkes, Hal R. | Online Contents | 2002


    Solving blocking flowshop scheduling problem with branch and bound algorithm

    Toumi, Said / Jarboui, Bassem / Eddaly, Mansour et al. | IEEE | 2013


    New Model of Random Regret Minimization

    Caspar G. Chorus | DOAJ | 2010

    Freier Zugriff