dcvrp专题

【DCVRP】元启发式算法进一步优化

为什么加入元启发式算法? DCVRP-IMGR的求解质量可以快速的达到10%之内,但在DCVRP_IMGR生成方案完成后至下一个动态事件发生之间存在一段时间,当动态事件发生的非常频繁,这段时间可能会非常短暂,然而动态事件发生得不是太频繁或者存在2个动态事件时间较长的情况下(这在实际配送中是比较常见的),这段时间的长度可能就足够采用更复杂的元启发式算法,以进一步改进DCVRP-IMGR生成的方案。

【D-DCVRP】求解DCVRP改进贪婪算法(三)

一、Held-Harp模型 海尔德和卡尔普在1970年提出景点模型,用于求解TSP问题的最优解下界· 该模型同样可以用于DCVRP问题,既有定理1成立。 定理1:根据Held-Karp模型使用向量 π = ( 0 , π 1 , π 2 , ⋯   , π n ) \pi=(0,\pi_1,\pi_2,\cdots,\pi_n) π=(0,π1​,π2​,⋯,πn​)改造DCVRP问题中1