李貴華,黃 敏

(1.東北大學信息科學與工程學院流程工業(yè)綜合自動化國家重點實驗室,沈陽110819;

2.沈陽工業(yè)大學管理學院,沈陽110870)

考慮多種運輸方式的第四方物流路徑優(yōu)化算法

李貴華1,2,黃 敏1

(1.東北大學信息科學與工程學院流程工業(yè)綜合自動化國家重點實驗室,沈陽110819;

2.沈陽工業(yè)大學管理學院,沈陽110870)

綜合運用不同運輸方式的技術(shù)和經(jīng)濟特點實施聯(lián)合運輸,是滿足貨主降低運輸費用和時間要求的有效措施。為此,針對不同運輸主體,提出多種運輸方式的優(yōu)化組合算法,以實現(xiàn)在滿足客戶運輸要求的前提下,綜合選擇運輸方式、第三方物流服務商及運輸路徑。將不同第三方物流服務商多種運輸方式的優(yōu)化選擇與路徑選擇相結(jié)合,建立單源點到單目地點完成多項任務的第四方物流路徑優(yōu)化模型,設計模型求解的最大最小螞蟻系統(tǒng)。實例計算結(jié)果表明,該算法能方便有效地求解考慮多種運輸方式的第四方物流路徑問題,為第四方物流企業(yè)決策提供參考。

路徑優(yōu)化;最大最小螞蟻系統(tǒng);第四方物流;多種運輸方式;蟻群優(yōu)化算法

1 概述

第四方物流(the fourth Party Logistics,4PL)是從外協(xié)的第三方物流(the third Party Logistics,3PL)演變成分享協(xié)作而出現(xiàn)的一種新的物流形式。4PL服務商通過有效整合供應鏈中的各種資源,能增加供應鏈的價值［1］。

4PL服務商在整合供應鏈資源進行優(yōu)化決策時,其中的關(guān)鍵問題是運輸路徑選擇、運輸方式選擇及3PL服務商的選擇。許多學者在這一領(lǐng)域進

行了相關(guān)的研究［2-4］,但這些研究一部分只是考慮了3PL服務商的單一運輸方式,忽略了不同運輸方式所具有不同的技術(shù)經(jīng)濟特點。如文獻［5］采用遺傳算法求解了單一運輸方式的第四方物流路徑問題;文獻［6］建立了考慮單一運輸方式的單任務的4PL路徑優(yōu)化模型并運用免疫算法進行了求解。另一部分是僅從多式聯(lián)運的角度進行研究,未能綜合考慮不同3PL服務商的服務能力及服務規(guī)模的效果。如文獻［7］提出了一個啟發(fā)式算法對利比亞半島區(qū)域內(nèi)的貨物進行了公路運輸和鐵路運輸?shù)膬?yōu)化。文獻［8］建立了具有模糊時間窗的多種運輸模式聯(lián)運的模型,并采用混合田口遺傳算法進行了路徑的優(yōu)化。文獻［9］也對基于多種傳輸方式的4PL路徑問題進行了深入研究。這些研究針對其特定的問題均給出了求解方法,但上述研究難以從綜合角度實現(xiàn)第四方物流的組合最優(yōu)化。為此,本文在文獻［9］研究的基礎上,針對考慮多種運輸方式的多任務4PL路徑優(yōu)化問題,提出一種優(yōu)化組合算法。

2 問題描述與建模

2.1 第四方物流路徑問題

假設4PL公司承接了多項運輸任務,運輸網(wǎng)絡用多重圖G(V,E)表示,如圖1和圖2所示。從源點v1到目的點v15,中途經(jīng)過若干個城市,任意相鄰的2個城市之間都可能存在多個3PL供應商,每個3PL供應商都可能有多種運輸方式可供選擇。當從一種運輸方式轉(zhuǎn)換到另一種運輸方式時,需要一定的中轉(zhuǎn)時間和中轉(zhuǎn)費用,而且在整個運輸過程中完成各項任務的時間不能超過其運輸期限。在綜合上述各種因素之后,確定最佳的3PL供應商和運輸組合方式,使總運費最低。

