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} }