A Branch-and-Cut Algorithm For The Time-Dependent Undirected Chinese Postman Problem

Routing Problems (RPs) have been studied in depth during the last 50 years due to the large number of practical applications and very important theoretical values. All about traditional RPs consider the costs of travel time on each arc as constant; they belong to Static network optimization. However, in real life the cost on each arc usually not a function of distance alone, so the assumption of constant is only an approximation of actual conditions, and so that made study in Time-Dependent Network (TDN) as necessary. About traditional RPs and NRPs with time-considered, from modeling to designing exact or heuristic algorithm is the unifying framework for study them. But for Time-Dependent Arc Routing Problems (TDARPs), because of hard modeling and mazy theory, beside our, there is no other work.The time-dependent Chinese Postman Problem (TDCPP) is a generalization of the classical Chinese Postman Problem (CPP), is belong to TDARPs. To study TDCPP, This article is also from modeling to designing exact algorithm. Firstly, thesis gives the definition of TDCPP on graph theory and analysis its categories, and discusses some of properties in TDN. Such as "Two-stage method" is no longer holds, in order to obtain the optimum, traversal times on each arc at most two is also not holds and so on.Secondly, thesis combines the property of CPP and TDCPP to give TDUCPP's (on undirected graph) two mathematical programming models, in which the cost or travel time are described as continuous functions. Then to prove the correctness of them, also analysis and discusses how to modeling other problems.Last, thesis introduces how to get upper and lower bounds and some valid, strengthening inequalities, which are used to TDUCPP exact algorithm, and mainly analysis odd cut inequalities and traversal inequalities. About algorithm designing, thesis gives two Branch-and-Cut exact algorithms (B&C) and two Heuristic Identification algorithms for TDUCPP. For B&C, this is the most promising algorithm for NP-hard problems. In the end, also gives some examples to test the correction of model and the validity of inequalities.