时间窗-时间依赖中国邮路问题的图转换算法

A Transformation Approach for the Chinese Postman Problem with Time Windows Based on a Time-Dependent Directed Network

研究时间依赖网络上带时间窗的中国邮路问题(TDCPPTW),该问题是对中国邮路问题的扩展,它考虑了时间因素,在实时软件测试等当前许多具有时间依赖性质的热门问题中更具优势。首先提出了一个新的图转换算法;然后,从理论上证明了该转换算法能够在伪多项式时间内将TDCPPTW转换为相应的广义乡村邮路问题(GRPP);最后,建立了一个0/1线性整数规划模型用于求解转换后的问题,并对随机生成的12个实例进行了求解实验。

This paper studies the Chinese postman problem with time windows and time-dependent service and travel times（TDCPPTW）.This problem is an extension of the famous Chinese postman problem,which is more attractive in the time-dependent network,where the ＂timing＂ of each intervention is crucial.The exact problem-solving approach reported here first transforms the TDCPPTW into an equivalent Generalized Rural Postman Problem（GRPP）.Then,the latter problem is solved by a 0/1 linear formulation.Computational results are reported on a set of instances and the results show that this algorithm is a good tool to optimally solve TDCPPTW.