车辆路径规划中的Location-Routing Problem简介

今天为大家介绍的是选址-路径问题(Location-Routing Problem, LRP)，首先上目录

目录

问题简介

基础模型、扩展问题及应用

算法

参考文献

1

问题简介

为了更好地了解这个问题，我们不妨当一波老板。

想象一下我们是经营一家口罩生产企业的老板，公司有一批比较固定的经销商会跟我们订货，我们要做的就是根据订单生产或者从仓库调拨口罩给他们送过去。位置呢大概是这样的

生产方面的事情我们先不考虑，我们考虑一下配送的问题。不要小看配送这一环节，物流运输的花费可不少。而且在配送环节小编觉得一般的企业在这里更多的是节流而不是开源，关注我们公众号肯定知道这里可以解一个VRP嘛，解出来以后可能可以省下一笔钱。是的，研究VRP的一个重要意义在于此，为了适应不同的需求还有了很多不一样的约束，这些我们公众号都有做过相关的介绍。

接下来，由于你学过VRP，配送环节花费减少，利润更多，你的市场开始扩张，几年以后，你的客户分布变成了这样子：

可能会有人说客户多了一样的，上VRP做优化就完事儿了。但是这个时候的问题已经不仅仅是路线规划了，如果经销商距离厂房很远的话把货物从生产仓房运输到比较远的经销商那里，在配送上的花费是巨大的，例如在过路费上的花费也会增加，交付时间会边长等等。

从运营上来说，这种情况下在别的地方选择新建厂房或者仓库是一个更好的选择。如果决定在别的地方新建厂房或者仓库的话，我们就开始到外地进行实地考察，看看哪些地方能建，以及建设的成本如何等等，收集一波数据，然后就变成了这样：

这时候又要开始头疼了，我们没有那么多资金也不一定有必要在这些位置都进行建设啊，那在哪里进行建设好呢？要建多少个呢？实际上这一类问题也是一类组合优化问题，选址问题、P-中位问题的研究都能够为这类决策提供强有力的支持。

当我们解决了设施选址的问题后，我们还会面临一开始所遇到的配送问题，也就是对于每一个新的厂房或者仓库，我们都需要研究一下车辆路径规划。这里就有个问题，选址除了要服务顾客以外，还会影响后面的车辆路径规划。也就是说目前我们是在两个不一样的环节中做优化，即选址环节和配送环节。这两个环节是相关的，而作为企业来讲需要考虑降低整体的成本，因此自然而然地，就有人提出把这两个环节当成一个环节来进行规划，这就是我们今天要说的Location-Routing Problem了。

选址-路径问题(Location-Routing Problem, LRP)是指给定一个可选厂址的集合，每个可选厂址都有开设成本，以及一个特定的车队和一个顾客点的集合。我们要做的是选择开放可选厂址集合中的一个子集，并为每一个顾客节点指定提供服务的厂址以及相应的车辆路径规划，使得总的花费最小。总花费包括开设厂房或者仓库的费用、车辆的固定费用、路费等等。

这个问题其实在很早之前就有人提出来了( Watson-Gandy and Dohrn (1973), Salhi, S., & Rand, G. K. (1989))。而且更重要的是这些作者证明了如果将这两个问题分离分别求解所得到的解往往不是最优解，正因为如此，研究这个问题才更有意义。但是在实际应用场景中，还是需要有比较稳定的需求，毕竟如果需求变动太大的话是不可能重新选址的。

2

基础模型、扩展问题和应用

最开始许多研究的假设都是没有容量限制的，但是后来的研究都把重点放在了有容量约束的选址-路径问题(CLRP)上，即设施和车辆都是有容量约束的，这也是这一类问题的基础模型。

扩展问题的分类从一些问题的特征入手

