考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题

doi:10.11896/jsjkx.210400005

摘要/Abstract

摘要： 消费者对外卖食品需求的多样性使得外卖订单出现一单多品的结构特点,即一份订单中的外卖食品是由两个及以上商家所提供的。在一单多品的外卖配送背景下,针对带时间窗的外卖订单配送问题,研究订单配送的车辆路径规划。该研究能够提高商家的服务水平与配送车辆的效率。食品销售商家从线上平台接收到消费者的订单,此后商家根据订单打包食品,待车辆在要求的时间窗内到达并取走食品,再送往消费者手中。根据该过程,构建目标函数为配送成本最小化的数学模型,设置各个实体餐饮店和消费者的时间窗限制,利用遗传算法求解订单配送问题。最后,通过算例实验,验证了该数学模型的有效性和可行性,并从实践的角度出发,给出管理和路径规划方面的建议和启示。

关键词: 带时间窗的车辆路径问题, 路径规划, 时间窗, 外卖配送, 遗传算法

Abstract: The rapid growth of take-out food transaction makes take-out food develop fast and becomes a kind of new demand in consumers' market.With more and more transactions in take-out food order volumes,consumers require more on the basis of fundamental take-out food delivery service.The demand of consumers for take-out food is becoming increasingly various,which captures the structural characteristic that one take-out food order can be composed of different kinds of food provided by two or more different food merchants.Under the background of one-order-multi-product for take-out food delivery,aiming at the problem of takeaway order delivery with time window,this paper studies vehicle routing planning for delivery.This application can improve the performance of merchant service level and efficiency of delivery vehicles.Food merchants accept orders from consumers via the online food-selling platform,then prepare food.The delivery vehicle will come and pick up the food in the specific time window and send to consumers.Then this paper constructs the objective function for the mathematical model considering the lowest delivery cost during the whole delivery process,and set the time window limits of entity merchants and consumer.The genetic algorithm is used to solve the problem of take-out order delivery.Finally,the validity and feasibility of the mathematical model are verified by an example experiment.At last,suggestions on practical management and enlightenments on vehicle path planning problem are given from the perspective of practice.

Key words: Genetic algorithm, Route planning, Takeaway food delivery service, Time windows, Vehicle routing problem with time window

中图分类号:

C934

杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题[J]. 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005

YANG Hao-xiong, GAO Jing, SHAO En-lu. Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery[J]. Computer Science, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005

参考文献

