考虑道路坡度因素的低碳VRP问题模型与求解策略

经典车辆路径问题(vehicle routing problem,VRP)模型不考虑道路的坡度,通常以最小化车辆行驶总距离、总耗时或派送车辆数为目标函数.在考虑道路坡度因素的基础上,提出了以配送车辆总能耗最小为目标的低碳车辆路径问题模型(energy consumption minimizing low-carbon VRP,ECM-LCVRP);然后,以带能力约束的车辆路径问题(capacitated VRP,CVRP)为参照,分析了ECM-LCVRP的解空间大小及基本算法改进法则在ECM-LCVRP中的执行复杂度,发现ECMLCVRP较CVRP更加难以求解,并且分析了不同坡度下ECM-LCVRP和CVRP的区别与联系;另外,基于配送方案的能耗值与行驶距离正相关的规律,提出了求解不同道路坡度环境下ECMLCVRP的双目标策略(two objective strategy,TOS);最后,设计了40个ECM-LCVRP算例,并采用综合了算法基本改进规则的混合局部搜索算法(hybrid local search,HLS)和HLS+TOS两种方式求解,求解结果表明:在不同的运算时间内,TOS策略均能够有效地提高HLS的求解质量,且求解时间越短,TOS的效果越明显.