今天為大家介紹的是選址-路徑問題(Location-Routing Problem, LRP)，首先上目錄

目錄

• 問題簡介

• 基礎模型、擴展問題及應用

• 算法

• 參考文獻

問題簡介

為了更好地了解這個問題，我們不妨當一波老板。

想象一下我們是經營一家口罩生產企業的老板，公司有一批比較固定的經銷商會跟我們訂貨，我們要做的就是根據訂單生產或者從倉庫調撥口罩給他們送過去。位置呢大概是這樣的

生產方面的事情我們先不考慮，我們考慮一下配送的問題。不要小看配送這一環節，物流運輸的花費可不少。而且在配送環節小編覺得一般的企業在這里更多的是節流而不是開源，關注我們公眾號肯定知道這里可以解一個VRP嘛，解出來以后可能可以省下一筆錢。是的，研究VRP的一個重要意義在于此，為了適應不同的需求還有了很多不一樣的約束，這些我們公眾號都有做過相關的介紹。

接下來，由于你學過VRP，配送環節花費減少，利潤更多，你的市場開始擴張，幾年以后，你的客戶分布變成了這樣子：

可能會有人說客戶多了一樣的，上VRP做優化就完事兒了。但是這個時候的問題已經不僅僅是路線規劃了，如果經銷商距離廠房很遠的話把貨物從生產倉房運輸到比較遠的經銷商那里，在配送上的花費是巨大的，例如在過路費上的花費也會增加，交付時間會邊長等等。

從運營上來說，這種情況下在別的地方選擇新建廠房或者倉庫是一個更好的選擇。如果決定在別的地方新建廠房或者倉庫的話，我們就開始到外地進行實地考察，看看哪些地方能建，以及建設的成本如何等等，收集一波數據，然后就變成了這樣：

這時候又要開始頭疼了，我們沒有那么多資金也不一定有必要在這些位置都進行建設啊，那在哪里進行建設好呢？要建多少個呢？實際上這一類問題也是一類組合優化問題，選址問題、P-中位問題的研究都能夠為這類決策提供強有力的支持。

當我們解決了設施選址的問題后，我們還會面臨一開始所遇到的配送問題，也就是對于每一個新的廠房或者倉庫，我們都需要研究一下車輛路徑規劃。這里就有個問題，選址除了要服務顧客以外，還會影響后面的車輛路徑規劃。也就是說目前我們是在兩個不一樣的環節中做優化，即選址環節和配送環節。這兩個環節是相關的，而作為企業來講需要考慮降低整體的成本，因此自然而然地，就有人提出把這兩個環節當成一個環節來進行規劃，這就是我們今天要說的Location-Routing Problem了。

選址-路徑問題(Location-Routing Problem, LRP)是指給定一個可選廠址的集合，每個可選廠址都有開設成本，以及一個特定的車隊和一個顧客點的集合。我們要做的是選擇開放可選廠址集合中的一個子集，并為每一個顧客節點指定提供服務的廠址以及相應的車輛路徑規劃，使得總的花費最小。總花費包括開設廠房或者倉庫的費用、車輛的固定費用、路費等等。

這個問題其實在很早之前就有人提出來了( Watson-Gandy and Dohrn (1973), Salhi, S., & Rand, G. K. (1989))。而且更重要的是這些作者證明了如果將這兩個問題分離分別求解所得到的解往往不是最優解，正因為如此，研究這個問題才更有意義。但是在實際應用場景中，還是需要有比較穩定的需求，畢竟如果需求變動太大的話是不可能重新選址的。

基礎模型、擴展問題和應用

最開始許多研究的假設都是沒有容量限制的，但是后來的研究都把重點放在了有容量約束的選址-路徑問題(CLRP)上，即設施和車輛都是有容量約束的，這也是這一類問題的基礎模型。

擴展問題的分類從一些問題的特征入手

1. 確定性信息、不確定性信息和模糊信息      確定性信息是指問題的所有信息都提前知道，這種情況也是大多數問題的場景。不確定性信息則是指問題的部分信息服從概率分布，例如各個節點顧客的需求量。模糊信息是指問題的一些參數的取值是一個模糊的數值，針對這種情況的研究并不多。

2. 靜態問題、動態問題和周期性問題      靜態問題考慮一個單一的規劃周期。動態一般指的是多個規劃階段的問題，其中有些信息最初的階段是不知道的，但是經過一段時間后就會知道，這種信息通常是顧客的需求信息。周期性問題則需要為多個規劃周期做規劃，并且假設所有的相關信息已知，周期性問題的目的是為了找到一種服務客戶的路徑規劃模式，例如每位顧客在什么時間段進行服務。

3. 離散選址、連續選址和網絡選址      離散選址問題是指可供選址的地址為圖上節點的一個子集。連續選址則可以不用局限于上述的集合中，可以被放在選定范圍內的任何一個地方。而網絡選址則要求在圖上的點或者邊上進行選址。大多數研究的問題場景都是離散選址。

4. 單階段和多階段      多階段問題的基本思想就是客戶并不是直接從中心場站獲得服務，而是通過N級網絡中的N個分支節點獲得服務。

別著急，我知道直接說看不懂，我們來回看一下我們的口罩企業

1. 如果我們選擇在可選地址上建立倉庫，發貨由倉庫發貨的話，整個顧客配送服務流程就變成了從生產廠房將貨物運輸到各地的倉庫，然后各地倉庫按照訂單進行配送。這個時候就是一個兩階段的問題，第一個階段是從生產廠房(有可能有多個)向各地倉庫運送貨物，第二個階段才是倉庫向顧客提供配送服務滿足需求，N階段的話以此類推。下面是一個3階段的示意圖。

   

2. 單目標規劃和多目標規劃這里的目標是指優化目標，Tavakkoli-Moghaddam, Makui, and Mazloomi (2010)就研究了一個雙目標的LRP，第一個優化目標是最小化設施開設成本、可變設備生產成本和車輛運輸成本的和。第二個優化目標是最大化能滿足顧客的需求量。但是大多數文章研究的還是單目標規劃問題。

3. 點路徑規劃和邊路徑規劃點路徑規劃考慮的服務是在圖中的點上進行的，而邊路徑規劃則是在需要服務的邊上進行作業。但是針對后者的研究并不多。

4. 其它例如需求可拆分的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都可以應用到這樣的場景上。

算法

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.