考虑油耗的车辆调度问题模型与算法

工业工程 ›› 2015, Vol. 18 ›› Issue (5): 134-140.

考虑油耗的车辆调度问题模型与算法

（上海交通大学机械与动力工程学院，上海 200240）

出版日期:2015-10-31 发布日期:2016-03-24
作者简介:任盼（1990-），男，河南省人，硕士研究生，主要研究方向为组合优化、物流与供应链.
基金资助:
国家自然科学基金资助项目(71302013)；高等学校博士学科点专项科研基金项目(20130073120047)；上海市浦江人才计划项目(13PJC075)；上海市自然科学基金资助项目(13ZR1456400)

Model and Algorithm for Fuel Consumption-Vehicle Routing Problem with Time Windows

(School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China)

Online:2015-10-31 Published:2016-03-24

摘要/Abstract

摘要： 针对目前运输行业中能源消耗已经成为影响社会环境和运行成本的重要因素这一实际，在分析汽车行驶油耗规律和定量描述的基础上，引入考虑能源消耗的车辆调度问题，考虑了车辆运行能耗目标以及客户的需求时间窗等约束，建立问题的精确数学模型。由于问题具有NPhard性质，为了求解实际大规模此类问题而设计了一种新型禁忌搜索算法。该算法引入大规模邻域搜索思想，并提出基于虚拟车辆的新型搜索邻域。通过算例试验验证了算法的有效性。

关键词: 油耗率, 车辆调度, 时间窗, 禁忌搜索

Abstract: with time windows is discussed. Based on fuel consumption rules analysis and quantitative description, an accurate mathematical model is built by considering the fuel consumption objective and constraints such as time windows. For the NPhard character of vehicle routing problem, a modified tabu search algorithm is designed to solve large scale such problem. The new algorithm introduces the large neighborhood theory and proposes a new kind neighborhood based on virtual vehicle. The validity of the new algorithm has been verified by computational study. 

Key words: fuel consumption rate, vehicle routing, time windows, tabu search

任盼，刘冉，江志斌，董蕊. 考虑油耗的车辆调度问题模型与算法[J]. 工业工程, 2015, 18(5): 134-140.

Ren Pan, Liu Ran, Jiang Zhi-bin, Dong Rui. Model and Algorithm for Fuel Consumption-Vehicle Routing Problem with Time Windows [J]. Industrial Engineering Journal , 2015, 18(5): 134-140.

参考文献

［1］Sahin B, Yilmaz H, Ust Y, et al. An approach for analyzing transportation costs and a case study［J］. European Journal of Operational Research, 2009, 193(1):1-11. ［2］ Tan K C, Lee L H, Zhu Q L, et al. Heuristic methods for vehicle routing problem with time windows ［J］. Artificial Intelligence in Engineering,2001,15（3）: 281-295.  ［3］ Barrie M, Baker, Ayechew M A. A genetic algorithm for the vehicle routing problem ［J］. Computers & Operations Research, 2003,30(5):787-800.  ［4］ Stefan Ropke, Pisinger David. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows ［J］. Transportation Science, 2006,40(4):455-472.  ［5］ Ibaraki T, Imahori S, Kubo M, et al. Effective local search algorithms for routing and scheduling problems with general timewindows constraints ［J］. Transportation Science, 2005,39(2):206-232.  ［6］ Jean-Fran-ois C-Ao^U2té, JeanYves Potvin. A tabu search heuristic for the vehicle routing problem with private fleet and common carrier ［J］. European Journal of Operational Research,2009,198(2):464-469.  ［7］ Cordeau JF, Laporte G, Mercier A. A unified tabu search heuristic for vehicle routing problems with time windows ［J］. Journal of the Operational Research Society,2001,52(8): 928936. ［8］ Cordeau J F, Gendreau M, Laporte G. A tabu search heuristic for periodic and multidepot vehicle routing problems ［J］. Networks,1997, 30(2): 105-119. ［9］ Xiao Yi-yong, Zhao Qiuhong, Ikou Kaku, et al. Development of a fuel consumption optimization model for the capacitated vehicle routing problem ［J］. Computers & Operations Research,2012, 39(7):1419-1431. ［10］ Lim Andrew. The single vehicle routing problem with toll-by-weight scheme: A branch-and-bound approach ［J］. European Journal of Operational Research, 2012,220(2): 295-304. ［11］ Tang Jia-fu, Zhang Jun, Pan Zhen-dong. A scatter search algorithm for solving vehicle routing problem with loading cost ［J］. Expert Systems with Applications, 2010,37(6): 4073-4083. ［12］ Marius M, Solomon. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints ［J］. Operations Research,1987,35(2):254-265.  ［13］ Taillard é, Badeau P, Gendreau M, et al. A tabu search heuristic for the vehicle routing problem with soft time windows ［J］. Transportation Science, 1997,31(2):170-86.  ［14］ Alvarenga G B, Mateus G R, deTomi G. A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows ［J］. Computers & Operations Research, 2007,34(6): 1561-1584.  ［15］ Gehring H, Homberger J. A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows ［C］. Proceedings of Eurogn99. Berlin: Springer, 1999: 57-64.

