濮明月，張彥如

(1.安徽新華學院 商學院，安徽 合肥 230088；2.合肥工業(yè)大學 機械工程學院，安徽 合肥 230009)

物流配送是物流系統(tǒng)中的重要環(huán)節(jié)，在企業(yè)配送過程選擇一個合理的路徑規(guī)劃能夠降低物流成本，提高自身的核心競爭力，尤其是生鮮等容易腐敗產(chǎn)品的運送，冷鏈運輸成本較高，如果路徑規(guī)劃不當，會造成很大的貨損和較高的運輸成本，因此對物流配送車輛路徑進行優(yōu)化十分必要[1-2].

在傳統(tǒng)的路徑優(yōu)化方法中，僅僅考慮到運輸過程中的成本和損耗，忽略了客戶時間窗約束產(chǎn)生的懲罰成本，導(dǎo)致物流路徑的優(yōu)化效果并不理想，因此設(shè)計一種基于改進蟻群算法的物流配送車輛路徑優(yōu)化方法.引入時間窗的懲罰機制，科學、合理地解決物流配送路徑優(yōu)化問題，對物流配送車輛路徑進行合理規(guī)劃，盡量減少配送過程中的懲罰成本和貨損成本，壓縮運輸損失.

1 物流配送車輛路徑優(yōu)化方法

1.1 蟻群算法的改進

蟻群算法實際上是模仿螞蟻的覓食行為來尋找最優(yōu)路徑，基于蟻群的個體數(shù)量龐大，它們之間通過信息素進行溝通，為同伴傳遞信息，大量的螞蟻形成一個反饋系統(tǒng)，因而具有較高的效率和時間復(fù)雜度，有效解決了尋找食物的問題[3-4].研究的是物流車輛的路徑優(yōu)化，主要目標是縮短配送距離，降低成本，為企業(yè)創(chuàng)造更高的利潤.蟻群算法是一種基于種群的進化算法，將其應(yīng)用在路徑優(yōu)化中，剛開始所有的蟻群會選擇不同的路徑尋找食物，在搜索過程中，蟻群會靠信息素進行溝通，選擇較優(yōu)的路徑進行二次食物尋找，如此反復(fù)迭代，會尋找到一條最優(yōu)路徑，其路徑搜索過程如圖1所示.

圖1 蟻群覓食路徑擇優(yōu)過程

蟻群算法具有很好的搜索能力，但是它的初始信息速匱乏，收斂速度比較慢，因此將蟻群算法和遺傳算法相結(jié)合，提出改進的混合蟻群算法進行迭代求解.結(jié)合蟻群算法，得到路徑優(yōu)化問題的算法流程，如圖2所示.

圖2 改進蟻群算法流程

以上算法的改進主要體現(xiàn)在信息素的更新步驟上.

主要待解決問題的目標為路徑的最優(yōu)解.為更新信息素，假定蟻群中的蟻群數(shù)量為n，物流配送終點客戶z和x的距離為dzx，且設(shè)定為客戶之間的親密程度，即為可見度.在某時刻t的某蟻群到z客戶之間的不可逆移動概率計算公式為：

(1)

公式(1)中，B為蟻群沒有達到的客戶集合，根據(jù)這個過程的不斷調(diào)整，得到路徑的信息素更新結(jié)果為：

(2)

公式(2)中的β為信息殘留程度.

在路徑信息素的更新基礎(chǔ)上，建立在基因編碼上進行遺傳算法的選擇、交叉和編譯3個遺傳操作.采用模仿染色體編碼的方法對配送路徑進行編碼，得到一組自然數(shù)組成的配送方案編碼，選擇的核心思想是復(fù)制，復(fù)制繼承父代中的最優(yōu)解繼續(xù)改進，避免優(yōu)質(zhì)解丟失，交叉可以產(chǎn)生新個體，增加多樣性，防止早熟停滯，對最優(yōu)個體進行變異操作，保存最優(yōu)解.

