An Artificial Bee Colony Algorithm for Static and Dynamic Capacitated Arc Routing Problems

Zsuzsanna Nagy, Ágnes Werner-Stark and Tibor Dulai
Additional contact information
Zsuzsanna Nagy: Department of Electrical Engineering and Information Systems, Faculty of Information Technology, University of Pannonia, Egyetem St. 10, 8200 Veszprém, Hungary
Ágnes Werner-Stark: Department of Electrical Engineering and Information Systems, Faculty of Information Technology, University of Pannonia, Egyetem St. 10, 8200 Veszprém, Hungary
Tibor Dulai: Department of Electrical Engineering and Information Systems, Faculty of Information Technology, University of Pannonia, Egyetem St. 10, 8200 Veszprém, Hungary

Mathematics, 2022, vol. 10, issue 13, 1-38

Abstract: The Capacitated Arc Routing Problem (CARP) is a combinatorial optimization problem, which requires the identification of such route plans on a given graph to a number of vehicles that generates the least total cost. The Dynamic CARP (DCARP) is a variation of the CARP that considers dynamic changes in the problem. The Artificial Bee Colony (ABC) algorithm is an evolutionary optimization algorithm that was proven to be able to provide better performance than many other evolutionary algorithms, but it was not used for the CARP before. For this reason, in this study, an ABC algorithm for the CARP (CARP-ABC) was developed along with a new move operator for the CARP, the sub-route plan operator. The CARP-ABC algorithm was tested both as a CARP and a DCARP solver, then its performance was compared with other existing algorithms. The results showed that it excels in finding a relatively good quality solution in a short amount of time, which makes it a competitive solution. The efficiency of the sub-route plan operator was also tested and the results showed that it is more likely to find better solutions than other operators.

Keywords: capacitated arc routing problem; dynamic capacitated arc routing problem; artificial bee colony algorithm; evolutionary optimization; move operator (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/13/2205/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/13/2205/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:13:p:2205-:d:846811

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().