談選址路徑問題及其優(yōu)化算法綜述

選址路徑問題及其優(yōu)化算法綜述摘要：本文敘述了物流系統(tǒng)中選址運(yùn)輸路徑安排問題(LRP)的含義、發(fā)展歷程，重點(diǎn)闡述了求解LRP優(yōu)化算法的機(jī)制，并對LRP的未來研究方向作了分析。關(guān)鍵詞：選址路徑；算法1選址路徑問題(LRP)概述選址-路徑問題(Location-RoutingProblems,LRP)的研究開始于70年代，Watson-Gandy和Dohrn將運(yùn)輸車輛行程安排的多點(diǎn)停留特性與定位-運(yùn)輸網(wǎng)絡(luò)結(jié)合起來開展研究。通過增加定位-運(yùn)輸網(wǎng)絡(luò)中巡回路線的建立決策，LRP問題比傳統(tǒng)的運(yùn)輸-定位模型更難解決。雖然存在求解及模型構(gòu)建方面的許多困難，真正意義上的LRP研究還是在20世紀(jì)70年代末和80年代初得到發(fā)展。這些研究工作包括Or和Pierskalla(1979)，Jacobsen和Madsen(1978)，Harrison(1979)，Jacobsen和Madsen(1980)，Nambiar(1981)，Laporte和Nobert(1981)，Madsen(1983)。到80年代后期，由于實(shí)際應(yīng)用的迫切需要，LRP的研究才得到了學(xué)術(shù)界的廣泛重視。據(jù)不完全統(tǒng)計(jì)，迄今為止，在英文出版物中，有關(guān)LRP的模型、算法的研究及綜述文章和論著已有數(shù)百篇。國內(nèi)學(xué)術(shù)界對LRP的起步雖然較晚，但也取得一些成就，如汪壽陽(2000)《集成物流管理系統(tǒng)中定位-運(yùn)輸路線安排問題的研究》，東北大學(xué)張潛的博士論文介紹了集成化物流中LRP問題的模型，并對其優(yōu)化算法進(jìn)行研究。2LRP問題的求解算法一般而言，LRP的算法可以分為兩類，一類是精確算法，一類是啟發(fā)式算法。2.1.精確算法由于LRP是NP-Hard的，因而用精確算法求解LRP是十分困難的，求解規(guī)模也十分小，用精確算法求解LRP的文獻(xiàn)十分的少，隨著實(shí)際問題越來越復(fù)雜，最近幾年很少有人研究精確算法求解，精確算法的研究一般是在早期的文獻(xiàn)里。主要有：整數(shù)規(guī)劃（IntegerProgramming）。在解決LRP的精確算法中，整數(shù)規(guī)劃占很大的比例。主要有：Laprote和Nobert(1981)用公式描述了整數(shù)規(guī)劃并采用放寬約束條件的方法解決不受旅行長度限制的LRP，Laporteetal(1983,1986)使用類似的方法去解決非滿載或滿載的多設(shè)施的LRP問題。用整數(shù)規(guī)劃解決LRP問題還有Revelleetal(1991)，Min(1996)等。動(dòng)態(tài)規(guī)劃(DynamicProgramming)。Averbankh和Berman(1994)用動(dòng)態(tài)規(guī)劃解決多分發(fā)人員的LRP。分枝定界(Branchandbound)。Laportetal(1988)用修改了的分枝定界法解決帶時(shí)間窗的非對稱的多中心的LRP；Laportetal.(1989)用此法解決固定車隊(duì)大小的隨機(jī)LRP。此外還有Daskin(1987)用此法解決了救護(hù)車的LRP。非線性規(guī)劃(Nonlinearprogramming}。Stowers和Pelekar(1993)用非線性規(guī)劃解決連續(xù)的、易損LRP。Averbankh和Berman(1995)使用非線形規(guī)劃解決帶不具體時(shí)間窗的商品分發(fā)員的LRP。此外還有GhoshetaI(1981)等。除以上幾種算法外，還有Bookbinder和Reece(1988)定義了三層多商品配送體系，建立了非線性混合整數(shù)規(guī)劃模型等。2.2啟發(fā)式算法目前，多采用啟發(fā)式方法來解決LRP問題，應(yīng)用啟發(fā)式算法可提高解題的效率，適于處理實(shí)際中較大規(guī)模的問題，并有利于對問題進(jìn)行靈敏度分析。LRP的啟發(fā)式算法一般將問題分解為若干個(gè)子問題，將這些子問題依次采用啟發(fā)式方法或精確方法來加以解決，各子問題之間存在相互依賴的關(guān)系。采用多階段分解步驟可使復(fù)雜的問題簡單化，避免產(chǎn)生局部最小化的結(jié)果。LRP的啟發(fā)式算法主要有：先解決定位-配給問題(Location-allocationfirst)，然后解決車輛路線安排問題(Route-second)，即先選址，后路徑。Jacobsen和Madsen(1978)用這種方法解決兩層報(bào)紙分發(fā)系統(tǒng)的交換點(diǎn)的帶時(shí)間窗的LRP，這兩人在(1980)用此方法與節(jié)約法解決了報(bào)紙分發(fā)的帶時(shí)間窗的LRP，Harrison(1979)用同樣的方法解決了多倉庫多車輛的隨機(jī)LRP。還有用此方法與插入法解決了多級、多設(shè)施、多車輛血庫的LRP。此外還有Nambiaretal(1981),Bookbinder和Reece(1988)等。先解決車輛路線安排問題(Route-first)，然后解決定位-配給問題(Location-allocationsecond)，即先路徑，后選址。Perl和Daskin(1984,1985)用這種方法解決了有車輛容量約束的和設(shè)施無容量約束的多設(shè)施多車輛的倉庫的LRP等。節(jié)約成本/插入。一般來說節(jié)約成本/插入算法不單獨(dú)使用，總是和其他的混合起來使用，且此算法一般用于生成路線，它是以Clarke和Wright及Rosenkrantzetal所提出的算法為基礎(chǔ)。Clarke和Wright(1964)提出的節(jié)約算法其核心思想就是將運(yùn)輸問題中存在的兩個(gè)回路合并成一個(gè)回路。改進(jìn)路線/交換。最初由Lin(1965)提出的“路線的改進(jìn)/交換”啟發(fā)式算法，也用于設(shè)計(jì)運(yùn)輸工具的行程路線，采用的方法是：可行的路線連續(xù)地改變，以便產(chǎn)生降低總成本的另一條可行路線，直至成本不可能再降低。因此，不同于降低成本/插入方法，這種啟發(fā)式算法在整個(gè)解題步驟中都要保持可行性。常見的交換算法有：k-optexchange,or-optexchange,λ-interchange,relocateexchange。其中：k-optexchange表示的是k邊交換，用的比較多的是2-optexchange和3-optexchange。用的比較多的是2-opt.exchange，它不會(huì)改變路的方向。relocateexchange表示的是不同線路點(diǎn)的交換。如圖：relocateexchange示意圖實(shí)際上是的擴(kuò)展，即一條線路上的小于等于個(gè)客戶與另一條線路的小于等于個(gè)客戶交換。參考文獻(xiàn)[1]汪壽陽,趙秋紅,夏國平.集成物流管理系統(tǒng)中定位-運(yùn)輸路線安排問題的研究[J].管理科學(xué)學(xué)報(bào),2000,6(3):69-75.[2]張長星,黨延忠.定位一運(yùn)輸路線安排問題的遺傳算法研究[J].計(jì)算機(jī)工程與應(yīng)用,2004,12,65-68.[3]Laporte,G,Nobert,Y.Anexactalgorithmforminimizingroutingandoperatingco