A local branching matheuristic for the multi-vehicle routing problem with stochastic demands

Florent Hernandez (), Michel Gendreau (), Ola Jabali () and Walter Rei ()
Additional contact information
Florent Hernandez: Polytechnique Montréal
Michel Gendreau: Polytechnique Montréal
Ola Jabali: Politecnico di Milano
Walter Rei: Université du Québec à Montréal

Journal of Heuristics, 2019, vol. 25, issue 2, No 3, 215-245

Abstract: Abstract This paper proposes a local branching matheuristic for the vehicle routing problem with stochastic demands (VRPSD). The problem is cast in a two-stage stochastic programming model, in which routes are planned in the first stage and executed in the second stage. In this setting, a failure may occur if a vehicle does not have sufficient capacity to serve the realized demand of a customer, which is revealed only upon arrival at a customer’s location. In the event of a failure, a recourse action is performed by having the vehicle return to the depot to replenish its capacity and resume its planned route at the point of failure. Thus, the objective of the VRPSD is to minimize the sum of the planned routes cost and of the expected recourse cost. We propose a local branching matheuristic to solve the multi-VRPSD. We introduce an intensification procedure applied at each node of the local branching tree. This procedure is embedded in a multi-descent scheme for which we propose a diversification strategy. Extensive computational results demonstrate the effectiveness of our matheuristic.

Keywords: Local branching; Stochastic vehicle routing problems; Vehicle routing; Stochastic demand; Stochastic programming; Matheuristics (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-018-9392-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:joheur:v:25:y:2019:i:2:d:10.1007_s10732-018-9392-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-018-9392-y

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().