Two phased hybrid local search for the periodic capacitated arc routing problem.

*(English)*Zbl 1380.90037Summary: The periodic capacitated arc routing problem (PCARP) is a challenging general model with important applications. The PCARP has two hierarchical optimization objectives: a primary objective of minimizing the number of vehicles \((F_v)\) and a secondary objective of minimizing the total cost \((F_c)\). In this paper, we propose an effective two phased hybrid local search (HLS) algorithm for the PCARP. The first phase makes a particular effort to optimize the primary objective while the second phase seeks to further optimize both objectives by using the resulting number of vehicles of the first phase as an upper bound to prune the search space. For both phases, combined local search heuristics are devised to ensure an effective exploration of the search space. Experimental results on 63 benchmark instances demonstrate that HLS performs remarkably well both in terms of computational efficiency and solution quality. In particular, HLS discovers 44 improved best known values (new upper bounds) for the total cost objective \(F_c\) while attaining all the known optimal values regarding the objective of the number of vehicles \(F_v\). To our knowledge, this is the first PCARP algorithm reaching such a performance. Key components of HLS are analyzed to better understand their contributions to the overall performance.

##### MSC:

90B06 | Transportation, logistics and supply chain management |

90C27 | Combinatorial optimization |

90C35 | Programming involving graphs or networks |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Keywords:

heuristics; capacitated arc routing; bi-level optimization; constrained combinatorial search
PDF
BibTeX
XML
Cite

\textit{Y. Chen} and \textit{J.-K. Hao}, Eur. J. Oper. Res. 264, No. 1, 55--65 (2018; Zbl 1380.90037)

Full Text:
DOI

##### References:

[1] | Beullens, P.; Muyldermans, L.; Cattrysse, D.; Oudheusden, D. V., A guided local search heuristic for the capacitated arc routing problem, European Journal of Operational Research, 147, 3, 629-643, (2003) · Zbl 1026.90015 |

[2] | Birattari, M.; Yuan, Z.; Balaprakash, P.; Stützle, T., F-race and iterated f-race: an overview, Proceedings of the experimental methods for the analysis of optimization algorithms, 311-336, (2010), Springer · Zbl 1204.68280 |

[3] | Brandão, J.; Eglese, R., A deterministic tabu search algorithm for the capacitated arc routing problem, Computers and Operations Research, 35, 4, 1112-1126, (2008) · Zbl 1179.90031 |

[4] | Chen, Y.; Hao, J.-K.; Glover, F., A hybrid metaheuristic approach for the capacitated arc routing problem, European Journal of Operational Research, 253, 1, 25-39, (2016) · Zbl 1346.90087 |

[5] | Chu, F.; Labadi, N.; Prins, C., The periodic capacitated arc routing problem linear programming model, metaheuristic and lower bounds, Journal of Systems Science and Systems Engineering, 13, 4, 423-435, (2004) |

[6] | Chu, F.; Labadi, N.; Prins, C., A scatter search for the periodic capacitated arc routing problem, European Journal of Operational Research, 169, 2, 586-605, (2006) · Zbl 1079.90028 |

[7] | Cordeau, J.-F.; Gendreau, M.; Laporte, G., A tabu search heuristic for periodic and multi-depot vehicle routing problems, Networks, 30, 2, 105-119, (1997) · Zbl 0885.90037 |

[8] | Díaz-Madroñero, M.; Peidro, D.; Mula, J., A review of tactical optimization models for integrated production and transport routing planning decisions, Computers and Industrial Engineering, 88, 518-535, (2015) |

[9] | Drummond, L. M.; Ochi, L. S.; Vianna, D. S., An asynchronous parallel metaheuristic for the period vehicle routing problem, Future generation computer systems, 17, 4, 379-386, (2001) · Zbl 1016.68176 |

[10] | Dueck, G.; Scheuer, T., Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing, Journal of computational physics, 90, 1, 161-175, (1990) · Zbl 0707.65039 |

[11] | Francis, P.; Smilowitz, K., Modeling techniques for periodic vehicle routing problems, Transportation Research Part B: Methodological, 40, 10, 872-884, (2006) |

