Branch And Price Algorithms For Vehicle Routing Problems With Coordination

In recent years, with the speed-up of economic globalization and booming of the international trade, the transportation has become an essential part of the global supply chain. To many logistics companies, the transportation cost to distribute goods accounts for a significant part of the operational cost. For this reason, the way to reduce the transportation cost is always a hot topic in industrial and academic communities.In this thesis, we introduce a coordination scheme into the vehicle routing problem and obtain a new problem-the vehicle routing problem with coordination. The purpose of coordination is to share the vehicle capacity and elimate overlapping or coinciding routes among several companies so that the transportation cost can be reduced and the overall performance can be improved.We mainly study the traditional Vehicle Routing Problem (VRP) and the Multi-vehicle Routing Problem with Profits (MVRPP). In the first chapter, we introduce the basic concepts, main categories and the state-of-art for both the problems in detail.In this thesis, an exact algorithm for VRP is introduced. The VRP is formulated as a mix-integer programming model with the objective to minimize the total traveling distance. By using the Danzig-Wolfe decomposition, this model is transformed into a set partitioning (SP) model and a pricing subproblem model. The subproblem is considered as a resource constrained elementary shortest path problem (RCESPP). We develop a bounded bi-directional dynamic programming procedure to solve the RCESPP. The numerical experiment reveals that the algorithm is competent to obtain the optimal solutions in a reasonable computing time for larger-sized instances.The VRP with coordination is considered and solved by an exact algorithm based on the branch-and-price framework. According to the feature of the problem, the SP model and the subproblem model are proposed. In order to reduce the computing time, we present a new idea which consists of an extension process and several join processes to improve the known dynamic programming algorithm. Computational results for CMT cases indicate that the coordination scheme for all companies is desirable. The coordination scheme can reduce the traveling cost of all companies and enhance companies'competitions. In further experiments, we introduce the concept of the stability for the coordination scheme and make some detailed numerical analyses.The MVRPP and the MVRPP with coordination are also considerd in Chapter 5. The MVRPP consists of two opposite objectives, one pushing vehicles to collect profits and the other inciting them to minimize the traveling cost. By formulating the travel cost objective as a constraint, the multi-objective problem is formulated as a single-objective programming model. We present a SP model with the objective to maximize the profit value for the MVRPP and improve the dynamic programming to solve the RCESPP. Then the models for the MVRPP with coordination are proposed. According to the features of the subproblem, a bounded bi-directional dynamic programming is developed. The computational results show that the coordination scheme can increase the income of all companies and has a high practical value in industries.