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

Jianbin Xin, Benyang Yu, Andrea D’Ariano, Heshan Wang*, Meng Wang

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

4 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)2943-2972
Number of pages30
JournalOperational Research
Issue number3
Publication statusPublished - 2021


  • Genetic algorithm
  • Rural postman problem
  • Time-dependent network
  • Time-space network model


Dive into the research topics of 'Time-dependent rural postman problem: time-space network formulation and genetic algorithm'. Together they form a unique fingerprint.

Cite this