[12] | Gaudioso, M.; Paletta, G., A heuristic for the periodic vehicle routing problem, Transportation Science, 26, 2, 86-92, (1992) · Zbl 0759.90025 |

[13] | Glover, F.; Laguna, M., Tabu search?, (2013), Springer |

[14] | Golden, B. L.; DeArmon, J. S.; Baker, E. K., Computational experiments with algorithms for a class of routing problems, Computers and Operations Research, 10, 1, 47-59, (1983) |

[15] | Golden, B. L.; Wong, R. T., Capacitated arc routing problems, Networks, 11, 3, 305-315, (1981) · Zbl 0459.90083 |

[16] | Hansen, P.; Mladenović, N.; Brimberg, J.; Pérez, J. A.M., Variable neighborhood search, (2010), Springer |

[17] | Hertz, A.; Laporte, G.; Mittaz, M., A tabu search heuristic for the capacitated arc routing problem, Operations research, 48, 1, 129-135, (2000) · Zbl 1106.90384 |

[18] | Hertz, A.; Mittaz, M., A variable neighborhood descent algorithm for the undirected capacitated arc routing problem, Transportation science, 35, 4, 425-434, (2001) · Zbl 1069.90517 |

[19] | Kansou, A.; Yassine, A., Ant colony system for the periodic capacitated arc routing problem, Proceedings of the year 2009 international network optimization conference, 1-7, (2009) |

[20] | Lacomme, P.; Prins, C.; Ramdane-Chérif, W., Evolutionary algorithms for multiperiod arc routing problems, Proceedings of the ninth international conference on information processing and management of uncertainty in knowledge-based systems IPMU year 2002, 845-852, (2002) |

[21] | Lacomme, P.; Prins, C.; Ramdane-Chérif, W., Competitive memetic algorithms for arc routing problems, Annals of Operations Research, 131, 159-185, (2004) · Zbl 1066.90010 |

[22] | Lacomme, P.; Prins, C.; Ramdane-Chérif, W., Evolutionary algorithms for periodic arc routing problems, European Journal of Operational Research, 165, 2, 535-553, (2005) · Zbl 1066.90006 |

[23] | Longo, H.; de Aragão, M. P.; Uchoa, E., Solving capacitated arc routing problems using a transformation to the CVRP, Computers and Operations Research, 33, 6, 1823-1837, (2006) · Zbl 1087.90054 |

[24] | López-Ibánez, M., Dubois-Lacoste, J., Stützle, T., & Birattari, M. (2011). The irace package, iterated race for automatic algorithm configuration. Citeseer, Technical Report. |

[25] | Martinelli, R.; Poggi, M.; Subramanian, A., Improved bounds for large scale capacitated arc routing problem, Computers and Operations Research, 40, 8, 2145-2160, (2013) · Zbl 1348.90476 |

[26] | Mei, Y.; Li, X.; Yao, X., Cooperative coevolution with route distance grouping for large-scale capacitated arc routing problems, IEEE Transactions on Evolutionary Computation, 18, 3, 435-449, (2014) |

[27] | Mei, Y.; Tang, K.; Yao, X., A global repair operator for capacitated arc routing problem, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 39, 3, 723-734, (2009) |

[28] | Mei, Y.; Tang, K.; Yao, X., A memetic algorithm for periodic capacitated arc routing problem, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 41, 6, 1654-1667, (2011) |

[29] | Polacek, M.; Doerner, K. F.; Hartl, R. F.; Maniezzo, V., A variable neighborhood search for the capacitated arc routing problem with intermediate facilities, Journal of Heuristics, 14, 5, 405-423, (2008) · Zbl 1211.90314 |

[30] | Santos, L.; Coutinho-Rodrigues, J.; Current, J. R., An improved ant colony optimization based algorithm for the capacitated arc routing problem, Transportation Research Part B: Methodological, 44, 2, 246-266, (2010) |

[31] | Tang, K.; Mei, Y.; Yao, X., Memetic algorithm with extended neighborhood search for capacitated arc routing problems, IEEE Transactions on Evolutionary Computation, 13, 5, 1151-1166, (2009) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.