考虑同时取送随机需求的多行程车辆路径研究

beoplay体育提现学报（社会科学版） ›› 2019, Vol. 29 ›› Issue (3): 87-95.

考虑同时取送随机需求的多行程车辆路径研究

刘虹,傅晓敏

福州大学经济与管理学院,福建福州 350108

收稿日期:2019-07-22 出版日期:2019-09-25 发布日期:2019-09-25
作者简介:刘虹（1973-）,女,福建三明人,福州大学经济与管理学院,副教授,研究方向：物流与供应链管理,灰色系统,智能算法等|傅晓敏（1994-）,女,福建三明人,福州大学经济与管理学院,硕士研究生,研究方向：物流与供应链管理
基金资助:
福建省自然科学基金项目“智慧物流配送网络动态集成与自适应优化模型及其算法”(2014J05082)

Study on Multi-Trip Vehicle Routing Problem with Stochastic Simultaneous Pickup-Delivery Demand

LIU HONG,FU XIAOMIN

School of Economic and Management,Fuzhou University,Fuzhou,350108,China

Received:2019-07-22 Online:2019-09-25 Published:2019-09-25

摘要/Abstract

摘要：

多行程配送,由于允许车辆在配送中心和路径客户点之间多次往返的完成配送任务,具有高服务效率、低遣车成本等优点。配送中,客户需求常具有动态性和不确定性,结合取送一体化的多行程配送模式和客户取送货需求的随机不确定性,建立带随机需求和同时取送货的多行程车辆路径优化模型。由于动态需求的突发性和同时取送,需对原有配送方案进行优化调整,提出“实时柔性点”的多行程路径调整策略;针对优化模型的随机特征,引入随机机会约束规划转化模型;设计了嵌套随机模拟的变邻域禁忌搜索算法的混合算法寻求最优配送路径。最后通过算例,验证了优化模型和求解算法是可行和有效的。

关键词: 多行程车辆路径, 随机需求, 同时取送, 柔性点策略, 禁忌搜索算法

Abstract:

Characterized by high service efficiency and low vehicle cost, multi-trip distribution allows the vehicle to travel multiple times between the distribution center and customers in order to complete the delivery task. Dynamic and uncertain customer demand is common during delivery. Combined pickup-delivery integration pattern with stochastic customer demand, an optimization model for multi-trip vehicle routing problem is set up with stochastic simultaneous pickup-delivery demand. Due to the sudden and simultaneous pickup-delivery of dynamic demand, the original distribution scheme needs to be optimized and adjusted, and the multi-trip routing adjustment strategy of "real-time flexible point" is proposed. According to the stochastic characteristics of the optimization model, a stochastic chance-constrained programming transformation model is introduced. A hybrid algorithm with nested stochastic simulation and variable neighborhood tabu search algorithm is designed to find the optimal distribution path. Finally, an example shows that the optimization model and algorithm are feasible and effective.

Key words: multi-trip vehicle routing, stochastic demand, simultaneous pickup-delivery, flexible point strategy, tabu search algorithm

中图分类号:

F252.1

刘虹,傅晓敏. 考虑同时取送随机需求的多行程车辆路径研究[J]. beoplay体育提现学报（社会科学版）, 2019, 29(3): 87-95.

LIU HONG,FU XIAOMIN. Study on Multi-Trip Vehicle Routing Problem with Stochastic Simultaneous Pickup-Delivery Demand[J]. Journal of Xidian University(Social Sciences Edition), 2019, 29(3): 87-95.

图/表 6

图1：

图2：

表1：

客户节点位置坐标"

编号	坐标	编号	坐标	编号	坐标	编号	坐标
$1$	$20,35$	$6$	$31,24$	$11$	$26,20$	$16$	$15,12$
$2$	$8,31$	$7$	$38,50$	$12$	$20,33$	$17$	$5,30$
$3$	$29,43$	$8$	$33,21$	$13$	$15,46$	$18$	$13,40$
$4$	$18,39$	$9$	$2,27$	$14$	$20,26$	$19$	$38,5$
$5$	$19,47$	$10$	$1,12$	$15$	$17,19$	$20$	$9,40$

表1：

表2：

算例仿真结果"

