摘要：研究了逆向需求动态出现的混合集散货物路线问题。将问题的求解过程分为静态和动态两阶段，每阶段分别用记录更新算法求解。记录更新法中采用随机大邻域搜索法及重起和扰动策略来提高解的质量，并通过约束邻域搜索范围和设计常量可行性检查两种策略来减少计算时间。通过算例表明了该算法的有效性，同时也表明将动态出现的逆向需求实时整合到已有路线中，比为动态需求单独安排配送更为经济。

关键词：调度；车辆路径问题；动态需求；记录更新法；插入法；大邻域搜索

1 引言

       在快递业务中，为提高对客户的反应速度，经常会遇到逆向需求动态出现的混合集散货物路线问题。通信技术的快速发展，为车辆实时调度的实现提供了技术保障。

已有集散货物路线问题的研究可分为三类：①先送货再集货的集散货物路线问题（vehicle routing problem with backhauls and time windows，VRPBTW）；②混合送货和集货的集散车辆路线问题（mixed vehicle routing problem with backhauls and time windows，MVRPBTW）；③同时集散货物的路线问题（vehicle routing problems with simultaneousdeliveries and pickups，VRPSDP）。第③类研究一般不考虑客户服务的时间窗，以降低成本为目标；第①类和第②类的区别在于第①类要求必须先把货物配送完再集货，第②类允许边送货边集货。每类问题均有其现实应用，本文仅以第②集散货物路线问题为研究对象。