时效要求下的甩挂牵引车调度问题与求解

李红启; 赵文聪; 李嫣然

doi:10.19818/j.cnki.1671-1637.2016.05.011

时效要求下的甩挂牵引车调度问题与求解

doi: 10.19818/j.cnki.1671-1637.2016.05.011

1.
北京航空航天大学交通科学与工程学院, 北京 100191
2.
北京华运交通咨询开发公司, 北京 100038

基金项目:

国家自然科学基金项目 71202016

详细信息

作者简介:
李红启(1977-), 男, 山东平度人, 北京航空航天大学讲师, 工学博士, 从事物流与供应链管理优化研究

中图分类号: U492.22
计量
- 文章访问数: 2122
- HTML全文浏览量: 129
- PDF下载量: 1896
- 被引次数: 0
出版历程
- 收稿日期: 2015-12-11
- 刊出日期: 2016-10-25

Trailer pick-up tractor routing problem with timeliness requirement and solving

1.
School of Transportation Science and Engineering, Beihang University, Beijing 100191, China
2.
Beijing Huayun Traffic Consulting and Development Corporation, Beijing 100038, China

More Information

Author Bio:
LI Hong-qi(1977-), male, lecturer, PhD, +86-10-82339923, lihongqi@buaa.edu.cn

Article Text (Baidu Translation)

摘要

摘要: 针对时效要求下的甩挂牵引车调度问题, 以整车运输和多对多运输需求为基本特征, 以货运吨公里CO_2排放量为目标函数, 构建了混合整数规划模型, 设计了基于节约算法和邻域搜索算法的两阶段启发式算法, 进行了带有时间窗的既有算例的求解。计算结果表明: 启发式算法所得满意解对基准算例1~12初始解的优化率分别为4.21%、2.06%、2.70%、3.87%、2.03%、3.54%、2.23%、3.35%、1.54%、2.11%、1.58%、0.81%, 平均水平为2.50%;最优解分别为101.22、107.05、106.21、103.94、116.23、103.16、102.61、102.14、101.05、103.38、103.69、100.54g·(t·km)-1, 平均值为104.27g·(t·km)^-1, 因此, 本文所构建的混合整数规划模型与启发式算法是可行和有效的, 时效要求下的甩挂牵引车调度优化可产生良好的节能减排效果。
- 公路运输 /
- 甩挂牵引车调度 /
- 节约算法 /
- 甩挂运输 /
- 时间窗
Abstract: Aiming at trailer pick-up tractor routing problem with timeliness requirement, fulltruck load transportation and many to many transportation demand were taken as basic characteristics, CO_2 emissions per ton-kilometer of freight transportation was taken as objective function, and a mixed integer programming model was built.A two-stage heuristic algorithm was designed based on saving algorithm and local search algorithm, and some known instances with time windows were solved.Calculation result shows that compared to the initial solutions of benchmark instances 1-12, the optimization rates of satisfactory solutions are 4.21%, 2.06%, 2.70%, 3.87%, 2.03%, 3.54%, 2.23%, 3.35%, 1.54%, 2.11%, 1.58%, and 0.81%respectively, and the average level is 2.50%, the optimum solutions are 101.22, 107.05, 106.21, 103.94, 116.23, 103.16, 102.61, 102.14, 101.05, 103.38, 103.69, and 100.54g·(t·km)-1respectively, and the average value is 104.27 g·(t·km)^-1.Obviously, the mixed integer programming model and the heuristic algorithm are feasible and effective, and the optimization of trailer pick-up tractor routing with prescription requirement can produce good energy saving and emission reduction effect.
- highway transportation /
- trailer pick-up tractor routing /
- saving algorithm /
- trailer pick-up transportation /
- time window

HTML全文

图 1 牵引车路线示例

Figure 1. Tractor route example

下载: 全尺寸图片幻灯片

图 2 基准算例1的节点分布与时间窗

Figure 2. Distribution and time windows of nodes for benchmark instance 1

下载: 全尺寸图片幻灯片

图 3 基准算例5的节点分布与时间窗

Figure 3. Distribution and time windows of nodes for benchmark instance 5

下载: 全尺寸图片幻灯片

图 4 基准算例6的节点分布与时间窗

Figure 4. Distribution and time windows of nodes for benchmark instance 6

下载: 全尺寸图片幻灯片

表 1 牵引车基本参数

Table 1. Basic parameters of tractor

下载: 导出CSV

表 2 基准算例的计算结果

Table 2. Calculation results of benchmark instances

下载: 导出CSV

参考文献(28)

