基于一种新型分支定价算法的电动车支线镇际快递配送路径规划研究

A novel branch and price algorithm for routing electric vehicles in inter-town express package delivery systems

针对由电动汽车支持的支线镇际快递配送系统,提出一类新型的分支定价算法实现对车辆和货物的路径规划。研究利用时空网络将时间离散化构建模型,同时考虑了车辆资源、仓储资源和充电桩资源的管理问题。在分支定价算法中,分支策略和割平面策略的结合有效削弱了时间离散化所带来的对称性问题。强化策略则通过对生成路径变量进行有效筛选,并利用求解器帮助算法快速找到高质量可行解。实验将分支定价算法和商用求解器求解以及基于列生成的启发式算法进行对比,结果表明分支定价算法在精确求解小规模问题和启发求解中等规模问题时都具有明显优势,从而能有效地对该问题进行求解。

This paper proposes a novel branch and price(B&P)algorithm to realize the route planning of vehicles and goods for the inter-town express package delivery system supported by electric vehicles.The time-space network is used to discretize the time to build a mathematical programming model,while the management of vehicle resources,storage resources and charging pile resources are taken into account.In the B&P algorithm,the combination of branch strategy and cutting plane strategy effectively weakens the symmetry problem caused by time discretization.The strengthening strategy effectively filters the generated path variables and uses a solver to help the algorithm quickly find a high-quality feasible solution.The experiment compares the B&P algorithm with commercial solvers and heuristic algorithms based on column generation.It shows that the B&P algorithm has obvious advantages in accurately solving small-scale problems and heuristically solving medium-scale problems,so that it can effectively solve the problems.