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

目錄

• 問(wèn)題簡(jiǎn)介

• 基礎(chǔ)模型、擴(kuò)展問(wèn)題及應(yīng)用

• 算法

• 參考文獻(xiàn)

問(wèn)題簡(jiǎn)介

為了更好地了解這個(gè)問(wèn)題，我們不妨當(dāng)一波老板。

想象一下我們是經(jīng)營(yíng)一家口罩生產(chǎn)企業(yè)的老板，公司有一批比較固定的經(jīng)銷(xiāo)商會(huì)跟我們訂貨，我們要做的就是根據(jù)訂單生產(chǎn)或者從倉(cāng)庫(kù)調(diào)撥口罩給他們送過(guò)去。位置呢大概是這樣的

生產(chǎn)方面的事情我們先不考慮，我們考慮一下配送的問(wèn)題。不要小看配送這一環(huán)節(jié)，物流運(yùn)輸?shù)幕ㄙM(fèi)可不少。而且在配送環(huán)節(jié)小編覺(jué)得一般的企業(yè)在這里更多的是節(jié)流而不是開(kāi)源，關(guān)注我們公眾號(hào)肯定知道這里可以解一個(gè)VRP嘛，解出來(lái)以后可能可以省下一筆錢(qián)。是的，研究VRP的一個(gè)重要意義在于此，為了適應(yīng)不同的需求還有了很多不一樣的約束，這些我們公眾號(hào)都有做過(guò)相關(guān)的介紹。

接下來(lái)，由于你學(xué)過(guò)VRP，配送環(huán)節(jié)花費(fèi)減少，利潤(rùn)更多，你的市場(chǎng)開(kāi)始擴(kuò)張，幾年以后，你的客戶(hù)分布變成了這樣子：

可能會(huì)有人說(shuō)客戶(hù)多了一樣的，上VRP做優(yōu)化就完事兒了。但是這個(gè)時(shí)候的問(wèn)題已經(jīng)不僅僅是路線(xiàn)規(guī)劃了，如果經(jīng)銷(xiāo)商距離廠房很遠(yuǎn)的話(huà)把貨物從生產(chǎn)倉(cāng)房運(yùn)輸?shù)奖容^遠(yuǎn)的經(jīng)銷(xiāo)商那里，在配送上的花費(fèi)是巨大的，例如在過(guò)路費(fèi)上的花費(fèi)也會(huì)增加，交付時(shí)間會(huì)邊長(zhǎng)等等。

從運(yùn)營(yíng)上來(lái)說(shuō)，這種情況下在別的地方選擇新建廠房或者倉(cāng)庫(kù)是一個(gè)更好的選擇。如果決定在別的地方新建廠房或者倉(cāng)庫(kù)的話(huà)，我們就開(kāi)始到外地進(jìn)行實(shí)地考察，看看哪些地方能建，以及建設(shè)的成本如何等等，收集一波數(shù)據(jù)，然后就變成了這樣：

這時(shí)候又要開(kāi)始頭疼了，我們沒(méi)有那么多資金也不一定有必要在這些位置都進(jìn)行建設(shè)啊，那在哪里進(jìn)行建設(shè)好呢？要建多少個(gè)呢？實(shí)際上這一類(lèi)問(wèn)題也是一類(lèi)組合優(yōu)化問(wèn)題，選址問(wèn)題、P-中位問(wèn)題的研究都能夠?yàn)檫@類(lèi)決策提供強(qiáng)有力的支持。

當(dāng)我們解決了設(shè)施選址的問(wèn)題后，我們還會(huì)面臨一開(kāi)始所遇到的配送問(wèn)題，也就是對(duì)于每一個(gè)新的廠房或者倉(cāng)庫(kù)，我們都需要研究一下車(chē)輛路徑規(guī)劃。這里就有個(gè)問(wèn)題，選址除了要服務(wù)顧客以外，還會(huì)影響后面的車(chē)輛路徑規(guī)劃。也就是說(shuō)目前我們是在兩個(gè)不一樣的環(huán)節(jié)中做優(yōu)化，即選址環(huán)節(jié)和配送環(huán)節(jié)。這兩個(gè)環(huán)節(jié)是相關(guān)的，而作為企業(yè)來(lái)講需要考慮降低整體的成本，因此自然而然地，就有人提出把這兩個(gè)環(huán)節(jié)當(dāng)成一個(gè)環(huán)節(jié)來(lái)進(jìn)行規(guī)劃，這就是我們今天要說(shuō)的Location-Routing Problem了。

