We study the General Routing Problem defined on a mixed graph and with stochastic demands. The problem under investigation is aimed atfinding the minimum cost set of routes to satisfy a set of clients whose demand is not deterministically known. Since each vehicle has a limited capacity, thedemand uncertainty occurring at some clients affects the satisfaction of the capacity constraints, that, hence, become stochastic. The contribution of this paper is twofold: firstly we present a chance-constrained integer programmingformulation of the problem for which a deterministic equivalent is derived.The introduction of uncertainty into the problem poses severe computational challenges addressed by the design of a branch--and--cut algorithm, for the exact solution of limited size instances, and of a heuristic solution approach exploring promising parts of the search space.The effectiveness of the solution approaches is shown on a probabilistically constrained version of the benchmark instances proposed in the literature for the mixed capacitated general routing problem.

The Mixed Capacitated General Routing Problem under Uncertainty

Beraldi P;Bruni ME;Laganà D;Musmanno R
2015

Abstract

We study the General Routing Problem defined on a mixed graph and with stochastic demands. The problem under investigation is aimed atfinding the minimum cost set of routes to satisfy a set of clients whose demand is not deterministically known. Since each vehicle has a limited capacity, thedemand uncertainty occurring at some clients affects the satisfaction of the capacity constraints, that, hence, become stochastic. The contribution of this paper is twofold: firstly we present a chance-constrained integer programmingformulation of the problem for which a deterministic equivalent is derived.The introduction of uncertainty into the problem poses severe computational challenges addressed by the design of a branch--and--cut algorithm, for the exact solution of limited size instances, and of a heuristic solution approach exploring promising parts of the search space.The effectiveness of the solution approaches is shown on a probabilistically constrained version of the benchmark instances proposed in the literature for the mixed capacitated general routing problem.
Routing problem; Mixed graph; Neighborhood search; Probabilistic constraints
File in questo prodotto:
File Dimensione Formato  
The Mixed Capacitated General Routing Problem under Uncertainty_submitted_version.pdf

accesso aperto

Descrizione: Versione editoriale disponibile al link https://www.sciencedirect.com/science/article/abs/pii/S037722171400589X (DOI: 10.1016/j.ejor.2014.07.023)
Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 183.01 kB
Formato Adobe PDF
183.01 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: http://hdl.handle.net/20.500.11770/138085
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 26
  • ???jsp.display-item.citation.isi??? 21
social impact