Modeling And Solving Vehicle Routing Problem With Complex Constraints

With the globalization and information of the economy, modern logistics has expanded from providing the society traditional transportation service to the integrated logistic system with the support of modern science, information technology and management. Vehicle scheduling is the key problem in the logistics scheduling. It can optimize the whole system and make full use of the resource of the system. With popularization of Internet and development of electronic commerce, Vehicle Routing Problem (VRP) and the Pickup and Delivery Problem (PDP) are the two sub-problems focused on recently. We perform a thorough research of these important problems in the logistic scheduling. Focusing on the models and algorithms of physical distribution vehicle routing problems, this thesis mainly includes the following contents:On the basis of analyzing the elements of physical distribution vehicle scheduling systematically, this thesis builds the model of Vehicles Routing Problem without time windows and with time windows. The complex constraints and objective functions were included in the model.As the information of road network is the foundation of the algorithms, we set focus on the construction and abstraction of the topological structure of realistic road network. An automatic construction method and a preprocess algorithm was built in the thesis. The sample instances were built using the automatic construction method. With the preprocess algorithm, the library of shortcut route can be achieved, and the efficiency and flexibility of the solving process was improved reasonably.With the model of VRP, the complex constraints were analyzed. In addition, the heuristic algorithm named modified C-W algorithm was put forward. As this algorithm cannot ensure the quality of the resolution, a global optimization algorithm named modified exhaust search was put forward in this thesis. Furthermore, the detail of algorithm for solving delivery vehicle routing problem with complex constraintswas developed. Numerical results on sample instances demonstrate the validity and efficiency of the global optimization algorithm.PDP is another important problem in the logistic scheduling problem. It is to arrange the optimal routes for a fleet of vehicles to satisfy the requirements of the customers. On the base of the model with complex constraints, the global optimization algorithm was developed.After the analysis of the exact and heuristic algorithms to VRP and PDP, the clustering method was used to solve the above two problems. Cluster analysis was used to gather the customers close to each other and construct the initial solution routes. The global optimization algorithm was exploited to get the global optimum solution for each cluster. The method improves the scale and efficiency of VRP and PDPTW. Numerical results on Solomon benchmark problems demonstrate the validity and efficiency of the improved global algorithm.