Model And Algorithm For Consistent Vehicle Routing Problem In Intra-City Distribution System

The logistics is a basic,strategic,and leading industry that supports the development of the national economy.It is also an important support for building a modern economic system and promoting high-quality economic development.Intra-city distribution,the“last mile” solution for the logistics,plays a very important role in the entire logistics system.It is not only a key step that affects the overall efficiency of distribution,but also one of the most important indices that customers evaluate the service.Therefore,the optimization of intra-city distribution plan is the key for logistics companies to improve their core competitiveness.Most existing studies only focus on single scenario(for example,one day),while ignoring the potential impact of the difference between the distribution plans in different scenarios.Based on the above background,this study focuses on the intra-city distribution problem.A strategy that collaboratively optimizes the vehicle routes in the several days is proposed.Then,the studied problem is abstracted as consistent vehicle routing problem based on multiple scenarios.The main contents of this paper are as follows:(1)Based on the analysis of the intra-city distribution problem,it is recognized that the difference between daily distribution plans may cause negative potential impacts,for instance,drivers are not familiar with the route and customers are served irregularly.To address this issue,this study collaboratively optimizes the vehicle routes in multiple scenarios to make them consistent.The connotation of consistency is analyzed,and the concept is extended from the space and time dimensions.In this way,the core content and research structure of the consistent vehicle routing problem are determined,which lays the foundation for the follow-up chapters.(2)From the perspective of reducing the transportation cost of logistics companies,a vehicle routing problem with time window is studied.An integer model based on a spacetime network is constructed.The goal is to minimize the distribution cost with the constraints of time window and the maximum fleet size.In order to solve the problem efficiently with the insurance of the solution quality,this study introduces the alternating direction multiplier method into the integer programming problem and designs an alternating direction multiplier method-based solution framework for the vehicle routing problem with time window.In the solution framework,the method of estimating the lower bound of the problem and the adaptive rule of updating the key parameter are proposed.The performance of the proposed approach is investigated using the classical Solomon dataset and a real-world instance.(3)From the perspective of improving the driver's familiarity with the driving environment,a consistent vehicle routing problem considering path consistency is studied.Based on a flexible consistency strategy,the study constructs a model,which minimizes the total transportation cost of multiple scenarios with the consideration of the path consistency of drivers in different scenarios.A branch-price-and-cut algorithm is designed to solve the problem.The algorithm is performed based on a two-layer network.Furthermore,an innovative aggregation technique is proposed to accelerate the algorithm,which is specifically designed for the studied problem.Finally,a dataset based on the real road-network structure of West Jordan is constructed,and the effectiveness of the algorithm is demonstrated on a set of numerical experiments.The impact of consistency on transportation distance is also analyzed.(4)From the perspective of improving customer satisfaction,this study considers a time window assignment vehicle routing problem,where time windows assigned to customers in each scenario need to be consistent.A mixed integer programming model is formulated for this problem,and an adaptive large neighborhood search algorithm is designed to solve it.To address the coupling relationship of routes in different scenarios,this study proposes two optimization strategies,i.e.,the route-priority strategy and the time window-priority strategy,and designs the corresponding independent operators and linked operators for the algorithm.Finally,numerical experiments are designed to verify the effectiveness of the model and algorithm.The impact of the length of the time window on the transportation cost is also analyzed based on the results.The study on consistent vehicle routing enriches the theoretical basis in the field of vehicle routing problem and operation research.At the same time,this study provides the guides for the logistic companies to make the distribution plan and plays an important role in promoting the high-quality development of logistics.