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

研究了考虑碳排放和速度优化的带时间窗车辆路径问题,引入了基于速度的碳排放计算方法,以油耗、碳排旅行时间费用最小化为目标,将速度作为决策变量,建立了混合整数规划模型. 提出了两阶段启发式算法,第一阶段采用改进的禁忌搜索算法优化配送网络中的速度,第二阶段设计了弧段速度优化算法用于优化路径弧段上的速寻求对最优解的进一步改进. 数值实验分析表明: ①两阶段启发式算法能快速有效地找到满意解; ②采用优度的路径安排比固定速度的路径安排能减少更多的碳排放和总费用; ③碳排放和旅行时间之间存在替换关系,减少碳排放会导致旅行时间的增加; ④传统的车辆路径安排中存在很大的碳排放改进空间,由于油耗和碳排放是相关的,减少碳排放有利于节约总费用.

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

A vehicle routing problem with time windows considering carbon emissions and speed optimization 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.