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

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

针对同时配集货的定位—路线问题,建立了三维指数混合整数规划模型,并设计了变邻域分散搜索求解算法,即在基本分散搜索算法的基础上保留参考集更新和组合策略的全局搜索能力。针对组合后的解可能是不可行解的问题,利用插入法将其改进为可行解,再运用变邻域搜索进行局部开发以提高可行解质量。为保证算法的多样性以进一步扩大搜索空间,初始种群采用两阶段混合多随机法构造。通过采用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.