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-01-01
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.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.