实验参数	仿真实验次数	$15$
实验参数	置信度水平	$0.8$
仿真次数	初始目标函数值( $× 104$ )	实际目标值( $× 104$ )	车辆数量	实际路径
$1$	$2.2486$	$2.4173$	$5$	$[10,14,15,16; 2,20,17,9; 11,6, 8,19; 18,0, 18,4, 1,12; 3,7, 5,13]$
$2$	$2.2338$	$2.2338$	$5$	$[3,7, 5,13; 10,9, 17,2; 20,18,4, 1; 12,14,15,16; 19,8, 6,11]$
$3$	$2.2461$	$2.3665$	$5$	$[4,7, 3,1; 2,0, 2,17,9, 10; 12,14,15,16; 18,5, 13,20; 19,8, 6,11]$
$4$	$2.2552$	$2.5827$	$5$	$[16,15,14,10; 9,17,20,0, 2; 11,6, 8,19; 4,5, 13,0, 18; 12,1, 3,7]$
$5$	$2.2338$	$2.3531$	$5$	$[13,5, 7,3; 10,9, 17,2; 11,0, 11,6, 8,19; 12,14,15,16; 1,4, 18,20]$
$6$	$2.2552$	$2.5676$	$5$	$[16,15,14,10; 9,17,20,2; 18,13,5, 4; 7,3, 1,0, 12; 11,6, 8,19,0, 19]$
$7$	$2.2688$	$2.4503$	$5$	$[11,6, 8,19; 2,18,20,17,0, 17; 1,4, 5,13; 12,3, 7,14; 10,9, 15,0, 16]$
$8$	$2.2338$	$2.3516$	$5$	$[20,18,4, 1; 13,5, 7,3; 10,9, 17,0, 2; 19,8, 6,11; 12,14,15,16]$
$9$	$2.2486$	$2.2486$	$5$	$[16,15,14,10; 9,17,20,2; 18,4, 1,12; 3,7, 5,13; 19,8, 6,11]$
$10$	$2.2461$	$2.2461$	$5$	$[18,5, 13,20; 4,7, 3,1; 12,14,15,16; 11,6, 8,19; 2,17,9, 10]$
$11$	$2.2338$	$2.4010$	$5$	$[16,15,14,12; 10,9, 17,2; 13,5, 7,3; 11,6, 8,19; 1,4, 18,0, 20]$
$12$	$2.2468$	$2.4924$	$5$	$[18,4, 1,12; 10,14,15,16; 13,5, 7,3; 19,8, 6,0, 11; 2,20,17,0, 9]$
$13$	$2.2338$	$2.4587$	$5$	$[1,4, 18,20; 2,17,9, 0,10; 11,6, 8,0, 19; 16,15,14,12; 3,7, 5,13]$
$14$	$2.2338$	$2.3975$	$5$	$[11,6, 8,19; 10,9, 17,2; 12,14,15,16; 20,18,4, 0,1; 3,7, 5,13]$
$15$	$2.2338$	$2.4010$	$5$	$[13,5, 7,3; 1,4, 18,0, 20; 2,17,9, 10; 16,15,14,12; 11,6, 8,19]$

表2：

图3：

图4：

参考文献 19

[1]	FLEISCHMANN B . The vehicle routing problem with multiple use of vehicle[EB/OL].( 2016 -01-27)[2019-01-12].
[2]	FRANÇOIS V, ARDA Y, CRAMA Y , et al. Large neighborhood search for multi-trip vehicle routing[J]. European Journal of Operational Research, 2016,255(2):422-441.
[3]	宋强 . 改进混合遗传算法MTVRPTW中的建模与优化[J]. 重庆交通大学学报(自然科学版), 2018,37(9):79-86,134.
[4]	HERNANDEZ F, FEILLET D, GIROUDEAU R , et al. Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows[J]. European Journal of Operational Research, 2016,249(2):551-559.
[5]	宋强 . 改进迭代局部搜索算法在MMTVRP中的应用[J]. 计算机工程与应用, 2017,53(7):248-255,262.
[6]	宋强, 杜暖男 . 改进变邻域搜索算法在求解VRPMT的应用[J]. 武汉理工大学学报(交通科学与工程版), 2017,41(1):27-31.
[7]	王连锋, 宋建社 . 基于模糊期望值模型的车辆路径问题[J]. 计算机集成制造系统, 2012,18(12):2777-2782.
[8]	李阳, 范厚明 . 随机需求车辆路径问题及混合变邻域分散搜索算法求解[J]. 控制理论与应用, 2017,34(12):1594-1604.
[9]	李阳, 范厚明 . 求解模糊需求车辆路径问题的两阶段变邻域禁忌搜索算法[J]. 系统工程理论与实践, 2018,38(2):522-531.
[10]	WASSAN N, WASSAN N, NAGY G , et al. The Multiple Trip Vehicle Routing Problem with Backhauls: Formulation and a Two-Level Variable Neighbourhood Search[J]. Computers & Operations Research, 2017,78(2):454-467.
[11]	张晓楠, 范厚明 . 模糊需求车辆路径优化及实时调整[J]. 上海交通大学学报, 2016,50(1):123-130,139.
[12]	张晓楠, 范厚明 . 带时间窗偏好的多行程模糊需求车辆路径优化[J]. 计算机集成制造系统, 2018,24(10):2461-2477.
[13]	CHARNES A, COOPER W W, SYMOND G H . Cost Horizons and Certainty Equivalents:An Approach to Stochastic Programming of Heating Oil[J]. Management Science, 1958(3):235-263.
[14]	刘宝碇, 赵瑞清, 王纲 . 不确定规划及应用[M]. 北京: 清华大学出版社, 2003: 79-103.
[15]	MEHRJERDI Y Z, NADIZADEH A . Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands[J]. European Journal of Operational Research, 2013,229(1):75-84.
[16]	NADIZADEH A, NASAB H H . Solving the dynamic capacitated location-routing problem with fuzzy demands by hybrid heuristic algorithm[J]. European Journal of Operational Research, 2014,238(2):458-470.
[17]	GLOVER F, MARTI R . Tabu search[J]. General Information, 1989,106(2):221-225.
[18]	HANSEN P, MLADENOVIC N . Variable neighborhood search: Principles and applications[J]. European Journal of Operational Research, 2001,130(3):449-467.
[19]	董宗然, 周慧 . 禁忌搜索算法评述[J]. 软件工程师, 2010(Z1):96-98.