Title: Hybrid metaheuristics for the periodic open arc routing problem

Authors: Ali Kansou; Bilal Kanso

Addresses: Department of Computer Science, Lebanese University, Beirut, Lebanon ' Department of Computer Science, Lebanese University, Beirut, Lebanon

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.

Keywords: metaheuristics; open arc routing problem; multi period; genetic algorithm; ant colony algorithm.

DOI: 10.1504/IJMHEUR.2022.127800

International Journal of Metaheuristics, 2022 Vol.8 No.1, pp.27 - 50

Received: 03 Jul 2019
Accepted: 27 Jul 2020
Published online: 19 Dec 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article