1. 确定性信息、不确定性信息和模糊信息 确定性信息是指问题的所有信息都提前知道，这种情况也是大多数问题的场景。不确定性信息则是指问题的部分信息服从概率分布，例如各个节点顾客的需求量。模糊信息是指问题的一些参数的取值是一个模糊的数值，针对这种情况的研究并不多。
2. 静态问题、动态问题和周期性问题 静态问题考虑一个单一的规划周期。动态一般指的是多个规划阶段的问题，其中有些信息最初的阶段是不知道的，但是经过一段时间后就会知道，这种信息通常是顾客的需求信息。周期性问题则需要为多个规划周期做规划，并且假设所有的相关信息已知，周期性问题的目的是为了找到一种服务客户的路径规划模式，例如每位顾客在什么时间段进行服务。
3. 离散选址、连续选址和网络选址 离散选址问题是指可供选址的地址为图上节点的一个子集。连续选址则可以不用局限于上述的集合中，可以被放在选定范围内的任何一个地方。而网络选址则要求在图上的点或者边上进行选址。大多数研究的问题场景都是离散选址。
4. 单阶段和多阶段 多阶段问题的基本思想就是客户并不是直接从中心场站获得服务，而是通过N级网络中的N个分支节点获得服务。

别着急，我知道直接说看不懂，我们来回看一下我们的口罩企业

如果我们选择在可选地址上建立仓库，发货由仓库发货的话，整个顾客配送服务流程就变成了从生产厂房将货物运输到各地的仓库，然后各地仓库按照订单进行配送。这个时候就是一个两阶段的问题，第一个阶段是从生产厂房(有可能有多个)向各地仓库运送货物，第二个阶段才是仓库向顾客提供配送服务满足需求，N阶段的话以此类推。下面是一个3阶段的示意图。

1. 单目标规划和多目标规划 这里的目标是指优化目标，Tavakkoli-Moghaddam, Makui, and Mazloomi (2010)就研究了一个双目标的LRP，第一个优化目标是最小化设施开设成本、可变设备生产成本和车辆运输成本的和。第二个优化目标是最大化能满足顾客的需求量。但是大多数文章研究的还是单目标规划问题。
2. 点路径规划和边路径规划 点路径规划考虑的服务是在图中的点上进行的，而边路径规划则是在需要服务的边上进行作业。但是针对后者的研究并不多。
3. 其它 例如需求可拆分的LRP(Split delivery LRP)，针对这个问题的研究不少(Archetti & Speranza,2008)。还有带取货送货的LRP(Pickup-and-deliveryLRP)以及Inventory LRPs，即考虑库存管理的LRP，需要决定顾客的需求货物哪些从仓库调拨，哪些由生产厂直接配送等等。

LRP在一些实际场景中已经得到了应用。Chan andBaker(2005)为在美国的武装部队递送文件的仓库位置和车辆路线，研究的问题是一个标准的LRP。Burks (2006)研究的是军事行动的战区分配问题，需要决定供应基地和车辆仓库的位置以及规划行驶路线，研究的问题是一个两阶段的LRP。Marinakis and Marinaki(2008)研究的是希腊某地的木材配送设置的位置以及配送车辆的行驶路线，是一个标准的LRP。Schittekat and Sörensen (2009)研究的是汽车零部件配送中心的选址及小型配送车辆的路线选择，也是一个标准的LRP。Govindan etal.(2014)研究易腐食品的配送，是一个带时间窗约束的两阶段LRP。

通过上面这些例子其实可以发现不管是哪个行业，只要涉及设施选址和路径规划这样的问题特征，LRP都可以应用到这样的场景上。

3

算法

LRP问题是NP-Hard问题，所以大家都知道解决这个问题算法就是精确性算法和启发式算法这两种了。但是无论是精确性算法还是启发式算法，解决LRP的关键还是如何处理选址问题、分配问题和路径问题等子问题(Drexl et al,2015)。关于精确性算法和启发式算法有哪些这个问题我们已经通过众多的推文回答了，这里不赘述了。但是有的方法可能在这个问题上有不错的效果，因为这些方法似乎更受学者们的青睐。