[1] ZHENG W,DOU C,ZHANG Z.Simulation of Benefit Distribution in Platform Delivery Mode[J].Journal of System Simulation,2021,33(3):631-644.
[2] WANG Z.Research on Distribution and Path Optimization of Takeaway Orders under Crowdsourcing[D].Shanghai:Donghua University,2020.
[3] XING P,HE T.Optimal Quality Effort Strategy in O2O Food Delivery Service Supply Chain Based on Three Operation Models[J].Chinese Journal of Management Science,2020,28(9):115-126.
[4] YEO V C S,GOH S,REZAEI S.Consumer experiences,attitude and behavioral intention toward online food delivery (OFD) services[J].Journal of Retailing and Consumer Services,2017,35(3):150-162.
[5] RAY A,BALA P K.User gerated content for exploring factors affecting intention to use travel and food delivery services[J].International Journal of Hospitality Management,2021,92:102730.
[6] CHEN P,LI H.Optimization Model and Algorithm based onTime Satisfaction for O2O Food Delivery[J].Chinese Journal of Management Science,2016,24:170-176.
[7] SHI Y,TAO T,CAO X,PEI X.The association between spatial attributes and neighborhood characteristics based on Meituan take-out data:Evidence from shanghai business circles[J].Journal of Retailing and Consumer Services,2021,58:102302.
[8] SHI J.Research on the Order Forecast of a Restaurant O2O Enterprise Based on the ARIMA-BP Combination Model[D].Beijing:Beijing Jiaotong University,2018.
[9] LIU R,XIE X,AUGUSTO V,RODRIGUEZ C.Heuristic algo-rithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care[J].European Journal of Operational Research,2013,230(3):475-486.
[10] JUN S,LEE S,YIH Y.Pickup and delivery problem with recharging for material handling systems utilizing autonomous mobile robots[J].European Journal of Operational Research,2021,289(3):1153-1168.
[11] ZHANG L.The Vehicle Routing Problem with Time Windows Based on Improved Genetic Algorithm[J].China Logistics and Purchasing,2020(14):66-69.
[12] NIU Q,LIU J.Improved Fireworks Algorithm for Solving Vehicle Routing Problem with Time Window[J].Chinese Building and Automation,2020(1):158-161.
[13] LI W L,LI K P,KUMAR P N R,et al.Simultaneous product and service delivery vehicle routing problem with time windows and order release dates[J].Applied Mathematical Modelling,2021,89:669-987.
[14] WU F,YANG B,HONG S.Scheduling optimization of emergencysupplies with multi-supply points based on variable length genotype genetic algorithm[J].Application Research of Computers,2021,39(4).
[15] WANG F,TENG G,YAO J.Multi-Objective Vegetable Transportation and Distribution Path Optimization with Time Windows[J].Smart Agriculture,2021,3(3):152-161.
[16] YIN Y,ZHANG J.The Multi-Temperature Joint DistributionRouting Optimization Considering Loading Strategy and Time-Varying Temperature[J].China Transportation Review,2021,43(11):108-116.
[17] ZHOU Y,KONG L,CAI Y,et al.A decomposition-based local search for large-scale many-objective vehicle routing problems with simultaneous delivery and pickup and time windows[J].IEEE System Journal,2020,14(4):5253-5264.
[18] WOLFINGER D.A Large Neighborhood Search for the Pickup and Delivery Problem with Time Windows,Split Loads and Transshipments[J].Computers and Operations Research,2020,126:105110.
[19] YANIK S,BOZKAYA B,DEKERVENOAEL R.A new VRPPD model and a hybrid heuristic solution approach for e-tailing[J].European Journal of Operational Research,2014,236(3):879-890.
[20] NASRI M,METRANE A,HAFIDI I,et al.A robust approach for solving a vehicle routing problem with time windows with uncertain service and travel times[J].International Journal of Industrial Engineering Computations,2020,11(1):1-16.
[21] LUO Y,SUN Y,LIAO P.Research on Multi-Depot LocationRouting Problem with Backhauls and Soft Time Windows[J].Operations Research and Management Science,2014,23(5):78-85.
[22] KARABOGA D.An idea based on honey bee swarm for numerical optimization:Technical Report-tr06[R].Erciyes University,Engineering Faculty,Computer Engineering Department,2005.
[23] DORIGO M,MANIEZZO V,COLORNI A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on SMC,1996,26(1):8-41.
[24] YU H,TANG W,WY T.Vehicle Routing Problem with Hard Time Windows for Instnt Delivery of O2O Fresh Takeout Orders[J].Journal of System and Management,2021,30(3):584-591.
[25] XIAO J,WANG F,BAI H,et al.Location of distribution centers for fresh agricultural products based on non-equal coverage ra-dius[J].Journal of Systems Engineering,2015,30(3):406-416.
[26] MARINAKIS Y,MARINAKI M,MIGDALAS A.A multi-adaptive particle swarm optimization for the vehicle routing problem with time windows[J].Information Sciences,2019,481:311-329.
[27] SHI S.A Study off Vehicle Routing Optimization Problem on Cold Chain Logistics[D].Xi'an:Xidian University,2015.
[28] QU P.Research on Vehicle Routing Problem of Urban FreshAgricultural Products Cold Chain Distribution[D].Harbin:Northeast Agricultural University,2017.
[29] LIN Y.Research on the Vehicle Routing Problem with TimeWindows Based on Cluster Analysis and Genetic Algorithm[D].Fuzhou:Fujian Agricultural and Forestry University,2009.
[30] LIANG D,DAI Z,WANG M.Assessing customer satisfaction of O2O takeaway based on online reviews by integrating fuzzy evaluation with AHP and probabilistic term stes[J].Applied Soft Computing,2021,98.

