Abstract: 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 two-phase model and algorithm was verified through testing standard case library and cigarette distribution in Jinan and comparing with other approaches.

Key words: order quantity change, change cost, pre-optimize, real-time adjustment, best fit decreasing insert algorithm, vehicle routing problem

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

关键词: 订货量变化, 变动成本, 预优化, 实时调整, 降序最佳适应插入算法, 车辆路径问题