We consider a novel variant of the Prize-Collecting Vehicle Routing Problem servicing customers with either deterministic or stochastic demand inspired by a real-life case. The objective is to maximize the profit obtained by servicing a selection of these customers. Each type of request is associated with a minimum acceptable service level and a profit level or prize. Service level requirements describe the minimum percentage of customer requests to be serviced. Furthermore, we take into account the setup costs of using additional resources for serving customers. We present a stochastic programming formulation of the problem in which the stochastic constraints are reformulated as probabilistic constraints. A deterministic equivalent mixed-integer programming model is derived. We propose a tailored algorithm that exploits the problem structure, and we present some preliminary computational results in order to assess the effectiveness of the proposed algorithm.
| Subject : | : | Abstracts |
| Topics | : | Exact methods |
| Topics | : | Heuristics |
| Topics | : | Stochastic vehicle routing |
| PDF version | : |  PDF version |
