选址-路径优化问题研究综述

何鸿康

(重庆交通大学管理学院 重庆 400074)

选址-路径优化问题研究综述

何鸿康

(重庆交通大学管理学院 重庆 400074)

设施节点选址以及城市配送引发的城市交通拥堵、配送成本高等问题制约着交通运输相关行业的发展，运用选址-路径优化模型分析城市道路交通运输问题，是解决城市拥堵的重要途径。本文综述了2011～2016年国内外有关选址-路径优化(Location Routing Problem)的文献，并按问题类别与求解模型分类，最后提出了未来选址-路径问题研究方向。

交通运输；选址-路径优化；文献综述；分析方法

引言

我国目前正处于交通运输行业发展的黄金时期，这就给我们的城市配送、旅客运输等业务带来了巨大的市场机遇。城市配送、旅客运输等业务的发展离不开设施选址与路径优化的支持与支撑，而现阶段设施选址与车辆调度不合理、车辆配送线路不经济等问题，制约了城市配送、旅客运输业务的发展，引发了城市拥堵、配送成本高、配送时间长、城市污染等现象，成为城市配送、旅客运输业务发展的瓶颈。鉴于选址-路径优化问题的重大理论意义和实践价值，有必要对国内外现有的选址-路径优化问题的研究成果进行归纳和分析。

一、LRP问题分类

(一)带时间窗LRP问题

对于带时间窗的LRP问题的研究主要结合多节点、需求与旅行时间不确定性等方面。罗耀波[1]通过建立带退货和软时间窗的多仓库LRP数学模型，解决集成物流网络问题。Wang[2]则采用自适应变领域搜索与强化禁忌搜索算法，解决带时间窗的电动汽车充电站选址问题与车辆路径优化问题。针对客户需求与旅行时间的不确定性，Zarandi[3]建立带时间窗的位置-路径模糊约束规划模型，并采用模拟退化算法求解。

(二)模糊条件LRP问题

目前关于模糊条件下LRP问题的研究，研究重点在于客户需求不确定性、旅行时间不确定性两方面。针对同时具有模糊需求和模糊时间等多约束条件问题，张晓楠[4]建立变动补偿的机会约束预优化模型，同时引入时间惩罚成本修正，得到实时调整变动幅度小且整体最优的预优化方案。针对应急物资配送需求和运输时间的不确定性，孙华丽[5]构造基于随机机会约束规划的多目标应急物流定位-路径模型，并引入处罚函数处理约束条件，最后通过算例验证模型的可行性。

(三)多目标LRP问题

在多目标LRP问题研究方面，主要从时间和费用最小化、总的环境影响、客户需求最大化以及最小处理量等目标着手进行优化。赵佳虹[6]考虑时变条件下应急物资类别多样性以及物流中心最小处理量要求，以时间和费用最小化为目标，建立混合整数线性规划模型，优化方案费用和时间消耗。针对同一问题，陈刚[7]则运用带精英策略的快速非支配排序遗传算法求解该问题，并与变权目标遗传算法对比，证明该方法能够得到更高质量的帕累托最优解。李双琳[8]在研究危化品运输问题时，构造危化品多级配送中心、多目标LRP优化模型，设计遗传算法得到最优解，有效控制风险。

(四)带容积约束LRP问题

容积约束作为LRP问题的一种约束条件，多与不确定性条件、多节点问题等相结合进行研究。针对客户弹性预约服务时间问题，罗耀波[9]以容量约束为基础，总成本最小和客户满意度最高为原则，采用两阶段模拟退火算法求解基于模糊时间窗的有容量限制的双目标LRP径优化问题，同时，为了解决同时送取货问题，结合客户需求多样性与时间不确定性，建立基于模糊时间窗的同时送取货的多车型、多仓库选址路径模型，并采用改进两阶段自适应遗传算法进行求解[10]。

(五)多车型LRP问题

