Abstract:

The Chinese Postman Problem is one of the classic problems in graph theory and has been deeply studied. It is applicable in a wide range of fields. With the rapid development of computer networks and communications, and Intelligent Transportation Systems (ITS), the problems in timedependent networks become more realistic than the classic problems. In this paper, we introduce the TimeDependent Chinese Postman Problem (TDCPP) for the first time,and the problem is formulated as an Integer Linear Program. The upper bound of the formulation is proved and the correctness of the formulation is verified by a small example.

Key words: Chinese Postman Problem;timedependent network;integer linear programming;unpper bound analysis