基于碳排放与速度优化的带时间窗车辆路径问题  

Vehicle routing problem with time windows based on carbon emissions and speed optimization

作　　者：李进[1,2] 张江华[3] 

机构地区：[1]浙江工商大学计算机与信息工程学院,杭州310018 [2]浙江工商大学现代商贸研究中心,杭州310018 [3]山东大学管理学院,济南250100

出　　处：《系统工程理论与实践》2014年第12期3063-3072,共10页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(71302035;71171178);教育部人文社科项目(12YJC630091);浙江省自然科学基金(Z14G020001;LQ12G02007);浙江工商大学青年人才基金(QY13-23)

摘　　要：研究了考虑碳排放和速度优化的带时间窗车辆路径问题,引相入了基于速度的碳排放计算方法,以油耗、碳排放和旅行时间费用最小化为目标,将速度作为决策变量,建立了混合整数规划模型.提出了两阶段启发式算法,第一阶段采用改进的禁忌搜索算法优化配送网络中的速度,第二阶段设计了弧段速度优化算法用于优化路径弧段上的速度以寻求对最优解的进一步改进.数值实验分析表明:①两阶段启发式算法能快速有效地找到满意解;②采用优化速度的路径安排比固定速度的路径安排能减少更多的碳排放和总费用;③碳排放和旅行时间之间存在替换关系,减少碳排放会导致旅行时间的增加;④传统的车辆路径安排中存在很大的碳排放改进空间,由于油耗和碳排放是相关的,减少碳排放有利于节约总费用.A vehicle routing problem with time windows considering carbon emissions and speed opti- mization is studied. By introducing a speed-based calculation method of carbon emissions, a mixed integer programming model is built, in which the fuel, carbon emissions and travel time costs are minimized and the speed is treated as a decision variable. Then, a two-phase heuristic algorithm is proposed. In the first phase, a modified tabu search algorithm is adopted to optimize the speed in the distribution network, and in the second phase, an arc speed optimization algorithm is designed to optimize the speed on the path arcs for searching further improvement of the optimal solution. Experimental results show the following meanings： ① This two-phase heuristic algorithm is fast and effective to search the satisfactory solutions.② The speed optimization routing arrangement can reduce more carbon emissions and total costs than fixed speed routing arrangement. ③ There exists trade-off relationship between carbon emissions and travel times. A reduction in emissions will result in an increase in travel time. ④ There is a lot of potential room for improving the carbon emissions in the traditional vehicle routing problem. As fuel consumption is correlated with carbon emissions, reducing emissions is beneficial to save the total costs.

关 键 词：带时间窗车辆路径问题 碳排放 速度优化 启发式算法 

分 类 号：N945.12[自然科学总论—系统科学] TP391.9[自动化与计算机技术—计算机应用技术]