基于局部貪婪算法改進的物流選址-分配問題研究

摘 要：本文根據物流選址-分配兩級中轉運輸實際，首先提出了受多重能力約束的兩級設施選址-分配問題模型和兩種啟發式算法，然后用兩種算法對進口物資中轉運輸兩級設施選址-分配問題進行了研究，并根據對比研究結果對局部貪婪算法進行了改進。本文所提出的模型和改進算法，能用來解決具有相同能力約束的兩級設施選址-分配問題，或為之提供參考。

關鍵詞：貪婪算法;物流;選址-分配

在物流實踐中，有許多的進出口物資要經過兩次甚至更多次的換裝才能運抵目的地，因此，研究受多重能力約束的兩級設施選址分配問題，不僅為解決大型企業進口原材料物流系統優化奠定基礎，而且也為解決相應的兩級設施選址-分配問題提供指導。

本文研究的受多重能力約束的兩級設施選址-分配問題，在將節點和邊同時都帶最大和最小單批容量轉化為邊帶最大和最小單批容量的基礎上，考慮物流網絡在邊的最大單批容量和最小單批容量、物流中心吞吐能力和運輸工具總運輸能力等多重能力約束下，如何進行中轉運輸的物流中心選址和相關資源分配，使總的費用最小。即本文研究的受多重能力約束的兩級設施選址分配問題，是考慮邊的帶最大和最小單批容量的受多重能力約束的兩級設施選址-分配問題，模型假設網絡系統滿足一個條件，即物品只能用不同運輸工具經過某兩級物流中心節點進行中轉運輸。

一、局部貪婪算法的改進

基于Dijkstra最短路法的全貪婪算法并不是最優的。通常局部貪婪算法所求得解不及最短路法所求得的解[4]。通過對相關求解過程的分析發現，以上提出的局部貪婪算法，既未完全優先選用平均單位運費較高的節點上單位變動費用較低的物流通路作為運輸路線，又未能將單位運費低的運輸工具的安排在其最具優勢的運輸路線上。針對以上問題，本文提出的局部貪婪算法進行改進，主要的改進體現在物流通路選取中物流文點的優先次序方面，即用“平均離差較大的一級文點（中轉文點或需求文點）的平均單位變動費用從高到低的文點順序”代替“物流中心文點數多的一級物流中心文點的平均單位變動費用從高到低的文點順序”。改進后的局部貪婪算法的簡要步驟如下：

第一階段，中轉站選址

1.計算邊能通行的運輸工具的平均單位運費。

2.分級計算各物流中心文點和需求文點物流通路的平均單位變動費用。平均單位變動費用包括物流通路各邊的平均單位運輸、各中轉文點的單位變動費用之和。

3.分級選取物流中心文點并初步選取其吞吐量。各級物流中心文點選取的方法、步驟及添加文點的要求同。分級計算物流中心文點和需求文點的物流通路平均單位變動費用的平均離差。如果需求文點的平均單位變動費用大于各級物流中心文點的平均單位變動費用離差，則已選取的全部物流中心文點的吞吐量為其全部吞吐能力。

第二階段，資源和運輸量分配

1.確定已選取的物流中心文點所連接的邊能通行的運輸工具，并計算其物流通路在不同的運輸工具組合下的單位運費。

2.分配資源和運輸量

分配資源和運輸量的方法。在已選取的物流中心文點及已選用的吞吐量范圍內，在供應文點的剩余供應量、物流中心文點的剩余吞吐能力和需求文點的剩余需求量均大于0的物流通路中，依平均離差較大的一級文點（中轉文點或需求文點）的平均單位變動費用從高到低的文點順序，依次選用單位運費低的物流通路作為運輸路線，按整車（船）運輸的原則，選取該運輸路線中物流中心文點的剩余吞吐能力、供應文點的剩余供應量、需求文點的剩余需求量和相應運輸工具的剩余運輸能力中的最小值作為該運輸路線中各運輸工具在相應文點間的運輸量。按此方法重復進行迭代，直到滿足需求。此步驟同時確定了決策變量y^r_ij的取值（若則x^r_ij>0則y^r_ij=1;反之y^r_ij=0）。

如果已選取的物流中心文點所連接的邊a_ij（a_ij=能通行的運輸工具的總運輸能力小于該文點所選取的吞吐能力，則將該文點剩余的吞吐能力轉移至已選取的同級物流中心文點中平均單位運費最大的物流中心文點，重新進行第五步。

如果已選取的物流中心文點中平均單位運費最大的文點沒有剩余吞吐能力，或者其剩余吞吐能力比擬轉移的吞吐能力小，則返回第四步添加同級物流中心文點。新添加的同級物流中心文點的吞吐能力為擬轉移的吞吐能力與已選取的物流中心文點中平均單位運費最大的文點的剩余吞吐能力的差值。

3.計算各運輸工具在各條邊上的運輸量。

4.計算目標函數值。

二、結論

本文的研究，一方面，注重模型的針對性，相關算法的快捷，另一方面，注意模型與算法的普遍適用性，力求為設施選址與運輸決策的綜合研究與應用提供理論和應用上的鋪墊。研究成果對相關企業進行物流系統設計或日常物流運營具有指導或參考價值。

參考文獻

[1] 楊珺，楊超，馬云峰.帶有雙重容量限制的FIP問題研究[J].中國公路學報，2004（4）：88-91.

[4] 邢文訓，謝金星.現代優化計算方法[M].北京：清華大學出版社， 2003，2.

【作者簡介】 王銳（1967—），女，大專，研究方向：企業經營管理。