Research On Open Vehicle Routing Problems With Fuel Consumption

This paper mainly research three open vehicle routing problems with fuelconsumption.Chapter1introduces the research status of vehicle routing problems with fuelconsumption, and the main contents of each chapter in this paper. Chapter2introduces the vehicle routing problems, the restricted conditions of the vehiclerouting problems, and some methods for solving these kinds of problems. Chapter3studies a single vehicle depot open vehicle routing problem with fuel consumption.Firstly, a mixed integer nonlinear programming model for this problem is built, andthen a tabu search algorithm is given to solve this problem. In the tabu searchalgorithm, in order to improve its performance, the paper takes strategies as follows.1)the paper gives an improved nearest neighbor algorithm to get a feasible solution, andtakes this feasible solution as the initial solution of the tabu search algorithm;2) somespecial operations of neighborhood are used on the basis of the vehicles havingdifferent types. Finally, an example is given to explain the tabu search algorithm.Chapter4discusses a multi-depot and heterogeneous-vehicle open vehicle routingproblem with fuel consumption which is gotten by changing the single depot in theproblem of chapter3into multi-depot and remaining other conditions of chapter3unchanged. The paper builds the mixed integer nonlinear programming model for thisproblem. When this problem is solved by a genetic algorithm, a nearest neighboralgorithm is developed to generate the initial population, some special operations areused in mutation and crossover, and an example is given to explain the geneticalgorithm. Chapter5researches a multi-depot and heterogeneous-vehicle open vehicle routing problem with time-window and fuel consumption which adds thetime-window constraint based on the problem in chapter4. The characteristic of thischapter is that the time-windows are all multi-time-windows, i.e. each customer has atleast one time-window for selection, and is served only by one vehicle in onetime-window. The problem in this chapter is still solved by a genetic algorithmwhich is quite different from the one in chapter4since the problem in this chapter is aextension to that in chapter4，i.e. own to the time window constrain being added inthis chapter, thus when nodes are swapped or inserted in the crossover and mutationoperation, the vehicles arrives each customer need to be checked whether they feedthe time-windows of their customers, if the time-windows are fed, the swapping orinserting operation is proceeded, otherwise, the swapping or inserting operation isstopped. At the end, this paper makes a prospect to the future research of vehiclerouting problem with fuel consumption.