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

Study on multi-depot open vehicle routing problem with soft time windows

作　　者：凌海峰[1,2] 谷俊辉 LING Haifeng;GU Junhui(School of Management, Hefei University of Technology, Hefei 230009, China;Key Laboratory of Process Optimization and Intelligent Decision-making, Hefei University of Technology, Hefei 230009, China)

机构地区：[1]合肥工业大学管理学院,合肥230009 [2]合肥工业大学过程优化与智能决策教育部重点实验室,合肥230009

出　　处：《计算机工程与应用》2017年第14期232-239,共8页Computer Engineering and Applications

基　　金：国家自然科学基金重大项目(No.71490725);国家自然科学基金面上项目(No.71371062);"973"计划项目(No.2013CB329603);青年科学基金项目(No.71302064)

摘　　要：带软时间窗的多车场开放式车辆调度问题是在开放式车辆路径问题的基础上,考虑了多车场和客户服务时间的约束,是一类典型的NP难解问题。针对该问题,提出了一种改进的蚁群算法求解方案,并建立了相应的数学模型。首先通过设置一个虚拟车场将多车场VRP转化为单车场VRP,然后利用参数控制的改进蚁群算法与2-opt算法结合来对模型求解。算法先利用K-means与细菌觅食算法相结合的聚类技术判断蚁群状态,进而动态调整算法参数,使其快速收敛到全局最优解附近,再依据混沌理论的特点来调整参数,使其跳出局部最优。最后,再利用2-opt算法对最优解进行优化。实验结果验证了该算法求解MDOVRPSTW问题的有效性。Multi-depot open vehicle routing problem with soft time windows is a variation of the open vehicle routingproblem constrained by time windows and multi-depot,which is a typical NP-hard problem.To solve this problem,animproved ant colony algorithm is proposed,and the corresponding mathematical model is established.By introducing avirtual depot,the multi-depot VRP is transformed into a single depot VRP.Then a new ant colony algorithm with parameteradaptation combined with2-opt algorithm is proposed to solve the problem.At the early stage of the algorithm,a clusteringtechnology based on the bacterial foraging chemotaxis algorithm and K-means algorithm is used to judge the state ofthe ant colony,and the parameters are adjusted adaptively to make the algorithm converge to the neighborhood of the globaloptimal solution.At the late stage,the parameters are tuned based on the characteristics of chaos theory to jump out oflocal optima.Experimental results verify the effectiveness of the proposed algorithm for solving the MDOVRPSTW problem.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]