Research On Optimization Algorithms For The Vehicle Routing Problems In Collaborative Transportation

Collaborative transportation, as an emerging new mode, represents one of the major developing trends of transportation systems. Collaborative transportation brings together all participants to improve the overall performance of transportation planning and scheduling, share the information among the transportation companies, and reduce system-wide inefficiencies and cut down operational costs. Collaborative transportation was raised and adopted for only few years, thus there are many new problems that need to be studied. Among all these problems, vehicle routing problem, VRP, is an important and basic problem, which can help the companies in the collaborative transportation to utilize the vehicles and determine the optimal route scheme under some side constraints. Meanwhile, the VRPs are the basis of the collaborative transportation, since the results of the VRPs are necessary for other problems in the collaborative transportation. Therefore, in the collaborative transportation, developing solution algorithms with high quality and robustness for the VRPs is very necessary and significant to improve the management level and reduce the operation costs.This dissertation focuses on some important variant problems of the VRP in the collaborative transportation. For these problems, this dissertation proposes mathematical models, develops sharp lower bounds and designs effective optimization algorithms. The major contributions are as follows: (1) This dissertation shows a survey of the classical VRPs (i.e., the node routing problems and arc routing problems) and some special VRPs in the collaborative transportation. The mathematical models, exact algorithms and metaheuristics for these various problems are presented and discussed. Meanwhile, the implementation mechanisms and comparison of the different algorithms are given.(2) The task selection and routing problem is introduced and studied in this dissertation, in which a truckload carrier receives tasks from shippers and other partners and makes a selection between a private vehicle and an external carrier to serve each task. The objective is to minimize the variable and fixed costs for operating the private fleet plus the total costs charged by the external carrier. Both the mathematical programming formulation and the lower bound are established. An effective memetic algorithm is developed to solve the problem. Computational experiments on a range of randomly generated instances are conducted. The results show that the proposed algorithm can produce high quality solutions within a reasonable computational time span.(3) An optimization problem called the Closed-Open mixed vehicle routing problem is for the first time put forward, which can be used to assist in identifying routes when a carrier serves the customers through his private vehicles and vehicles hired from external carriers. The objective of the problem is to minimize the fixed and variable costs for operating the private vehicles and the hired vehicles. A mixed-integer programming model and an effective memetic algorithm are established for the problem. Computational experiments are conducted. The results show that the proposed algorithm is able to produce high reasonable solutions within an acceptable running time, and always outperforms the robust mixed-integer programming solver Cplex.(4) A special optimization problem in the carrier collaboration system called the multi-depot capacitated arc routing problem with full truckloads is tackled in this dissertation. This dissertation proposes a mathematical programming model and its corresponding graph theory model, with the objective of minimizing empty vehicle movements. A two-phase greedy algorithm is given to solve practical large-scale problem instances. In the first phase, a set of directed cycles is created to fulfill the transportation orders. In the second phase, chains that are composed of cycles are generated. Furthermore, a set of local search strategies is put forward to improve the initial results. To evaluate the performance of the proposed algorithms, two lower bounds are developed. Finally, computational experiments on various randomly generated problems are conducted. The results show that the proposed methods are effective and the algorithms can provide reasonable solutions within an acceptable computational time.(5) The profit sharing problem among transportation companies is also studied in this dissertation. This problem is studied on the basis of the optimization result of vehicle routing problems in the collaborative transportation. And, it is an extension of the vehicle routing problems in the collaborative transportation. In the first part, the profit margins resulting from cooperation among freight carriers are analyzed. In the second part, the possibilities of sharing these profit margins fairly among the partners are discussed. The Shapley value can be used to determine a fair allocation. Numerical results for test instances are presented. This study can promote the alliance of collaborative transportation. It can be absorbed and adapted by the future research about the related problems in the collaborative transportation.