Robust vehicle routing solutions to manage time windows in the case of uncertain travel times

Abstract

The vehicle routing is a difficult combinatorial optimization problem which has attracted many researchers to apply meta-heuristics to find approximate solutions. In the case of time windows within which goods have to picked-up or delivered it is even more difficult to find good solutions. Of course, congestion makes it hard for planners to find good routes for delivery or pick-up because travel times between customers, or between a depot and a customer are uncertain. In this chapter, the problem is handled by assigning a range of possible travel times between customers to represent the uncertainty. From these ranges, scenarios are built to find near-optimal solutions. But our main goal is that a solution is found which is robust, which means it performs ‘well’ in even bad scenarios. Next to our theoretical development, our experiments show that these robust results can be obtained in a computationally reasonable time, which means that the concept and its computer implementation can be used by practitioners, who are confronted with this type of uncertainty. Most of the applications appear in commercial routing, but also applications in a social environment exist. An earthquake or a flood might lead to road disruptions. Higher traffic delays appear either due to a lower than expected speed on flooded roads, or due to time spent on finding alternative routes in case no throughway is available. This type of routing includes evacuation of wounded or diseased victims or delivery of food and medical supplies. This social type of routing is hardly studied in literature but makes up the topic of this chapter. The 2011 flooding in Thailand has been the major inspiration for this work.