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

關(guān)鍵詞：貪婪算法;物流;選址-分配

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

本文研究的受多重能力約束的兩級設(shè)施選址-分配問題，在將節(jié)點和邊同時都帶最大和最小單批容量轉(zhuǎn)化為邊帶最大和最小單批容量的基礎(chǔ)上，考慮物流網(wǎng)絡(luò)在邊的最大單批容量和最小單批容量、物流中心吞吐能力和運輸工具總運輸能力等多重能力約束下，如何進(jìn)行中轉(zhuǎn)運輸?shù)奈锪髦行倪x址和相關(guān)資源分配，使總的費用最小。即本文研究的受多重能力約束的兩級設(shè)施選址分配問題，是考慮邊的帶最大和最小單批容量的受多重能力約束的兩級設(shè)施選址-分配問題，模型假設(shè)網(wǎng)絡(luò)系統(tǒng)滿足一個條件，即物品只能用不同運輸工具經(jīng)過某兩級物流中心節(jié)點進(jìn)行中轉(zhuǎn)運輸。

一、局部貪婪算法的改進(jìn)

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

第一階段，中轉(zhuǎn)站選址

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

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

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

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

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

2.分配資源和運輸量

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

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

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

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

4.計算目標(biāo)函數(shù)值。

二、結(jié)論

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

參考文獻(xiàn)

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

[4] 邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計算方法[M].北京：清華大學(xué)出版社， 2003，2.

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