Study On Periodic Vehicle Routing Problem With Service Pattern Selection In Time-Space Network

The continuous innovation of information technology and the substantial improvement of the social and economic level have not only changed the production and lifestyle of residents in all aspects,but also brought about an increasing demand for logistics and transportation.As an important channel to contact manufacturers and consumers,logistics and transportation enterprises are also expanding their business scope and gradually build a logistics and transportation network connecting all parts of the country.However,compared with developed countries,Chinese logistics enterprises have several problems such as low transportation efficiency,high cost,and insufficient specialization level,which restrict the steady development of the logistics industry to a certain extent.In the whole process of logistics and transportation,most of the transportation costs occur during distribution,and the efficiency of vehicle distribution determines the operation cost and the service level of enterprises to a large extent.How to formulate flexible vehicle scheduling schemes,and meet customers’ personalized needs with the minimum cost has become a hot spot of concern for logistics enterprises and research fields.Studying vehicle routing problem can not only help transportation enterprises optimize vehicle scheduling scheme and improve service efficiency,but also save customers’ waiting time and improve service quality.In particular,the continuous emergence of offline retail stores and large supermarkets will put forward periodic door-to-door demands,logistics enterprises need to develop periodic vehicle scheduling schemes that can be reused to meet customers’ periodic replenishment needs,resulting in the focus of this paper--periodic vehicle routing problem.Most of the studies about the periodic vehicle routing problem adopt the customer or physical network.These two types of networks are static networks,which only consider the variation of the vehicle’s location in space,ignoring the coupling relationship of vehicle paths in time and space.Without considering the influence of the time-dependent link travel time on the optimal paths of the vehicle,they cannot accurately simulate the dynamic traffic operating conditions.In addition,the mathematical models of periodic vehicle routing problems established in the existing literature often have complex model structures,which are difficult to solve directly.Existing algorithms are difficult to obtain high-quality solutions when solving large-scale realistic route planning problems.Therefore,how to improve the model according to the characteristics of the actual traffic network and design a targeted solution algorithm has become a major appeal to efficiently solve the periodic vehicle routing problem.Based on this,this paper studies the periodic vehicle routing problem with service pattern selection.In this paper,the periodic vehicle routing problem is clearly defined in the physical network at first,and the customer service patterns,the representation method of vehicle service paths and the research characteristics of the problem are explained,as well as the significance and method of adding virtual nodes and virtual links in the network.Through a detailed comparison of customer network,physical network,and time-space network,this paper demonstrates the advantages of conducting periodic vehicle routing problem in the time-space network.Further,this paper systematically expounds the construction method of the time-space network,that is,introducing the time dimension to expand the one-dimensional physical network into a two-dimensional time-space network.Through simple examples,this paper illustrates the representation method of periodic vehicle routing problem in the time-space network,and demonstrates the role of time-dependent link travel time in finding the optimal vehicle paths.Secondly,by comparing the integer programming models of the vehicle routing problem and the periodic vehicle routing problem in the physical network,the difference and connection between the two types of problems are explained.Based on the constructed time-space network,two types of binary decision variables are selected,and the objective function is to minimize the total vehicle transportation cost.The flow balance constraints of nodes,vehicle capacity constraints,customer service pattern selection constraints,and consistency constraints between vehicle routes and customer service patterns(coupling constraints)are considered,and the timespace network model of periodic vehicle routing problem is established.Further,the physical network model and the time-space network model are compared,and the structure of the model is analyzed in this paper.Modeling in the time-space network can eliminate the complex broken sub-circle constraints,and embed the vehicle service time constraints into the time-space network,making the model more concise.The existence of coupling constraints connects the two types of decision variables together,which makes the problem difficult to decompose.By relaxing the coupling constraints,the problem can be decomposed and the complexity of the model solution can be reduced.Furthermore,a heuristic algorithm combined with Lagrangian relaxation theory is designed.Using the standard Lagrangian relaxation technique to relax the coupling constraints,the Lagrangian relaxation problem that is easy to decompose can be constructed,and a series of independent shortest path problems and customer service pattern assignment problems can be obtained through model decomposition.In this paper,a forward dynamic programming algorithm is designed to solve the shortest path problems,and an integer programming solver is used to solve the assignment problems.The lower bound of the optimal solution of the original problem is constructed by the solution of the Lagrangian dual problem,and the upper bound of the optimal solution of the original problem is constructed by the feasible processing of the lower bound solution.Finally,several sets of test cases are designed in this paper,and the solutions are carried out in small-scale,medium-scale and large-scale networks respectively,and the application feasibility of the model and solution effectiveness of the algorithm are verified.The test results show that the algorithm designed in this paper can effectively solve the periodic vehicle routing problem of different scales.After several iterations,the algorithm will gradually converge,and the optimal solution or the approximate optimal solution with high quality can be obtained.The comparison with the solution results of commercial solvers also verifies the high stability of the proposed algorithm.In addition,this paper analyzes the changing process of Lagrangian multipliers,the changing process of upper and lower bounds,and the convergence process of GAP during algorithm iteration,and explains the economic significance of Lagrangian multipliers.Sensitivity analysis of the algorithm is carried out in four aspects: the length of periods,the number of customers,the number of vehicles and the vehicle capacity.The influence of the changes of key parameters on the solution effect of the algorithm is explained,and some suggestions are provided for further improving the algorithm and optimizing the vehicle scheduling schemes of transportation enterprises.