Exact Solution of Several Families of Location-Arc Routing Problems

Elena Fernández (), Gilbert Laporte () and Jessica Rodríguez-Pereira ()
Additional contact information
Elena Fernández: Department of Statistics and Operations Research, Polytechnic University of Catalonia, 08034 Barcelona, Spain; Barcelona Graduate School of Mathematics, 08193 Bellaterra, Spain;
Gilbert Laporte: Department of Decision Sciences, HEC Montréal, Montreal, Quebec H3T 2A7, Canada
Jessica Rodríguez-Pereira: Department of Statistics and Operations Research, Polytechnic University of Catalonia, 08034 Barcelona, Spain;

Transportation Science, 2019, vol. 53, issue 5, 1313-1333

Abstract: We model and solve several families of location-arc routing problems on an undirected graph. These problems extend the multidepot rural postman problem to the case where the depots are not fixed. The aim is to select the facility locations and to construct a set of routes traversing each required edge of the graph, where each route starts and ends at the same facility. The models differ from each other in their objective functions and on whether they include a capacity constraint. Alternative formulations are presented that use only binary variables, and are valid even when the input graph is not complete. This applies, in particular, to a compact two-index formulation for problems minimizing the overall routing costs, with or without facility setup costs. This formulation incorporates a new set of constraints that force the routes to be consistent and return to their original depots. A polyhedral study is presented for some of the formulations, which indicates that the main families of constraints are facet defining. All formulations are solved by branch and cut, and instances with up to 200 vertices are solved to optimality. Despite the difficulty of the problems, the numerical results demonstrate the good performance of the algorithm.

Keywords: arc routing; location; polyhedral analysis; facets; branch and cut (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/trsc.2018.0881 (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:53:y:2019:i:5:p:1313-1333

Access Statistics for this article

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