Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem

[EN] The generalized directed rural postman problem is an arc routing problem with many interesting real-life applications, such as routing for meter reading. In this application, a vehicle with a receiver travels through a series of neighborhoods. If the vehicle gets closer than a certain distance to a meter, the receiver is able to record the gas, water, or electricity consumption. Therefore, the vehicle does not need to traverse every street, but only a few, to get close enough to each meter. We study an extension of this problem in which a fleet of vehicles is available. Given the characteristics of the mentioned application, the vehicles have no capacities but there is a maximum distance (or time) constraint all of them have to satisfy.We introduce four formulations for this problem, propose some families of valid inequalities, and present four branch-and-cut algorithms for its solution. The formulations and the algorithms are compared on a large set of instances.The authors thank the Spanish Ministerio de Economia y Competitividad (project MTM2012-36163-C06-02) and the Generalitat Valenciana (project GVPROMETEO2013-049) for their support.Ávila, T.; Corberán, A.; Plana, I.; Sanchís Llopis, JM. (2017). Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem. EURO Journal on Computational Optimization. 5(3):339-365. https://doi.org/10.1007/s13675-015-0053-833936553Ávila T, Corberán Á, Plana I, Sanchis JM (2015) A new branch-and-cut algorithm for the generalized directed rural postman problem. Transp Sci. doi: 10.1287/trsc.2015.0588Benavent E, Carrotta A, Corberán Á, Sanchis JM, Vigo D (2007) Lower bounds and heuristics for the windy rural postman problem. Eur J Oper Res 176:855–869Benavent E, Corberán Á, Plana I, Sanchis JM (2009) Min–max k-vehicles windy rural postman problem. Networks 54:216–226Corberán Á, Laporte G (eds) (2014) Arc routing: problems, methods, and applications MOS-SIAM series on optimization, PhiladelphiaCorberán Á, Plana I, Sanchis JM (2015) Arc routing problems: data instances. http://www.uv.es/corberan/instancias.htmDrexl M (2007) On some generalized routing problems. PhD thesis, Rheinisch-Westfälische Technische Hochschule, Aachen UniversityDrexl M (2014) On the generalized directed rural postman problem. J Oper Res Soc 65:1143–1154Gendreau M, Laporte G, Semet F (1997) The covering tour problem. Oper Res 45:568–576Gomory RE, Hu TC (1961) Multi-terminal network flows. J Soc Ind Appl Math 9:551–570Hà M-H, Bostel N, Langevin A, Rousseau L-M (2014) Solving the close enough arc routing problem. Networks 63:107–118Shuttleworth R, Golden BL, Smith S, Wasil EA (2008) Advances in meter reading: heuristic solution of the close enough traveling salesman problem over a street network. In: Golden BL, Raghavan S, Wasil EA (eds) The vehicle routing problem: latest advances and new challenges. Springer, Berlin, pp 487–50