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.

Xin, J., Yu, B., D'Ariano, A., Wang, H., Wang, M. (2021). Time-dependent rural postman problem: time-space network formulation and genetic algorithm. OPERATIONAL RESEARCH [10.1007/s12351-021-00639-0].

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

D'Ariano A.;
2021-01-01

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.
2021
Xin, J., Yu, B., D'Ariano, A., Wang, H., Wang, M. (2021). Time-dependent rural postman problem: time-space network formulation and genetic algorithm. OPERATIONAL RESEARCH [10.1007/s12351-021-00639-0].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/391039
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact