Optimization Of Vehicle Routing Problem With Stochastic Demand For The Classified Municipal Solid Waste Based On Approximate Dynamic Programming

Under the background of the increasingly significant urbanization characteristics and the rapid improvement of people’s living standards,China has become the world’s largest waste producer,and the amount of municipal solid waste produced is increasing day by day.In order to improve the resource value and economic value of garbage,the problem of garbage classification has gradually received the attention of the whole society.As a key link between the front period with rubbish throwing and the end period with rubbish disposal,the collection and transportation logistics of garbage classification directly determines the operating cost of waste recycling,and also determines whether the waste sorting policy can be effectively implemented.Therefore,how to carry out reasonable vehicle routing optimization methods during the collection and transportation process has become a concern.Due to the short period of time for the comprehensive implementation of the garbage classification policy in China,the current research on the vehicle routing problem for the municipal solid waste lacks consideration of the classification collection and transportation mode,and most of the research is still at the stage of mixed garbage transportation.In addition,there are many uncertainties in the actual garbage collection and transportation process,among which the amount of garbage produced at each collection point is random.Only when pick-up trucks arrive at the points,can they know the exact demands.The demands of each point gradually appear in the form of information flow over time,and the progress of science and technology has made it possible for real-time information interaction and real-time decision-making.Therefore,this paper considers the dynamic adjustment of the collection routing caused by the fluctuation of the demand of garbage collection points,uses the Markov Decision Processes to establish the real-time path decision-making models under the two classification transportation modes,“sub-packing” and “unified-packing”,and applies the Approximate Dynamic Programming(ADP)to solve them.The ADP algorithm,which can solve the problem of "dimensional disaster" in solving complex problems,has developed rapidly in recent years and has been gradually applied to the field of transportation.This paper uses Boltzmann exploration strategy to improve the approximate iterative algorithm and solves two models respectively.In addition,discuss the advantages and disadvantages of two modes,and the scope of application,so as to provide reference for the operation scheme of garbage classification and collection for various sanitation departments.The main work of this paper is as follows: First,carry out basic research on the VRP problem of waste classification collection and transportation,VRP problem with stochastic demand,and ADP algorithm,summarize the particularity of the waste classification collection and transportation VRP problem,and analyze the research status of ADP and its application in VRP problems based on the Vosviewer bibliometric software.Secondly,considering the aspects of time,decision-making,status and cost,construct two transportation modes,“sub-packing” and “unified-packing”.And complex conditions,such as multiple operations at the transfer station,multiple types of garbage,and satisfaction constraints,are also considered comprehensively.In terms of model solving,the approximate value iterative algorithm is used,and the Boltzmann exploration strategy is applied to improve the algorithm.Finally,the real data of the garbage collection and transportation in the Waste Transfer Station in Jiangbei District,Nanjing,is used as an example analysis.Through the comparative analysis of the two transportation modes and algorithms,the following conclusions can be drawn:(1)Compared with the “sub-packing” mode,the “unifiedpacking”mode uses fewer vehicles,reduces the transportation cost by 25.9%,and the total cost by 13.9%,so the efficiency is higher.But the time penalty cost of it is 44.4%higher.(2)In areas with dense garbage collection points,it is more suitable to continue to use the “sub-packing” system to complete the task on time,while the “unifiedpacking”mode is more suitable to implement in the area with scattered collection points to reduce the cost of collection and transportation.(3)Through the comparative analysis of the ADP algorithm based on Boltzmann exploration strategy with Q-learning,and the approximate iteration strategy based on the value function of the post-decision variable,it is found that the ADP algorithm based on the Boltzmann exploration strategy has faster convergence speed and higher execution efficiency.