带退货和软时间窗的多仓库选址-路径问题研究

运筹与管理 ›› 2014, Vol. 23 ›› Issue (5): 78-85.

带退货和软时间窗的多仓库选址-路径问题研究

罗耀波, 孙延明, 廖鹏

华南理工大学工商管理学院,广东广州 510641

收稿日期:2012-12-01 出版日期:2021-05-25
作者简介:罗耀波(1989-),男,广东珠海人,硕士研究生,主要研究方向为物流系统建模与仿真(178743212);孙延明(1968-),男,黑龙江穆棱人,教授,博导,主要研究方向为现代制造信息系统、复杂系统。
基金资助:
国家自然科学基金项目(71071059);国家自然科学基金项目(50675069);国家自然科学基金资助项目(71071057);中央高校基本科研业务费专项资金资助项目(2012ZMO031)

Research on Multi-Depot Location Routing Problem with Backhauls and Soft Time Windows

LUO Yao-Bo, SUN Yan-Ming, LIAO Peng

School of Business Administration, South China University of Technology, Guangzhou 510641, China

Received:2012-12-01 Online:2021-05-25

摘要/Abstract

摘要： 选址-路径问题(location routing problems, LRP)是集成物流网络研究中的难题,也是任何一个大型物流配送企业必须面对的管理决策问题。本文在仓库容量约束和车辆容量约束的基础上,结合送取货一体化的配送模式和客户服务时间要求,建立了带退货和软时间窗的多仓库选址-路径(MDLRP)数学模型。针对MDLRP问题求解的复杂性,引入局部搜索算法和重组策略,设计了自适应混合遗传算法,对模型进行整体求解。最后进行数值实验,表明本文提出的模型和改进算法具有实用性和优越性,可为选址和车辆运输决策提供重要参考依据。

关键词: 选址-路径问题, 集成物流网络, 带退货, 软时间窗, 遗传算法

Abstract: Location routing problems is not only of great significance in integrated logistics network planning research, but also an important management decision that every large logistics company has to make. Based on the warehouse capacity and vehicle capacity constraints, the paper proposes a multi-depot location routing problem model(MDLRP)with backhauls and soft time windows. The model takes full consideration of logistics distribution mode with the simultaneous delivery and pick-up and the customer service time requirements. Given the complexity of the MDLRP model, the paper proposes an improved hybrid genetic algorithm with iterated local search and recombination strategy to solve the model integrally. The performance of the heuristic is assessed by computational experiments. As can be seen from the solution, the model with its hybrid genetic algorithm is feasible and superior, and it can be provided to be an alternative tool for location and routing decision.

Key words: location-routing problem, integrated logistics network, backhauls, soft time windows, genetic algorithm

中图分类号:

F253.4

罗耀波, 孙延明, 廖鹏. 带退货和软时间窗的多仓库选址-路径问题研究[J]. 运筹与管理, 2014, 23(5): 78-85.

LUO Yao-Bo, SUN Yan-Ming, LIAO Peng. Research on Multi-Depot Location Routing Problem with Backhauls and Soft Time Windows[J]. Operations Research and Management Science, 2014, 23(5): 78-85.

参考文献

[1] 胡欣悦,刘金兰,汤勇力.遗传算法在设施定位与车辆运输路线安排中的应用[J].工业工程,2007,10(2):102-111.
[2] Min H, Vaidyanathan J, Srivastava R. Combined location-routing problems: a synthesis and future research direction[J]. European Journal of Operational Research, 1998, 108(1): 1-15.
[3] 汪寿阳,赵秋红,夏国平.集成物流管理系统中的定位-运输线路安排问题的研究[J].管理科学学报,2000,3(2):69-75.
[4] Hansen P, Hegedahl B, Hjortkjaer S, Obel B. A heuristic solution to the warehouse location-routing problem[J]. European Journal of Operational Research, 1994, 76(1): 117-127.
[5] Prins C, Prodhon C, Ruiz A, Soriano P,Wolfler-Calvo R. Solving the capacitated location-routing problem by a cooperative lagrangean relaxation-granular tabu search heuristic[J]. Transportation Science, 2007, 41(4): 470- 483.
[6] Nguyen V P, Prins C, Prodhon C. Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking[J]. European Journal of Operational Research, 2012, 216(1): 113-126.
[7] 王绍仁,马祖军.震后应急物流系统中带时间窗的模糊动态LRP[J].运筹与管理,2011,20(5):63-72.
[8] 马汉武,杨相,赵林度,程发新.基于时间的随机需求二级分销网络物流系统集成优化研究[J].运筹与管理,2012,21(4):63-72.
[9] Zarandi M H F, Hemmati A, Davari S, Turksen B. Capacitated location-routing problem with time windows under uncertainty[J]. Knowledge-Based Systems, 2013, 37(1): 480- 489.
[10] Barreto S, Ferreira C, Paixao J, Souza Santos B. Using clustering analysis in a capacitated location-routing problem[J]. European Journal of Operational Research, 2007, 179(3): 968-977.
[11] Liu S C, Lee S B. A two-phase heuristic method for the multi-depot location routing problem taking inventory control decisions into consideration[J]. The International Journal of Advanced Manufacturing Technology, 2003, 22(11): 941-950.
[12] Bouhafs L, Hajjam A, Koukam A. A combination of simulated annealing and ant colony system for the capacitated location-routing problem[J]. Lecture Notes in Computer Science, 2006, 4251: 409- 416.
[13] Tuzun D, Burke L I. A two-phase tabu search approach to the location routing problem[J]. European Journal of Operational Research. 1999, 116(1): 87-99
[14] Prins C, Prodhon C, Ruiz A, Wolfler-Calvo R. Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking[J]. 4OR, 2006, 4(3): 221-238.
[15] Yu V F, Lin S W, Lee W, Ting C J. A simulated annealing heuristic for the capacitated location routing problem[J]. Computers & Industrial Engineering, 2012, 58(2): 288-299.
[16] Holland J. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[M]. Cambridge, Mass: MIT Press, 1992. 211.
[17] Srivastava R. Alternate solution procedures for the location-routing problem[J]. Omega Journal of Management Science, 1993, 21(4): 497-506.
[18] Prins C, Prodhon C, Soriano P, Ruiz A. A memetic algorithm with population management(MA|PM)for the capacitated location-routing problem[J]. Lecture Notes in Computer Science, 2006, 3906: 183-194.
[19] Salhi S, Nagy G. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling[J]. Journal of the Operational Research Society, 1999, 50(10): 1034-1042.