The profitable arc tour problem: Solution with a branch-and-price algorithm

The profitable arc tour problem: Solution with a branch-and-price algorithm

0.00 Avg rating0 Votes
Article ID: iaor20063602
Country: United States
Volume: 39
Issue: 4
Start Page Number: 539
End Page Number: 552
Publication Date: Nov 2005
Journal: Transportation Science
Authors: , ,
Keywords: networks: flow
Abstract:

In this article, we introduce a new arc routing problem that we call the profitable arc tour problem. This problem is defined on a graph in which profits and travel costs are associated with the arcs. The objective is to find a set of cycles in the graph that maximizes the collection of profit minus travel costs, subject to constraints limiting the number of times that profit is available on arcs and the maximal length of cycles. The problem is related both to constrained flow problems and to vehicle-routing problems. We tackle it from this standpoint and propose a branch-and-price algorithm for its solution. In the column-generation phase, the issue of the collection decisions while travelling through the arcs is addressed. In the branching phase, the fact that viewing solutions in terms of flow variables regularly induces an integer flow matrix leads us to introduce a branching method called the flow-splitting method. Finally, the relatioinships of this problem with constrained flow optimization are taken into account in an initial phase of the algorithm.

Reviews

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