| The vehicle routing problem, VRP, is a classical combinatorial optimization problem, which has become one of the hot issue tackled in the field of combinatorial optimization and operations research. The optimization objective of the VRP is to consider how best to utilize the vehicles and determines the optimal route scheme under some side constraints. To study different versions of VRPs and construct solution algorithms with high quality and robustness is very necessary and significant to improve the management level and reduce operation cost of production management.Based on combinatorial optimization and metaheuristic, this dissertation chooses the VRP as research topic, and systematically studies mathematical models and optimization algorithms of some variants of standard vehicle routing problem. Main research work and contributions are shown as follows:1. This dissertation shows a survey of the VRPs Based on the definition of classified criteria for the VRP, we give a survey of the VRPs. We discuss main variants of standard VRPs and give the survey of different versions of metaheuristics for solving standard VRP. In the survey, we show implementation mechanisms and comparison results of the algorithmic performance of different algorithms.2. We give the survey of metaheuristics for solving hard combinatorial optimization problems Based on the definition of combinatorial optimization and computational complexity, this dissertation surveys all kinds of metaheuristic for solving complex combinatorial optimization problems.3. The open vehicle routing problem is studied In standard VRP, the vehicle route is assumed to be a Hamiltonian tour. By relaxing such condition, we study the open vehicle routing problem in which the vehicles don't return to the starting depot after serving the last customers or, if they do, they must make the same trip in the reverse order. We first give the mathematical model of the open vehicle routing problem and then propose an ant colony optimization metaheuristic. It is a MAX-MIN ant system hybridized with tabu search, which is implemented in the hyper-cube framework. Additionally, a post-optimization procedure is incorporated to further improve the best-found solutions. We experimentally check the efficiency and effectiveness of our algorithm by comparing the obtained results to the best available methods on a wide range of benchmark instance.4. We study a class of VRP with new time constraint, open vehicle routing problem with time windows or time deadlines We first give mathematical models and then construct an iterated local search based on tabu search for solving this problem. Different acceptance criteria and a post-optimization procedure based on threshold acceptance are incorporated in the proposed algorithm. The computational results based on randomly generated instances show that the proposed algorithm is an efficient and effective approach to solving the open vehicle routing problem with time windows or time deadlines.5. This dissertation studies the vehicle routing problem with time windows and random travel and service times By introducing new side constraints: time windows and random travel and service times, a new stochastic VRP, the vehicle routing problem with time windows and random travel and service times is studied. This problem is originally formulated as a chance constrained programming model and a stochastic programming model with recourse in terms of different optimization criteria. The former is to minimize transportation cost composed of fixed cost and travel distance under some stochastic constraints. The latter is a two-stage optimization problem, where the objective is to determine the first-stage route plans minimizing the expected transportation cost in the second-stage problem. To efficiently solve these two models, a tabu search based heuristic is then proposed, which takes into account the stochastic nature of this problem. Finally, some testing instances with different properties are established to investigate the algorithmic performance and computational results are reported.6. The heterogeneous vehicle routing problem with fixed vehicle fleet is also studied In the classical VRP, the vehicles are assumed to be homogeneous and the number of the vehicles is also assumed to be unlimited. But in the operations practice, the vehicles are heterogeneous (different capacity, fixed cost and variable cost) and the vehicle fleet is fixed. By relaxing the above assumptions, we study heterogeneous vehicle routing problem with fixed vehicle fleet. We first establish a mathematical model and then propose a multistarts adaptive memory programming metaheuristic for solving such version of the VRPs. In the experimental parts, we investigate the effects of considered diversification strategies and compare the performance of the proposed algorithm with those of other methods in the literatures. Computational results show that our proposed algorithm found new solutions for five instances.7. Finally we consider a case study of the VRP Taking as an example the distribution of city daily newspaper, we study the application of the VRP. Based on the actual data, we apply the framework of the VRPs studied in this dissertation to determine optimal distribution routes. We implement our proposed algorithm in this dissertation and generate optimal schemes of different versions of vehicle routing. The computational results indicate that those algorithms proposed in this dissertation are efficient and they can be used to solve actual vehicle routing problems in the production management.The research contributions of this dissertation are shown as follows:1. By relaxing the assumption that the vehicle route is Hamiltonian tour for standard VRP, we study the open vehicle routing problem in which the route is Hamiltonian path. To solve this problem, we propose an ant colony optimization algorithm. It is a MAX-MIN ant system combined with a post-optimization procedure, which is implemented in the hyper-cube framework. The comparison results with other algorithms indicate that our algorithm is an efficient method and it improves the solution quality on many instance.2. The OVRP with time windows or time deadlines is studied. To efficiently solve such two problems, we establish an iterated local search algorithm and investigate algorithmic performance based on some randomly generated instances.3. Introducing these constraints time windows, random random travel and service times, we study the vehicle routing problem with time windows and random travel and service times. Based on different optimization criteria, this problem is formulated as a chance constrained programming model and a stochastic programming model with recourse. To solve this problem, a tabu search based algorithm is proposed and its performance is investigated based on some randomly generated instance.4. By relaxing the assumption that the vehicles are homogeneous and the number of the vehicles is unlimited for standard VRP, we study the heterogeneous vehicle routing problem with fixed vehicle fleet. We propose a multistarts adaptive memory programming metaheuristic for this problem. Computational results show that our proposed algorithm is a good algorithm for solving the heterogeneous vehicle routing problem with fixed vehicle fleet and it found new solutions for five instances.This dissertation systematically studies the models and algorithms for some variants of the VRPs by applying operations research and combinatorial optimization. This research work extends the research field of the vehicle routing problem and enriches the theoretical research of operations research and management science. It also can give reference for the design and planning of optimal vehicle routing scheme encountered in the filed of transportation, logistics, and distribution management.
|
PDF Full Text Request