1.2 基于改進蟻群算法的物流配送車輛路徑優(yōu)化建模

路徑優(yōu)化問題中，主要包括物流配送中心、需求地點、貨物、車輛、約束條件和目標函數(shù)等要素構(gòu)成.在實際的物流配送過程中，會存在一個車輛實際載重問題，假設(shè)在一次配送過程中，有K輛車共同配送到N個需求地點，第i個地點對于運送貨物的需求量為mi，每輛車的最大載重設(shè)為Q，需求點i到需求點j的距離表示為dij，車輛的平均行駛速度為s，需求點i要求貨物到達的最早時間表示為ai，要求貨物到達的最晚時間表示為bi，第i輛車的配送路線上需求點的數(shù)量表示為nk，那么研究問題最優(yōu)蟻群目標函數(shù)可以表示為：

(3)

若第k輛車從需求點i行駛到了到需求點j，那么xijk的值為1，否則為0[5-6].針對上述的目標函數(shù)做出假設(shè)，設(shè)定的配送中心僅有一個且位置確定不變，配備足夠的產(chǎn)品和物流配送車輛，所有的配送車輛都需要送配送中心出發(fā)，最后再返回配送中心，方便對物流車輛進行下一次的調(diào)度管理，所有的需求點位置已知且固定不變，根據(jù)上述條件，能夠得到目標函數(shù)的約束條件為：

(4)

公式(4)中L為客戶總數(shù).在配送過程中，若第k輛車完成需求點i的配送服務(wù)，那么yik的取值為1，否則為0[7-8].在約束條件中，對配送過程進行相關(guān)的配送約束，約束條件中的第1個約束公式表示每個需求點有且僅有1次配送服務(wù)，也就是說只能由一輛車進行配送；第2個約束公式表示每輛車的配送路線上所有需求點的貨物需求量總和不能超過車輛的最大載重；第3個公式表示配送車輛的出發(fā)地點都必須在配送中心；第4個公式表示配送車輛完成配送后都必須回到配送中心.

1.3 物流配送成本

在物流配送的過程中，為保證配送物品的新鮮與完整，配送的成本一般包括固定成本和變動成本.固定成本主要是指與車輛有關(guān)的購置費、折舊費以及開車司機和裝卸工人的工資等，固定成本是在進行配送服務(wù)之前就已經(jīng)產(chǎn)生了，與后續(xù)的配送路程沒有關(guān)系，且固定成本是由配送車輛的數(shù)目決定的[9-11].變動成本包含的項目比較多，主要包括運輸成本、貨損成本、懲罰成本以及生鮮類商品需要冷鏈運輸?shù)闹评涑杀綶12-13].對物流配送車輛路徑進行優(yōu)化的主要目的就是要降低變動成本，其中的運輸成本主要是指商品在運輸過程中所產(chǎn)生的費用，包括燃油費以及制冷費等與車輛行駛的距離和時間成正比，可以表示為：

(5)

式(5)中，B代表所有需求點的集合；U代表所有車輛的集合；Ck表示運輸車輛單位里程的運輸成本.當車輛k從需求點i行駛到需求點r時，zirk為1，否則為0,貨損成本可以表示為：

(6)

式(6)中，ρ1表示配送產(chǎn)生的貨損比例；ρ2表示卸貨貨損比例；C0表示單位商品的價值；tirk表示車輛k從需求點i到r的行駛時間.當車輛k完成對需求點r的配送時，yrk為1，否則為0.制冷成本可以表示為[14-15]：

(7)

式(7)中，α0表示車體劣化程度；E為熱傳導(dǎo)率；Sout、Sin分別表示車體的外、內(nèi)表面積；Tout、Tin分別表示車體的外、內(nèi)溫度；p為制冷劑價格.運送的懲罰成本可以表示為：

C5=δC0Mi.

