Integer Programming Method For Time-Dependent Chinese Postman Problem Based On Arc-Path Variable

Chinese Postman Problem is one of the classical problems in graph theory and has received much research. It is applicable in a wide range of fields such as commodity dispatch, garbage collection, mail send-receive, snow removal and VLSI layout and so on. Therefore, a lot of scholars have studied this problem.All about traditional Chinese Postman Problems consider the costs of travel time on each arc as constant. However, in reality, the cost on each arc or edge usually varies with time. The typical examples are Computer Networks and Communication and Intelligent Transportation Systems. The research on Time-Dependent Chinese Postman Problem has more important actural meaning.In this paper, we firstly make a summary of research methods on traditional Chinese Postman Problem, present the polyhedral theory in detail, and give polyhedral results on Chinese Postman Problem. We study the Time-Dependent Chinese Postman Problem (TDCPP) and set up a new Integer Linear Program Model:Arc-Path Model. Moreover, we analyse the polyhedron of this model, define the Arc-Path Alternation Sequence (APAS) Polyhedron, prove the dimension of APAS Polyhedron and propose a kind of facets.As to the algorithm design, we use heuristic cutting plane algorithm to solve the Time-Dependent Chinese Postman Problem. We obtain the upper bound through the heuristic algorithm and obtain the lower bound through the cutting plane algorithm. The facet defining inequalities are used to tighten the integer programming formulation so that we are able to get a better upper bound. At last, the experiment results show that the upper bound we obtain by using facets is better.