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. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 240:2(2015), pp. 382-392.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
Titolo: | The Mixed Capacitated General Routing Problem under Uncertainty |
Autori: | |
Data di pubblicazione: | 2015 |
Rivista: | |
Citazione: | The Mixed Capacitated General Routing Problem under Uncertainty / Beraldi, P; Bruni, Me; Laganà, D; Musmanno, R. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 240:2(2015), pp. 382-392. |
Handle: | http://hdl.handle.net/20.500.11770/138085 |
Appare nelle tipologie: | 1.1 Articolo in rivista |