Article ID: | iaor20128156 |
Volume: | 64 |
Issue: | 1 |
Start Page Number: | 34 |
End Page Number: | 47 |
Publication Date: | Jan 2013 |
Journal: | Journal of the Operational Research Society |
Authors: | Eglese R, Mumford C, Harwood K |
Keywords: | combinatorial optimization, optimization: simulated annealing, heuristics: tabu search, programming: travelling salesman |
Metaheuristic algorithms, such as simulated annealing and tabu search, are popular solution techniques for vehicle routing problems (VRPs). These approaches rely on iterative improvements to a starting solution, involving slight alterations to the routes (ie, neighbourhood moves), moving a node to a different part of a solution, swapping nodes or inverting sections of a tour, for example. When working with standard VRPs, where the costs of the arcs do not vary with advancing time, evaluating changes to the total cost following a neighbourhood move is a simple process: simply subtract the cost of the links removed from the solution and add the costs for the new links. When a time‐varying aspect (eg, congestion) is included in the costs, these calculations become estimations rather than exact values. This paper focuses on a single vehicle routing problem, similar to the Travelling Salesman Problem, and investigates the potential for using estimation methods on simple models with time‐variant costs, mimicking the effects of road congestion.