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].
Titolo: | Time-dependent rural postman problem: time-space network formulation and genetic algorithm | |
Autori: | ||
Data di pubblicazione: | 2021 | |
Rivista: | ||
Citazione: | 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]. | |
Handle: | http://hdl.handle.net/11590/391039 | |
Appare nelle tipologie: | 1.1 Articolo in rivista |