In a vehicle routing problem (VRP) with time windows, the start of service needs to take place within the customer time window. Due to uncertainty on travel times, vehicles might arrive late at a customer's site. A VRP is mostly solved to minimize a total cost criterion (travel time, travel distance, fixed and variable vehicle costs). But the dispatcher might also take into consideration the risk of non-conformance with the service agreement to start service within the time window. Therefore, a measure of risk, called “vulnerability of a solution,” is developed to serve as a second criterion. This chapter develops such a measure based on a distance metric and investigates its strengths and weaknesses.
TopIntroduction
While the Vehicle Routing Problem (VRP) has been under study for several decades, its solution methods in recent times have been able to deal with real-time complexities (e.g. Hartl et al. (2006), Drexl (2012)). The problems have become richer by including time windows, time-dependent travel times, multiple vehicle types, vehicle loading constraints, etc. The scientific literature publishes from time to time reviews on the evolution of either solution methods for the variants of the VRP or on a classification of various types of VRPs. The most recent review can be found in Braekers et al. (2016), in which the interested reader can find references to most of the earlier reviews and classifications.
Like many combinatorial problems, also the vehicle routing problem can be formulated as a mixed-integer linear program including a huge amount of binary variables which make that a fast solution of the problem is hardly possible. Therefore, in recent times, VRPs are solved by advanced (meta)heuristic methods. Moreover, the optimal solution depends on input data which are assumed to be deterministic but mostly are only an approximation of the reality. A small perturbation on the input could result in impractical or suboptimal solutions. To cope with uncertainty in the input data of a VRP, one wants to find solutions which are robust to perturbations caused by the uncertainty. In robust optimisation, there is a trade-off between robustness and quality of the solution. Therefore, the stochastic VRP has been defined and solution methods have been proposed. Stochastic Vehicle Routing Problems include different models: VRP with Stochastic Demands, VRP with Stochastic Customers and VRP with Stochastic Travel Times.
Demand uncertainty is a serious problem in the VRP as it may lead to unmet demands. Due to the limited vehicle capacity, the main issue is that a vehicle might have to pay an extra visit to the depot for restocking, which requires algorithms for re-optimisation (Haughton, 1998). Exact solutions for the VRP with stochastic demand and customers have been proposed by Gendreau et al. (1995) and Sungur et al. (2008). Metaheuristics like tabu search have been proposed by Gendreau et al. (1996) and particle swarm optimization by Moghaddam et al. (2012).
Stochastic travel times have been studied in Laporte and Louveaux (1992). Van Woensel et al. (2008) studied the VRP with travel times resulting from a stochastic process due to traffic congestion. Also, combinations of various sources of uncertainty have been studied, for example in Erera (2010) and in Sörensen and Sevaux (2009).
Any VRP problem becomes more complex in case it involves time windows. The constraints of the problem are to service all customers within the earliest and latest (start of service) time of the customer without exceeding the route time of the vehicle. The route time of the vehicle is defined as the sum of the waiting times, the service times and the travel times. A vehicle that reaches a customer before the earliest time, after the latest time and after the route time incurs waiting time, tardiness time and overtime, respectively. In this chapter the VRP with stochastic travel times is considered in combination with time windows (VRPTW).