A model of low-carbon vehicle routing problem considering road gradient and its solving strategy

RAO Wei-zhen, JIN Chun, WANG Xin-hua, LIU Feng

Systems Engineering - Theory & Practice ›› 2014, Vol. 34 ›› Issue (8) : 2092-2105.

PDF(1764 KB)
中国科学院数学与系统科学研究院期刊网
PDF(1764 KB)
Systems Engineering - Theory & Practice ›› 2014, Vol. 34 ›› Issue (8) : 2092-2105. DOI: 10.12011/1000-6788(2014)8-2092

A model of low-carbon vehicle routing problem considering road gradient and its solving strategy

  • RAO Wei-zhen1, JIN Chun2, WANG Xin-hua1, LIU Feng3
Author information +
History +

Abstract

The classical model of vehicle routing problem (VRP) generally minimizes the distance covered by vehicles, the sum of traveling time or the number of vehicle dispatched, without considering the degree of road gradient. This paper firstly presents a model of energy consumption minimizing low-carbon VRP (ECM-LCVRP) in which road gradient is considered; and secondly the solving complexity of ECM-LCVRP model is analyzed based on classical capacitated vehicle routing problem (CVRP). It is found that ECM-LCVRP is more difficult to solve than CVRP by comparing their solution space and the complexity of 2-opt, or-opt, exchange and swap in their solutions. In order to solve efficiently ECM-LCVRP, a two objective strategy (TOS) is proposed in this paper by summarizing the relation and difference between ECM-LCVRP and CVRP under environment with different degree of road gradient. Finally, 40 ECM-LCVRP instances are devised. Then we use hybrid local search algorithm (HLS) with and without TOS to solve the 40 instances. The experimental results indicate that the TOS can significantly improve the quality of solutions generated by HLS and the performance of TOS is better when the running time is shorter.

Key words

low-carbon logistics / vehicle routing problem / road gradient / energy consumption of vehicle

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
RAO Wei-zhen , JIN Chun , WANG Xin-hua , LIU Feng. A model of low-carbon vehicle routing problem considering road gradient and its solving strategy. Systems Engineering - Theory & Practice, 2014, 34(8): 2092-2105 https://doi.org/10.12011/1000-6788(2014)8-2092

References

