Hybrid metaheuristics for the periodic open arc routing problem. (12th December 2022)

• Record Type: Journal Article
• Authors: Kansou, Ali; Kanso, Bilal
• Is Part Of: International journal of metaheuristics. Volume 8:Number 1(2023)
• Page Start: 27
• Page End: 50
• Publication Date: 2022-12-12
• Subjects: metaheuristics -- open arc routing problem -- multi period -- genetic algorithm -- ant colony algorithm; Heuristic algorithms -- Periodicals; 006.3105
• Languages: English
• ISSNs: 1755-2176

Abstract

This work considers the periodic open arc routing problem (POCARP) that models the meter reader application. This application is very interesting when the routes are planned on horizon of several periods. We develop two approaches to solve the problem under study: the first one is based on hybrid genetic algorithm with a specific crossover and the second one on hybrid ant colony method combined with an insertion heuristic. The two proposed algorithms are hybridised with a local search procedure that exploits several moves (relocate, swap, 2-opt and change combination). The objective of the problem is to find a combination of service periods for each task as well as the feasible routes of each period by using a predefined number of available vehicles that minimise the total travelling distance over the multi-period horizon. We extended the optimal splitting procedure to generate and evaluate solutions. We compared our approaches with one of the most important insertion heuristics adapted to this problem. Computational experiments are conducted on a set of generated benchmark instances and indicate that the proposed metaheuristics dominate the good insertion heuristic.