Premium
Analyses of advanced iterated tour partitioning heuristics for generalized vehicle routing problems
Author(s) -
Seth Anupam,
Klabjan Diego,
Ferreira Placid M.
Publication year - 2013
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21478
Subject(s) - heuristics , computer science , vehicle routing problem , routing (electronic design automation) , iterated local search , variety (cybernetics) , set (abstract data type) , iterated function , mathematical optimization , distributed computing , metaheuristic , algorithm , mathematics , computer network , artificial intelligence , mathematical analysis , programming language , operating system
Theoretical analyses of a set of iterated‐tour partitioning vehicle routing algorithms applicable to a wide variety of commonly used vehicle routing problem variants are presented. We analyze the worst‐case performance of the algorithms and establish tightness of the derived bounds. Among other variants, we capture the cases of pick‐up and delivery and multiple depots. We also introduce brand new concepts such as mobile depots, partitioning of customer nodes into groups, and potential opportunistic under‐utilization of vehicle capacity by only partially loading the vehicle, among others, which arise from a printed circuit board application. The problems studied are of critical importance in many practical applications. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013