蒋华伟 郭 陶 杨 震 赵丽科

(粮食信息处理与控制教育部重点实验室(河南工业大学) 郑州 450001)

(河南工业大学信息科学与工程学院 郑州 450001)

1 引言

自然灾害及重大公共卫生事件的发生会严重威胁人们的生命财产安全，并对社会生产造成不利影响[1]。为最大限度降低灾害带来的损失，就需要研究和构建科学合理的物资(如粮食)应急调度模型，来获取最优路径，减少物资配送时间，以保证灾区救援物资的充足供应，从而为开展及时高效的救援工作提供物资保障。

灾后物资应急调度的本质是多种约束条件下的车辆路径问题(Vehicle Routing Problem, VRP)[2]，即具有多配送中心带时间窗的VRP。作为经典的组合优化问题，VRP已被证明为NP-hard问题[3]，其求解方法主要有精确算法[4,5]和启发式算法[6,7]两类。精确算法针对具体问题建立相应的数学模型，利用数学方法求出问题的最优解，但其计算时间随问题规模的增大呈爆炸式增长，因此只能解决规模相对较小的问题。启发式算法是相对于精确算法提出的，在可接受范围内给出问题的解，相比于精确算法，在处理大规模VRP时，具有更高的鲁棒性、可行性。因此国内外学者主要采用启发式算法对VRP及其变体问题进行研究，如在求解带时间窗VRP时，Marinakis等人[8]采用3种不同的自适应策略优化粒子群算法，分别用于初始解的生成、解的移动以及算法参数的自适应调整，以提高算法的求解性能；此外，Ramachandranpillai等人[9]将改进萤火虫算法与脉冲神经系统结合，使其可以快速地搜索解空间，从而提高算法求解的收敛速度。……