圖1 第四方物流路徑問題的多重圖模型

圖2 基于多種運輸方式的兩點間多重圖模型

2.2 模型建立

設在任意2個城市間只能選擇一個4PL服務商的一種運輸方式,運輸方式的轉(zhuǎn)換只能在城市所對應的節(jié)點處發(fā)生。模型參數(shù)及變量描述如下:

表示i,j兩點間供應商的數(shù)量(i,j=1,2,…,n);

Df為任務f的貨運量;K為客戶要求的信譽;Tf為任務f的時間期限。

建立的數(shù)學模型如下:

在上述模型中,式(1)為目標函數(shù),表示實現(xiàn)整個運輸過程中的運輸總成本的最小化,其中運輸成本由運費和中轉(zhuǎn)費用2個部分組成;式(2)表明完成每一任務的貨物運輸必須在規(guī)定期限Tf內(nèi)運到;式(3)表示對于完成各項任務所選擇的物流公司的該種運輸方式的運輸能力應大于客戶要求的運輸能力Df;式(4)表明對于完成各項任務所選擇路徑的節(jié)點的吞吐能力應大于客戶要求的能力Df;式(5)表示完成各項任務所選擇的物流公司的信譽指標應大于客戶要求的指標K;式(6)保證Rf是一條以vs為起點,vt為終點的合法路徑。

3 最大最小螞蟻系統(tǒng)

蟻群算法是意大利學者Dorigo等人提出的一種模擬螞蟻群體覓食行為方式的仿生優(yōu)化方法,該方法及其改進算法解決了許多復雜優(yōu)化和經(jīng)典NP-C問題。文獻［10］提出了基于選路優(yōu)化的改進蟻群算法,該算法通過減少基本蟻群算法中的選路次數(shù),提高算法的執(zhí)行效率。文獻［11］運用最大最小蟻群算法求解了帶時間窗的車輛路線問題。文獻［12］提出了簡化蟻群算法解決了最大最小蟻群算法中信息素下界難以確定的問題,并通過旅行商問題驗證算法的有效性。在眾多的改進蟻群算法中,最大最小螞蟻系統(tǒng)(Max-Min Ant System,MMAS)是其中應用比較廣泛蟻群算法,在實際的應用中也取得了很好的效果。為此,本文采用MMAS求解單源點到單目地點的多任務的考慮多種運輸方式的第四方物流路徑優(yōu)化問題。

3.1 MMAS數(shù)學模型

信息素全局更新公式為:

其中,Const為一常數(shù),表示螞蟻循環(huán)一周在經(jīng)過的路徑上所釋放的信息素總量;Z(q?)代表本代中費用最低的最優(yōu)螞蟻組所經(jīng)過路徑的總費用。

其含義為:當?shù)玫降闹敌∮?時,取0;得到的值大于零時則取其實際差值。

3.2 蟻群算法步驟

蟻群算法步驟如下:

Step2將F×Q只螞蟻放在初始節(jié)點上。

Step3循環(huán)次數(shù)Nc←Nc+1。

Step4令螞蟻禁忌表索引號q=1,f=1。

Step5令t=0,把初始節(jié)點依次放入到Tabuqf和路徑表Rqf中。

Step6t=t+1。

Step7根據(jù)狀態(tài)轉(zhuǎn)移概率式(7)計算第q組完成任務f的螞蟻從節(jié)點i到節(jié)點j選擇第k供應商的第l種運輸方式的概率(以弧的選擇概率來確定節(jié)點的選擇概率)。

Step8選擇具有最大狀態(tài)轉(zhuǎn)移概率的弧對應的節(jié)點,將螞蟻移動到該節(jié)點,并把該節(jié)點計入禁忌表Tabuqf中;將選擇的弧和節(jié)點順序計入路徑表Rqf中。

