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: | Dejax Pierre, Gendreau Michel, Feillet Dominique |
Keywords: | networks: flow |
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.