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

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

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

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.