Step9若禁忌表Tabuqf中包含了目的節(jié)點,在路徑表Rqf中會獲得一條完成某一任務的可行路徑,轉(zhuǎn)到Step10;否則轉(zhuǎn)到Step6。

Step10令f=f+1,如果f≤F,轉(zhuǎn)到Step5;否則,轉(zhuǎn)到Step11。

Step11令q=q+1,如果q≤Q,轉(zhuǎn)到Step5,否則,轉(zhuǎn)到Step12。

Step12在所有生成的可行解中,找出目標函數(shù)最優(yōu)解和最優(yōu)螞蟻組。

Step13對最優(yōu)螞蟻組經(jīng)過的路徑,根據(jù)式(8)～式(12)進行信息素的更新。

Step15若Nc＜Ncmax,則清空禁忌表和路徑記錄表轉(zhuǎn)到Step3;否則,停止迭代輸出最優(yōu)路徑及結(jié)果。

4 算例驗證

為了驗證本文提出的模型和算法的有效性,設計了一個仿真算例對其進行驗證,算法用Virtual studio 2008,Access 2003實現(xiàn),并在3.4 GHz Intel Core PC機上運行。

假設某第四方物流公司承接了4項運輸任務,要求將貨物從城市1送到城市15,運輸網(wǎng)絡如圖1、圖2所示,所選定的2個供應商分別能提供3種運輸方式可供選擇,假設4項任務的運量和時間期限分別為:5和40;6和45;10和50;15和43,其他數(shù)據(jù)經(jīng)過預處理如圖3和圖4所示。

圖3 運輸網(wǎng)絡圖中相鄰節(jié)點間弧的數(shù)據(jù)

圖4 各種運輸方式間的轉(zhuǎn)換費用和時間

圖3中形如a/b/c的數(shù)據(jù),a為單位費用,b為時間,c為能力;圖4中數(shù)據(jù)的分子為轉(zhuǎn)換費用,分母為轉(zhuǎn)換時間。

通過多次試驗,各參數(shù)取值分別為Q,Nc,α,β,Const,ρ=(10,400,3,3,100,0.35)時,得到的最優(yōu)路徑是:

任務1:R1={1,23,3,13,5,13,10,13,14,13,15};

任務2:R2={1,23,2,13,8,13,12,22,15};

任務3:R3=1,12,2,12,8,12,12,21,15};

任務4:R4={1,13,3,22,7,22,11,12,15}。

其中,R1所需作業(yè)時間為36;R2所需作業(yè)時間為38;R3所需作業(yè)時間為50;R4所需作業(yè)時間為41,完成4項任務所需的總運費為3 417。計算結(jié)果表明基于本文建立的模型及優(yōu)化算法,可以在滿足客戶運輸時間要求的前提下,得到最經(jīng)濟的運輸路徑、運輸方式和3PL供應商的組合,可以為4PL服務商提供決策依據(jù)。

5 結(jié)束語

不同的運輸方式有不同的技術(shù)和經(jīng)濟特點,綜合運用不同運輸主體的各種運輸方式,對降低貨物運輸?shù)某杀?、保障貨物運輸?shù)馁|(zhì)量和時間要求具有重要的意義。本文建立了考慮多種運輸方式的單源點到單目地點的多任務第四方物流路徑優(yōu)化模型,提出了求解該問題的MMAS,并通過算例驗證了該算法求解第四方物流路徑優(yōu)化問題的有效性。但本文未考慮同時承擔多項運輸任務的費用折扣問題,這有待今后進一步研究。

［1]Christopher M.Logistics and Supply Chain Management［M］.New York,USA:Free Press,1994.

［2]陳建清,劉文煌,李 秀.第四方物流中決策支持系統(tǒng)及物流方案的優(yōu)化［J］.計算機工程,2004,30(5):150-153.

［3]王 濤,王 剛.一種多式聯(lián)運網(wǎng)絡運輸方式的組合優(yōu)化模式［J］.中國工程科學,2005,7(10):46-50.

