.png){kind=icon}
.png){kind=icon}
Return
Using an exact bi-objective decoder in a memetic algorithm for arc-routing (and other decoder-expressible) problems
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2023.07.021.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We address the bi-objective Capacitated Arc Routing Problem (CARP) by considering two levels of solution interpretation: implicit and explicit solutions. An algorithm that translates implicit solutions into explicit solutions is called a decoder. In this work, the decoder takes as input a permutation of the required edges and generates a Pareto frontier of CARP solutions. While bi-objective CARP was our main focus and starting point, we could also use the proposed framework to solve a bi-objective version of the traveling salesman problem by plugging-in a different decoder. Recall that bi-objective CARP asks to service (the demands of) a set of required edges using a fleet of vehicles of limited capacity so as to minimize: (i) the total travelled distance and (ii) the length of the longest route. Any permutation s of the required edges constitutes an implicit CARP solution. The decoder constructs all non-dominated explicit solutions that service the edges in the order indicated by s , i.e., the decoder is an exact algorithm that returns the optimal Pareto frontier subject to the service order s . To achieve competitive CARP results it is also important to reinforce the decoder using a local search operator that acts on explicit routes (and that may change the service order s ). For nine instances, the resulting algorithm was even able to find a new total-cost upper bound, improving upon the best solutions reported in the (considerably larger) mono-objective CARP literature. This shows that (some of) the proposed ideas can also be useful in single objective optimization: the second objective can be seen as a guide for the mono-objective search process.(c) 2023 Elsevier B.V. All rights reserved.
Keywords:
Combinatorial optimization
Bi-objective exact decoder
Bi-objective EA
Permutation problem
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
Organization
View more organizations