Study On Optimization Methods Of Large Scale Vehicle Routing Problems

Distribution operation has an essential position in the logistics networks.According to the authoritative data, more than half of the cost is generated duringdistribution operation, especially, in the large-scale network. Accompanied by thecomplex transportation and the higher quick-response requests, it seems moreimportant to efficiently optimizite the delivery routes. Therefore, the research on thelarge-scale vehicle routing problems (VRP) becomes the key part for cost reduction.In this thesis, the vehicle routing problem is studied from the aspects of static andstochastic demands. Firstly, under the static demands, the problem is studied whendemands are split or not. Secondly, considering the stochastic demands, MarkovDescission Process and heurisitcs are used to genenrate a real-time dynamic routescheduling strategy.The main contributions are listed as following.Large-scale networks normally need to be partitioned into several sub-zones,then, shipment consolidation can be implemented in each sub-zone, so we analyze themethod for the customer clustering problem. Firstly, an improved clustering methodbased on artificial immune is proposed. To obtain the initial solutions, the initialantibody network has been introduced by SOM (self organizing map) method. In theprocess of the clustering iterations, a series of optimization and evolution strategieshave been designed, such as Clustering satisfaction, the threshold design of scalecompression, the learning rate, the clustering monitoring points and the clusteringevaluations indexes. These strategies can make the clustering thresholds to bequantified and to reduce the operator’s subjective factors. Thus, the local optimal andthe global optimal clustering simultaneously have been proposed by the synthesizedfunction of these strategies. Finally, the experiment and the comparisons demonstratethe effectiveness of the proposed method.Secondly, the classical vehicle routing problem under static demands isconsidered. On the basis of the above study, a heuristic to solve the vehicle routingproblem is proposed based on the artificial immune system. By introducing the routecovering methodology, a new encoding with a heuristic structure is developed. Routesare constructed primarily by cluster-first-route-second method, with the network renewal mechanism to generate initial antibodies and the bi-learning withbalanced-opportunity approach to expand antibody population. The concentric-circlebuilder is developed to identify different customer clusters to further form routes.Upon the elite strategy (AB) and (R), worse antibodies are deleted to keep routesdiversified in the pool. By further solving the set covering model, regarding theupdated route pool, the VRP solution is improved along with the increasing routechoices. Further, the route combination phase is developed to add promising routes,which brings the final optimal VRP solution by selecting optimal routes from the finalroute pool. Finally, experiment tests are carried out to illustrate the effectiveness ofthe proposed heuristics.Thirdly, under static demands, a problem of consolidating shipments into fullloads is considered when split deliveries are allowed. A bi-level clustering model isproposed to describe the problem. A bi-level clustering method is introduced, namelyfirst clustering, second shipment consolidation for each customer group. Thealgorithm is composed of the artificial immune technique and pseudo hierarchicalclustering assignment algorithm by iterative improvements to obtain the final bestsolutions. On the numerical study, compared with a latest results of some reference,the proposed algorithm shows a better performance.Finally, we develop a paired cooperative reoptimization strategy to solve thevehicle routing problem with stochastic demands. The strategy can realizereoptimization policy under cooperation between a pair of vehicles, and can be furtherapplied in the multi-vehicle situation. The strategy works as repeatedly triggeringcommunication and partition to reschedule vehicle assignment upon the real-timerevealed customer demands. We present a bi-level Markov decision process todescribe how one pair of vehicles coordinate to serve customers under the PCRstrategy. We also propose the corresponding heuristic, by implementing the heuristic,customer visiting sequence and vehicle assignment can be dynamically altered uponthe updated information. In comparison with another latest cooperation strategy fromthe literature, the results reveal that our strategy has a better performance, withaverage around20%to30%cost saving versus the other strategy.