考虑交通拥堵及工作量平衡性的一致性车辆路径问题

刘恒宇; 汝宜红

doi:10.3969/j.issn.0258-2724.2016.05.016

考虑交通拥堵及工作量平衡性的一致性车辆路径问题

doi: 10.3969/j.issn.0258-2724.2016.05.016

刘恒宇,
汝宜红^,

基金项目:

云南省教育厅课题（SYSX201412）

北京市科委课题（Z141100003614059）

详细信息

作者简介:
刘恒宇(1990-),男,博士研究生,研究方向为城市物流,E-mail:14113138@bjtu.edu.cn

通讯作者:
汝宜红(1953-),女,教授,博士生导师,研究方向为逆向物流,E-mail:yhru@bjtu.edu.cn

计量
- 文章访问数: 610
- HTML全文浏览量: 77
- PDF下载量: 206
- 被引次数: 0
出版历程
- 收稿日期: 2015-09-07
- 刊出日期: 2016-10-25

Consistent Vehicle Routing Problem Considering Traffic Congestion and Workload Balance

LIU Hengyu,
RU Yihong^,

摘要

摘要: 为研究快递公司在提供一致性配送服务时，交通拥堵以及快递人员工作量平衡性因素对配送路径的影响，在传统车辆路径问题研究的基础上，提出了考虑拥堵和工作量的一致性车辆路径问题，并构建了混合整数规划模型。针对该模型的NP难性质，提出了基于模板路径的两阶段模拟退火算法（template-based simulated annealing heuristic，TSA）。该算法通过构建模板路径求解初始路径方案，再利用模拟退火算法优化路径方案，降低车辆总行驶时间。将该模型和算法应用于3组基准数据（benchmark data set）的数值实验，结果表明：本文模型和算法能有效解决此类问题，交通拥堵使最优配送路径的总行驶时间平均增加18.38%，使快递人员在任意两天到达同一顾客的最早与最晚时刻之差平均增加12.92%；当快递人员配件量的不平衡性平均下降35.82%后，二者仅分别平均增加2.29%和1.68%。
- 一致性车辆路径问题 /
- 快递业 /
- 交通拥堵 /
- 工作量平衡性
Abstract: In order to investigate the effects of transportation congestion and workload balance on the delivery routing of express delivery companies which wish to provide consistent services, a consistent vehicle routing problem considering traffic congestion and workload balance was proposed and a mixed integer programming model for this problem was constructed. In view of the model' s NP-hard property, a two-phase template-based simulated annealing method (TSA) was applied to solve this problem. The TSA attains an initial route plan by constructing template routes first, and then optimizes them using the simulated annealing method to decrease the total travel time. To verify the validity of the proposed model and algorithm, numerical experiments were conducted using three benchmark data sets. Results show that the model and TSA can solve this problem effectively. The traffic congestion will significantly increase the total travel time by an average of 18.38% and increase the difference between the earliest and latest arrival time at the same customer within any two days by an average of 12.92%. Besides, when the average difference of the delivery men's shipment quantity decreases by 35.82%, the total travel time and the difference between the earliest and latest arrival time at the same customer are only increased by 2.29% and 1.68%, respectively.
- consistent vehicle routing problem /
- express delivery industry /
- traffic congestion /
- workload balance

HTML全文

参考文献(21)

DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6: 80-91.

NAGY G, WASSAN N A, SPERANZA M G, et al. The vehicle routing problem with divisible deliveries and pickups[J]. Transportation Science, 2015, 49(2): 271-294.

邹书蓉,黄晓滨,张宏伟. 有容量约束车辆路径问题的多目标遗传算法[J]. 西南交通大学学报,2009,44(5): 782-786.

SCHNEIDER M, STENGER A, GOEKE D. The electric vehicle routing problem with time windows and recharging stations[J]. Transportation Science, 2014, 48(4): 500-520.

LAPORTE G. Fifty years of vehicle routing[J]. Transportation Science, 2009, 43(4): 408-416.

王雅琪,杨雪梅. 电子商务与快递业融合发展的动力机制研究[J]. 物流工程与管理,2015,37(1): 150-151.

KOVACS A A, PARRAGH S N, HARTL R F. A template-based adaptive large neighborhood search for the consistent vehicle routing problem[J]. Networks, 2014, 63(1): 60-81.

GROER C, Golden B, WASIL E. The consistent vehicle routing problem[J]. Manufacturing Service and Operations Management, 2009, 11(4): 630-643.

WOODWARD C A, ABELSON J, TEDFORD S, et al. What is important to continuity in home care? perspectives of key stakeholders[J]. Social Science and Medicine, 2004, 58(1): 177-192.

FEILLET D, GARAIX T, LEHUEDE F, et al. A new consistent vehicle routing problem for the transportation of people with disabilities[J]. Networks, 2014, 63(3): 211-224.

TARANTILIS C D, STAVROPOULOU F, REPOUSSIS P P. A template-based tabu search algorithm for the consistent vehicle routing problem[J]. Expert Systems with Applications, 2012, 39(4): 4233-4239.

GOLDEN B L, KOVACS A A, HARTL R F, et al. The generalized consistent vehicle routing problem[J]. Transportation Science, 2015, 49(4): 796-816.

LUO Z X, QIN H, CHE C H, et al. On service consistency in multi-period vehicle routing[J]. European Journal of Operational Research, 2015, 243(3): 731-744.

JANSSENS J, DEN BERGH J V, SORENSEN K, et al. Multi-objective microzone-based vehicle routing for courier companies: From tactical to operational planning[J]. European Journal of Operational Research, 2015, 242: 222-231.

北京交通发展研究中心. 北京市2010年交通运行报告[R]. 北京:北京交通发展研究中心,2011.

FIGLIOZZI M A. The impacts of congestion on commercial vehicle tour characteristics and costs[J]. Transportation Research Part E, 2010, 46: 496-506.

TAN T F, NETSSINE S. When does the devil make work? an empirical study of the impact of workload on worker productivity[J]. Management Science, 2014, 60(6): 1574-1593.

SOYSAL M, BLOEMHOF-RUWAARD J M, BEKTAS T. The time-dependent two-echelon capacitated vehicle routing problem with environmental considerations[J]. International Journal of Production Economics, 2015, 164: 366-378.

KOK A L, HANS E W, SCHUTTEN J M J. Vehicle routing under time-dependent travel times: the impact of congestion avoidance[J]. Computers and Operations Research, 2012, 39: 910-918.

JANSSENS J, DEN BERGH J V, SORENSEN K, et al. Multi-objective microzone-based vehicle routing for courier companies: from tactical to operational planning[J]. European Journal of Operational Research, 2015, 242: 222-231.

YU V F, LIN S Y. A simulated annealing heuristic for the open location-routing problem[J]. Computers and Operations Research, 2015, 62: 184-196.

施引文献

附加材料(0)

访问统计