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 language | English |
---|---|
Article number | 106052 |
Journal | Computers and Operations Research |
Volume | 150 |
DOIs | |
State | Published - Feb 2023 |
Bibliographical note
Publisher Copyright:© 2022 Elsevier Ltd
Keywords
- Generalized
- Intermediate facilities
- Length restrictions
- Multi-objective optimization
- Periodic
- Rural postman problem
ASJC Scopus subject areas
- General Computer Science
- Modeling and Simulation
- Management Science and Operations Research