(8)

式(8)中，δ為懲罰因子；Mi表示需求點i的缺貨數(shù)量.根據(jù)上述的成本計算公式，能夠清晰地計算出物流配送過程中的固定成本和變化成本.對于路徑的優(yōu)化有很好的參考作用.

至此完成基于改進蟻群算法的物流配送車輛路徑優(yōu)化.

2 算例分析

2.1 數(shù)據(jù)來源

算例分析以某連鎖生鮮經(jīng)營企業(yè)的物流配送為例，選取生鮮作為算例中的配送產(chǎn)品，由配送中心對編號1-18門店進行冷卻生鮮配送.目標是優(yōu)化配送中心生鮮的車輛配送路徑，將物流的配送成本降到最低.配送中心以及各個門店的地理位置如圖3所示：

圖3 配送中心和各個門店的地理分布圖

圖3中，標號為0的地標代表配送中心，標號1～18代表18家門店，配送中心在對各個門店進行生鮮產(chǎn)品配送時，要保證在規(guī)定時間內(nèi)送達，且需要保證供應(yīng)數(shù)量，否則會給該門店造成一定損失，配送要受到懲罰.因此在進行路徑規(guī)劃時，需要對生鮮商品需求量以及約定的服務(wù)時間窗進行設(shè)置，如表1所示.

表1 各門店生鮮商品需求量以及時間窗

2.2 實驗結(jié)果分析

在分別對算例進行100次求解后，最終得到了傳統(tǒng)文獻[3]方法和所提方法的最優(yōu)配送路徑，如圖4所示：

(a)文獻[3]方法

(b)所提方法圖4 不同配送路徑對比

圖4(a)為傳統(tǒng)方法最終得到的最優(yōu)路徑；圖4(b)為所提方法最終得到的最優(yōu)路徑.對這兩種配送路徑進行成本分析，如表2所示：

表2 路徑成本分析

在路徑分析中，考慮了5種成本進行路徑優(yōu)化，在實際應(yīng)用中的約束效果更好，得到的最優(yōu)路徑能夠明顯的節(jié)省運輸成本，提高收益；懲罰成本是從各個門店的視角出發(fā)，能夠體現(xiàn)配送滿意度.

在驗證所提方法的成本約束基礎(chǔ)上，為更直觀測試不同方法的物流配送車輛路徑的有效性，以耗時為實驗指標進行實驗結(jié)果輸出.假定本次實驗中所有物流運輸車輛的車速一致，其耗時越低，則說明其路徑越短，優(yōu)化效果越好，具體實驗結(jié)果如圖5所示：

待配送門店數(shù)量/個圖5 不同方法的路徑耗時對比

由圖5的實驗結(jié)果可以看出，隨著待配送門店數(shù)量的增多，兩種方法的路徑耗時不斷增加.但是很明顯，所提方法的耗時始終低于文獻[3]方法，且門店數(shù)量達到300個以上時，耗時的增量較小.通過以上實驗結(jié)果可以得出結(jié)論：使用設(shè)計的方法對物流配送車輛路徑進行優(yōu)化，在滿足車輛容量約束、時間窗約束和懲罰約束的情況下，能夠得到總成本最低的物流配送路徑方案.

3 結(jié) 論

物流車輛的入境規(guī)劃是物流配送的關(guān)鍵，基于傳統(tǒng)路徑規(guī)劃方法的缺陷，將蟻群算法與遺傳算法進行結(jié)合設(shè)計了一種新的物流車輛配送路徑優(yōu)化方法.實驗結(jié)果表明，所設(shè)計方法對路徑進行優(yōu)化后，能夠有效地降低變動成本.但是研究還有一些不足之處，建立的模型約束條件相對于實際情況考慮的不夠全面，例如交通方面出現(xiàn)突發(fā)狀況時，缺乏實際的調(diào)度能動性，在今后的研究中需要進一步解決.