選址-路徑問(wèn)題(Location-Routing Problem, LRP)是指給定一個(gè)可選廠址的集合，每個(gè)可選廠址都有開(kāi)設(shè)成本，以及一個(gè)特定的車(chē)隊(duì)和一個(gè)顧客點(diǎn)的集合。我們要做的是選擇開(kāi)放可選廠址集合中的一個(gè)子集，并為每一個(gè)顧客節(jié)點(diǎn)指定提供服務(wù)的廠址以及相應(yīng)的車(chē)輛路徑規(guī)劃，使得總的花費(fèi)最小。總花費(fèi)包括開(kāi)設(shè)廠房或者倉(cāng)庫(kù)的費(fèi)用、車(chē)輛的固定費(fèi)用、路費(fèi)等等。

這個(gè)問(wèn)題其實(shí)在很早之前就有人提出來(lái)了( Watson-Gandy and Dohrn (1973), Salhi, S., & Rand, G. K. (1989))。而且更重要的是這些作者證明了如果將這兩個(gè)問(wèn)題分離分別求解所得到的解往往不是最優(yōu)解，正因?yàn)槿绱?，研究這個(gè)問(wèn)題才更有意義。但是在實(shí)際應(yīng)用場(chǎng)景中，還是需要有比較穩(wěn)定的需求，畢竟如果需求變動(dòng)太大的話(huà)是不可能重新選址的。

基礎(chǔ)模型、擴(kuò)展問(wèn)題和應(yīng)用

最開(kāi)始許多研究的假設(shè)都是沒(méi)有容量限制的，但是后來(lái)的研究都把重點(diǎn)放在了有容量約束的選址-路徑問(wèn)題(CLRP)上，即設(shè)施和車(chē)輛都是有容量約束的，這也是這一類(lèi)問(wèn)題的基礎(chǔ)模型。

擴(kuò)展問(wèn)題的分類(lèi)從一些問(wèn)題的特征入手

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

2. 靜態(tài)問(wèn)題、動(dòng)態(tài)問(wèn)題和周期性問(wèn)題      靜態(tài)問(wèn)題考慮一個(gè)單一的規(guī)劃周期。動(dòng)態(tài)一般指的是多個(gè)規(guī)劃階段的問(wèn)題，其中有些信息最初的階段是不知道的，但是經(jīng)過(guò)一段時(shí)間后就會(huì)知道，這種信息通常是顧客的需求信息。周期性問(wèn)題則需要為多個(gè)規(guī)劃周期做規(guī)劃，并且假設(shè)所有的相關(guān)信息已知，周期性問(wèn)題的目的是為了找到一種服務(wù)客戶(hù)的路徑規(guī)劃模式，例如每位顧客在什么時(shí)間段進(jìn)行服務(wù)。

3. 離散選址、連續(xù)選址和網(wǎng)絡(luò)選址      離散選址問(wèn)題是指可供選址的地址為圖上節(jié)點(diǎn)的一個(gè)子集。連續(xù)選址則可以不用局限于上述的集合中，可以被放在選定范圍內(nèi)的任何一個(gè)地方。而網(wǎng)絡(luò)選址則要求在圖上的點(diǎn)或者邊上進(jìn)行選址。大多數(shù)研究的問(wèn)題場(chǎng)景都是離散選址。

4. 單階段和多階段      多階段問(wèn)題的基本思想就是客戶(hù)并不是直接從中心場(chǎng)站獲得服務(wù)，而是通過(guò)N級(jí)網(wǎng)絡(luò)中的N個(gè)分支節(jié)點(diǎn)獲得服務(wù)。

別著急，我知道直接說(shuō)看不懂，我們來(lái)回看一下我們的口罩企業(yè)

1. 如果我們選擇在可選地址上建立倉(cāng)庫(kù)，發(fā)貨由倉(cāng)庫(kù)發(fā)貨的話(huà)，整個(gè)顧客配送服務(wù)流程就變成了從生產(chǎn)廠房將貨物運(yùn)輸?shù)礁鞯氐膫}(cāng)庫(kù)，然后各地倉(cāng)庫(kù)按照訂單進(jìn)行配送。這個(gè)時(shí)候就是一個(gè)兩階段的問(wèn)題，第一個(gè)階段是從生產(chǎn)廠房(有可能有多個(gè))向各地倉(cāng)庫(kù)運(yùn)送貨物，第二個(gè)階段才是倉(cāng)庫(kù)向顧客提供配送服務(wù)滿(mǎn)足需求，N階段的話(huà)以此類(lèi)推。下面是一個(gè)3階段的示意圖。

   

2. 單目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃這里的目標(biāo)是指優(yōu)化目標(biāo)，Tavakkoli-Moghaddam, Makui, and Mazloomi (2010)就研究了一個(gè)雙目標(biāo)的LRP，第一個(gè)優(yōu)化目標(biāo)是最小化設(shè)施開(kāi)設(shè)成本、可變?cè)O(shè)備生產(chǎn)成本和車(chē)輛運(yùn)輸成本的和。第二個(gè)優(yōu)化目標(biāo)是最大化能滿(mǎn)足顧客的需求量。但是大多數(shù)文章研究的還是單目標(biāo)規(guī)劃問(wèn)題。

