Study On Open Vehicle Routing Problem With Soft Time Windows

Transportation operations management and logistics delivery management 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.For researching the VRP systematically, it is divided into tow kinds by the circles of operations research: Closed VRP and Open VRP. When the vehicles are required to return to the depot after finished the transportation assignment, it is called Closed VRP (VRP in generally); while 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, it is called Open VRP (OVRP).The OVRP is an NP-hard problem, so Heuristic is the main-stream of solving OVRP so far. The main content of this thesis is how to apply Heuristic to solve OVRP. First, it reviews the past studies on open vehicle routing problem and their solution algorithms, focusing on the presentation of the open vehicle routing problem with time windows which is researched in this thesis. Then, the shortest neighborhood search algorithm is designed for OVRPSTW based on classic Heuristic, in which neighborhood evaluation function is given and is tested by an example. Then, genetic algorithm is designed for OVRPSTW based on meta-Heuristic and key issues in genetic algorithm such as code, reproduction, genetic cross and so on are analyzed. Finally, genetic algorithm performance is tested and the result is compared and analyzed. The performances of GA by using different reproduction, different cross operator and different cross and mutation probability is compared and sort add the best individual reservations, the cross operator add single genetic operator, adaptive cross and mutation probability and so on strategy which have more efficient performance is selected. More, computational results of GA on a set of benchmark problems are provided. Comparison with the best ones in references and the results of the shortest neighborhood search algorithm shoes that the genetic algorithm is efficient for OVRPSTW.The thesis research shows that: GA has the superiority for OVRP and can get the better satisfactory solution of the problem and the paper lays the foundation for designing more effective GA to solve the practical problems related OVRP.