Abstract
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.
Similar content being viewed by others
References
Dijkstra EW (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1 (1): 269–271.
Dreyfus SE (1969). An appraisal of some shortest-path algorithms. Operations Research 17 (3): 395–412.
Eglese R, Maden W and Slater A (2006). A road timetable™ to aid vehicle routing and scheduling. Computers & Operations Research 33 (12): 3508–3519.
Fisher ML, Greenfield AJ, Jaikuman R and Lester JT (1982). A computerized vehicle routing application. Interfaces 12 (4): 42–52.
Hill A, Mabert V and Montgomory D (1988). A decision support system for the courier vehicle scheduling problem. Omega International Journal of Management Science 16 (4): 333–345.
Horn MET (2000). Efficient modeling of travel in networks with time-varying link speeds. Networks 36 (2): 80–90.
Ichoua S, Gendreau M and Potvin JY (2003). Vehicle dispatching with time-dependent travel times. European Journal of Operations Research 144 (2): 379–396.
Kaufman DE and Smith RL (1993). Fastest paths in time-dependent networks for intelligent vehicle-highway systems application. Journal of Intelligent Transportation Systems 1 (1): 1–11.
Kok AL, Hans EW and Schutten JMJ (2009). Vehicle routing under time dependent travel times: The impact of congestion avoidance. Internal Report, University of Twente.
Malandraki C and Dial RB (1996). A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem. European Journal of Operations Research 90 (1): 45–55.
Sung K, Bell MGH, Seong M and Park S (2000). Shortest paths in a network with time-dependent flow speeds. European Journal of Operations Research 121 (1): 32–39.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Harwood, K., Mumford, C. & Eglese, R. Investigating the use of metaheuristics for solving single vehicle routing problems with time-varying traversal costs. J Oper Res Soc 64, 34–47 (2013). https://doi.org/10.1057/jors.2012.17
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2012.17