Scientific Program > Talks by Speaker > Florio Alexandre

The Vehicle Routing Problem with Stochastic Demands (VRPSD) has been traditionally studied under the assumption of the detour-to-depot policy. Nevertheless, it is generally a consensus that such restocking policy is rather suboptimal and tends to be adopted very seldom in practical scenarios.

In this talk we present a new model for the single-vehicle VRPSD under the a priori optimization approach. Our model computes the optimal tour assuming the optimal restocking policy is to be used. We conduct tests on instances of up to 50 nodes, and verify the large suboptimality of the detour-to-depot policy, especially in high vehicle load scenarios.

When the instance size increases our model quickly becomes intractable. For this reason, we introduce an approximate branch-and-bound based solution method suitable for solving heuristically larger instances of the VRPSD. The heuristic finds the optimal solution of all instances solved to optimality. It also significantly improves the upper-bound obtained by combining the optimal Travelling Salesman Problem (TSP) solution with the optimal restocking policy, which in turn performs better than the optimal detour-to-depot solution.

We conclude by pointing out a few remarks of practical relevance. In particular, we discuss in which situations it generally pays off pursuing the optimal solution, and when the solution obtained by solving the corresponding TSP problem is good enough.