Local-Ideal-Points based Autonomous Space Decomposition framework for the Multi-objective Periodic Generalized Directed Rural Postman problem under Length Restrictions with Intermediate Facilities

Long Chen, Peng Xu, Xuedong Yan, Reginald R. Souleyrette, Teng (Alex) Wang

Research output: Contribution to journalArticlepeer-review

Abstract

This paper introduces a Multi-objective Periodic Generalized Directed Rural Postman Problem under Length Restrictions with Intermediate Facilities (MO-PGDRPPLRIF) applied in the metro track inspection routing problem, which is a variant of the Arc Routing Problem (ARP). In the MO-PGDRPPLRIF, arcs are partitioned into given clusters, and each cluster is associated with a service frequency. As the vehicle has limited working hours per day, several trips may be necessary to complete all tasks. The vehicle must stop at an intermediate facility after each trip such that the parking location where the vehicle ends one day is the same as the position where the vehicle starts the next day. The following objectives are considered in the problem: (i) minimizing the total distance; (ii) making time intervals between two adjacent services for clusters with multiple service frequencies as consistent as possible; and (iii) minimizing the number of trips. In this paper, a novel multi-objective evolutionary algorithm, namely Local-Ideal-Points based Autonomous Space Decomposition (LIP-ASD), is developed to address the proposed problem. LIP-ASD employs a space-decomposition scheme to narrow the search space and exclude inferior solutions. The Discrete Particle Swarm Optimization (DPSO) is embedded to find a satisfactory solution in each decomposed space. The proposed approach is tested through the modified Capacitated ARP (CARP) benchmark instances and a real-world application in Beijing Metro Corporation. Computational results confirm that our solution approach can solve the problem effectively and outperforms the other three state-of-the-art multi-objective evolutionary algorithms.

Original languageEnglish
Article number106052
JournalComputers and Operations Research
Volume150
DOIs
StatePublished - Feb 2023

Bibliographical note

Funding Information:
We are grateful to the reviewers whose constructive comments have helped to improve the work. This work was supported by the Fundamental Research Funds for the Central Universities (2019JBZ105 and 2022YJS063). This paper was also financially supported by Beijing Subway through a project. The metro network and infrastructure inspection schedule data are from Beijing Metro Corporation.

Funding Information:
We are grateful to the reviewers whose constructive comments have helped to improve the work. This work was supported by the Fundamental Research Funds for the Central Universities (2019JBZ105 and 2022YJS063). This paper was also financially supported by Beijing Subway through a project. The metro network and infrastructure inspection schedule data are from Beijing Metro Corporation.

Publisher Copyright:
© 2022 Elsevier Ltd

Keywords

  • Generalized
  • Intermediate facilities
  • Length restrictions
  • Multi-objective optimization
  • Periodic
  • Rural postman problem

ASJC Scopus subject areas

  • Computer Science (all)
  • Modeling and Simulation
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Local-Ideal-Points based Autonomous Space Decomposition framework for the Multi-objective Periodic Generalized Directed Rural Postman problem under Length Restrictions with Intermediate Facilities'. Together they form a unique fingerprint.

Cite this