目前单独研究多车型LRP问题的文献较少，多与多级配送与车辆容量限制问题相结合研究。石兆[11]首先采用改进聚类分析方法确定配送中心、服务群位置，然后采用遗传算法很好地解决了包含不同车型、车辆容量、时间窗等约束的配送选址-多车型运输路径优化问题。赵崤含[12]在研究污水处理厂选址-配送问题时，充分考虑车辆容量以及设施容量等约束，在此基础上构建多设施多车型的有容量限制的LRP模型，采用遗传算法求解得到优化的设施选址与路径。

(六)多级LRP问题

目前学者们主要对两级LRP问题进行研究。Rahmani[13]在研究两级LRP问题时，同时考虑多产品、收发货以及配送问题，建立带有收发货和交付两级多产品LRP模型，采用混合整数线性规划方法求得最优方案。Grangier[14]在研究使用两级车队运输物品的LRP问题时，结合城市物流时间窗约束，并采用自适应大邻域搜索求解。基于应急物资配送依托多级应急物流中心的特点，杨恩缘[15]考虑应急物流中心容量限制，运用混合整数规划模型求解，实现最小运输成本的选址-路径优化。针对制造商、零售商以及客户组成的三级网络定位-路线问题，Torfi[16]首先采用梯形模糊数对评价权重进行分析，以中心仓库位置与集散系统到客户路线为目标建立模型，并采用模拟退火算法进行求解，从而降低了整个网络成本。

(七)多节点LRP问题

针对多节点问题，一般采用启发式算法获取多节点LRP问题的近似最优解。Montoya[17]对多节点车辆路径问题进行综述，并对时间窗、分割交付、异构车队、定期交付等问题进行研究。基于多节点多旅行商问题与LRP问题的联系，Benavent[18]采用分支和切割算法研究多方面诱导的不均衡性，证明该方法同样适用于选址-路径问题。基于多仓库配送中仓库选择与共享商品交付问题，Ray[19]建立多段拆分车辆路径模型，并采用启发式算法求解在同一目标函数下允许建立的符合客户要求的仓库位置与车路径。胡大伟[20]建立单设施LRP问题模型，利用空间填充曲线构造初始解，并采用动态规划方法确定最优车辆配置。万凤娇[21]考虑单独研究物流设施选址和车辆运输路线安排问题的局限性，提出了多仓库LRP安排问题，并首先采用禁忌搜索算法求得一个较好的设施位置，再利用蚁群算法获得对应的优化运输路线。

二、研究方法

(一)精确算法

在选址-路径优化涉及精确算法研究中，主要运用混合整数规划方法来解决多目标时变LRP问题[6]、多级LRP问题[13][15]。在上述研究中，对于多节点多旅行商LRP问题也采用分支定界[18]方法求解，此外，胡大伟等[20]采用了动态规划方法。

(二)启发式算法

本文综述的LRP问题启发式算法主要包括：蚁群算法、遗传算法、变领域搜索算法以及各种混合算法。在涉及启发式算法研究文献中，主要运用模拟退火算法解决带时间窗LRP问题[3]、三级网络LRP问题[16]、带容积约束LRP问题[9]。对于危化品多级-多目标运输问题[8]、带容积约束LRP问题[10]、多车型LRP问题[11][12]采用遗传算法进行求解。除此以外Wang等[2]、万凤娇[21]采用了禁忌搜索算法，罗耀波[1]采用了混合遗传算法，Grangier等[14]采用了自适应搜索算法。

三、 结论与发展趋势

通过对以上LRP问题研究文献的分析，学者们对LRP优化问题重点关注多节点、多目标、模糊条件以及带时间窗的LRP问题。对LRP优化问题的求解主要采用了启发式算法，同时精确算法也有所应用。随着人们对于城市道路交通拥堵问题的关注，本文认为LRP优化问题还将在以下两个方面继续深入探讨研究：

(一)可持续的配送LRP优化

随着经济的不断发展，城市不断扩张，汽车保有量逐年升高，从而引发了严重的交通拥堵问题以及环境问题。为了适应交通大环境的要求，后续对于LRP问题的研究应该考虑在交通限行条件下，如何以最高的燃油经济性与最低的碳排放来满足客户需求，同时使得物流企业自身利益最大化，从而建立可持续的配送路径优化效果。

