Transformations of node-balanced routing problems

Transformations of node-balanced routing problems

0.00 Avg rating0 Votes
Article ID: iaor201526572
Volume: 62
Issue: 5
Start Page Number: 370
End Page Number: 387
Publication Date: Aug 2015
Journal: Naval Research Logistics (NRL)
Authors: ,
Keywords: programming: travelling salesman, programming: assignment
Abstract:

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.

Reviews

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