TY - GEN
T1 - MA-ABC
T2 - 2021 Genetic and Evolutionary Computation Conference, GECCO 2021
AU - Ramamoorthy, Muhilan
AU - Forrest, Stephanie
AU - Syrotiuk, Violet R.
N1 - Funding Information:
SF was supported in part by NSF (CCF 1908633), DARPA (FA8750-19C-0003, N6600120C4020), AFRL (FA8750-19-1-0501), and the Santa Fe Institute. VRS was supported in part by NSF NeTS 1813451.
Publisher Copyright:
© 2021 ACM.
PY - 2021/6/26
Y1 - 2021/6/26
N2 - Services such as garbage collection, road gritting, street sweeping, and power line inspection can each be formulated as a capacitated arc routing problem (CARP). The traditional formulation of CARP has the goal of minimizing the total cost of the routes making up a solution. Recently, operators of such services require routes that are balanced and visually attractive in addition to low cost. Routes that are balanced are about equal in length and provide fair work assignments. Visually attractive routes are subjective, but they usually involve non-crossing routes that provide well defined service areas. These additional features are important because they address operational complexities that arise from using the routes in practice. This paper presents MA-ABC, a memetic algorithm to find solutions for CARP that maximize route attractiveness and balance, while minimizing total cost. A novel fitness function combines route overlap with route contiguity to assess route attractiveness. MA-ABC is the first to incorporate attractiveness in a three-objective search for heuristic solutions for CARP. Experimental results on CARP benchmark instances show that MA-ABC finds a diverse set of heuristic solutions at the Pareto front, providing a wide choice for service operators to tradeoff design objectives.
AB - Services such as garbage collection, road gritting, street sweeping, and power line inspection can each be formulated as a capacitated arc routing problem (CARP). The traditional formulation of CARP has the goal of minimizing the total cost of the routes making up a solution. Recently, operators of such services require routes that are balanced and visually attractive in addition to low cost. Routes that are balanced are about equal in length and provide fair work assignments. Visually attractive routes are subjective, but they usually involve non-crossing routes that provide well defined service areas. These additional features are important because they address operational complexities that arise from using the routes in practice. This paper presents MA-ABC, a memetic algorithm to find solutions for CARP that maximize route attractiveness and balance, while minimizing total cost. A novel fitness function combines route overlap with route contiguity to assess route attractiveness. MA-ABC is the first to incorporate attractiveness in a three-objective search for heuristic solutions for CARP. Experimental results on CARP benchmark instances show that MA-ABC finds a diverse set of heuristic solutions at the Pareto front, providing a wide choice for service operators to tradeoff design objectives.
KW - Capacitated arc routing problem (CARP)
KW - Evolutionary computation
KW - Genetic algorithm
KW - Memetic algorithm
KW - Multi-objective optimization
KW - Visual attractiveness
UR - http://www.scopus.com/inward/record.url?scp=85110077038&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85110077038&partnerID=8YFLogxK
U2 - 10.1145/3449639.3459268
DO - 10.1145/3449639.3459268
M3 - Conference contribution
AN - SCOPUS:85110077038
T3 - GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference
SP - 1043
EP - 1051
BT - GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference
PB - Association for Computing Machinery, Inc
Y2 - 10 July 2021 through 14 July 2021
ER -