Abstract
The team orienteering arc routing problem (TOARP) is a relatively new vehicle routing problem. In this problem, a fleet of vehicles are available to serve two sets of customers, each of which is associated with an arc of a directed graph. The customers of the first set are required to be served whereas the ones of the second set are potential and may be not served. Each potential customer is associated with a profit, and the profit can be gained at most once when it is served. The TOARP aims to maximize the total profit gained by serving the customers while each vehicle must start from and end at a depot within a permitted maximum traveling time. This paper shows that the TOARP can be transformed into a team orienteering problem defined on a directed graph. To solve the TOARP, an iterated local search based algorithm is presented. The effectiveness of the proposed algorithm is studied on the benchmark instances.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Archetti, C., Corberán, Á., Plana, I., Sanchis, J.M., Speranza, M.G.: A matheuristic for the team orienteering arc routing problem. Eur. J. Oper. Res. 245(2), 392–401 (2015)
Archetti, C., Speranza, M.G.: Arc routing problems with profits. In: Arc Routing: Problems, Methods, and Applications. MOS-SIAM Series on Optimization, pp. 257–284 (2013)
Archetti, C., Speranza, M.G., Corberán, Á., Sanchis, J.M., Plana, I.: The team orienteering arc routing problem. Transp. Sci. 48(3), 442–457 (2013)
Bentley, J.J.: Fast algorithms for geometric traveling salesman problems. ORSA J. Comput. 4(4), 387–411 (1992)
Goldberg, A.V., Radzik, T.: A heuristic improvement of the Bellman-Ford algorithm. Appl. Math. Lett. 6(3), 3–6 (1993)
Hertz, A., Laporte, G., Hugo, P.N.: Improvement procedures for the undirected rural postman problem. INFORMS J. Comput. 11(1), 53–62 (1999)
Laporte, G.: Fifty years of vehicle routing. Transp. Sci. 43(4), 408–416 (2009)
Longo, H., De Aragaao, M.P., Uchoa, E.: Solving capacitated arc routing problems using a transformation to the CVRP. Comput. Oper. Res. 33(6), 1823–1837 (2006)
Lourenço, H.R., Martin, O.C., Stützle, T.: Iterated local search: framework and applications. In: Gendreau, M., Potvin, J.-Y. (eds.) Handbook of Metaheuristics, pp. 363–397. Springer, New York (2010)
Ropke, S., Pisinger, D.: An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp. Sci. 40(4), 455–472 (2006)
Toth, P., Vigo, D.: Vehicle Routing: Problems, Methods, and Applications, vol. 18. SIAM, Philadelphia (2014)
Acknowledgements
The authors would like to thank the anonymous reviewers for their insightful comments. This work was supported by National Natural Science Foundation of China (No. 61573277, 71471158), the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. PolyU 15201414), the Fundamental Research Funds for the Central Universities, the Open Research Fund of the State Key Laboratory of Astronautic Dynamics under Grant 2015ADL-DW403, and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry, Natural Science Basic Research Plan in Shaanxi Province of China (No. 2015JM6316). The authors also would like to thank The Hong Kong Polytechnic University Research Committee for financial and technical support.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Ke, L., Yang, W. (2017). Reformulation and Metaheuristic for the Team Orienteering Arc Routing Problem. In: Tan, Y., Takagi, H., Shi, Y., Niu, B. (eds) Advances in Swarm Intelligence. ICSI 2017. Lecture Notes in Computer Science(), vol 10386. Springer, Cham. https://doi.org/10.1007/978-3-319-61833-3_52
Download citation
DOI: https://doi.org/10.1007/978-3-319-61833-3_52
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-61832-6
Online ISBN: 978-3-319-61833-3
eBook Packages: Computer ScienceComputer Science (R0)