精确性算法通常使用的方法是在所有可选厂址组成的集合的子集中，找到这样一个子集：最小化设施开放成本和最小化这个子集对应的多车场VRP的最优解所花费的成本。其中多车场VRP中对应的车场就是这个子集中的设施。

而启发式算法则常常将问题分解为两个阶段，一个阶段是选址-分配，即需要决定在什么位置开设设施，然后为设施分配顾客；另一个阶段是路径规划，这个时候就是在上述阶段的基础上解VRP了。有时候分配问题也会放在后面的阶段里。基于群体的元启发式算法和单体的元启发式算法都能够很好地运用到这类问题的求解中。对于许多LRP的扩展问题，解的质量很大程度上取决于设施的开放位置(Prins et al.,2006a)，因此比较成功的启发式算法都需要有有效的设施选址配置的方法。

通过这些优化，相信企业一定能够节省更多的费用，获得更强的竞争力。

参考文献

Archetti,C.,&Speranza,M.G.(2008). The split delivery vehicle routing problem: Asurvey. In B.Golden, S.Raghavan, & E.Wasil(Eds.), The vehicle routing problem: Latest advances and new challenges(pp.103–122). NewYork: Springer.

Burks,R.(2006). An adaptive tabu search heuristic for the location routing pick up and delivery problem with time windows with a theater distribution application. PhDthesis, Graduate School of Engineering and Management, AirForce Institute of Technology,Ohio.

Chan,Y.,&Baker,S.(2005).The multiple depot, multiple traveling sales men facility location problem: Vehiclerange, service frequency, and heuristic implementations. Mathematical and Computer Modelling,41,1035–1053.

Drexl, Michael, &Michael Schneider. 2015. A Survey of Variants and Extensions of the Location-Routing Problem. European Journal of Operational Research 241 (2): 283–308.

Govindan,K.,Jafarian,A.,Khodaverdi,R.,&Devika,K.(2014).Two-echelon multiple-vehicle location-routing problem with time windows for optimization of sustain-able supply chain network of perishable food. International Journal of Production Economics,152,9–28.

Marinakis,Y.,&Marinaki,M.(2008). A bi-level genetic algorithm for a real life location-routing problem. International Journal of Logistics Research and Applications,11,49–65.

Prins,C.,Prodhon,C.,&Wolfler Calvo,R.(2006). Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. 4OR – A Quarterly Journal of Operations Research,4,221–238.

Prodhon, Caroline, 和Christian Prins. 2014. A Survey of Recent Research on Location-Routing Problems. European Journal of Operational Research 238 (1): 1–17.

Salhi, S., & Rand, G. K. (1989). The effect of ignoring routes when locating depots. European Journal of Operational Research, 39, 150–156.

Schittekat,P.,&Sörensen,K.(2009).OR practice—Supporting 3PL decisions in the automotive industry by generating diverse solutions to a large-scale location-routing problem. Operations Research,57,1058–1067.

Tavakkoli-Moghaddam,R.,Makui,A.,&Mazloomi,Z.(2010). A new integrated mathematical model for a bi-objective multi-depot location routing problem solved by a multi-objective scatter search algorithm. Journal of Manufacturing Systems,29,111–119.

Watson-Gandy, C., & Dohrn, P. (1973). Depot location with van salesmen – Apractical approach. Omega, 1(3), 321–329.

赞 赏

长按下方二维码打赏

感谢您，

支持学生们的原创热情！

郑重承诺

打赏是对工作的认可

所有打赏所得

都将作为酬劳支付给辛勤工作的学生

指导老师不取

---The End---

文案 && 编辑：庄浩城

审稿人：秦时明岳（华中科技大学管理学院）

指导老师：秦时明岳（华中科技大学管理学院）

如对文中内容有疑问，欢迎交流。PS:部分资料来自网络。

如有需求，可以联系：

秦虎老师（professor.qin@qq.com）

庄浩城 (华中科技大学管理学院本科四年级：1604088003@qq.com)