no. 2
Open Capacitated ARC routing problem by Hybridized Ant Colony Algorithm
RAIRO. Operations Research, Tome 55 (2021) no. 2, pp. 639-652

The Open Capacitated Arc Routing Problem OCARP is a well-known NP-hard real-world combinatorial optimization problem. It consists of determining optimal routes for vehicles in a given service area at a minimal cost distance. The main real application for OCARP is the Meter Reader Routing Problem (MRRP). In MRRP problem, each worker in the electric (or gas) company must visit and read the electric (or gas) meters to a set of customers by starting his route from the first customer on his visit list and finishing with the last one. The worker leaves where he wants once all the associated customers have been visited. In this paper, a metaheuristic called an Hybridized Ant Colony Algorithm (HACA) is developed and hybridized with a local search algorithm that involves the 2-opt, Swap, Relocate and Cross-exchange moves to solve OCARP problem. Computational results conducted on five different sets of OCARP-instances showed that our proposed algorithm HACA has reached good and competitive results on benchmark instances for the problem.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2021034
Classification : 90C32, 90C26, 90C59
Keywords: Open Capacitated Arc Routing Problem, metaheuristic, Ant Colony Algorithm, local search, Simulated Annealing 
@article{RO_2021__55_2_639_0,
     author = {Kanso, Bilal and Kansou, Ali and Yassine, Adnan},
     title = {Open {Capacitated} {ARC} routing problem by {Hybridized} {Ant} {Colony} {Algorithm}},
     journal = {RAIRO. Operations Research},
     pages = {639--652},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     number = {2},
     doi = {10.1051/ro/2021034},
     mrnumber = {4238787},
     zbl = {1472.90112},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2021034/}
}
TY  - JOUR
AU  - Kanso, Bilal
AU  - Kansou, Ali
AU  - Yassine, Adnan
TI  - Open Capacitated ARC routing problem by Hybridized Ant Colony Algorithm
JO  - RAIRO. Operations Research
PY  - 2021
SP  - 639
EP  - 652
VL  - 55
IS  - 2
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2021034/
DO  - 10.1051/ro/2021034
LA  - en
ID  - RO_2021__55_2_639_0
ER  - 
%0 Journal Article
%A Kanso, Bilal
%A Kansou, Ali
%A Yassine, Adnan
%T Open Capacitated ARC routing problem by Hybridized Ant Colony Algorithm
%J RAIRO. Operations Research
%D 2021
%P 639-652
%V 55
%N 2
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2021034/
%R 10.1051/ro/2021034
%G en
%F RO_2021__55_2_639_0
Kanso, Bilal; Kansou, Ali; Yassine, Adnan. Open Capacitated ARC routing problem by Hybridized Ant Colony Algorithm. RAIRO. Operations Research, Tome 55 (2021) no. 2, pp. 639-652. doi: 10.1051/ro/2021034

[1] R. K. Arakaki and F. L. Usberti, Hybrid genetic algorithm for the open capacitated arc routing problem. Comput. Oper. Res. 90 (2018) 221–231. | MR | Zbl | DOI

[2] E. Benavent, V. Campos, A. Corberán and E. Mota, The capacitated arc routing problem: lower bounds. Networks 22 (1992) 669–690. | MR | Zbl | DOI

[3] A. Colorni, M. Dorigo and V. Maniezzo, Distributed optimization by ant colonies (1991) 134–142.

[4] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd edition. The MIT Press (2009). | MR | Zbl

[5] M. Dorigo, V. Maniezzo and A. Colorni, Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part B (Cybern.) 26 (1996) 29–41. | DOI

[6] R. W. Eglese, Routing winter gritting vehicles. Disc. Appl. Math. 48 (1994) 231–244. | Zbl | DOI

[7] B. L. Golden and R. T. Wong, Capacitated arc routing problems. Networks 11 (1981) 305–315. | MR | Zbl | DOI

[8] B. L. Golden, J. S. Dearmon and E. K. Baker, Computational experiments with algorithms for a class of routing problems. Comput. Oper. Res. 10 (1983) 47–59. | MR | DOI

[9] S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing. Science 220 (1983) 671–680. | MR | Zbl | DOI

[10] P. Lacomme, C. Prins and W. Ramdane-Ch′Erif, Evolutionary algorithms for periodic arc routing problems. Eur. J. Oper. Res. 165 (2005) 535–553. Project Management and Scheduling. | Zbl | DOI

[11] L. Muyldermans and G. Pang, A guided local search procedure for the multi-compartment capacitated arc routing problem. Comput. Oper. Res. 37 (2010) 1662–1673. | MR | Zbl | DOI

[12] I. H. Osman and C. N. Potts, Simulated annealing for permutation flow-shop scheduling. Omega 17 (1989) 551–557. | DOI

[13] L. Santos, J. Coutinho-Rodrigues and J. R. Current, An improved ant colony optimization based algorithm for the capacitated arc routing problem. Trans. Res. B: Methodol. 44 (2010) 246–266. | DOI

[14] H. I. Stern and M. Dror, Routing electric meter readers. Comput. Oper. Res. 6 (1979) 209–223. | DOI

[15] T. Stutzle and M. Dorigo, A short convergence proof for a class of ant colony optimization algorithms. IEEE Trans. Evol. Comput. 6 (2002) 358–365. | DOI

[16] G. Ulusoy, The fleet size and mix problem for capacitated arc routing. Eur. J. Oper. Res. 22 (1985) 329–337. | MR | Zbl | DOI

[17] F. L. Usberti, P. M. França and A. L. M. França, The open capacitated arc routing problem. Comput. Oper. Res. 38 (2011) 1543–1555. | MR | Zbl | DOI

[18] F. L. Usberti, P. M. França and A. L. M. França, Branch-and-bound algorithm for an arc routing problem. Annals XLIV SBPO, Rio de Janeiro (2012).

[19] F. L. Usberti, P. M. França and A. L. M. França, Grasp with evolutionary path-relinking for the capacitated arc routing problem. Comput. Oper. Res. 40 (2013) 3206–3217. | MR | Zbl | DOI

[20] P. J. M. Van Laarhoven, E. H. L. Aarts and J. K. Lenstra, Job shop scheduling by simulated annealing. Oper. Res. 40 (1992) 113–125. | MR | Zbl | DOI

[21] J. Wunderlich, M. Collette, L. Levy and L. Bodin, Scheduling meter readers for Southern California gas company. INFORMS J. Appl. Anal. 22 (1992) 22–30. | DOI

Cité par Sources :