同时配集货定位—路线问题的变邻域分散搜索算法  

Variable neighborhood scatter search algorithm for LRP with simultaneous pickup and delivery

作　　者：张晓楠[1,2] 范厚明[1,2] 李剑锋[1] 

机构地区：[1]大连海事大学交通运输管理学院,辽宁大连116026 [2]大连海事大学战略管理与系统规划研究所,辽宁大连116026

出　　处：《计算机集成制造系统》2015年第9期2535-2548,共14页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(70801007;61473053);辽宁省软科学指导计划资助项目(2012401196);辽宁省教育厅科学技术研究一般项目(L2014196);大连市科学技术计划资助项目(2010A16GX084)~~

摘　　要：针对同时配集货的定位—路线问题,建立了三维指数混合整数规划模型,并设计了变邻域分散搜索求解算法,即在基本分散搜索算法的基础上保留参考集更新和组合策略的全局搜索能力。针对组合后的解可能是不可行解的问题,利用插入法将其改进为可行解,再运用变邻域搜索进行局部开发以提高可行解质量。为保证算法的多样性以进一步扩大搜索空间,初始种群采用两阶段混合多随机法构造。通过采用Lingo求解简单算例验证了模型的正确性,采用设计的变邻域分散搜索算法仿真已有算例并与其他算法比较,证明了该算法的有效性。Aiming at the Location-Routing Problem with Simultaneous Pickup and Delivery （LRPSPD）, a three-index exponential-size MIP model was formulated, and a Variable Neighborhood Scatter Search （VNSS） algorithm was designed. In VNSS, Reference Set Update Method （RSUM） and Solution Combination Method （SCM） in basic scatter search algorithm were reserved to search the global-space. An insert method was used to make the infeasible solutions improve as the feasible solutions, and a Variable Neighborhood Search （VNS） was developed to search the local-space and enhance the feasible solutions quality. To ensure the diversity and further expand the search space, a two-stage mixed multiple random method was used to construct the initial population. The correctness of formulated model was verified through solving the simple experiment with LINGO method. Compared with other algorithms by simulating the existing experiments, the proposed algorithm could obtain the better solution and solve LRPSPD and LRP effectively.

关 键 词：定位-路线问题 同时配集货 分散搜索 变邻域搜索 启发式算法 

分 类 号：F253.4[经济管理—国民经济]