Dissertation > Excellent graduate degree dissertation topics show

Research on Cutting Plane Algorithm for Directed Chinese Postman Problem with Time Dependent Travel Times

Author: WangJinXiang
Tutor: TanGuoZhen
School: Dalian University of Technology
Course: Applied Computer Technology
Keywords: Time - varying network Chinese Postman Problem Integer linear programming Cutting plane algorithm Heuristic
CLC: F618
Type: Master's thesis
Year: 2010
Downloads: 56
Quote: 2
Read: Download Dissertation

Abstract


Chinese Postman Problem is a famous graph theory, combinatorial optimization, classic in the field of logistics planning One of the problems detected in the communication system, traffic management, robotics, interactive systems analysis, website usability and software testing and other areas has important applications. However, the time characteristic of the practical problems are concerned with the application of complex field of communication technology and the development of distributed systems, hybrid systems, tests and intelligent traffic, i.e., the arc weights in the network varies dependent on the time variation, we call The network of this nature time-varying network. Chinese Postman problem in the past, been assumed that the weights in the network is static, identified, and practical problems in networks are often dynamic, such as real traffic network, traffic accidents and weather changes accidental events may cause changes in road traffic conditions, will also change the postman messenger travel time along the way through the streets. Chinese Postman Problem traditional models and algorithms can only solve the problem fixed arc right conditions, in the time-varying network application solutions obtained by the traditional methods do not comply with the requirements of the actual situation. Therefore, the study time-varying network Chinese Postman Problem model and optimization algorithm has important practical significance. However, new problems to solve in the introduction of the time factor becomes very difficult, time-varying network to Chinese Postman Problem has been shown to be NP-hard, often it is not practical to directly solve the optimal solution. This paper, starting from the point of view of mathematical programming optimization method to study the time-varying network to Chinese Postman Problem, first learn the time-varying network modeling idea of ??the traveling salesman problem combined with the cycle cover theory, a time-varying network to Chinese Postman Problem integer programming model. And stepped characteristics based on the time dependence of the driving function of time, the model is a linear, but also through the upper boundary of the analysis model to optimize the model. Then, based on integer linear programming model, this paper presents a heuristic cutting plane algorithm. In addition, according to the characteristics of the travel time, this paper also proposes two types of strong valid inequalities as cutting plane constraints added to the iteration process. Finally, combined with some test case models and algorithms were tested and analyzed. Cutting plane heuristic algorithm mentioned in this article, in the cut plane in the framework of the exact algorithm adds some new heuristic rules, the experimental results show that the algorithm is not optimal algorithm, but for less than 15 arc small-scale The algorithm can find the optimal solution of 67% of the instances, the difference between the upper and lower bounds of the solution obtained for medium-sized problems average of less than 20%, which two types of strong inequalities will improve the quality of the solution of the problem by about 28 percent. Heuristic cutting plane algorithm is fast and to solving high quality expanded mathematical programming optimization algorithm and heuristic algorithm applications. In addition, the proposed new model, the other arc routing problem of time-varying network has a good reference.

Related Dissertations

  1. Study on Site Selection of Ecological Food Franchisees in Jiaxiang, Taiyuan,F426.82
  2. Adaptive Adjustment of fire emergency plan,X928.7
  3. The Research of Memory Database Query Optional in Multi-core System,TP311.13
  4. The Research and Realization of Unwanted Code Monitoring System Based on Heuristic Algorithm,TP393.08
  5. Research of Vehicle Scheduling Problem Based on Ant Colony Algorithm,TP301.6
  6. The Research of Signal Detecting Algorithms and Improved Sphere Detecting Algorithms in MIMO Systems,TN919.3
  7. Hysteresis -based optimization of vehicle routing problem,O224
  8. Parallel sorting multiple orders optimization problem,F224
  9. Research on Optimization of Multi-Manned Assembly Line Balancing Problem,TG95
  10. Aircraft assembly moving assembly line job scheduling optimization,V262.43
  11. Chinese folk music feature extraction and classification technology research,J607
  12. Rural Postman Problem varying network and ant colony algorithm cutting plane,O221.4
  13. Segmentation based on two-dimensional human pose estimation consistency,TP391.41
  14. Air travel based on the optimal temporal reasoning Transferring Planning System,O221
  15. Flexible resource scheduling algorithm for dynamic combinatorial production and realization,F426.8
  16. Resource-based needs analysis study time production plant logistics optimization,F426.471
  17. Research on Techniques of Collecting Internet Traffic Ground Truth,TP393.06
  18. Research on Analysis Methods of Earth-Observing Requests and Application,V474.26
  19. Single herb Citrus aurantium Citrus aurantium Citrus aurantium and medicine - dried tangerine peel , ginger - clove volatile compounds,R284
  20. Drug on the chemical composition of dried ginger - galangal volatile oil and Salvia miltiorrhiza fingerprinting studies,R284
  21. Topic-based Web Information Monitoring System Strategy and Implementation,TP393.09

CLC: > Economic > Posts and Telecommunications economic > Postal > Postal services
© 2012 www.DissertationTopic.Net  Mobile