［4]范志強,莊佳芳.基于多維權(quán)有向圖的多式聯(lián)運中運輸方式的選擇研究［J］.物流技術(shù),2006,25(5):47-48.

［5]Chen J Q,WangS,LiX,etal.DirectedGraph Optimization Model and Its Solving Method Based on Genetic Algorithm in Fourth Party Logistics［C］// ProceedingsofIEEEInternationalConferenceon System,Man and Cybernetics.Washington D.C.,USA: IEEE Press,2003:1961-1966.

［6]Min Huang,Wei Tong,Qing Wang.Immune Algorithm BasedRoutingOptimizationinFourth-partyLogistics［C］//ProceedingsofIEEEWorldCongresson Computational Intelligence.Washington D.C.,USA:IEEE Press,2006:3029-3034.

［7]Arnold P,Peeters D,Thomas I.Modeling a Rail/Road Intermodal Transportation System［J］.Transportation Research,Part E,2004,40:255-270.

［8]熊桂武.具有模糊時間窗的多模式聯(lián)運建模及優(yōu)化［J］.工業(yè)工程,2012,15(4):7-11

［9]李貴華,柴偉莉,玄 雪.基于多種運輸方式的第四方物流路徑問題研究［J］.物流技術(shù),2010,29(1):72-74.

［10]張 毅,梁艷春.基于選路優(yōu)化的改進蟻群算法［J］.計算機工程與應用,2007,43(2):60-63.

［11]陳 琪,寧 博.MMAS在帶時間窗的車輛路線問題中的應用［J］.江蘇科技大學學報:自然科學版,2009, 23(3):263-266.

［12]張兆軍,馮祖仁,陳竹青.簡化蟻群算法［J］.控制與決策,2012,27(9):1325-1330.

編輯 金胡考

The Fourth Logistics Routing Optimization Algorithm Considering Multiple Transportation Modes

LI Guihua1,2,HUANG Min1
(1.State Key Laboratory of Synthetical Automation for Process Industries,
College of Information Science and Engineering,Northeastern University,Shenyang 110819,China;
2.School of Management,Shenyang University of Technology,Shenyang 110870,China)

To use comprehensively different transport modes and combined transport are effective to decrease transportation cost and time.Therefore,this paper provides a solution for the combinational optimization of multiple transport modes.The solution selects comprehensively transport modes,logistics suppliers and transport routes on the premise of meeting transportation need.This paper integrates the optimization selection of multiple transport modes and path selection,establishes the route optimization model for multitasking from one origination to one destination in the fourth Party Logistics(4PL),and proposes the solution of Max-Min Ant System(MMAS).The results of experiments show that,the route optimization problem based on the selection of multiple transport modes in the 4PL can be solved by MMAS conveniently and effectively,which can be consulted by 4PL companies.

path optimization;Max-Min Ant System(MMAS);the fourth Party Logistics(4PL);multiple transportation modes;Ant Colony Optimization(ACO)algorithm

李貴華,黃 敏.考慮多種運輸方式的第四方物流路徑優(yōu)化算法［J］.計算機工程,2015,41(3):273-277.

英文引用格式:Li Guihua,Huang Min.The Fourth Logistics Routing Optimization Algorithm Considering Multiple Transportation Modes［J］.Computer Engineering,2015,41(3):273-277.

1000-3428(2015)03-0273-05

:A

:TP29

10.3969/j.issn.1000-3428.2015.03.051

國家自然科學基金資助項目(71071028);國家杰出青年科學基金資助項目(71325002,61225012);高等學校博士學科點專項科研基金資助項目(20120042130003,20110042110024);中央高校基本科研業(yè)務費專項基金資助項目(N110204003,N120104001);流程工業(yè)綜合自動化國家重點實驗室基礎科研業(yè)務費基金資助項目(2013ZCX11)。

李貴華(1973-),女,副教授、碩士,主研方向:物流系統(tǒng)優(yōu)化;黃 敏,教授、博士。

2014-04-04

:2014-05-19E-mail:gao_yining@126.com