Route Balance On Vehicle Routing Problem With Time Windows

The Vehicle Routing Problem with Time Windows,VRPTW for short,is an important problem in logistics. There has recently been an explosion of interest since 1987.However, the most common researches were focused on the optimization of the two objectives: reduce the number of vehicle and minimize the total travel distance.Although there existed related research on Route Balance since 2006, all the previously balance researches are for vehicle loading. Nicolas .etc published their contribution on route duration balance on VRP,which is the first publication on the problem. There has been no related publications about route duration balance on VRPTW so far. With more and more attention on the human resource,the optimization of workload balance among drivers of a fleet arises as a new challenge.Based on the importance in logistics and the realistic significance of route balance on VRPTW, there exists urgent need to explorer the problem deeply.The Objective of this research is to find a set of effective and efficient heuristics, and then do optimization on the sub-route balance for the VRPTW solution.The algorithm is made up of 4 parts:the first is to obtain a initial solution using Solomon's InsertionⅠunder the framework SWO.Second,do optimization to the initial solution to reduce the number of vehicles used.And then under the premise of keeping the number of vehicle used constant,reduce the total travel distance by applying local search strategy to construct all kinds of solution neighborhood.Last but not least,is to optimize the sub-route balance to control the solution quality, and then adjust solution balance level by applying the strategy of cutting nodes from long route to insert into short route.