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. © 2013 Operational Research Society Ltd. All rights reserved.
https://doi.org/10.1057/jors.2012.17Cite as:
@article{Harwood_2013,
doi = {10.1057/jors.2012.17},
url = {https://doi.org/10.1057%2Fjors.2012.17},
year = 2013,
month = {jan},
publisher = {Informa {UK} Limited},
volume = {64},
number = {1},
pages = {34--47},
author = {K Harwood and C Mumford and R Eglese},
title = {Investigating the use of metaheuristics for solving single vehicle routing problems with time-varying traversal costs},
journal = {Journal of the Operational Research Society}
}