主管：中国科学院
主办：中国优选法统筹法与经济数学研究会
　　　中国科学院科技战略咨询研究院
中国管理科学

中国管理科学 ›› 2015, Vol. 23 ›› Issue (10): 98-106.doi: 10.16381/j.cnki.issn1003-207x.2015.10.011

• 论文 • 上一篇    下一篇

低碳环境下的车辆路径问题及禁忌搜索算法研究

李进1,2, 傅培华1, 李修琳1, 张江华3, 朱道立4   

  1. 1. 浙江工商大学计算机与信息工程学院, 杭州 310018;
    2. 浙江工商大学现代商贸研究中心, 杭州 310018;
    3. 山东大学管理学院, 济南 250100;
    4. 上海交通大学安泰经济与管理学院, 上海 200052
  • 收稿日期:2013-03-19 修回日期:2014-07-20 出版日期:2015-10-20 发布日期:2015-10-24
  • 作者简介:李进(1980-),男(汉族),江苏人,浙江工商大学,副教授,研究方向:绿色物流、智能算法.
  • 基金资助:

    国家自然科学基金资助青年项目(71302035);浙江省自然科学基金资助项目(LZ14G02001,LQ14E050001);教育部人文社科项目(12YJC630091);浙江工商大学青年人才基金资助项目(QY13-23)

Study on Vehicle Routing Problem and Tabu Search Algorithmunder Low-carbon Environment

LI Jin1,2, FU Pei-hua1, LI Xiu-lin1, ZHANG Jiang-hua3, ZHU Dao-li4   

  1. 1. School of Computer and Information Engineering, Zhejiang Gongshang University, Hangzhou 310018, China;
    2. Contemporary Business and Trade Research Center of Zhejiang Gongshang University, Hang zhou 310018, China;
    3. School of Management, Shandong University, Ji'nan 250100, China;
    4. Antai College of Economics & Management, Shanghai Jiaotong University, Shanghai 200052, China
  • Received:2013-03-19 Revised:2014-07-20 Online:2015-10-20 Published:2015-10-24

PDF (PC)

1726

被引次数

50

摘要： 基于节能减排的新视角,本文研究了低碳环境下由第三方提供运输服务的车辆路径问题,在安排车辆路径时,同时考虑了能耗、碳排放和租车费用,而这些费用不仅与距离有关,也与客户点的需求量和车辆速度有关。提出了考虑车辆运量和速度的能耗计算方法,建立了非满载运输方式下的低碳路径模型——LCRP。设计了基于路径划分的禁忌搜索算法RS-TS对问题进行求解,该算法引入了一种新颖的路径编码与解码算法WSS,采用了三种邻域搜索方法。通过基准测试实例验证了算法能有效地找到满意解,并揭示了距离、能耗、行驶时间等参数之间的关系,实验分析表明采用低碳路径安排更加经济环保且选择中低的交通速度更有利于节约能耗和降低碳排放。

关键词: 低碳环境, 车辆路径问题, 禁忌搜索算法, 能耗, 环保

Abstract: From a new perspective of saving energy and reducing emissions, a vehicle routing problem under low-carbon environment is studied, in which transportation services are provided by a third party. The costs of energy, carbon emissions and vehicle leasing are considered simultaneously, which depend not only on distance, but also on client demands and vehicle speed. An energy consumption calculation method is proposed taking into account the vehicle weight and speed. Using the peddling shipment strategy, a low-carbon routing model named LCRP is built. Then, a tabu search algorithm named RS-TS using routes splitting method is designed to solve this model. This algorithm introduces a novel routes encoding and decoding algorithms named WSS, and adopts three neighborhood search methods. Computational results of benchmark instances verify that this algorithm is effective to search the satisfactory solutions, which also shed light on the tradeoffs of distance, energy, travel time and other parameters. Experimental analysis shows that the low-carbon routing arrangement is more economic and environmentally friendly, and selecting medium or low traffic speed is better to save energy consumption and reduce carbon emissions.

Key words: low-carbon environment, vehicle routing problem, tabu search algorithm, energy consumption, environmental protection

中图分类号: