考虑动态需求的外卖配送路径优化模型及算法
|
摘要
外卖业务模式高度复杂,现有文献中缺少针对外卖配送路径优化问题的研究.鉴于此,基于同时送取货VRP问题的求解策略,引入时间惩罚成本衡量外卖配送超出时间窗的情况,定义目标函数为外卖配送成本增量总和,包括新订单的固定配送成本、额外配送成本和时间惩罚成本之和.考虑随机参数对计算复杂程度产生的影响,设定配送区域范围,对新订单进行调度时,已指派但尚未完成的订单仍由原车配送,且将时间惩罚成本作为变动成本修正目标函数,直接去掉时间窗约束,降低算法求解难度.设计"商家-客户"配对策略,引入k-means对"商家-客户"进行聚类,同一类内设计"商家-客户"遗传算法,得到启发式路径优化方案.最后,采用随机模拟算法生成动态订单测试算例,通过R语言测试模型及算法的有效性.
The business pattern of takeout is very complex and there are shot of references focusing on the optimization of takeout distribution. In view of this, a time penalty cost is introduced for deliveries outside a specified time window, which is based on the vehicle routing problem with simultaneous pickup and delivery. Then, the objective function is set as the sum of the incremental costs of takeout distribution, which includes the fixed distribution costs as well as the additional distribution cost and time penalty cost of new orders. As the random parameters have an impact on the computational complexity of this problem, a specified distribution area is designed, although orders that have not yet been completed remain with the original vehicle while new orders are dispatched. Then the time penalty cost is used as a variable cost to modify the objective function, and the time window is removed to reduce the mathematical complexity. We employ k-means clustering to group "seller–customer"items and a genetic algorithm to identify the optimal routes for seller–customer pairs in the same cluster. Finally, random simulation algorithm is used to generate a dynamic order test dataset,and R language is used to test the effectiveness of the algorithm.
The business pattern of takeout is very complex and there are shot of references focusing on the optimization of takeout distribution. In view of this, a time penalty cost is introduced for deliveries outside a specified time window, which is based on the vehicle routing problem with simultaneous pickup and delivery. Then, the objective function is set as the sum of the incremental costs of takeout distribution, which includes the fixed distribution costs as well as the additional distribution cost and time penalty cost of new orders. As the random parameters have an impact on the computational complexity of this problem, a specified distribution area is designed, although orders that have not yet been completed remain with the original vehicle while new orders are dispatched. Then the time penalty cost is used as a variable cost to modify the objective function, and the time window is removed to reduce the mathematical complexity. We employ k-means clustering to group "seller–customer"items and a genetic algorithm to identify the optimal routes for seller–customer pairs in the same cluster. Finally, random simulation algorithm is used to generate a dynamic order test dataset,and R language is used to test the effectiveness of the algorithm.
引文
[1]Salhi S,Rand G K.The effect of ignoring routes when locating depots[J].European J of Operational Research1989,39(2):150-156.
[2]Karaoglan I,Altiparmak F,Kara I,et al.A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery[J].European J of Operational Research,2011,211(2):318-332.
[3]Min H.The multiple vehicle routing problem with simultaneous delivery and pick-up points[J]Transportation Research Part A General,1989,23(5)377-386.
[4]陈萍,李航.基于时间满意度的O2O外卖配送路径优化问题研究[J].中国管理科学,2016,24(A1):170-176(Chen P,Li H.Optimization model and algorithm based on time satisfaction for O2O Food Delivery[J].Chinese Jof Management Science,2016,24(A1):170-176.)
[5]王晓文,田新,李凯.供应链治理结构的影响因素分析--基于集中式外卖模式的案例研究[J].软科学2009,23(7):46-50.(Wang X W,Tian X,Li K.An analysis of factors influencing governance structure of supply chainBased on the Case of Delivery System[J].Soft Science2009,23(7):46-50.)
[6]Kao E P C.A preference order dynamic program for a stochastic traveling salesman problem[J].Operations Research,1978,26(6):1033-1045.
[7]马慧茹,赵峰,贾利民,等.基于随机机会约束规划模型的旅行商问题及其求解算法[J].长安大学学报:自然科学版,2015,35(S1):179-183.(Ma H R,Zhao F,Jia L M,et al.Traveling salesman problem and its solution algorithm based on random chance constrained programming model[J].J of Chang’an University:Natural Science Edition,2015,35(S1):179-183.)
[8]李锋,魏莹.求解随机旅行时间的C-VRP问题的混合遗传算法[J].系统管理学报,2014,23(6):819-825.(Li F,Wei Y.Hybrid genetic algorithm for capacitated vehicle routing problem with stochastic travel time[J].Jof Systems&Management,2014,23(6):819-825.)
[9]张涛,余绰娅,刘岚,等.同时送取货的随机旅行时间车辆路径问题方法[J].系统工程理论与实践,2011,31(10):1912-1920.(Zhang T,Yu C Y,Liu L,et al.Method for the stochastic traveling time VRPSPD problem[J].Systems Engineering-Theory&Practice,2011,31(10):1912-1920.)
[10]张晓楠,范厚明,李剑锋.变动补偿的多模糊选址-路径机会约束模型及算法[J].系统工程理论与实践,2016,36(2):442-453.(Zhang X N,Fan H M,Li J F.Chance-constrained model and algorithm for LRP with multiple fuzzy variables under change-reward[J].Systems Engineering-Theory&Practice,2016,36(2):442-453.)
[11]张晓楠,范厚明.模糊需求车辆路径优化及实时调整[J].上海交通大学学报,2016,50(1):123-130.(Zhang X N,Fan H M.Optimization and real-time adjustment for vehicle routing problem with fuzzy demand[J].J of Shanghai Maritime University,2016,50(1):123-130.)
[12]Zarandi M H F,Hemmati A,Davari S.The multi-depot capacitated location-routing problem with fuzzy travel times[J].Expert Systems with Applications,2011,38(8):10075-10084.
[13]Ghaffari-Nasab N,Ahari S G,Ghazanfari M.A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands[J].Scientia Iranica,2013,20(3):919-930.
[14]Singh P,Borah B.An efficient time series forecasting model based on fuzzy time series[J].Engineering Applications of Artificial Intelligence,2013,26(10):2443-2457.
[15]Yolcu O C,Lam H K.A combined robust fuzzy time series method for prediction of time series[J].Neurocomputing,2017,247:87-101.
[16]Anastasios D,Panagiotis P R,Christos D.Assessing customer service reliability in route planning with self-imposed time windows and stochastic travel times[J].Transportation Science,DOI:org/10.1287/trsc.2017.0748.
[17]Sumaiya Iqbal,Kaykobad M,Sohel Rahman M.Solving the multi-objective vehicle routing problem with soft time windows with the help of bees[J].Swarm and Evolutionary Computation,2015,24:50-64.
[18]Duygu Ta,Ola Jabali,Tom Van Woensel.Avehicle routing problem with flexible time windows[J].Computers and Operations Research,2014,52(A):39-54.
[2]Karaoglan I,Altiparmak F,Kara I,et al.A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery[J].European J of Operational Research,2011,211(2):318-332.
[3]Min H.The multiple vehicle routing problem with simultaneous delivery and pick-up points[J]Transportation Research Part A General,1989,23(5)377-386.
[4]陈萍,李航.基于时间满意度的O2O外卖配送路径优化问题研究[J].中国管理科学,2016,24(A1):170-176(Chen P,Li H.Optimization model and algorithm based on time satisfaction for O2O Food Delivery[J].Chinese Jof Management Science,2016,24(A1):170-176.)
[5]王晓文,田新,李凯.供应链治理结构的影响因素分析--基于集中式外卖模式的案例研究[J].软科学2009,23(7):46-50.(Wang X W,Tian X,Li K.An analysis of factors influencing governance structure of supply chainBased on the Case of Delivery System[J].Soft Science2009,23(7):46-50.)
[6]Kao E P C.A preference order dynamic program for a stochastic traveling salesman problem[J].Operations Research,1978,26(6):1033-1045.
[7]马慧茹,赵峰,贾利民,等.基于随机机会约束规划模型的旅行商问题及其求解算法[J].长安大学学报:自然科学版,2015,35(S1):179-183.(Ma H R,Zhao F,Jia L M,et al.Traveling salesman problem and its solution algorithm based on random chance constrained programming model[J].J of Chang’an University:Natural Science Edition,2015,35(S1):179-183.)
[8]李锋,魏莹.求解随机旅行时间的C-VRP问题的混合遗传算法[J].系统管理学报,2014,23(6):819-825.(Li F,Wei Y.Hybrid genetic algorithm for capacitated vehicle routing problem with stochastic travel time[J].Jof Systems&Management,2014,23(6):819-825.)
[9]张涛,余绰娅,刘岚,等.同时送取货的随机旅行时间车辆路径问题方法[J].系统工程理论与实践,2011,31(10):1912-1920.(Zhang T,Yu C Y,Liu L,et al.Method for the stochastic traveling time VRPSPD problem[J].Systems Engineering-Theory&Practice,2011,31(10):1912-1920.)
[10]张晓楠,范厚明,李剑锋.变动补偿的多模糊选址-路径机会约束模型及算法[J].系统工程理论与实践,2016,36(2):442-453.(Zhang X N,Fan H M,Li J F.Chance-constrained model and algorithm for LRP with multiple fuzzy variables under change-reward[J].Systems Engineering-Theory&Practice,2016,36(2):442-453.)
[11]张晓楠,范厚明.模糊需求车辆路径优化及实时调整[J].上海交通大学学报,2016,50(1):123-130.(Zhang X N,Fan H M.Optimization and real-time adjustment for vehicle routing problem with fuzzy demand[J].J of Shanghai Maritime University,2016,50(1):123-130.)
[12]Zarandi M H F,Hemmati A,Davari S.The multi-depot capacitated location-routing problem with fuzzy travel times[J].Expert Systems with Applications,2011,38(8):10075-10084.
[13]Ghaffari-Nasab N,Ahari S G,Ghazanfari M.A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands[J].Scientia Iranica,2013,20(3):919-930.
[14]Singh P,Borah B.An efficient time series forecasting model based on fuzzy time series[J].Engineering Applications of Artificial Intelligence,2013,26(10):2443-2457.
[15]Yolcu O C,Lam H K.A combined robust fuzzy time series method for prediction of time series[J].Neurocomputing,2017,247:87-101.
[16]Anastasios D,Panagiotis P R,Christos D.Assessing customer service reliability in route planning with self-imposed time windows and stochastic travel times[J].Transportation Science,DOI:org/10.1287/trsc.2017.0748.
[17]Sumaiya Iqbal,Kaykobad M,Sohel Rahman M.Solving the multi-objective vehicle routing problem with soft time windows with the help of bees[J].Swarm and Evolutionary Computation,2015,24:50-64.
[18]Duygu Ta,Ola Jabali,Tom Van Woensel.Avehicle routing problem with flexible time windows[J].Computers and Operations Research,2014,52(A):39-54.