Study On Disruption Management For Vehicle Routing Problem

Logistics distribution vehicle routing problem with time windows belongs to a typical NP-Hard problem. In addition, all kinds of disruptions occur in the actual logistic activities. These disruptions disturb the original optimal routing solution, impact on serving customers on time and make service quality and service efficiency decline. Therefore, it is very necessary and meaningful to quickly and efficiently handle disruptions which emerge during the logistics distribution vehicle routing problem.As a methodology of handling disruptions in real time, disruption management chiefly settles such kind of incidents that happens frequently. Based on the concept of disruption management, the recovery model and its algorithm are researched. The main researches in this paper are as follows:(1) After analyzed the differences and the settling demands in the sorts of vehicle routing problem with disruptions, three rescuing strategies, namely the same way rescue strategy, nearby rescue strategy and addition rescue strategy, are proposed to slove the disruption problem. Besides, according to the disruption management, the predigestion strategies are put forward to predigest the search space.(2) To tackle the disruption caused by the customer time window changes in the logistics, the disruption recovery solution is given based on the theory of disruption management. The transformation method for the disruption recovery of the vehicle routing problem is proposed based on multiple depots, and the disruption recovery strategies and the methods of deviation measurement are given, which is the basis of the disruption management modeling for the vehicle routing problem. For the disruption management of vehicle routing problem with the request changes of customers, the disruption is illustrated, the disruption management model is constructed, and the normalization processing for the model is given, making the model compatible with VRPTW. The chromosome code based on customer is ameliorated and the genetic algorithm is designed. A representative result and the analysis are given in this paper, and the experiment indicates the validity of the model and algorithm.(3) Demand changes in vehicle routing problem with backhaul are researched, such as new requests, requests of canceling service and increase/decrease in the quantity from backhauls. And based on disruption management thoughts, demand changes are analyzed, their impact on the original plan is measured, and a disruption recovery model for the problem is put forward. Then two strategies and heuristics algorithm are designed. Finally, benchmark data are used to test. And results show the effectiveness of the model and the algorithm.(4) From the disruption management point of view, the rescue requirements are analyzed, model for the problem with a broken-down vehicle in VRPTW with servicing distribution are proposed and the strategies are given. The algorithm founded on the strategies above is designed. Finally, the performance of these strategies are analyzed and compared.