A Rule-Based Recourse for the Vehicle Routing Problem with Stochastic Demands

Majid Salavati-Khoshghalb (), Michel Gendreau (), Ola Jabali () and Walter Rei ()
Additional contact information
Majid Salavati-Khoshghalb: Département d’Informatique et de Recherche Opérationnelle, Université de Montréal, Montreal, Quebec H3C 3J7, Canada; Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise, la Logistique et le Transport, Montreal, Quebec H3C 3J7, Canada;
Michel Gendreau: Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise, la Logistique et le Transport, Montreal, Quebec H3C 3J7, Canada; Département de Mathématiques et de Génie Industriel, Polytechnique Montréal, Montreal, Quebec H3C 3J7, Canada;
Ola Jabali: Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, Milan 20133, Italy;
Walter Rei: Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise, la Logistique et le Transport, Montreal, Quebec H3C 3J7, Canada; Département de Management et Technologie, École des Sciences de la Gestion, Université du Québec à Montréal, Montreal, Quebec H3C 3P8, Canada

Transportation Science, 2019, vol. 53, issue 5, 1334-1353

Abstract: In this paper we consider the vehicle routing problem with stochastic demands (VRPSD). We consider that customer demands are only revealed when a vehicle arrives at customer locations. Failures occur whenever the residual capacity of the vehicle is insufficient to serve the observed demand of a customer. Such failures entail that recourse actions be taken to recover route feasibility. These recourse actions usually take the form of return trips to the depot, which can be either done in a reactive or proactive fashion. Over the years, there have been various policies defined to perform these recourse actions in either a static or a dynamic setting. In the present paper, we propose policies that better reflect the fixed operational rules that can be observed in practice and that also enable implementing preventive recourse actions. We define the considered operational rules and show how, for a planned route, these operational rules can be implemented using a fixed threshold-based policy to govern the recourse actions. An exact solution algorithm is developed to solve the VRPSD under the considered policies. Finally, we conduct an extensive computational study, which shows that significantly better solutions can be obtained when using the proposed policies compared with solving the problem under the classic recourse definition.

Keywords: threshold-based recourse policies; operational rules; vehicle routing problem with stochastic demands; partial routes; integer L -shaped algorithm lower bounding functionals (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
https://doi.org/10.1287/trsc.2018.0876 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:53:y:2019:i:5:p:1334-1353

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().