带软时间窗的多车场开放式车辆调度

来源：计算机工程与应用杂志2017年第14期北京时间：

作者：凌海峰1，2，谷俊辉1

单位：1.合肥工业大学 管理学院，合肥 230009；2.合肥工业大学 过程优化与智能决策教育部重点实验室，合肥 230009

摘要：带软时间窗的多车场开放式车辆调度问题是在开放式车辆路径问题的基础上，考虑了多车场和客户服务时间的约束，是一类典型的NP难解问题。针对该问题，提出了一种改进的蚁群算法求解方案，并建立了相应的数学模型。首先通过设置一个虚拟车场将多车场VRP转化为单车场VRP，然后利用参数控制的改进蚁群算法与2-opt算法结合来对模型求解。算法先利用K-means与细菌觅食算法相结合的聚类技术判断蚁群状态，进而动态调整算法参数，使其快速收敛到全局最优解附近，再依据混沌理论的特点来调整参数，使其跳出局部最优。最后，再利用2-opt算法对最优解进行优化。实验结果验证了该算法求解MDOVRPSTW问题的有效性。

关键词：开放式车辆路径问题,时间窗,蚁群算法,聚类技术,2-opt