A hybrid recourse policy for the vehicle routing problem with stochastic demands

Majid Salavati-Khoshghalb (), Michel Gendreau (), Ola Jabali () and Walter Rei ()
Additional contact information
Majid Salavati-Khoshghalb: la Logistique et le Transport (CIRRELT)
Michel Gendreau: la Logistique et le Transport (CIRRELT)
Ola Jabali: la Logistique et le Transport (CIRRELT)
Walter Rei: la Logistique et le Transport (CIRRELT)

EURO Journal on Transportation and Logistics, 2019, vol. 8, issue 3, No 3, 269-298

Abstract: Abstract In this paper, we propose a new recourse policy for the vehicle routing problem with stochastic demands (VRPSD). In this routing problem, customer demands are characterized by known probability distributions. The actual demand values are only revealed upon arriving at a customer location. The objective of the problem is to plan routes minimizing the travel cost and the expect recourse cost. The latter cost is a result of a predetermined recourse policy designed to handle route failures. Given the planned routes, such failures may occur in the event where a vehicle has insufficient capacity to serve the current customer or the next customer. In the relevant literature, there are three types of recourse policies: (i) classical, where failures at customers are handled by return trips to the depot, (ii) optimal restocking, where preventive restocking trips to the depot are performed based on optimized customer-specific thresholds, and failures are handled by return trips to the depot, and (iii) rule-based policies, where preventive restocking trips are performed based on thresholds established by preset rules, and failures are handled by performing return trips to the depot. While the first type is rather myopic, the last two types of recourse policies use simplistic comparisons of the vehicle’s residual capacity to trigger recourse actions. In this paper, we propose a more advanced rule-based recourse policy, which does not solely depend on the vehicle’s residual capacity. To do so, we first propose a taxonomy that groups rule-based policies into three classes, we then propose the first hybrid recourse policy, which simultaneously combines two of these classes, namely risk and distance. We develop an exact solution algorithm for the VRPSD with this hybrid recourse policy and conduct a broad range of computational experiments. The algorithm is able to solve instances with up to 60 customers, and for certain experimental configurations, the exact algorithm solves to optimality up to 79% of the instances. Finally, we show that when the optimal routes of the hybrid policy are operated under the optimal restocking policy they yield a marginal average cost difference.

Keywords: Hybrid recourse policy; Preventive restocking; Operational rules; Vehicle routing problem with stochastic demands; Partial routes; 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 (18)

Downloads: (external link)
http://link.springer.com/10.1007/s13676-018-0126-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:eurjtl:v:8:y:2019:i:3:d:10.1007_s13676-018-0126-y

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13676

DOI: 10.1007/s13676-018-0126-y

Access Statistics for this article

EURO Journal on Transportation and Logistics is currently edited by Michel Bierlaire

More articles in EURO Journal on Transportation and Logistics from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().