Font Size: a A A

Model And Algorithm Of The Vehicle Routing Problem With Multiple Trips And Time Windows

Posted on:2012-01-13Degree:MasterType:Thesis
Country:ChinaCandidate:W B LiangFull Text:PDF
GTID:2218330368988239Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
One of the most important problems in combinatorial optimization and operations research is the well-known vehicle routing problem (VRP), whose objective is to consider how best to utilize the vehicles and determine optimal routes to be performed by a fleet of vehicles to serve a given set of customers under some side constraints, and the interest on VRP is indeed motivated both by its considerable difficulty and by its practical relevance. Recently, there has been an increasing focus on extensions of VRP arising from real-world applications, and a great deal of research results and economic benefits have been gained.In most studies, a fundamental assumption is that a vehicle dispatched for service finishes its duty in that scheduling period after it performs one route. Clearly, in many cases this assumption may not hold. In this paper, we consider this problem:A big logistic company has one depot where a fixed-size fleet of vehicles is available to do the distribution tasks. Meanwhile, the customers have strict limit to their service time and hope to be served in appointed time intervals (time windows), and each vehicle can perform multiple routes during its scheduling period and the duration of each route is limited. The problem above can be abstracted as vehicle routing problem with multiple trips and time windows. For the introduction of dual constraints of multiple trips and time windows, it becomes much more difficult to solve this type of vehicle routing problem.The models and algorithms of vehicle routing problem with multiple trips and time windows are studied in this paper. The main research works are as follows:The model about the vehicle routing problem with multiple trips and time windows was built and the heuristic algorithms commonly used to solve the vehicle routing problem with multiple trips and time windows were introduced.A route-based heuristic algorithm was designed and implemented, with the development of the presentation of route and operators in local search which comply better with the problem character, and the random route construction and efficient rout assignment were also introduced.Computational experiments were carried on Solomon's instances, as well as Gehring's benchmark instances, which are both modified to fit our problem. Experimental results demonstrate that our algorithm not only outperforms previous approaches and found all new best-known solutions for the benchmark problems, but also increases the solution quality by a big margin.
Keywords/Search Tags:Vehicle Routing, Multiple Trips, Time Windows, Route-based Heuristic
PDF Full Text Request
Related items