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.
https://doi.org/10.1007/s12351-021-00639-0Cite as:
@article{Xin_2021,
doi = {10.1007/s12351-021-00639-0},
url = {https://doi.org/10.1007%2Fs12351-021-00639-0},
year = 2021,
month = {may},
publisher = {Springer Science and Business Media {LLC}},
volume = {22},
number = {3},
pages = {2943--2972},
author = {Jianbin Xin and Benyang Yu and Andrea D'Ariano and Heshan Wang and Meng Wang},
title = {Time-dependent rural postman problem: time-space network formulation and genetic algorithm},
journal = {Operational Research}
}