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

• 作者: 师欣欣 陈树国 马弘 邓明荣
• 来源期刊: 计算机工程与科学
• 关键词: 电动汽车 车辆路径 时空网络 分支定价算法
• 年，卷（期）: 2021,（6）
• 所属期刊栏目: 人工智能与数据挖掘
• 页码范围: 1121-1130
• 页数: 10页
• 分类号: F540.82
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2021.06.023

摘要

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