The Open Vehicle Routing Problems And Their Applications

Transportation comprises a significant fraction of the national economy. In the routine work, various modes of transportation all face such a common problem: how to make routes and timetables for the vehicles (trucks, buses, trains, ships and airplanes) that passengers and goods can be transported from one place to another efficiently. These problems are generally known as vehicle routing problems (VRP) in the circles of operations research.It is clear that the vehicle routing problem is the key problem in the optimization of transportation operations. Over the past three decades, the problems concerning the distribution of goods between depots and final users (customers) have received extensive attention, and researchers have made enormous progress in developing theory, models and solution methods for these problems. In this dissertation, we firstly describe the characteristics and classification of these problems, and the state-of-the-art in the solution algorithms.The open vehicle routing problem (OVRP) is another kind of the vehicle routing problem and a new research area with wide applications. The important feature of this problem, which distinguishes it from the basic VRP, is that the vehicles are not required to return to the depot, or if they are required to do so by revisiting the customers assigned to them in the reverse order. In this dissertation the Distance-Constrained and Capacitated OVRP is studied. By exploiting the special feature of this type of problem, we present a new neighborhood structure; introduce a stochastic type of diversification during the search, etc., thus proposing a new tabu search heuristic for solution. Starting with the initial solutions generated randomly and by the proposed Farthest First Heuristic respectively, the final solutions, in 9 cases out of 16 test problems, found by our tabu search heuristic are better than those in the literature. By comparing the performance of the tabu search heuristic starting with the initial solutions generated by the special heuristic with ones generated randomly, it shows that there is not much influence of initial solution on final solutions in this tabu search heuristic for the OVRP for the test databased on a complete network.Based on the above research in theory, a case of the Capacitated OVRP, the school bus routing problem is studied. It is formulated as a multi-objective combinatorial optimization problem. According to the special structure of the problem, an optimization-based heuristic for its solution is proposed. Numerical results are reported using test data from a kindergarten in Hong Kong. It has shown to be effective with a saving of 29% in total pupils' traveling times, and 22.8% in total bus loaded travel times, when comparing to existing routes planned manually.Furthermore, the passenger train planning and timetabling can also be formulated as a kind of OVRP with soft time windows. In this dissertation, the subproblem of this case, passenger train timetabling, is studied from a new point of view. Based on the fact that the importance of different category of trains, different stations on the network, and different objectives to be optimized are different, and passengers with different travel distances have different favorite departure and arrival time windows, the problem is formulated as a multi-objective programming one. A hierarchical single objective solution to the problem is proposed. In the order of category of trains and importance of stations, the problem of scheduling trains to minimize the total passeger inconvenience is solved firstly. Given solutions found at this stage, a subset that minimizes the number of passenger cars needed is determined. By the aid of the idea of constructing the penalty function in solving the VRP with soft time windows, penalties are introduced for the passenger inconvenience and the number of passenger cars needed when train departure and arrival times fall into different time windows. Thus both problems are formulated as assignment problem to solve. To find out...