A Two-stage Approach For The Time Dependent Rural Postman Problem With Time Windows

This paper puts forward a two-stage algorithm for the Time Dependent Rural Postman Problem with Time Windows (TDRPPTW), which is an important variant of the well-known Chinese Postman Problem. As a kind of classical problem in graph theory, the traditional Chinese Postman Problem and its variants which based on the static networks have been studied for decades. Nowadays, with the increasing needs of the real time systems like cyber-physical system (CPS) and Intelligent Transport System (ITS) that build upon dynamic networks, the formal theories which relied on static networks meets great challenges. Therefore, we need to rebuild these theories and models on the time-dependent networks to adapt to these demands.First, the state of the art and the research trend of the Rural Postman Problem are analyzed, and the definition of TDRPPTW is presented after that. After considering the unique properties of TDRPPTW, we propose a two-stage approach to solve the problem.In the first stage, we present an updated graph transformation algorithm, through which we can transform TDRPPTW that base on the time-dependent network to the general rural postman problem (GRPP) that build upon a static network. Then a solution programming model using 0-1 mixed integer is established to solve GRPP. The path we obtain in this stage is not the complete solution, it is the path that directly back to the source point after traversing all arcs which need to be served in time windows without passing any other arcs and points. So we must get the real path to complete the solution.In the second stage, we take the final point and time from the path l1 which is the solution get in the first stage as a new start point, and find the shortest path between the new start point and the source point on the formal time-dependent networks. Then we obtain another path l2, which combine with l1 make a complete circle. And the circle is proved to be an equivalent solution of TDRPPTW.In the end, we verify the correctness and effectiveness of the solution on some randomly generated instances, computational results show that the two-stage algorithm is good strategy to solve medium-sized TDRPPTW instances build on time-dependent networks with the nature of first in first out (FIFO).