考虑变动成本的车辆路径问题建模及求解

Modeling and solving vehicle routing problem with changing cost

为满足实际配送中变化的客户订货量,同时控制方案实时调整对配送效率及成本产生的影响,提出变动成本的概念,引入预优化策略,建立了带变动限制的随订货量变化实时调整的车辆路径问题的两阶段数学模型,并设计了一种两阶段求解算法。采用粒子群算法求解预优化阶段模型,采用改进的装箱问题降序最佳适应插入算法求解实时调整阶段模型。通过对标准算例库和济南卷烟配送的实例测试及与其他优化方法的比较,验证了两阶段模型和算法的有效性。

To meet the changed customers＇ order quantities in actual distribution and to control the effect of real time scheme adjustment on distribution efficiency and cost, the concept of change cost was proposed, and a two-stage mathematical model of the vehicle routing problem with change restriction of ordering quantity real-time adjustment was presented by introducing the pre-optimizing strategy. A two-phase solving algorithm was also designed. Particle swarm optimization was applied to solve the model of pre-optimizing phase, and a modified best fit decreasing insert algorithm from bin packing problem was used to calculate real-time adjusting phase model. The effectiveness of twc~ phase model and algorithm was verified through testing standard case library and cigarette distribution in Jinan and comparing with other approaches.