Premium
Transformations of node‐balanced routing problems
Author(s) -
MartinezSykora Antonio,
Bektaş Tolga
Publication year - 2015
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.21634
Subject(s) - travelling salesman problem , computer science , transformation (genetics) , routing (electronic design automation) , node (physics) , homogeneous , mathematical optimization , workload , class (philosophy) , vehicle routing problem , graph , construct (python library) , mathematics , theoretical computer science , computer network , combinatorics , artificial intelligence , biochemistry , chemistry , structural engineering , engineering , gene , operating system
This article describes a polynomial transformation for a class of unit‐demand vehicle routing problems, named node‐balanced routing problems (BRP), where the number of nodes on each route is restricted to be in an interval such that the workload across the routes is balanced. The transformation is general in that it can be applied to single or multiple depot, homogeneous or heterogeneous fleet BRPs, and any combination thereof. At the heart of the procedure lies transforming the BRP into a generalized traveling salesman problem (TSP), which can then be transformed into a TSP. The transformed graph exhibits special properties which can be exploited to significantly reduce the number of arcs, and used to construct a formulation for the resulting TSP that amounts to no more than that of a constrained assignment problem. Computational results on a number of instances are presented. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 370–387, 2015