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.

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

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2019
Local branching; Matheuristics; Stochastic demand; Stochastic programming; Stochastic vehicle routing problems; Vehicle routing; Software; Information Systems; Computer Networks and Communications; Control and Optimization; Management Science and Operations Research; Artificial Intelligence
File in questo prodotto:
File
Hernandez2019_Article_ALocalBranchingMatheuristicFor.pdf

Accesso riservato

Dimensione 686.26 kB

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11311/1087445`
• ND
• 12
• 12