Models And Algorithms For Express Vehicle Routing Problem With Time Window

With the rapid rise of e-commerce, many courier companies are constantly emerging, how to reasonly arrange delivery vehicles to reduce the transportation cost becomes an urgent need to be addressed. Express vehicle routing problem is a variant of vehicle routing problem(VRP), which is also a NP-hard problem. The difficulties and key points of the research are rapid heuristic algorithm and the method of evaluating solution. Solving the problem can reduce transportation cost of courier company and decrease carbon dioxide emissions of the vehicle, which will have a positive impact on economic and environment. How to schedule cargo and vehicle under the given network of hubs and their time window plus the goods traffic structure and their time constraint is the most common problem in practice. In this dissertation, we will conduct our research in modeling and sovling the express vehicle routing problem with time window. The main research content are as follows.(1) Modeling and solving the express vehicle routing problem with hard-time windowThis problem focuses on how to schedule vehicle under fixed pick-up time window and delivery time window, so that the total cost is minimal. This dissertation establishes the mathematical model of the problem, designs a fast algorithm based on greedy heuristic method, proposes a new bus schedule method(circular car plus unilateral car) to replace the relatively poor symmetric bus arrangement method and gives a lower bound model to evaluate the solution. Through the experiments on real data sets in different scale, this dissertation compares the results with lower bound to verify the algorithm’s precision. Besides, this dissertation also compares the results obtained from the two bus arrangement method, which exactly illustrates the new bus schedule method is better than the original one. For 9 city dataset and 21 city dataset, the algorithm’s computing time is 1 second and 54 seconds, respectively.(2) Modeling and solving the express vehicle routing problem with variable time windowWe analyze the results of hard-time window problem and find that the time windows have great influence on the bus arrangement. In order to reduce the transportation cost further, we need to include time window as a variable parameter in the model. This dissertation names the new problem as express vehicle routing problem with variable time window and establishes the problem’s mathematical model based on the hard-time window problem, which uses the new bus schedule method(circular car plus unilateral car). In order to evaluate the merits of the solution, this dissertation builds a lower bound model by relaxing time constraints, proves the correctness of the model and uses Lingo to solve the model. Besides, this dissertation designs a two-phase algorithm for the problem which includes time window problem-solving and hard-time window problem-solving. In the phase of time window problem-solving, this dissertation designs an evaluation function to evaluate a set of time window. The results of 9 city dataset and 21 city dataset show that time windows have a great impact on the bus arrangement and a set of good time window can effectively reduce the transportation cost.