[1]	闫军, 常乐, 王璐璐, 赵彤. 带时间窗的同时取送货车辆路径问题求解算法[J]. 工业工程, 2021, 24(5): 72-76.
[2]	王宁, 张玉萍, 赵姣, 金子阳. 考虑碳排放及时间窗的LIRP模型与算法研究[J]. 工业工程, 2021, 24(2): 34-42.
[3]	李玉民, 邱梦, 黑柏林, 方曾利. 考虑高铁时间窗和客户满意度的生鲜品公铁联运路径选择[J]. 工业工程, 2021, 24(2): 49-56.
[4]	吴斌, 宋琰, 程晶, 董敏. 基于密度峰值聚类的VRPTW问题研究[J]. 工业工程, 2020, 23(5): 58-66,74.
[5]	李博威, 户佐安, 贾叶子, 唐诗韵. 带软时间窗的同时取送货车辆路径问题研究[J]. 工业工程, 2020, 23(5): 75-81.
[6]	王泽, 杨信丰, 刘兰芬. 考虑电量消耗的车辆调度优化研究[J]. 工业工程, 2020, 23(4): 140-147.
[7]	张巍, 李鹏翔, 仝自强, 岳毅蒙. 基于损坏车辆分布预测与损益阈值分析下的共享单车回收研究[J]. 工业工程, 2020, 23(3): 132-137.
[8]	朱辉, 杨立乾, 赵金楼. 基于优先规则的船舶分段空间调度算法[J]. 工业工程, 2020, 23(2): 76-82.
[9]	姚冠新, 朱晨俊, 戴盼倩. 混合轴辐式城乡一体化物流网络构建研究[J]. 工业工程, 2019, 22(6): 1-7.
[10]	芦娟, 夏扬坤, 邹安全, 符卓, 王松, 魏占国, 符瑛. 带装载能力的需求依背包拆分车辆路径问题[J]. 工业工程, 2019, 22(6): 67-73.
[11]	于之靖, 王科平, 郑建文, 陶永奎, 李鑫, 刘志东. 改进TS算法的助航灯光站人员管理优化方法[J]. 工业工程, 2019, 22(4): 1-6,48.
[12]	冯春, 秦冰芳, 叶露. 共享电动车电池配送问题研究[J]. 工业工程, 2019, 22(3): 52-56.
[13]	户佐安, 贾叶子, 李博威, 刘陆. 考虑客户满意度的车辆路径优化研究[J]. 工业工程, 2019, 22(1): 100-107.
[14]	刘兰芬, 杨信丰. 时间依赖网络城市物流车辆调度的模型及算法[J]. 工业工程, 2017, 20(4): 18-24.
[15]	王维军, 罗伟. 基于改进智能水滴算法的冷链物流配送路径优化问题研究[J]. 工业工程, 2017, 20(2): 38-43.