A Hybrid Scatter Search Algorithm to Solve the Capacitated Arc Routing Problem with Refill Points

详细信息    查看全文

• 关键词：Scatter search ; Arc routing ; Hybrid algorithms ; Refill points ; Simulated annealing ; Iterated local search
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9772
• 期：1
• 页码：3-15
• 全文大小：416 KB
• 参考文献：1.Assad, A.A., Golden, B.L.: Arc routing methods and applications. In: Handbooks in Operations Research and Management Science, pp. 375–483. Elsevier (1995)
  2.Golden, B.L., Wong, R.T.: Capacitated arc routing problems. Networks 11, 305–315 (1981)MathSciNet CrossRef MATH
  3.Wøhlk, S.: A decade of capacitated arc routing. In: Golden, B., Raghavan, S., Wasil, E. (eds.) The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research/Computer Science Interfaces Series, vol. 43, pp. 29–48. Springer, Heidelberg (2008)CrossRef
  4.Belenguer, J.-M., Benavent, E., Lacomme, P., Prins, C.: Lower and upper bounds for the mixed capacitated arc routing problem. Comput. Oper. Res. 33, 3363–3383 (2006)MathSciNet CrossRef MATH
  5.Lacomme, P., Prins, C., Sevaux, M.: Multiobjective capacitated arc routing problem. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) EMO 2003. LNCS, vol. 2632, pp. 550–564. Springer, Heidelberg (2003)CrossRef
  6.Lacomme, P., Prins, C., Sevaux, M.: A genetic algorithm for a bi-objective capacitated arc routing problem. Comput. Oper. Res. 33, 3473–3493 (2006)CrossRef MATH
  7.Reghioui, M., Prins, C., Labadi, N.: GRASP with path relinking for the capacitated arc routing problem with time windows. In: Giacobini, M. (ed.) EvoWorkshops 2007. LNCS, vol. 4448, pp. 722–731. Springer, Heidelberg (2007)
  8.Chu, F., Labadi, N., Prins, C.: A scatter search for the periodic capacitated arc routing problem. Eur. J. Oper. Res. 169, 586–605 (2006)MathSciNet CrossRef MATH
  9.Fleury, G., Lacomme, P., Prins, C.: Stochastic Capacitated Arc Routing Problem (2005)
  10.Pia, A., Filippi, C.: A variable neighborhood descent algorithm for a real waste collection problem with mobile depots. Int. Trans. Oper. Res. 13, 125–141 (2006)CrossRef MATH
  11.Amaya, A., Langevin, A., Trépanier, M.: The capacitated arc routing problem with refill points. Oper. Res. Lett. 35, 45–53 (2007)MathSciNet CrossRef MATH
  12.Amaya, C.-A., Langevin, A., Trépanier, M.: A heuristic method for the capacitated arc routing problem with refill points and multiple loads. J. Oper. Res. Soc. 61, 1095–1103 (2010)CrossRef MATH
  13.Shan, H.U., Dan, L.I.N.: Algorithms for solving CARP-RP-ML problem. Comput. Eng. 38, 168–170 (2012)
  14.Hirabayashi, R., Saruwatari, Y., Nishida, N.: Tour construction algorithm for the capacitated arc routing problem. Asia Pac. J. Oper. Res. 9, 155–175 (1992)MathSciNet MATH
  15.Belenguer, J.M., Benavent, E.: A cutting plane algorithm for the capacitated arc routing problem. Comput. Oper. Res. 30, 705–728 (2003)MathSciNet CrossRef MATH
  16.Baldacci, R., Maniezzo, V.: Exact methods based on node-routing formulations for undirected arc-routing problems. Networks 47, 52–60 (2006)MathSciNet CrossRef MATH
  17.Longo, H., de Aragão, P.M., Uchoa, E.: Solving capacitated arc routing problems using a transformation to the CVRP. Comput. Oper. Res. 33, 1823–1837 (2006)CrossRef MATH
  18.Tagmouti, M., Gendreau, M., Potvin, J.-Y.: Arc routing problems with time-dependent service costs. Eur. J. Oper. Res. 181, 30–39 (2007)MathSciNet CrossRef MATH
  19.Eglese, R.W.: Routeing winter gritting vehicles. Discret. Appl. Math. 48, 231–244 (1994)CrossRef MATH
  20.Hertz, A., Mittaz, M.: A variable neighborhood descent algorithm for the undirected capacitated arc routing problem. Transp. Sci. 35, 425–434 (2001)CrossRef MATH
  21.Hertz, A., Laporte, G., Mittaz, M.: A tabu search heuristic for the capacitated arc routing problem. Oper. Res. 48, 129–135 (2000)MathSciNet CrossRef MATH
  22.Fung, R.Y.K., Liu, R., Jiang, Z.: A memetic algorithm for the open capacitated arc routing problem. Transp. Res. Part E: Logist. Transp. Rev. 50, 53–67 (2013)CrossRef
  23.Liu, M., Singh, H.K., Ray, T.: Application specific instance generator and a memetic algorithm for capacitated arc routing problems. Transp. Res. Part C: Emerg. Technol. 43, 249–266 (2014)CrossRef
  24.Wang, Z., Jin, H., Tian, M.: Rank-based memetic algorithm for capacitated arc routing problems. Appl. Soft Comput. 37, 572–584 (2015)CrossRef
  25.Beullens, P., Muyldermans, L., Cattrysse, D., Van Oudheusden, D.: A guided local search heuristic for the capacitated arc routing problem. Eur. J. Oper. Res. 147, 629–643 (2003)MathSciNet CrossRef MATH
  26.Glover, F.: Heuristics for integer programming using surrogate constraints. Decis. Sci. 8, 156–166 (1977)CrossRef
  27.Rego, C., Leão, P.: A scatter search tutorial for graph-based permutation problems. In: Sharda, R., Voß, S., Rego, C., Alidaee, B. (eds.) Metaheuristic Optimization via Memory and Evolution. Operations Research/Computer Science Interfaces Series, vol. 30, pp. 1–24. Kluwer Academic Publishers, Boston (2005)CrossRef
  28.Russell, R.A., Chiang, W.-C.: Scatter search for the vehicle routing problem with time windows. Eur. J. Oper. Res. 169, 606–622 (2006)MathSciNet CrossRef MATH
  29.Laguna, M., Martí, R., Martí, R.C.: Scatter Search: Methodology and Implementations in C. Operations Research/Computer Science Interfaces Series, vol. 1. Springer Science & Business Media, New York (2003)CrossRef MATH
  30.Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Upper Saddle River (1993)MATH
  31.Benavent, E., Campos, V., Corberan, A., Mota, E.: The capacitated arc routing problem: lower bounds. Networks 22, 669–690 (1992)MathSciNet CrossRef MATH
  
• 作者单位：Eduyn Ramiro López-Santana (15)
  Germán Andrés Méndez-Giraldo (15)
  Carlos Alberto Franco-Franco (16)
  
  15. Universidad Distrital Francisco José de Caldas, Bogotá, Colombia
  16. Universidad de la Sabana, Chía, Cundinamarca, Colombia
  
• 丛书名：Intelligent Computing Theories and Application
• ISBN：978-3-319-42294-7
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9772

文摘

This paper presents a hybrid scatter search algorithm to solve the capacitated arc routing problem with refill points (CARP-RP). The vehicle servicing arcs must be refilled on the spot by using a second vehicle. This problem is addressed in real-world applications in many services systems. The problem consists on simultaneously determining the vehicles routes that minimize the total cost. In the literature is proposed an integer linear programming model to solve the problem. We propose a hybrid algorithm based on Scatter Search, Simulated Annealing and Iterated Local Search. Our method is tested with instances from the literature. We found best results in the objective function for the majority instances.