IEEE Access (Jan 2019)
Dynamic Pick-Up and Delivery Optimization With Multiple Dynamic Events in Real-World Environment
Abstract
Real-time city distribution strategies are highly dependent on dynamic environments, requiring timely responses to real-time changes due to various dynamic events that take place in the distribution system. Considering the influence of four kinds of real-time information on vehicle routing and vehicle scheduling, including new requests arriving gradually, old requests being modified or canceled, traffic congestion and vehicle breakdowns, a dynamic vehicle routing model based on a dynamic pick-up and delivery problem considering multiple dynamic events in a real-world environment (DPDP-MDE) is established. A dynamic algorithm framework is designed to solve the problem, the tabu search (TS) algorithm and the adaptive large neighborhood search (ALNS) algorithm are adopted to improve the quality of the initial solution, and the dynamic insertion method is adopted to solve the synchronization problem of unfixed requests (that is, unaccepted customer requests and modified requests) and new requests. The experimental results show that the model and dynamic algorithm framework proposed in this paper can effectively solve the dynamic pick-up and delivery problem with time windows (DPDP-TW). At different scheduling time horizons T, the TS algorithm improves the initial solution by an average of 3.11% and the ALNS algorithm by an average of 9.98%. Under different degrees of urgency, compared to the ALNS algorithm, the quality of the solution produced by the TS algorithm is not high, but the computation time is very small and it is relatively stable. Under different request sizes, the TS algorithm can obtain optimization results in 60s under four request levels, which gives it a significant advantage over the ALNS algorithm.
Keywords
