考虑不确定行驶时间的双目标外卖配送路径优化

赵向南; 邢磊; 靳志宏

doi:10.16411/j.cnki.issn1006-7736.2019.04.009

大连海事大学学报 >

2019 , Vol. 45 >Issue 4: 65 - 72

DOI: https://doi.org/10.16411/j.cnki.issn1006-7736.2019.04.009

交通运输工程

考虑不确定行驶时间的双目标外卖配送路径优化

赵向南 ,
邢磊 ,
靳志宏

展开

(大连海事大学交通运输工程学院，辽宁大连 116026)

赵向南（1994 — ），男，硕士生，E-mail：dmuzhaoxu@dlmu.edu.cn. 靳志宏（1963 — ），男，教授，博士生导师，E-mail：jinzhihong@dlmu.edu.cn.

收稿日期: 2019-05-14

修回日期: 2019-07-03

网络出版日期: 2023-06-02

基金资助

国家自然科学基金面上项目（71572023；71702019）；欧盟H2020项目（MSCA-RISE-777742-56）；大连市领军人才项目（2018-573）；中央高校基本科研业务费专项资金资助项目（3132019301；3132019031）.

收起

Bi-objective takeaway distribution route optimization considering uncertain driving time

ZHAO Xiang-nan ,
XING Lei ,
JIN Zhi-hong

Expand

(Transportation Engineering College, Dalian Maritime University, Dalian 116026，China)

Received date: 2019-05-14

Revised date: 2019-07-03

Online published: 2023-06-02

Fold

摘要

以运营成本和解的鲁棒性为优化目标，研究了考虑不确定行驶时间的外卖配送路径优化问题，建立混合整数规划模型，并设计了可有效求解该模型的带有精英策略的非支配排序遗传算法(NSGA-II).算例实验和数值分析验证了本文所建立模型的可行性和算法的有效性，可为第三方外卖平台调度优化提供决策支持.

关键词： 外卖配送; 路径优化; 不确定行驶时间; 非支配排序遗传算法(NSGA-II); 鲁棒性

本文引用格式

赵向南 , 邢磊 , 靳志宏 . 考虑不确定行驶时间的双目标外卖配送路径优化[J]. 大连海事大学学报, 2019 , 45(4) : 65 -72 . DOI: 10.16411/j.cnki.issn1006-7736.2019.04.009

Abstract

Taking the operation cost and robustness of the solution as the optimization objective,the delivery route optimization problem with uncertain driving time was studied, a mixed integer programming model was established, and a non-dominated sorting genetic algorithm (NSGA-II) with elite strategy to solve the model effectively was designed. The feasibility and effectiveness of the proposed model were verified by numerical analysis and example experiments, which can provide decision support for the scheduling optimization of third-party takeaway platform.

Key words： take-out delivery; routing optimization; uncertain travel times; NSGA-II; robustness

参考文献

[1]Trustdata.2018年Q1中国外卖行业发展分析报告.

[2]Ghilas V, Demir E, Woensel T V.An adaptive large neighborhood search heuristic for the Pickup and Delivery Problem with Time Windows and Scheduled Lines[J].Computers & Operations Research, 2016, 72(C):12-30

[3]Cherkesly M, Desaulniers G, Laporte G.A population-based metaheuristic for the pickup and delivery problem with time windows and LIFO loading[J].Computers & Operations Research, 2015, 62(C):23-35

[4]Li Y, Chen H, Prins C.Adaptive large neighborhood search for the pickup and delivery problem with time windows,profits,and reserved requests[J].European Journal of Operational Research, 2016, 252(1):27-38

[5]潘立军, 符卓.求解带时间窗取送货问题的遗传算法[J].系统工程理论与实践, 2012, 32(1):120-126

[6]慕静, 杜田玉, 刘爽, 等.基于即时配送和收益激励的众包物流运力调度研究[J].[J].运筹与管理, 2018, 146(05):62-69

[7]Ta? D, Dellaert N P, Woensel T V, Kok T D.Vehicle routing problem with stochastic travel times including soft time windows and service costs[J].Computers & Operations Research, 2013, 40(1):214-224

[8]Li X Y, Tian P, Leung S C.H,Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm[J].International Journal of Production Economics, 2010, 125(1):137-145

[9]陈萍, 李航.基于时间满意度的O2O外卖配送路径优化问题研究[J][J].中国管理科学, 2016, :181-187

[10]Ta? D, Gendreau M, Dellaert N, Woensel T V, Kok A.G. DVehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach[J].European Journal of Operational Research, 2014, 236(3):789-799

[11]Ehmke J F, Campbell A M, Urban T L.Ensuring service levels in routing problems with time windows and stochastic travel times[J].European Journal of Operational Research, 2015, 240(2):539-550

[12]Masson R, Ropke S, Fabien Lehuédé, Olivier Péton.A branch-and-cut-and-price approach for the pickup and delivery problem with shuttle routes[J].European Journal of Operational Research, 2014, 236(3):849-862

[13]Liu R, Xie X, Augusto V, Rodriguez C.Heuristic algorithms 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

[14]Deb K, Pratap A, Agarwal S, Meyarivan T.A fast and elitist multiobjective genetic algorithm: NSGA-II[J].IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197

[15]王旭坪, 张凯, 胡祥培.基于模糊时间窗的车辆调度问题研究[J].管理工程学报, 2011, 25(3):148-154

[16]Nedjati A, Izbirak G, Arkat J.Bi-objective covering tour location routing problem with replenishment at intermediate depots: Formulation and Meta-heuristics[J]. Computers & Industrial Engineering, 2017, 110.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

参考文献