(二)动态LRP优化

随着选址-路径优化理论研究的进一步深入，已经逐步建立了LRP问题研究基本框架，然而，目前对于LRP优化问题的研究主要集中于算法的创新以及约束条件增加，缺少实际数据作为支撑。在现实情况下，客户需求、车辆调度等条件都是实时变化的，因此未来LRP优化问题的实证研究将成为研究的热点。

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

[2]Wang L Y, Song Y B. Multiple Charging Station Location-Routing Problem with Time Window of Electric Vehicle[J]. Journal Of Engineering Science & Technology Review, 2015, 8(5): 190-201.

[3]Fazel Zarandi M H, Hemmati A, Davari S, et al. Capacitated location-routing problem with time windows under uncertainty[J]. Knowledge-Based Systems, 2013, 37(2): 480-489.

[4]张晓楠, 范厚明, 李剑锋. 变动补偿的多模糊选址-路径机会约束模型及算法[J]. 系统工程理论与实践, 2016(2): 442-453.

[5]孙华丽, 周战杰, 薛耀锋. 考虑路径风险的不确定需求应急物流定位-路径问题[J]. 上海交通大学学报, 2013, 47(6): 962-966.

[6]赵佳虹. 时变条件下应急物流多目标LRP研究[J]. 公路交通科技, 2012, 29(4): 137-142+148.

[7]陈刚, 付江月. 基于NSGAII的应急物流多目标LRP研究[J]. 软科学, 2016(4): 135-139.

[8]李双琳, 马祖军, 邹坤. 危险品物流中的多目标定位-路径问题[J]. 运筹与管理, 2014(3): 8-15.

[9]罗耀波, 孙延明. 基于模糊时间窗的带容积约束选址路径问题[J]. 系统工程, 2014(1): 19-25.

[10]罗耀波. 基于模糊时间窗的同时送取货选址路径规划模型研究[D].华南理工大学, 2014.

[11]石兆, 符卓. 配送选址-多车型运输路径优化问题及求解算法[J]. 计算机科学, 2015, 42(5): 245-250.

[12]赵崤含, 李冰毅, 石咏, 郭海湘, 周欣然, 潘雯雯. 基于遗传算法的污水处理厂选址-配送问题集成研究[J]. 物流技术, 2015, 34(11): 136-141.

[13]Rahmani Y, Cherifkhettaf W R, Oulamara The two-echelon multi-products location-routing problem with pick-up and delivery: formulation and heuristic approaches[J]. International Journal Of Production Research, 2015, 54(4): 999-1019.

[14]Grangier P, Gendreau M, Lehuédé F, et al. An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization[J]. European Journal of Operational Research, 2014, 254(1): 80-91.

[15]杨恩缘, 李进, 严翌娴, 黄文耀. 震后多品种应急物资多级配送中的选址-路径模型[J]. 灾害学, 2016, 2016(2): 200-205.

[16]Torfi F, Farahani RZ, Mahdavi I. Fuzzy MCDM for weight of object’s phrase in location routing problem[J]. Applied Mathematical Modeling, 2015, 40(1): 526-541.

[17]Montoya-Torres J R, Franco J L, Isaza S N, et al. A literature review on the vehicle routing problem with multiple depots[J]. Computers & Industrial Engineering, 2015, 79: 115-129.

[18]Benavent E, Martinez A. Multi-depot Multiple TSP: a polyhedral study and computational results[J]. Annals Of Operations Research, 2013, 207(207): 7-25.

[19]Ray S, Soeanu A, Berger J, Debbabi M. The multi-depot split-delivery vehicle routing problem: Model and solution algorithm[J]. Knowledge-Based Systems, 2014, 71: 238-265.

[20]胡大伟, 胡勇, 朱志强. 基于空间填充曲线和动态规划解的定位路线问题[J]. 长安大学学报(自然科学版), 2006, 26(3): 80-83.

[21]万凤娇. 多仓库定位-运输路线安排问题的模型和算法研究[J]. 江汉大学学报(自然科学版), 2012, 40(3): 26-32.