相关文章 15

[1]	王兵, 吴洪亮, 牛新征. 基于改进势场法的机器人路径规划 Robot Path Planning Based on Improved Potential Field Method 计算机科学, 2022, 49(7): 196-203. https://doi.org/10.11896/jsjkx.210500020
[2]	谭任深, 徐龙博, 周冰, 荆朝霞, 黄向生. 海上风电场通用运维路径规划模型优化及仿真 Optimization and Simulation of General Operation and Maintenance Path Planning Model for Offshore Wind Farms 计算机科学, 2022, 49(6A): 795-801. https://doi.org/10.11896/jsjkx.210400300
[3]	沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[4]	吴善杰, 王新. 基于AGA-DBSCAN优化的RBF神经网络构造煤厚度预测方法 Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks 计算机科学, 2021, 48(7): 308-315. https://doi.org/10.11896/jsjkx.200800110
[5]	陈镜宇, 郭志军, 尹亚昆. 基于混合算法的智能割草机全遍历路径规划及其系统设计 Full Traversal Path Planning and System Design of Intelligent Lawn Mower Based on Hybrid Algorithm 计算机科学, 2021, 48(6A): 633-637. https://doi.org/10.11896/jsjkx.201100002
[6]	王金恒, 单志龙, 谭汉松, 王煜林. 基于遗传优化PNN神经网络的网络安全态势评估 Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network 计算机科学, 2021, 48(6): 338-342. https://doi.org/10.11896/jsjkx.201200239
[7]	郑增乾, 王锟, 赵涛, 蒋维, 孟利民. 带宽和时延受限的流媒体服务器集群负载均衡机制 Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster 计算机科学, 2021, 48(6): 261-267. https://doi.org/10.11896/jsjkx.200400131
[8]	杜婉茹, 王潇茵, 田涛, 张越. 面向未知环境及动态障碍的人工势场路径规划算法 Artificial Potential Field Path Planning Algorithm for Unknown Environment and Dynamic Obstacles 计算机科学, 2021, 48(2): 250-256. https://doi.org/10.11896/jsjkx.191100170
[9]	左剑凯, 吴杰宏, 陈嘉彤, 刘泽源, 李忠智. 异构无人机编队防御及评估策略研究 Study on Heterogeneous UAV Formation Defense and Evaluation Strategy 计算机科学, 2021, 48(2): 55-63. https://doi.org/10.11896/jsjkx.191100053
[10]	龚追飞, 魏传佳. 基于拓扑相似和XGBoost的复杂网络链路预测方法 Complex Network Link Prediction Method Based on Topology Similarity and XGBoost 计算机科学, 2021, 48(12): 226-230. https://doi.org/10.11896/jsjkx.200800026
[11]	郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划 Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021
[12]	姚泽玮, 林嘉雯, 胡俊钦, 陈星. 基于PSO-GA的多边缘负载均衡方法 PSO-GA Based Approach to Multi-edge Load Balancing 计算机科学, 2021, 48(11A): 456-463. https://doi.org/10.11896/jsjkx.210100191
[13]	赵杨, 倪志伟, 朱旭辉, 刘浩, 冉家敏. 基于改进狮群进化算法的面向空间众包平台的多工作者多任务路径规划方法 Multi-worker and Multi-task Path Planning Based on Improved Lion Evolutionary Algorithm forSpatial Crowdsourcing Platform 计算机科学, 2021, 48(11A): 30-38. https://doi.org/10.11896/jsjkx.201200085
[14]	曹波, 陈锋, 成静, 李华, 李永乐. 基于全向路口模型的非结构化道路重复节点路径规划 Route Planning of Unstructured Road Including Repeat Node Based on Bidirectional Search 计算机科学, 2021, 48(11A): 77-80. https://doi.org/10.11896/jsjkx.201200193
[15]	高帅, 夏良斌, 盛亮, 杜宏亮, 袁媛, 韩和同. 基于投影圆度和遗传算法的空间圆柱面拟合方法 Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm 计算机科学, 2021, 48(11A): 166-169. https://doi.org/10.11896/jsjkx.201100057

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed