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

Fast synchronous optimization algorithm for pickup and delivery route

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

A fast synchronous optimization algorithm was developed to improve the calculational efficiency of solution for the cargo pickup and delivery problem. A non-accurate hybrid distance matrix was used as the input instead of the mileage matrix, with the result then fed back to the input to iteratively update hybrid distance matrix until the optimization target is achieved. Calculations for a pickup and delivery route with 40 customers in Beijing show that the fast synchronous optimization algorithm is 40% faster with only a 4.92% reduction accuracy than the traditional asynchronous optimization algorithm. Thus the algorithm is suitable for dynamic dispatching in real-time.