集送货路径的同步优化快速算法

作者：曹剑东; 郑四发; 王建强; 连小珉

来源：清华大学学报(自然科学版)网络.预览, 2008, (08): 1344-1346.

DOI：10.16511/j.cnki.qhdxxb.2008.08.022

• 调度
• 集送货
• 车辆路径问题
• 同步 dispatch
• pickup and delivery
• vehicle routing problem
• synchronous

为提高集送货问题的求解效率,提出一种新的同步优化快速算法,即先以非精确的混合距离矩阵替代里程矩阵为输入进行求解,然后将结果反馈到输入端动态更新混合距离矩阵中对应的元素,以更新的混合距离矩阵为输入再次求解,以此反复迭代,直至满足优化目标。以40个遍布于北京的客户构成的集送货问题为例,用该算法进行了求解,并与传统异步优化算法的优化结果进行对比,结果表明同步优化快速算法能够在精度降低4.92%的情况下,比传统异步算法节省40%的计算时间,适用于实时性要求很高的动态调度。

• 单位
  清华大学; 汽车安全与节能国家重点实验室