定位-路径问题综述

Review on location-routing problem

研究了定位-路径问题(LRP),总结了国内外LRP模型及其扩展模型,比较了LRP模型求解算法的适用性,分析了LRP测试算例的节点分布和数据规模,提出了LRP研究的主要方向。研究结果表明:LRP模型从基于基础网络的最简化问题(带容量约束的LRP,CLRP)向多方向模型进行扩展,包括基于网络复杂化的LRP扩展,如特定网络系统的多目标LRP(MOLRP)、同时取送货LRP(LRPSPD)、接驳转运中心LRP(CDCLRP)、两阶段LRP(2E-LRP)、选址-弧路径问题(LARP)、卡车和拖车路径问题(TTRP)与设施地点为二维连续的LRP(PLRP),基础网络参数不确定化的LRP,包括带模糊数据的LRP与多计划周期LRP(MPLRP),且正在向更切合实际的问题如高度集成、不确定与动态LRP发展;LRP算法方面,精确算法仅可用于求解小规模LRP,主要LRP求解算法由早期的智能算法逐渐转向元启发式算法、基于邻域搜索优化的算法与混合算法方向发展,这些改进算法均基于特定LRP设计,具有更好的求解性能,尤其是采用基于多种破坏和修复因子的自适应大邻域搜索算法求解大规模LRP取得了较好的解,且其改造性极强;常用LRP测试算例的节点呈现均匀分布、堆分布及均匀与堆混合分布,且逐渐产生了适用于2E-LRP与LRPSPD等扩展LRP的测试算例;根据物流市场环境变化和需求,提出LRP未来扩展研究的主要方向,包括多阶段LRP的扩展(如2E-LRPSPD、考虑库存的2E-LRP等)、节点二维连续的LRP、客户含优先级的带竞争或盈利LRP、混合不确定LRP等切合实际的问题;提出了LRP求解算法未来方向,包括设计新型精确算法求解中、大规模LRP,设计更准确更高效的组合启发式算法与应用近似算法求解LRP及扩展LRP的最优解。

Location-routing problem （LRP） was studied. The models of LRP and LRP extensions at home and abroad were summarized. The applicability of solving methods to LRP models were compared. The nodes-distributions and data scale of testing instances were analyzed. The main future research directions of LRP were proposed. Analysis result shows that the research of LRP models extends from the mostly simplified problem of basic logistics network （the capacitated LRP, CLRP） to multi-direction： including LRP extensions based on complicated networks such as, multi-objective LRP based on specific network systems, LRP with simultaneous pickup and delivery, LRP with cross-docking center, two-echelon LRP, location arc routing problems, truck and trailer routing problem and Planar LRP; and extensions based on uncertainties such as, LRP with fuzzy factors, multi-period LRP- meanwhile developing to more practical problems such as highly integrated LRPs, LRP with uncertainties and dynamic LRPs. On algorithms for LRPs, the exact algorithm can only be used to solve the small-scale problem. So the main researches on algorithms are gradually turned from intelligent algorithms in earlier times to metaheuristic algorithms, algorithms based on various neighborhood search optimization methods and hybrid algorithms. These algorithms which are designed based on the specific problems have good performance, especially the adaptive large neighbors search with various destruction factors and repair factors obtained better solutions on large-scale instances, and it is highly reusable. Test instances frequently used in the literature reflect that nodes in the instances follow uniform distribution, heap distribution and mix distribution. The instances specifically adapted to 2E- LRP, LRPSPD and other LRP extensions are gradually generated. Finally, the main direction of future research on LRP extensions is put forward according to the change and demand of logistics market environment, which include extensions of multi-echelon LRP such as 2E-LRPSPD and 2E- LRP with inventory, planar LRP, priority based LRP with profits or competition, LRP with mixed uncertainty. Future directions on solving methods are also proposed, further exploration of exact algorithms for medium and large scale problems, the designation of hybrid heuristic algorithms with higher accuracy and efficiency, and the application of approximate algorithm for solving the optimal solutions of LRP and LRP extensions. 4 tabs, 3 figs, 161 refs.