The Profitable Arc Tour Problem: Solution with a Branch-and-Price Algorithm

Dominique Feillet (), Pierre Dejax () and Michel Gendreau ()
Additional contact information
Dominique Feillet: Laboratoire d’Informatiquè d’Avignon, 339 Chemin des Meinajariés, Agroparc BP 1228, 84911 Avignon, France
Pierre Dejax: École des Mines de Nantes and Communications and Cybernetic Research Institute of Nantes, 4, rue Alfred Kastler, 44307 Nantes, France
Michel Gendreau: CRT Université de Montréal, C.P. 6128, succursale Centre-ville, Montréal, Canada H3C 3J7

Transportation Science, 2005, vol. 39, issue 4, 539-552

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 traveling 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 relationships of this problem with constrained flow optimization are taken into account in an initial phase of the algorithm.

Keywords: arc-routing problem; routing problem with profits; column generation; branch and price; bounded cycle cover (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (24)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1040.0106 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:39:y:2005:i:4:p:539-552

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().