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

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