Font Size: a A A

Solving Time Dependent Chinese Postman Problem With Time Windows Through A Graph Transformation

Posted on:2011-05-02Degree:MasterType:Thesis
Country:ChinaCandidate:J P ChenFull Text:PDF
GTID:2178330332960834Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
In recent years, with the rapid development of modern information technology and the arrival of a hot research upsurge driven by the internet of things, people put forward higher request to reality application system of real-time,more and more practical problems become closely associated with time factors.The time-dependent problem closely combines with the practical application, which has a bright prospect in the field of study. As it can provide a more realistic problem modeling for accurate method, apparently it is a very challenging field and worth further studying.This paper studies the Time Dependent Chinese Postman Problem with Time Windows (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.Because the traditional routing algorithm based on static network did not give effective solutions about dynamic network. Therefore, how to build models aimed at the time constraints and real-time characters, and how to rapidly and precisely get the optimal solution are vital problems.We firstly discuss the definitions and properties of TDCPPTW, and analyzes its solving complexities caused by the time windows and time-dependent travel times, found that the traditional arc routing transformation methods no longer applies to the time-depend networks.Then, we put forward a new "graph transformation" algorithm which can transform the original time-dependent network to a static auxiliary graph (with "arc cluster" structures) by disperse the time sequence. Furthermore, based on the static auxiliary graph, the original time dependent problems can be converted to an equivalent generalized arc routing problems, and we theoretically prove the equivalence between the original and the after-transformation problems. Meanwhile, in order to overcome the serious increase of the scale of static auxiliary graph, we design a "graph reduction" algorithm and theoretically proved that this reduction algorithm is correct and effective.Next, a 0-1 mixed integer programming model is established to solve the general arc routing problem, and we analyses its number of variables and constraints, found that when the problem's scale is increasing, its model variables becomes quite large. Therefore, we consider to re-construct the model to use the column generation algorithm which adapts to solve some large scale problems.Finally, some testing instances are randomly generated to conduct experiments using our transform algorithm and mathematical model.Computational results are reported on 32 instances and the results show that our transform algorithm and mathematical model are good tools to optimally solve TDRPPTW instances.
Keywords/Search Tags:Timing Property, Time Dependant, the Chinese Postman Problem, Graph Transformation Algorithm, Integer Programming
PDF Full Text Request
Related items