Optimization Of The Dynamic Vehicle Routing Problem With Increasing Scale

With the rapid economic development in China, the retail industry has developed tremendously in the past decade, and presents colony type characteristics, i.e., the number of stores is increasing, the orders per store is small but the total demand is large. To gain the benefit of the economies of scale, usually a unified distribution center serves all the stores in a region. With the transportation cost taking up to 50 percentage of the whole distribution cost, it is important to reduce the transportation cost which makes the vehicle routing problem crucial in the real business practice. This thesis studies the new problem which we called dynamic vehicle routing problem with an increasing scale (DIS-VRP), i.e., the number of stores is more than one thousand and keeps increasing stochastically.Increase in the number of stores makes the route change every day. However, the driver familiarity with routes and customers conduces to less service time, error and exceptional cost. Also for many other practical reasons, it's beneficial to control route adjustment by creating regular or consistent routes for the DIS-VRP that assign the same driver to the set of customers to serve them through the same routes. Such consistent routes are easy to adapt to the realization of the daily uncertainty and help logistics improve the service quality.We propose a mixed integer programming formulation for the DIS-VRP, and develop an efficient three-phase heuristic algorithm based on customers cluster and Clarke & Wright and Tabu search. The model represents the uncertainty in stores changing and includes a master plan problem using all the customers at the beginning of period. The master plan routes are created without considering the similarity. After receiving distribution job, the daily schedules obtaining from the master routes are improved using a Tabu search algorithm.The scheme is implemented on real-life data. Application results show that the proposed three-phase heuristic provides high quality solutions within a reasonable running time.