Abstract: Split delivery vehicle routing problem with stochastic demands is used to describe some realistic problems like garbage collection or cash collection. In real case, stochastic demands appear gradually over time as information flows. Routing decisions have to be made in an ever-changing process of stochastic information, and when and how the stochastic information appears determines the entire decision making process. Several literatures have focused on split delivery vehicle routing problem with stochastic demands, but have used a prior optimization framework to solve the problem, which cannot incorporate the dynamic nature of stochastic demands and cannot obtain solutions with high level of accuracy. To overcome the problems, an approximate dynamic optimization framework is adapted in this paper.
A bi-level Markov decision process model allowing split delivery is formulated. The upper level model solves the division of the customer set, and decides the customer subset serviced by each vehicle. If some customer is split, the left part of the customer is treated as a new customer with stochastic demand and will be assigned to the customer set of other vehicles. When each upper level decision is made, the state is transformed into the lower level model. The lower level model decides the service sequence of the customer. When some vehicle finishes servicing a customer, the state is transformed into upper level model. The number of stages in the models is not an accurate number for allowing split demands. But based on the assumption that each demand could only be split no more than once, the number of the stages will be finite. So the model in this paper is a dynamic model with finite number of states which is not known before. Incorporating the split demand and multi-vehicle feature, we use another vehicle to serve customers as a recourse to deal with route failure when the residual capacity of a vehicle cannot meet another customer's demand. In order to solve the problem efficiently, a global recourse policies based on the dynamic decomposition and the partial reoptimization based on the approximate dynamic programming are adapted. The efficiency of the model and algorithm proposed in this paper is verified by computational results of two instance sets. One instance set is modified from the classical VRP instance set, Solomon Set, and the other set is generated by a random process which is the most commonly used method to generate instances for VRP with stochastic demands.
The test showed several conclusions: 1)The ratio between the number of the cars in the optimal solution and the expected lowest number of the cars is a little more than 1.2 times, and the number is close to the number of cars in the optimal solution derived from the heuristic. 2)The dynamic decomposition is better than the static decomposition on the expected demand delivery and the expected travel cost, even though it is more time-consuming and more customers split. 3)The optimal solution is, on the average, 2.6 percent and 1.9 percent better than the initial solution obtained by the fixed route policy, respectively on the expected demand delivery and the expected travel cost, and also, the number of split customers is, on the average, 2.5 higher than the initial solution.
Further research will take place in three areas. Firstly, models with more realistic stochastic demand distributions should be developed. As more and more information technologies and big data appear, many advanced information collecting and data processing techniques will be used to collect detailed data and to accurately describe the uncertain characteristics of stochastic demands. Second, better methods for decomposition and reoptimization should be developed. Third, new methods such as robust optimization algorithms should be used to solve split delivery vehicle routing problem with stochastic demands.

Key words: stochastic demands, split delivery VRP, approximate dynamic programming, Markov decision process

摘要： 本文针对现实生活中固体废弃物收集等需求随机的分批配送车辆路径问题,建立双层马尔科夫决策模型,使用基于动态分区的全局修正策略和基于部分重优化算法的近似动态规划进行求解。通过算例测试和分析表明模型和算法的有效性。得到以下结论:1)SDVRPSD的最优解中车辆数略高于最小期望车辆数的1.2倍,接近使用进化算法得到的最优解中的车辆数,这两者平均约相差0.6辆。2)与静态分区相比,动态分区以花费较多时间为代价,能显著提升服务范围、降低服务费用,并增加分批配送点数量。3)算法最优解与使用固定路径算法得到的初始解相比,期望服务需求量平均提高约2.6%,期望行驶费用平均降低约1.9%;分批配送点数平均多2.5个。

关键词: 随机需求, 分批配送车辆路径问题, 近似动态规划, 马尔科夫决策过程