Abstract: In response to the current situation of increasingly restricted automobile emissions in cities,the relationship between the load and the fuel consumption of three types of typical distribution vehicles was analyzed,and the multiplicity characteristics of the lowest fuel path in multi-graph network was discussed.The corresponding propositions and the proofs were proposed,thereby,a mixed integer programming model of low-carbon routing problem on multi-graph was formulated.Three sets of decision variables were defined in the model,which corresponded to the path selection of different type of vehicle,the vehicle load and the time reaching the customer.then gives The specific constraints for each group of variables was given,which expanded the Heterogeneous Vehicle Routing Problem (HVRP) model and the Vehicle Routing Problems With Time Windows (VRPTW) model in the low carbon vehicle routing problem.In addition,a set of valid inequalities was proposed according to the model features to speed up the convergence of calculations.The experiments were constructed to verify the effectiveness of model and the acceleration effect of valid inequalities.A reasonable emission could be reduced when multiple paths and multiple types of vehicles were considered simultaneously in distribution planning.

Key words: heterogeneous vehicle routing problem, low-carbon, distribution in cities, multi-graph network, valid inequalities

摘要： 针对城市汽车排放日益受到限制的问题,从分析3类典型物流配送车型装载量与油耗的关系入手,讨论了多通路网络环境下油耗最低通路的多重性特征,提出相应的命题并给出证明,建立了多通路网络下多车型低碳路径优化的混合整数规划模型。模型中定义了3组决策变量,分别对应不同车型的通路选择、车辆装载量和到达客户的时刻,并给出每组变量的具体约束,扩展了低碳车辆路径问题中的多车型车辆路径问题模型和有时间窗车辆路径问题模型;根据模型特征提出一组有效不等式,用于加快计算的收敛。通过算例验证了模型的有效性和有效不等式的加速求解效果,实验结果表明通过采用多种车型与城市多条通路的合理搭配,可以明显降低配送路径规划的整体车辆油耗。

关键词: 多车型车辆路径问题, 低碳, 城市配送, 多通路网络, 有效不等式