[1] Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.
[2] Laporte G. Fifty years of vehicle routing[J]. Transportation Science, 2009, 43(4): 408-416.
[3] 丁秋雷, 胡祥培, 李永先. 求解有时间窗的车辆路径问题的混合蚁群算法[J]. 系统工程理论与实践, 2007, 27(10): 98-104.Ding Qiulei, Hu Xiangpei, Li Yongxian. A hybrid ant colony system for vehicle routing problem with time windows[J]. Systems Engineering——Theory & Practice, 2007, 27(10): 98-104.
[4] 葛显龙, 许茂增, 王伟鑫. 多车型车辆路径问题的量子遗传算法研究[J]. 中国管理科学, 2013, 21(1): 125-133.Ge Xianlong, Xu Maozeng, Wang Weixin. Study on multi-types vehicle routing problem and its quantum genetic algorithm[J]. Chinese Journal of Management Science, 2013, 21(1): 125-133.
[5] Mirabi M, Fatemi Ghomi S M T, Jolai F. Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem[J]. Robotics and Computer-Integrated Manufacturing, 2010, 26(6): 564-569.
[6] 孙国华. 带时间窗的开放式满载车辆路径问题建模及其求解算法[J]. 系统工程理论与实践, 2012, 32(8): 1801-1807.Sun Guohua. Modeling and algorithm for open vehicle routing problem with full-truck loads and time windows[J]. Systems Engineering——Theory & Practice, 2012, 32(8): 1801-1807.
[7] 余明珠, 李建斌, 雷东. 装卸一体化的车辆路径问题及基于插入法的新禁忌算法[J]. 中国管理科学, 2010, 18(2): 89-95.Yu Mingzhu, Li Jianbin, Lei Dong. The research of VRP with pick up and delivery and a new Tabu search based on insertion method[J]. Chinese Journal of Management Science, 2010, 18(2): 89-95.
[8] Hellstrom E, Ivarsson M, Aslund J, et al. Look-ahead control for heavy trucks to minimize trip time and fuel consumption[J]. Control Engineering Practice, 2009, 17(2): 245-254.
[9] Tavares G, Zsigraiova Z, Semiao V, et al. Optimization of MSW collection routes for minimum fuel consumption using 3D GIS modelling[J]. Waste Management, 2009, 29(3): 1176-1185.
[10] Bektas T, Laporte G. The pollution-routing problem[J]. Transportation Research Part B, 2011, 45(8): 1232-1250.
[11] Erdogan S, Miller-Hooks E. A green vehicle routing problem[J]. Transportation Research Part E, 2012, 48(1): 100-114.
[12] Xiao Y Y, Zhao Q H, Kaku I, et al. Development of a fuel consumption optimization model for the capacitated vehicle routing problem[J]. Computers & Operations Research, 2012, 39(7): 1419-1432.
[13] Jabali O, Van W T, Kok A G. Analysis of travel times and CO2 emissions in time-dependent vehicle routing[J]. Production and Operations Management, 2012, 21(6): 1060-1074.
[14] Ross M. Automobile fuel consumption and emissions: Effects of vehicle and driving characteristics[J]. Annual Review of Energy and the Environment, 1994, 19: 75-112.
[15] 邓爱民, 毛超, 周彦霆.带软时间窗的集配货一体化VRP改进模拟退火算法优化研究[J].系统工程理论与实践, 2009, 29(5): 186-192.Deng Aimin, Mao Chao, Zhou Yanting. Optimizing research of an improved simulated annealing algorithm to soft time windows vehicle routing problem with pick-up and delivery[J]. Systems Engineering——Theory & Practice, 2009, 29(5): 186-192.
[16] Kuo Y. Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem[J]. Computers & Industrial Engineering, 2010, 59(4): 157-165.
[17] 傅成红, 符卓. 一种毗邻信息改进的车辆路径问题禁忌搜索算法[J]. 系统工程, 2010, 28(5): 81-84.Fu Chenghong, Fu Zhuo. An improved Tabu search algorithm with adjacent information for capacitated vehicle routing problem[J]. Systems Engineering, 2010, 28(5): 81-84.
[18] 刘志硕, 申金升, 关伟. 车辆路径问题的混合蚁群算法设计与实现[J]. 管理科学学报, 2007, 10(3): 15-22.Liu Zhishuo, Shen Jinsheng, Guan Wei. Design and realization of a hybrid ant colony algorithm for vehicle muting problem[J]. Journal of Management Sciences in China, 2007, 10(3): 15-22.
[19] 潘震东, 唐加福, 韩毅. 带货物权重的车辆路径问题及遗传算法[J]. 管理科学学报, 2007, 10(3): 23-29.Pan Zhendong, Tang Jiafu, Han Yi. Vehicle routing problem with weight coefficients[J]. Journal of Management Sciences in China, 2007, 10(3): 23-29.
[20] Marinakis Y, Marinaki M. A hybrid genetic-particle swarm optimization algorithm for the vehicle routing problem[J]. Expert Systems with Applications, 2010, 37(2): 1446-1455.
[21] Khouadjia M R, Alba E, Jourdan L, et al. Multi-swarm optimization for dynamic combinatorial problems: A case study on dynamic vehicle routing problem[J]. Lecture Notes in Computer Science, 2010, 6234(1): 227-238.
[22] Kytojokia J, Nuortio T, Braysy O, et al. An efficient variable neighborhood search heuristic for very large scale vehicle routing problems[J]. Computers & Operations Research, 2007, 34(9): 2743-2757.
[23] Barth M, Boriboonsomsin K. Real-world CO2 impacts of traffic congestion[J]. Transportation Research Record, 2008, 2058(11): 163-171.
[24] Barth M, Younglove T, Scora G. Development of a heavy-duty diesel modal emissions and fuel consumption model[R]. Technical Report, UC Berkeley: California Partners for Advanced Transit and Highways, San Francisco, 2005.
[25] Carslawa D C, Goodman P S, Lai F C, et al. Comprehensive analysis of the carbon impacts of vehicle intelligent speed control[J]. Atmospheric Environment, 2010, 44(23): 2674-2680.
[26] 中国交通部公路规划设计院. 城镇道路桥梁施工规范[M]. 北京: 中国建筑工业出版社, 2008.CCCC Highway Consultants. Town road and bridge design specifications[M]. Beijing: China Architecture & Building Press, 2008.
[27] Golden B, Wasil J, Kelly I M. Fleet management and logistics[M]. Kluwer Boston, 1998: 33-56.
[28] Renaud J, Boctor F F, Laporte G. An improved petal heuristic for the vehicle routing problem[J]. Journal of the Operational Research Society, 1996, 47(2): 329-336.
[29] 饶卫振, 金淳, 黄英艺. 求解TSP问题的最近邻域与插入混合算法[J]. 系统工程理论与实践, 2011, 31(8): 1419-1428.Rao Weizhen, Jin Chun, Huang Yingyi. Hybrid algorithm of the nearest neighbor and insertion for the traveling salesman problem[J]. Systems Engineering——Theory & Practice, 2011, 31(8): 1419-1428.
PDF(1764 KB)

501

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