In:
Transportation Science, Institute for Operations Research and the Management Sciences (INFORMS), Vol. 53, No. 5 ( 2019-09), p. 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.
Type of Medium:
Online Resource
ISSN:
0041-1655
,
1526-5447
DOI:
10.1287/trsc.2018.0881
Language:
English
Publisher:
Institute for Operations Research and the Management Sciences (INFORMS)
Publication Date:
2019
detail.hit.zdb_id:
2015901-8
detail.hit.zdb_id:
160958-0
SSG:
3,2
