This paper describes an exact algorithm for a variant of the vehicle routing problem in which customer demands to be collected are stochastic. Demands are revealed upon the vehicle arrival at customer locations. As a result, a vehicle may reach a customer and does not have sufficient capacity to collect the realized demand. Such a situation is referred to as a failure. In this paper the following recourse action is then applied when failure occurs: the vehicle returns to the depot to unload and resumes its planned route at the point of failure. The capacitated vehicle routing problem with stochastic demands (VRPSD) consists of minimizing the sum of the planned routes cost and of the expected recourse cost. The VRPSD is formulated as a two-stage stochastic programming model and solved by means of an integer L-shaped algorithm. This paper introduces three lower bounding functionals based on the generation of general partial routes, as well as an exact separation procedure to identify violated cuts. Extensive computational results confirm the effectiveness of the proposed algorithm, as measured by a substantial reduction in the number of feasible solutions that have to be explicitly eliminated. This translates into a higher proportion of instances solved to optimality, reduced optimality gaps, and lower computing times. © 2014 Elsevier B.V. All rights reserved.

Partial-route inequalities for the multi-vehicle routing problem with stochastic demands

JABALI, OLA;
2014-01-01

Abstract

This paper describes an exact algorithm for a variant of the vehicle routing problem in which customer demands to be collected are stochastic. Demands are revealed upon the vehicle arrival at customer locations. As a result, a vehicle may reach a customer and does not have sufficient capacity to collect the realized demand. Such a situation is referred to as a failure. In this paper the following recourse action is then applied when failure occurs: the vehicle returns to the depot to unload and resumes its planned route at the point of failure. The capacitated vehicle routing problem with stochastic demands (VRPSD) consists of minimizing the sum of the planned routes cost and of the expected recourse cost. The VRPSD is formulated as a two-stage stochastic programming model and solved by means of an integer L-shaped algorithm. This paper introduces three lower bounding functionals based on the generation of general partial routes, as well as an exact separation procedure to identify violated cuts. Extensive computational results confirm the effectiveness of the proposed algorithm, as measured by a substantial reduction in the number of feasible solutions that have to be explicitly eliminated. This translates into a higher proportion of instances solved to optimality, reduced optimality gaps, and lower computing times. © 2014 Elsevier B.V. All rights reserved.
2014
General partial routes, Integer L-shaped algorithm, Lower bounding functionals, Stochastic demand, Stochastic programming, Stochastic vehicle routing problem, Applied Mathematics, Discrete Mathematics and Combinatorics
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0166218X14002558-main.pdf

Accesso riservato

Descrizione: Articolo principale
: Publisher’s version
Dimensione 555.49 kB
Formato Adobe PDF
555.49 kB Adobe PDF   Visualizza/Apri
Partial-route inequalies for the multi-vehicle routing problem_11311-1005734_Jabali.pdf

accesso aperto

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 449.91 kB
Formato Adobe PDF
449.91 kB Adobe PDF Visualizza/Apri

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/1005734
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 36
  • ???jsp.display-item.citation.isi??? 31
social impact