車輛路徑規(guī)劃中的Location-Routing Problem簡介
今天為大家介紹的是選址-路徑問題(Location-Routing Problem, LRP)，首先上目錄
目錄
問題簡介
基礎(chǔ)模型、擴(kuò)展問題及應(yīng)用
算法
參考文獻(xiàn)
為了更好地了解這個問題，我們不妨當(dāng)一波老板。
? ? ? ?想象一下我們是經(jīng)營一家口罩生產(chǎn)企業(yè)的老板，公司有一批比較固定的經(jīng)銷商會跟我們訂貨，我們要做的就是根據(jù)訂單生產(chǎn)或者從倉庫調(diào)撥口罩給他們送過去。位置呢大概是這樣的
? ? ? 生產(chǎn)方面的事情我們先不考慮，我們考慮一下配送的問題。不要小看配送這一環(huán)節(jié)，物流運(yùn)輸?shù)幕ㄙM(fèi)可不少。而且在配送環(huán)節(jié)小編覺得一般的企業(yè)在這里更多的是節(jié)流而不是開源，關(guān)注我們公眾號肯定知道這里可以解一個VRP嘛，解出來以后可能可以省下一筆錢。是的，研究VRP的一個重要意義在于此，為了適應(yīng)不同的需求還有了很多不一樣的約束，這些我們公眾號都有做過相關(guān)的介紹。
? ? ? ?接下來，由于你學(xué)過VRP，配送環(huán)節(jié)花費(fèi)減少，利潤更多，你的市場開始擴(kuò)張，幾年以后，你的客戶分布變成了這樣子：
? ? ? ?可能會有人說客戶多了一樣的，上VRP做優(yōu)化就完事兒了。但是這個時候的問題已經(jīng)不僅僅是路線規(guī)劃了，如果經(jīng)銷商距離廠房很遠(yuǎn)的話把貨物從生產(chǎn)倉房運(yùn)輸?shù)奖容^遠(yuǎn)的經(jīng)銷商那里，在配送上的花費(fèi)是巨大的，例如在過路費(fèi)上的花費(fèi)也會增加，交付時間會邊長等等。
? ? ? ?從運(yùn)營上來說，這種情況下在別的地方選擇新建廠房或者倉庫是一個更好的選擇。如果決定在別的地方新建廠房或者倉庫的話，我們就開始到外地進(jìn)行實地考察，看看哪些地方能建，以及建設(shè)的成本如何等等，收集一波數(shù)據(jù)，然后就變成了這樣：
? ? ? ?這時候又要開始頭疼了，我們沒有那么多資金也不一定有必要在這些位置都進(jìn)行建設(shè)啊，那在哪里進(jìn)行建設(shè)好呢？要建多少個呢？實際上這一類問題也是一類組合優(yōu)化問題，選址問題、P-中位問題的研究都能夠為這類決策提供強(qiáng)有力的支持。
? ? ? ?當(dāng)我們解決了設(shè)施選址的問題后，我們還會面臨一開始所遇到的配送問題，也就是對于每一個新的廠房或者倉庫，我們都需要研究一下車輛路徑規(guī)劃。這里就有個問題，選址除了要服務(wù)顧客以外，還會影響后面的車輛路徑規(guī)劃。也就是說目前我們是在兩個不一樣的環(huán)節(jié)中做優(yōu)化，即選址環(huán)節(jié)和配送環(huán)節(jié)。這兩個環(huán)節(jié)是相關(guān)的，而作為企業(yè)來講需要考慮降低整體的成本，因此自然而然地，就有人提出把這兩個環(huán)節(jié)當(dāng)成一個環(huán)節(jié)來進(jìn)行規(guī)劃，這就是我們今天要說的Location-Routing Problem了。
? ? ? ?選址-路徑問題(Location-Routing Problem, LRP)是指給定一個可選廠址的集合，每個可選廠址都有開設(shè)成本，以及一個特定的車隊和一個顧客點(diǎn)的集合。我們要做的是選擇開放可選廠址集合中的一個子集，并為每一個顧客節(jié)點(diǎn)指定提供服務(wù)的廠址以及相應(yīng)的車輛路徑規(guī)劃，使得總的花費(fèi)最小。總花費(fèi)包括開設(shè)廠房或者倉庫的費(fèi)用、車輛的固定費(fèi)用、路費(fèi)等等。
? ? ? ?這個問題其實在很早之前就有人提出來了( Watson-Gandy and Dohrn (1973), Salhi, S., & Rand, G. K. (1989))。而且更重要的是這些作者證明了如果將這兩個問題分離分別求解所得到的解往往不是最優(yōu)解，正因為如此，研究這個問題才更有意義。但是在實際應(yīng)用場景中，還是需要有比較穩(wěn)定的需求，畢竟如果需求變動太大的話是不可能重新選址的。
? ? ? 最開始許多研究的假設(shè)都是沒有容量限制的，但是后來的研究都把重點(diǎn)放在了有容量約束的選址-路徑問題(CLRP)上，即設(shè)施和車輛都是有容量約束的，這也是這一類問題的基礎(chǔ)模型。
? ? ?
擴(kuò)展問題的分類從一些問題的特征入手
確定性信息、不確定性信息和模糊信息
? ? ? 確定性信息是指問題的所有信息都提前知道，這種情況也是大多數(shù)問題的場景。不確定性信息則是指問題的部分信息服從概率分布，例如各個節(jié)點(diǎn)顧客的需求量。模糊信息是指問題的一些參數(shù)的取值是一個模糊的數(shù)值，針對這種情況的研究并不多。靜態(tài)問題、動態(tài)問題和周期性問題
? ? ? 靜態(tài)問題考慮一個單一的規(guī)劃周期。動態(tài)一般指的是多個規(guī)劃階段的問題，其中有些信息最初的階段是不知道的，但是經(jīng)過一段時間后就會知道，這種信息通常是顧客的需求信息。周期性問題則需要為多個規(guī)劃周期做規(guī)劃，并且假設(shè)所有的相關(guān)信息已知，周期性問題的目的是為了找到一種服務(wù)客戶的路徑規(guī)劃模式，例如每位顧客在什么時間段進(jìn)行服務(wù)。離散選址、連續(xù)選址和網(wǎng)絡(luò)選址
? ? ? 離散選址問題是指可供選址的地址為圖上節(jié)點(diǎn)的一個子集。連續(xù)選址則可以不用局限于上述的集合中，可以被放在選定范圍內(nèi)的任何一個地方。而網(wǎng)絡(luò)選址則要求在圖上的點(diǎn)或者邊上進(jìn)行選址。大多數(shù)研究的問題場景都是離散選址。單階段和多階段
? ? ? 多階段問題的基本思想就是客戶并不是直接從中心場站獲得服務(wù)，而是通過N級網(wǎng)絡(luò)中的N個分支節(jié)點(diǎn)獲得服務(wù)。
? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ? ??? ???
別著急，我知道直接說看不懂，我們來回看一下我們的口罩企業(yè)
? ? ? ?如果我們選擇在可選地址上建立倉庫，發(fā)貨由倉庫發(fā)貨的話，整個顧客配送服務(wù)流程就變成了從生產(chǎn)廠房將貨物運(yùn)輸?shù)礁鞯氐膫}庫，然后各地倉庫按照訂單進(jìn)行配送。這個時候就是一個兩階段的問題，第一個階段是從生產(chǎn)廠房(有可能有多個)向各地倉庫運(yùn)送貨物，第二個階段才是倉庫向顧客提供配送服務(wù)滿足需求，N階段的話以此類推。下面是一個3階段的示意圖。
單目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃
這里的目標(biāo)是指優(yōu)化目標(biāo)，Tavakkoli-Moghaddam, Makui, and Mazloomi (2010)就研究了一個雙目標(biāo)的LRP，第一個優(yōu)化目標(biāo)是最小化設(shè)施開設(shè)成本、可變設(shè)備生產(chǎn)成本和車輛運(yùn)輸成本的和。第二個優(yōu)化目標(biāo)是最大化能滿足顧客的需求量。但是大多數(shù)文章研究的還是單目標(biāo)規(guī)劃問題。點(diǎn)路徑規(guī)劃和邊路徑規(guī)劃
點(diǎn)路徑規(guī)劃考慮的服務(wù)是在圖中的點(diǎn)上進(jìn)行的，而邊路徑規(guī)劃則是在需要服務(wù)的邊上進(jìn)行作業(yè)。但是針對后者的研究并不多。其它
例如需求可拆分的LRP(Split delivery LRP)，針對這個問題的研究不少(Archetti & Speranza,2008)。還有帶取貨送貨的LRP(Pickup-and-deliveryLRP)以及Inventory LRPs，即考慮庫存管理的LRP，需要決定顧客的需求貨物哪些從倉庫調(diào)撥，哪些由生產(chǎn)廠直接配送等等。
? ? ? LRP在一些實際場景中已經(jīng)得到了應(yīng)用。Chan andBaker(2005)為在美國的武裝部隊遞送文件的倉庫位置和車輛路線，研究的問題是一個標(biāo)準(zhǔn)的LRP。Burks (2006)研究的是軍事行動的戰(zhàn)區(qū)分配問題，需要決定供應(yīng)基地和車輛倉庫的位置以及規(guī)劃行駛路線，研究的問題是一個兩階段的LRP。Marinakis and Marinaki(2008)研究的是希臘某地的木材配送設(shè)置的位置以及配送車輛的行駛路線，是一個標(biāo)準(zhǔn)的LRP。Schittekat and S?rensen (2009)研究的是汽車零部件配送中心的選址及小型配送車輛的路線選擇，也是一個標(biāo)準(zhǔn)的LRP。Govindan etal.(2014)研究易腐食品的配送，是一個帶時間窗約束的兩階段LRP。
? ? ? 通過上面這些例子其實可以發(fā)現(xiàn)不管是哪個行業(yè)，只要涉及設(shè)施選址和路徑規(guī)劃這樣的問題特征，LRP都可以應(yīng)用到這樣的場景上。
? ? ? ?LRP問題是NP-Hard問題，所以大家都知道解決這個問題算法就是精確性算法和啟發(fā)式算法這兩種了。但是無論是精確性算法還是啟發(fā)式算法，解決LRP的關(guān)鍵還是如何處理選址問題、分配問題和路徑問題等子問題(Drexl et al,2015)。關(guān)于精確性算法和啟發(fā)式算法有哪些這個問題我們已經(jīng)通過眾多的推文回答了，這里不贅述了。但是有的方法可能在這個問題上有不錯的效果，因為這些方法似乎更受學(xué)者們的青睞。
? ? ? ?精確性算法通常使用的方法是在所有可選廠址組成的集合的子集中，找到這樣一個子集：最小化設(shè)施開放成本和最小化這個子集對應(yīng)的多車場VRP的最優(yōu)解所花費(fèi)的成本。其中多車場VRP中對應(yīng)的車場就是這個子集中的設(shè)施。
? ? ? ?而啟發(fā)式算法則常常將問題分解為兩個階段，一個階段是選址-分配，即需要決定在什么位置開設(shè)設(shè)施，然后為設(shè)施分配顧客；另一個階段是路徑規(guī)劃，這個時候就是在上述階段的基礎(chǔ)上解VRP了。有時候分配問題也會放在后面的階段里。基于群體的元啟發(fā)式算法和單體的元啟發(fā)式算法都能夠很好地運(yùn)用到這類問題的求解中。對于許多LRP的擴(kuò)展問題，解的質(zhì)量很大程度上取決于設(shè)施的開放位置(Prins et al.,2006a)，因此比較成功的啟發(fā)式算法都需要有有效的設(shè)施選址配置的方法。
通過這些優(yōu)化，相信企業(yè)一定能夠節(jié)省更多的費(fèi)用，獲得更強(qiáng)的競爭力。
參考文獻(xiàn)
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.
?贊 賞?
長按下方二維碼打賞感謝您，支持學(xué)生們的原創(chuàng)熱情！
?
---The End---
文案?&&?編輯：莊浩城審稿人：秦時明岳（華中科技大學(xué)管理學(xué)院）指導(dǎo)老師：秦時明岳（華中科技大學(xué)管理學(xué)院）
如對文中內(nèi)容有疑問，歡迎交流。PS:部分資料來自網(wǎng)絡(luò)。如有需求，可以聯(lián)系：秦虎老師（[email protected]）莊浩城 (華中科技大學(xué)管理學(xué)院本科四年級：[email protected])