[1]	LAPORTE G. Fifty years of vehicle routing[J]. Transportation Science, 2009, 43(4): 408-416. doi: 10.1287/trsc.1090.0301
[2]	BALDACCI R, TOTH P, VIGO D. Recent advances in vehicle routing exact algorithms[J]. 4OR: A Quarterly Journal of Operations Research, 2007, 5(4): 269-298. doi: 10.1007/s10288-007-0063-3
[3]	DREXL M. Applications of the vehicle routing problem with trailers and transshipments[J]. European Journal of Operational Research, 2013, 227(2): 275-283. doi: 10.1016/j.ejor.2012.12.015
[4]	TAN K C, CHEW Y H, LEE L H. A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems[J]. European Journal of Operational Research, 2006, 172(3): 855-885. doi: 10.1016/j.ejor.2004.11.019
[5]	SCHEUERER S. A tabu search heuristic for the truck and trailer routing problem[J]. Computers and Operations Research, 2006, 33(4): 894-909. doi: 10.1016/j.cor.2004.08.002
[6]	LIN S W, YU V F, CHOU S Y. Solving the truck and trailer routing problem based on a simulated annealing heuristic[J]. Computers and Operations Research, 2009, 36(5): 1683-1692. doi: 10.1016/j.cor.2008.04.005
[7]	LI Hong-qi, LU Tan, LU Ying-rong. The combination truck routing problem: a survey[J]. Procedia Engineering, 2016, 137: 639-648. doi: 10.1016/j.proeng.2016.01.301
[8]	李红启, 吕潭. 汽车列车调度问题研究综述[J]. 大连海事大学学报: 社会科学版, 2015, 14(6): 1-10. doi: 10.3969/j.issn.1671-7031.2015.06.001 LI Hong-qi, LU Tan. Research summary of vehicles combination routing problem[J]. Journal of Dalian Maritime University: Social Sciences Edition, 2015, 14(6): 1-10. (in Chinese). doi: 10.3969/j.issn.1671-7031.2015.06.001
[9]	SEMET F, TAILLARD E. Solving real-life vehicle routing problems efficiently using tabu search[J]. Annals of Operations Research, 1993, 41(4): 469-488. doi: 10.1007/BF02023006
[10]	GERDESSEN J C. Vehicle routing problem with trailers[J]. European Journal of Operational Research, 1996, 93(1): 135-147. doi: 10.1016/0377-2217(95)00175-1
[11]	CHAO I M. A tabu search method for the truck and trailer routing problem[J]. Computers and Operations Research, 2002, 29(1): 33-51. doi: 10.1016/S0305-0548(00)00056-3
[12]	LIN S W, YU V F, CHOU S Y. A note on the truck and trailer routing problem[J]. Expert Systems with Applications, 2010, 37(1): 899-903. doi: 10.1016/j.eswa.2009.06.077
[13]	LIN S W, YU V F, LU C C. A simulated annealing heuristic for the truck and trailer routing problem with time windows[J]. Expert Systems with Applications, 2011, 38(12): 15244-15252. doi: 10.1016/j.eswa.2011.05.075
[14]	DERIGS U, PULLMANN M, VOGEL U. Truck and trailer routing-problems, heuristics and computational experience[J]. Computers and Operations Research, 2013, 40(2): 536-546. doi: 10.1016/j.cor.2012.08.007
[15]	DE MEULEMEESTER L, LAPORTE G, LOUVEAUX F V, et al. Optimal sequencing of skip collections and deliveries[J]. The Journal of the Operational Research Society, 1997, 48(1): 57-64. doi: 10.1057/palgrave.jors.2600325
[16]	BODIN L, MINGOZZI A, BALDACCI R, et al. The rollonrolloff vehicle routing problem[J]. Transportation Science, 2000, 34(3): 271-288. doi: 10.1287/trsc.34.3.271.12301
[17]	WY J, KIM B I, KIM S. The rollon-rolloff waste collection vehicle routing problem with time windows[J]. European Journal of Operational Research, 2013, 224(3): 466-476. doi: 10.1016/j.ejor.2012.09.001
[18]	BALDACCI R, BODIN L, MINGOZZI A. The multiple disposal facilities and multiple inventory locations rollonrolloff vehicle routing problem[J]. Computers and Operations Research, 2006, 33(9): 2667-2702.
[19]	范林强. 汽车甩挂运输组织模式选择问题研究[D]. 成都: 西南交通大学, 2013. FAN Lin-qiang. Study on the choice of organization modes of semi-trailer swap transportation[D]. Chengdu: Southweat Jiaotong University, 2013. (in Chinese).
[20]	张磊磊. LPG循环甩挂运输调度优化研究[D]. 大连: 大连海事大学, 2013. ZHANG Lei-lei. Research on LPG cycle drop and pull transport optimization scheduling[D]. Dalian: Dalian Martime University, 2013. (in Chinese).
[21]	范宁宁. 烟大滚装甩挂运输牵引车调度优化研究[D]. 大连: 大连海事大学, 2012. FAN Ning-ning. Research on tractor optimization scheduling of rollon left-hanging transportation from Yantai to Dalian[D]. Dalian: Dalian Martime University, 2012. (in Chinese).
[22]	LI Hong-qi, LU Tan, LI Yan-ran. The tractor and semitrailer routing problem with many-to-many demand considering carbon dioxide emissions[J]. Transportation Research Part D: Transport and Environment, 2015, 34: 68-82. doi: 10.1016/j.trd.2014.10.004
[23]	LI Hong-qi, LI Yan-ran, LU Yue, et al. The effects of the tractor and semitrailer routing problem on mitigation of carbon dioxide emissions[J]. Discrete Dynamics in Nature and Society, 2013, 2013: 1-14.
[24]	LI Hong-qi, LI Yan-ran, ZHAO Qiu-hong, et al. The tractor and semitrailer routing considering carbon dioxide emissions[J]. Mathematical Problems in Engineering, 2013, 2013: 1-12.
[25]	SOLOMON M M, DESROSIERS J. Survey paper-time window costrained routing and scheduling problems[J]. Transportation Science, 1988, 22(1): 1-13.
[26]	ERDOGAN S, MILLER-HOOKS E. A green vehicle routing problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2012, 48(1): 100-114.
[27]	CHU C W. A heuristic algorithm for the truckload and lessthan-truckload problem[J]. European Journal of Operational Research, 2005, 165(3): 657-667.
[28]	LAI M, CRAINIC T G, FRANCESCO M D, et al. An heuristic search for the routing of heterogeneous trucks with single and double container loads[J]. Transportation Research Part E: Logistics and Transportation Review, 2013, 56: 108-118.