Vehicle Routing Problem with Multiple Fuzzy Time Windows Based on Traffic Flow

doi:10.12005/orms.2018.0176

Abstract

Abstract: A multi-fuzzy time window vehicle routing problem based on traffic flow is investigated in this paper. The dynamic change of traffic flow and the fuzzy time window of customers are considered. A multi-fuzzy time window vehicle routing model based on time-varying traffic flow is proposed, and the objective function is to minimize the total cost of distribution and maximize customer satisfaction. According to the basic principle of Ito algorithm, an improved Ito algorithm for solving the model is designed. We further do simulation on an example, and compare the results obtained by Ito algorithm and ant colony algorithm. The results show that the improved Ito algorithm to solve multi-fuzzy time window vehicle routing problem based on traffic flow has the advantages of small number of iterations and high efficiency, and it can converge to the global optimal solution in a short time. The improved Ito algorithm is an efficient algorithm for solving vehicle routing problem with multiple fuzzy time windows.

Key words: traffic flow, multi-fuzzy time window, ito algorithm, vehicle routing, customer satisfaction

摘要： 研究了基于交通流的多模糊时间窗车辆路径问题,考虑了实际中不断变化的交通流以及客户具有多个模糊时间窗的情况,以最小化配送总成本和最大化客户满意度为目标,构建基于交通流的多模糊时间窗车辆路径模型。根据伊藤算法的基本原理,设计了求解该模型的改进伊藤算法,结合仿真算例进行了模拟计算,并与蚁群算法的计算结果进行了对比分析,结果表明,利用改进伊藤算法求解基于交通流的多模糊时间窗车辆路径问题,迭代次数小,效率更高,能够在较短的时间内收敛到全局最优解,可以有效的求解多模糊时间窗车辆路径问题。

关键词: 交通流, 多模糊时间窗, 伊藤算法, 车辆路径, 顾客满意度

CLC Number:

F253.4

CAO Qing-kui ,YANG Kai-wen, REN Xiang-yang, ZHAO Li-fei. Vehicle Routing Problem with Multiple Fuzzy Time Windows Based on Traffic Flow[J]. Operations Research and Management Science, 2018, 27(8): 20-26.

曹庆奎,杨凯文,任向阳,赵丽飞. 基于交通流的多模糊时间窗车辆路径优化[J]. 运筹与管理, 2018, 27(8): 20-26.

References

[1] Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.
[2] 于洪玲,王洪国,曲建华,孟春华.基于交通流的车辆路径选择优化方法[J].计算机应用研究,2013,30(6):1675-1677.
[3] 曹庆奎,刘新雨,任向阳.基于模拟植物生长算法的车辆调度问题[J].系统工程理论与实践,2015,35(6):1449-1456.
[4] 王旭坪,阮俊虎,孙自来,曹海艳.带回程取货车辆路径问题的干扰恢复模型[J].系统工程学报,2013, 28(5):608-616.
[5] Qureshi A G, Taniguchi E, Yamada T. An exact solution approach for vehicle routing and scheduling problems with soft time windows[J]. Transportation Research Part E Logistics & Transportation Review, 2009, 45(6): 960-977.
[6] Hong L. An improved LNS algorithm for real-time vehicle routing problem with time windows[J]. Computers & Operations Research, 2012, 39(2): 151-163.
[7] 何小锋,马良.带时间窗车辆路径问题的量子蚁群算法[J].系统工程理论与实践,2013,33(5):1255-1261.
[8] Ghannadpour S F, Noori S, Tavakkoli-Moghaddam R, et al. A multi-objective dynamic vehicle routing problem with fuzzy time windows: Model, solution and application[J]. Applied Soft Computing, 2014, 14(1): 504-527.
[9] 孟祥虎,胡蓉,钱斌.求解带时间窗车辆路径问题的有效混合PBIL算法[J].系统工程理论与实践,2014(10):2701-2709.
[10] 彭碧涛,周永务.多时间窗车辆路径问题的混合蚁群算法[J].计算机工程与应用,2010, 46(31):28-31.
[11] 李珍萍,赵菲,刘洪伟.多时间窗车辆路径问题的智能水滴算法[J].运筹与管理,2015,24(6):1-10.
[12] 闫芳,王媛媛.多模糊时间窗车辆路径问题的建模及求解[J].交通运输系统工程与信息,2016,16(6):182-188.
[13] Woensel T V, Kerbache L, Peremans H, et al. Vehicle routing with dynamic travel times: a queueing approach[J]. European Journal of Operational Research, 2008, 186(3): 990-1007.
[14] Stefanie Kritzinger A L. Using traffic information for time-dependent vehicle routing[J]. Procedia-Social and Behavioral Sciences, 2012, 39: 217-229.
[15] Kok A L, Hans E W, Schutten J M J. Vehicle routing under time-dependent travel times:the impact of congestion avoidance[J]. Computers & Operations Research, 2012, 39(5): 910-918.
[16] 李妍峰,李军,高自友.动态规划启发式算法求解时变车辆调度问题[J].系统工程理论与实践,2012,32(8):1712-1718.
[17] 石兆,符卓.时变网络条件下带时间窗的食品冷链配送定位—运输路径优化问题[J].计算机应用研究,2013,30(1):183-188.
[18] 朱婷,王旭磊,赵来军.带时间窗的时变多目标危险化学品道路运输路径优化[J].工业工程,2016,19(2):62-67.
[19] Malandraki C, Daskin M S. Time dependent vehicle routing problem: formulations,properties and heuristic algorithms[J]. Transportation Science, 1992, 26(3): 185-200.
[20] Woensel T V, Kerbache L, Peremans H, et al. Vehicle routing with dynamic travel times: a queueing approach[J]. European Journal of Operational Research, 2008, 186(3): 990-1007.
[21] Donati A V, Montemanni R, Casagrande N, et al. Time dependent vehicle routing problem with a multi ant colony system[J]. European Journal of Operational Research, 2008, 185(3): 1174-1191.
[22] 杨善林,马华伟,顾铁军.时变条件下带时间窗车辆调度问题的模拟退火算法[J].运筹学学报,2010,14(3):83-90.
[23] 朱晓锋,林灼强.基于时变交通流带时间窗的运输调度问题研究[J].中国储运,2014,(3):112-115.
[24] Dey P P, Chandra S, Gangopadhaya S. Speed distribution curves under mixed traffic conditions[J]. Journal of Transportation Engineering, 2006, 132(6): 475-481.
[25] 王祺,李力,胡坚明,邹斌.不同车头间距下交通流的速度分布[J].清华大学学报自然科学版,2011(3):309-312.
[26] 王晨蕾.基于交通流的多车场动态车辆路径问题研究[D].北京:北京交通大学,2016.
[27] 董文永,张文生,于瑞国.求解组合优化问题伊藤算法的收敛性和期望收敛速度分析[J].计算机学报,2011,34(4):636-646.
[28] 易云飞,蔡永乐,董文永,林郭隆.求解带容量约束的车辆路径问题的改进伊藤算法[J].计算机科学,2013,40(5):213-216.
[29] 易云飞,董文永,林晓东,蔡永乐.求解带软时间窗车辆路径问题的改进伊藤算法及其收敛性分析[J].电子学报,2015,43(4):658-664.
[30] 王浩光,余世明.求解车辆路径问题的改进伊藤算法[J].计算机科学,2015,42(9):253-256.
[31] 尹志扬,余世明.求解环境车辆路径问题的多种群伊藤算法[J].计算机科学,2016,43(12):260-263.