Time-dependent rural postman problem: time-space network formulation and genetic algorithm

Jianbin Xin (), Benyang Yu (), Andrea D’Ariano (), Heshan Wang () and Meng Wang ()
Additional contact information
Jianbin Xin: Zhengzhou University
Benyang Yu: Zhengzhou University
Andrea D’Ariano: Università Degli Studi Roma Tre
Heshan Wang: Zhengzhou University
Meng Wang: Delft University of Technology

Operational Research, 2022, vol. 22, issue 3, No 45, 2943-2972

Abstract: Abstract In this paper, a new time-space network model is proposed for addressing the time-dependent rural postman problem (TDRPP) of a single vehicle. The proposed model follows the idea of arc-path alternation to form a feasible and complete route. Based on the proposed model, the time dependency of the TDRPP is better described to capture its dynamic process, compared to the existing methods using a piecewise constant function with limited intervals. Furthermore, the property of first-in-first-out (FIFO) can be satisfied with the time spent on each arc. We investigate the FIFO property for the considered time-dependent network and key optimality property for the TDRPP. Based on this property, a dedicated genetic algorithm (GA) is proposed to efficiently solve the considered TDRPP that suffers from computational intractability for large-scale cases. Comprehensive simulation experiments are conducted for various time-dependent networks to show the effectiveness of the proposed GA.

Keywords: Rural postman problem; Time-space network model; Time-dependent network; Genetic algorithm (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s12351-021-00639-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:22:y:2022:i:3:d:10.1007_s12351-021-00639-0

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-021-00639-0

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().