Sensitivity analysis of vehicle routing solutions to uncertainty in travel times

Abstract

Various algorithms and heuristics exist for solving the vehicle routing problem. When the problem is enriched with time windows (either from the depot or imposed by the customers) the methods of finding optimal solutions become harder and most analysts turn to heuristics. The methods mostly assume deterministic travel times between customers, which might be an unrealistic assumption. Once a heuristics solution for the vehicle routing problem is found, the solution might be evaluated against various scenarios including uncertainty in travel times. The paper first models a single route as a project network and links the notions of slack and criticality with notions in the vehicle routing solution. Further evaluation of the solution is investigated if the uncertainty in travel time can be expressed as an interval between finite lower and upper bounds.