基于时间满意度的O2O外卖配送路径优化问题研究
详细信息 查看官网全文
- 英文论文题名：Optimization Model and Algorithm based on Time Satisfaction for O2O Food Delivery
- 论文作者：陈萍 ; 李航
- 英文论文作者：CHEN Ping ; LI Hang ; Business School ; Nankai University ; The Research Center of Logistics ; Nankai University
- 年：2016
- 作者机构：南开大学商学院;南开大学现代物流研究中心;
- 论文关键词：取送货车辆路径问题 ; 时间满意度 ; O2O外卖 ; 时间窗 ; 启发式算法
- 英文论文关键词：pickup and delivery vehicle routing problem ; time satisfaction ; O2O food delivery ; time windows ; heuristic algorithm
- 会议召开时间：2016-11-12
- 会议录名称：第十八届中国管理科学学术年会论文集
- 英文会议录名称：Proceedings of the 18th Chinese Annual Conference on Management Science
- 语种：中文
- 分类号：F724.6;F719.3;TP18
- 学会代码：ZHYJ
- 会议名称：第十八届中国管理科学学术年会
- 会议地点：中国陕西西安
- 主办单位：中国优选法统筹法与经济数学研究会、西安交通大学、中国科学院科技战略咨询研究院、《中国管理科学》编辑部
- 学会名称：中国优选法统筹法与经济数学研究会
- 页数：7
- 文件大小：579k
- 原文格式：O
- 会议级别：全国
摘要
本文在分析餐饮O2O外卖客户满意度特点的基础上,基于传统的取送货车辆路径问题模型,提出一个适合餐饮O2O外卖配送的优化模型,并提出了能够有效求解该模型的启发式算法。模型以最大化客户时间满意度为目标,其中客户满意度利用到达客户时间的函数进行刻画。利用调研获取的某外卖平台的某个配送中心的实际数据构造测试算例,通过数值实验,验证了模型和算法的有效性。最后,基于仿真实验结果提出可行的外卖平台改进配送效率和客户满意度的建议。
O2O food delivery has developed quickly in recent years,in which the customer time satisfaction is an essential goal.In this paper,based on the analysis of characteristics of customer satisfaction in O2 O food delivery,aproper model is built on the basis of classical pickup and delivery vehicle routing problem.Also,heuristic algorithm is proposed for solving this model.The aim is to maximize the customer time satisfaction,which is described as a function to the arrival time at the customer.A test instance is built based on the data from a real O2 O food delivery organization.Computational results demonstrate the effectiveness of the model and algorithm.Finally,suggestions that can potentially improve both the delivery efficiency and customer satisfaction are provided.
O2O food delivery has developed quickly in recent years,in which the customer time satisfaction is an essential goal.In this paper,based on the analysis of characteristics of customer satisfaction in O2 O food delivery,aproper model is built on the basis of classical pickup and delivery vehicle routing problem.Also,heuristic algorithm is proposed for solving this model.The aim is to maximize the customer time satisfaction,which is described as a function to the arrival time at the customer.A test instance is built based on the data from a real O2 O food delivery organization.Computational results demonstrate the effectiveness of the model and algorithm.Finally,suggestions that can potentially improve both the delivery efficiency and customer satisfaction are provided.
引文
[1]艾瑞咨询.2015年中国外卖O2O行业发展报告[EB/OL].2015.http://www.iresearch.com.en/report/2370.html.
[2]Dantzig G,Ramser J.The truck dispatching problem[J].Management Science,1959,6(1):80-91.
[3]Toth P,Vigo D.Vehicle routing:Problems,methods,and applications(2~(nd)ed.)[M].Philadelphia:MOS-SIAM series on optimization.2014.
[4]Parragh S N.Doerner K F,Hartl R F.A survey on pickup and delivery problems.PartⅡ:Transportation between pickup and delivery locations[J].Journal fur Betriebswirtschaft,2008,175(2):81-117.
[5]Lu Q.Dessouky M M.A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows[J].European Journal of Operational Research,2006,175(2):672-687.
[6]Nanry W P,Barnes W Solving the pickup and delivery problem with time windows using reactive tabu search[J].Transportation Research Part B,2000,34(2):107-121.
[7]Pankratz G.A grouping algorithm for the pickup and delivery problem with time windows[J].OR Spectrum,2005,27(1):21-41.
[8]Ropke S,Pisinger D.An adaptive large neighborhood search for the pickup and delivery problem with time windows[J].Transportation Science,2006,40(4):455-472.
[9]Bent R.van Hentenryck P.A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows[J].Computers&Operations Research,2006,33(4):875-893.
[10]Ropke S,Cordeau J F,Laporte G.Models and a branchand-cut algorithm for pickup and delivery problems with time windows[J].Networks,2007,49(4):258-272.
[11]Ropke S,Cordeau J F.Branch and cut and price for the pickup and delivery problem with time windows[J].Transportation Science,2009,43(3):267-286.
[12]Baldacci R,Bartolini E,Mingozzi A.An exact algorithm for the pickup and delivery problem with time windows[J].Operations Research,2011,59(2):414-426.
[13]Chen Qingfeng.Li Kunpeng,Liu Zhixue.Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads[J].Transportation Research Part E:Logistics and Transportation Review,2014,69(3):218-235.
[14]Mannel D,Bortfeldt A.A hybrid algorithm for the vehicle routing problem with pickup and delivery and threedimensional loading constraints[J].European Journal of Operational Research,2016,254(3):840-858.
[15]Madankumar S.Rajendran C.Mathematical models for green vehicle routing problems with pickup and delivery%A case of semiconductor supply chain[J].Computers&Operations Research,2016,DOI:10.1016 li.cor.2016.03.013
[16]Li yuan,Chen haoxan,Prins C,et al.Adaptive large neighborhood search for the pickup and delivery problem with time windows,profits,and reserved requests[J].European Journal of Operational Research,2015,252(1):27-38.
[17]Tang Jiafu,Yu Yang,Li Jia.An exact algorithm for the multi-trip vehicle routing and scheduling problem of pickup and delivery of customers to the airport[J].Transportation Research Part E,2015,73:114-132.
[18]陈淑姣.基于客户价值和时间满意度的企业物流配送网络规划研究[D].重庆:重庆大学,2014.
[19]Jung S,Haghani A.Genetic algorithm for a pickup and delivery problem with time windows[J].Transportation Research Record Journal of the Transportation Research Board,2000,1733,(2):1-7.
[20]曹道友,程家兴.基于改进的选择算子和交叉算子的遗传算法[J].计算机技术与发展,2010,20(2):44-47.
[21]詹孝龙.遗传算法在带时间窗的车辆路径问题中的应用[D].南昌:江西理工大学,2014.
[2]Dantzig G,Ramser J.The truck dispatching problem[J].Management Science,1959,6(1):80-91.
[3]Toth P,Vigo D.Vehicle routing:Problems,methods,and applications(2~(nd)ed.)[M].Philadelphia:MOS-SIAM series on optimization.2014.
[4]Parragh S N.Doerner K F,Hartl R F.A survey on pickup and delivery problems.PartⅡ:Transportation between pickup and delivery locations[J].Journal fur Betriebswirtschaft,2008,175(2):81-117.
[5]Lu Q.Dessouky M M.A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows[J].European Journal of Operational Research,2006,175(2):672-687.
[6]Nanry W P,Barnes W Solving the pickup and delivery problem with time windows using reactive tabu search[J].Transportation Research Part B,2000,34(2):107-121.
[7]Pankratz G.A grouping algorithm for the pickup and delivery problem with time windows[J].OR Spectrum,2005,27(1):21-41.
[8]Ropke S,Pisinger D.An adaptive large neighborhood search for the pickup and delivery problem with time windows[J].Transportation Science,2006,40(4):455-472.
[9]Bent R.van Hentenryck P.A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows[J].Computers&Operations Research,2006,33(4):875-893.
[10]Ropke S,Cordeau J F,Laporte G.Models and a branchand-cut algorithm for pickup and delivery problems with time windows[J].Networks,2007,49(4):258-272.
[11]Ropke S,Cordeau J F.Branch and cut and price for the pickup and delivery problem with time windows[J].Transportation Science,2009,43(3):267-286.
[12]Baldacci R,Bartolini E,Mingozzi A.An exact algorithm for the pickup and delivery problem with time windows[J].Operations Research,2011,59(2):414-426.
[13]Chen Qingfeng.Li Kunpeng,Liu Zhixue.Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads[J].Transportation Research Part E:Logistics and Transportation Review,2014,69(3):218-235.
[14]Mannel D,Bortfeldt A.A hybrid algorithm for the vehicle routing problem with pickup and delivery and threedimensional loading constraints[J].European Journal of Operational Research,2016,254(3):840-858.
[15]Madankumar S.Rajendran C.Mathematical models for green vehicle routing problems with pickup and delivery%A case of semiconductor supply chain[J].Computers&Operations Research,2016,DOI:10.1016 li.cor.2016.03.013
[16]Li yuan,Chen haoxan,Prins C,et al.Adaptive large neighborhood search for the pickup and delivery problem with time windows,profits,and reserved requests[J].European Journal of Operational Research,2015,252(1):27-38.
[17]Tang Jiafu,Yu Yang,Li Jia.An exact algorithm for the multi-trip vehicle routing and scheduling problem of pickup and delivery of customers to the airport[J].Transportation Research Part E,2015,73:114-132.
[18]陈淑姣.基于客户价值和时间满意度的企业物流配送网络规划研究[D].重庆:重庆大学,2014.
[19]Jung S,Haghani A.Genetic algorithm for a pickup and delivery problem with time windows[J].Transportation Research Record Journal of the Transportation Research Board,2000,1733,(2):1-7.
[20]曹道友,程家兴.基于改进的选择算子和交叉算子的遗传算法[J].计算机技术与发展,2010,20(2):44-47.
[21]詹孝龙.遗传算法在带时间窗的车辆路径问题中的应用[D].南昌:江西理工大学,2014.