Investigating the use of metaheuristics for solving single vehicle routing problems with time‐varying traversal costs

Investigating the use of metaheuristics for solving single vehicle routing problems with time‐varying traversal costs

0.00 Avg rating0 Votes
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: , ,
Keywords: combinatorial optimization, optimization: simulated annealing, heuristics: tabu search, programming: travelling salesman
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.

Reviews

Required fields are marked *. Your email address will not be published.