An improved multi-objective framework for the Rich arc routing problem

Long Chen, Peng Xu, Reginald R. Souleyrette

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


This article introduces a Rich Arc Routing Problem (RARP). Required arcs are partitioned into given clusters, and each cluster shall be serviced for prescribed times during the planning horizon. There is a time limit that restricts the visits that can be performed in a single day. Each vehicle has to stop at one of intermediate facilities before the end of the specific hours per day. Accordingly, several days may be necessary to complete all tasks, and paths traveled by different vehicles on the same day shall not overlap. The RARP consists of finding a set of routes with (i) the minimum total distance, (ii) the minimum number of vehicles, (iii) the minimum pure working days, and (iv) the temporal service time interval consistency of each cluster. Recently, a Local-Ideal-Points based Autonomous Space Decomposition (LIP-ASD) algorithm has been demonstrated to be a competitive multi-objective framework. However, randomly generating an initial population in each decomposed space decreases the convergence speed of LIP-ASD. In addition, retaining only one individual preserved in each sub-space limits population diversity. In response to these issues, an Improved LIP-ASD (I-LIP-ASD) for RARP is developed. The two improvements of the proposed algorithm are as follows: (i) the initial population in the current sub-space is generated by combining existing nondominated individuals, and (ii) all nondominated solutions will be output from the evolved population in each decomposed sub-space. Finally, we conduct a series of experiments over converted capacitated arc routing problem instances, as well as analyze them under a real-world case to evaluate and demonstrate the effectiveness of the proposed solution algorithm.

Original languageEnglish
Article number106345
JournalComputers and Operations Research
StatePublished - Nov 2023

Bibliographical note

Publisher Copyright:
© 2023 Elsevier Ltd


  • Intermediate facilities
  • Length restrictions
  • Multi-objective optimization
  • Periodic
  • Rich arc routing problem

ASJC Scopus subject areas

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research


Dive into the research topics of 'An improved multi-objective framework for the Rich arc routing problem'. Together they form a unique fingerprint.

Cite this