The Mixed Capacitated General Routing Problem under Uncertainty

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.