3. 點(diǎn)路徑規(guī)劃和邊路徑規(guī)劃點(diǎn)路徑規(guī)劃考慮的服務(wù)是在圖中的點(diǎn)上進(jìn)行的，而邊路徑規(guī)劃則是在需要服務(wù)的邊上進(jìn)行作業(yè)。但是針對(duì)后者的研究并不多。

4. 其它例如需求可拆分的LRP(Split delivery LRP)，針對(duì)這個(gè)問(wèn)題的研究不少(Archetti & Speranza,2008)。還有帶取貨送貨的LRP(Pickup-and-deliveryLRP)以及Inventory LRPs，即考慮庫(kù)存管理的LRP，需要決定顧客的需求貨物哪些從倉(cāng)庫(kù)調(diào)撥，哪些由生產(chǎn)廠直接配送等等。

LRP在一些實(shí)際場(chǎng)景中已經(jīng)得到了應(yīng)用。Chan andBaker(2005)為在美國(guó)的武裝部隊(duì)遞送文件的倉(cāng)庫(kù)位置和車(chē)輛路線(xiàn)，研究的問(wèn)題是一個(gè)標(biāo)準(zhǔn)的LRP。Burks (2006)研究的是軍事行動(dòng)的戰(zhàn)區(qū)分配問(wèn)題，需要決定供應(yīng)基地和車(chē)輛倉(cāng)庫(kù)的位置以及規(guī)劃行駛路線(xiàn)，研究的問(wèn)題是一個(gè)兩階段的LRP。Marinakis and Marinaki(2008)研究的是希臘某地的木材配送設(shè)置的位置以及配送車(chē)輛的行駛路線(xiàn)，是一個(gè)標(biāo)準(zhǔn)的LRP。Schittekat and S?rensen (2009)研究的是汽車(chē)零部件配送中心的選址及小型配送車(chē)輛的路線(xiàn)選擇，也是一個(gè)標(biāo)準(zhǔn)的LRP。Govindan etal.(2014)研究易腐食品的配送，是一個(gè)帶時(shí)間窗約束的兩階段LRP。

通過(guò)上面這些例子其實(shí)可以發(fā)現(xiàn)不管是哪個(gè)行業(yè)，只要涉及設(shè)施選址和路徑規(guī)劃這樣的問(wèn)題特征，LRP都可以應(yīng)用到這樣的場(chǎng)景上。

算法

LRP問(wèn)題是NP-Hard問(wèn)題，所以大家都知道解決這個(gè)問(wèn)題算法就是精確性算法和啟發(fā)式算法這兩種了。但是無(wú)論是精確性算法還是啟發(fā)式算法，解決LRP的關(guān)鍵還是如何處理選址問(wèn)題、分配問(wèn)題和路徑問(wèn)題等子問(wèn)題(Drexl et al,2015)。關(guān)于精確性算法和啟發(fā)式算法有哪些這個(gè)問(wèn)題我們已經(jīng)通過(guò)眾多的推文回答了，這里不贅述了。但是有的方法可能在這個(gè)問(wèn)題上有不錯(cuò)的效果，因?yàn)檫@些方法似乎更受學(xué)者們的青睞。

精確性算法通常使用的方法是在所有可選廠址組成的集合的子集中，找到這樣一個(gè)子集：最小化設(shè)施開(kāi)放成本和最小化這個(gè)子集對(duì)應(yīng)的多車(chē)場(chǎng)VRP的最優(yōu)解所花費(fèi)的成本。其中多車(chē)場(chǎng)VRP中對(duì)應(yīng)的車(chē)場(chǎng)就是這個(gè)子集中的設(shè)施。

而啟發(fā)式算法則常常將問(wèn)題分解為兩個(gè)階段，一個(gè)階段是選址-分配，即需要決定在什么位置開(kāi)設(shè)設(shè)施，然后為設(shè)施分配顧客；另一個(gè)階段是路徑規(guī)劃，這個(gè)時(shí)候就是在上述階段的基礎(chǔ)上解VRP了。有時(shí)候分配問(wèn)題也會(huì)放在后面的階段里?；谌后w的元啟發(fā)式算法和單體的元啟發(fā)式算法都能夠很好地運(yùn)用到這類(lèi)問(wèn)題的求解中。對(duì)于許多LRP的擴(kuò)展問(wèn)題，解的質(zhì)量很大程度上取決于設(shè)施的開(kāi)放位置(Prins et al.,2006a)，因此比較成功的啟發(fā)式算法都需要有有效的設(shè)施選址配置的方法。

通過(guò)這些優(yōu)化，相信企業(yè)一定能夠節(jié)省更多的費(fèi)用，獲得更強(qiáng)的競(jìng)爭(zhē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.