李想等：两级选址~路径问题的大规模邻域搜索模拟退火算法 ·961· INI,需求点总数； [10]Nguyen V P,Prins C.Prodhon C.A multi-start iterated local IN,中转站总数； search with tabu list and path relinking for the two-echelon loca- 「*1，向上取整 tion-routing problem.Eng Appl Artif Intelligence,2012.25(1): 56 [11]Deng X P,Zhou X M,Tian S H.Research on integrated optimi- 参考文献 zation of location and routing for B2C E-commerce logistics cen- ter.J Chongging Unie Posts Telecommunications Nat Sci Ed, [1]Karaoglan I,Altiparmak F,Kara I,et al.A branch and cut algo- 2016,28(4):593 rithm for the location-routing problem with simultaneous pickup (邓学平，周昔敏，田帅辉.B2C电子商务物流中心选址-路 and delivery.Eur J Operational Res,2011,211(2):318 径综合优化研究.重庆邮电大学学报：自然科学版，2016， [2]Zhang X N,Fan H M,LiJ F.Chance-constrained model and al- 28(4):593) gorithm for LRP with multiple fuzzy variables under change-re- [12]Steinbrunn M,Moerkotte G,Kemper A.Heuristic and random- ward.Syst Eng Theory Practice,2016,36(2):442 ized optimization for the join ordering problem.VIDB1997,6 (张晓梢，范厚明，李创锋.变动补偿的多模糊选址-路径机 (3):191 会约束模型及算法.系统工程理论与实践，2016,36(2)： [13]Yu V F,Lin S Y.A simulated annealing heuristic for the open 442) location-routing problem.Comput Operations Res,2015,62: [3]Cheng C S,Pu Y H,Wu Y.Single-stage algorithm of location- 184 routing problem optimization model for integrated logistics.Cen- [14]Shaw P.Using constraint programming and local search methods ral S Univ Forestry Technol,2008,28(5):113 to solve vehicle routing problems /International Conference on (程赐胜，蒲云虎，吴颖.集成化物流选址-路径问题优化模 Principles and Practice of Constraint Programming-CP98. 型的算法研究.中南林业科技大学学报，2008,28(5)：113) Heidelberg:Springer.1998:417 [4]Duhamel C,Lacomme P,Prins C,et al.A GRASP x ELS ap- [15]Schrimpf G,Schneider J,Stamm-Wilbrandt H,et al.Record proach for the capacitated location-routing problem.Comput Oper- breaking optimization results using the ruin and recreate princi- ations Res,2010,37(11):1912 ple.J Comput Phys,2000,159(2)139 [5]Marinakis Y.An improved particle swarm optimization algorithm [16]Pisinger D,Ropke S.Large neighborhood search /Handbook of for the capacitated location routing problem and for the location Metaheuristics.New York:Springer US,2010:399 routing problem with stochastic demands.Appl Soft Computing, [17]Wei Z Y,Wu L,Zhang J W,et al.An adaptive large neighbor- 2015,37:680 hood search for two-echelon vehicle routing problem.Logistics [6]Ponboon S,Qureshi A G,Taniguchi E.Branch-and-price algo- Sci-Tech,2015,38(8):4 rithm for the location-routing problem with time windows.Trans- (魏占阳，邬炼，张佳伟，等基于自适应大规模邻域搜索算 portation Res Part E Logistics Transportation Rev,2016,86:1 法的两级车辆路径问题.物流科技.2015,38(8)：4) [7]Lopes R B.Ferreira C.Santos B S.A simple and effective evolu- [18]Breunig U,Schmid V,Hartl R F,et al.A large neighborhood tionary algorithm for the capacitated location-routing problem. based heuristic for two-echelon routing problems.Comput Opera- Comput Operations Res,2016,70:155 tions Res,2016,76:208 [8]Chen J M,Zeng B.Artificial bee colony algorithm with variable [19]Toth P.Vigo D.The granular tabu search and its application to neighborhood search and path relinking for two-echelon location- the vehicle-routing problem.Informs Computing,2003,15 routing problem.Comput Integr Manuf Syst,2014,20(5):1228 (4):333 (陈久梅，曾波.两级定位一路径问题的路径重连变邻域搜索 [20]Vidal T,Crainic T G,Gendreau M,et al.Heuristics for multi- 人工蜂群算法.计算机集成制造系统，2014,20(5)：1228) attribute vehicle routing problems:a survey and synthesis.Eur/ [9]Jacobsen S K,Madsen O B G.A comparative study of heuristics Operational Res,2013,231(1):1 for a two-level routing-location problem.Eur J Operational Res, [21]Croes G A.A method for solving traveling-salesman problems. 1980,5(6):378 Operations Res,1958,6(6):791李 想等: 两级选址鄄鄄路径问题的大规模邻域搜索模拟退火算法 | NC | , 需求点总数; | NS | , 中转站总数; 腋*骎, 向上取整. 参 考 文 献 [1] Karaoglan I, Altiparmak F, Kara I, et al. A branch and cut algo鄄 rithm for the location鄄routing problem with simultaneous pickup and delivery. Eur J Operational Res, 2011, 211(2): 318 [2] Zhang X N, Fan H M, Li J F. Chance鄄constrained model and al鄄 gorithm for LRP with multiple fuzzy variables under change鄄re鄄 ward. Syst Eng Theory Practice, 2016, 36(2): 442 (张晓楠, 范厚明, 李剑锋. 变动补偿的多模糊选址鄄鄄 路径机 会约束模型及算法. 系统工程理论与实践, 2016, 36 (2 ): 442) [3] Cheng C S, Pu Y H, Wu Y. Single鄄stage algorithm of location鄄 routing problem optimization model for integrated logistics. J Cen鄄 tral S Univ Forestry Technol, 2008, 28(5): 113 (程赐胜, 蒲云虎, 吴颖. 集成化物流选址鄄鄄 路径问题优化模 型的算法研究. 中南林业科技大学学报, 2008, 28(5): 113) [4] Duhamel C, Lacomme P, Prins C, et al. A GRASP 伊 ELS ap鄄 proach for the capacitated location鄄routing problem. Comput Oper鄄 ations Res, 2010, 37(11): 1912 [5] Marinakis Y. An improved particle swarm optimization algorithm for the capacitated location routing problem and for the location routing problem with stochastic demands. Appl Soft Computing, 2015, 37: 680 [6] Ponboon S, Qureshi A G, Taniguchi E. Branch鄄and鄄price algo鄄 rithm for the location鄄routing problem with time windows. Trans鄄 portation Res Part E Logistics Transportation Rev, 2016, 86: 1 [7] Lopes R B, Ferreira C, Santos B S. A simple and effective evolu鄄 tionary algorithm for the capacitated location鄄routing problem. Comput Operations Res, 2016, 70: 155 [8] Chen J M, Zeng B. Artificial bee colony algorithm with variable neighborhood search and path relinking for two鄄echelon location鄄 routing problem. Comput Integr Manuf Syst, 2014, 20(5): 1228 (陈久梅, 曾波. 两级定位—路径问题的路径重连变邻域搜索 人工蜂群算法. 计算机集成制造系统, 2014, 20(5): 1228) [9] Jacobsen S K, Madsen O B G. A comparative study of heuristics for a two鄄level routing鄄location problem. Eur J Operational Res, 1980, 5(6): 378 [10] Nguyen V P, Prins C, Prodhon C. A multi鄄start iterated local search with tabu list and path relinking for the two鄄echelon loca鄄 tion鄄routing problem. Eng Appl Artif Intelligence, 2012, 25(1): 56 [11] Deng X P, Zhou X M, Tian S H. Research on integrated optimi鄄 zation of location and routing for B2C E鄄commerce logistics cen鄄 ter. J Chongqing Univ Posts Telecommunications Nat Sci Ed, 2016, 28(4): 593 (邓学平, 周昔敏, 田帅辉. B2C 电子商务物流中心选址鄄鄄路 径综合优化研究. 重庆邮电大学学报: 自然科学版, 2016, 28(4): 593) [12] Steinbrunn M, Moerkotte G, Kemper A. Heuristic and random鄄 ized optimization for the join ordering problem. VLDB J, 1997, 6 (3): 191 [13] Yu V F, Lin S Y. A simulated annealing heuristic for the open location鄄routing problem. Comput Operations Res, 2015, 62: 184 [14] Shaw P. Using constraint programming and local search methods to solve vehicle routing problems / / International Conference on Principles and Practice of Constraint Programming — CP98. Heidelberg: Springer, 1998: 417 [15] Schrimpf G, Schneider J, Stamm鄄Wilbrandt H, et al. Record breaking optimization results using the ruin and recreate princi鄄 ple. J Comput Phys, 2000, 159(2): 139 [16] Pisinger D, Ropke S. Large neighborhood search / / Handbook of Metaheuristics. New York: Springer US, 2010: 399 [17] Wei Z Y, Wu L, Zhang J W, et al. An adaptive large neighbor鄄 hood search for two鄄echelon vehicle routing problem. Logistics Sci鄄Tech, 2015, 38(8): 4 (魏占阳, 邬炼, 张佳伟, 等. 基于自适应大规模邻域搜索算 法的两级车辆路径问题. 物流科技, 2015, 38(8): 4) [18] Breunig U, Schmid V, Hartl R F, et al. A large neighborhood based heuristic for two鄄echelon routing problems. Comput Opera鄄 tions Res, 2016, 76: 208 [19] Toth P, Vigo D. The granular tabu search and its application to the vehicle鄄routing problem. Informs J Computing, 2003, 15 (4): 333 [20] Vidal T, Crainic T G, Gendreau M, et al. Heuristics for multi鄄 attribute vehicle routing problems: a survey and synthesis. Eur J Operational Res, 2013, 231(1): 1 [21] Croes G A. A method for solving traveling鄄salesman problems. Operations Res, 1958, 6(6): 791 ·961·