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

Abstract: 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.

Key words: location-routing problem, simultaneous pickup and delivery, scatter search, variable neighborhood search, heuristic algorithms