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

李貴華,黃 敏

(1.東北大學(xué)信息科學(xué)與工程學(xué)院流程工業(yè)綜合自動(dòng)化國(guó)家重點(diǎn)實(shí)驗(yàn)室,沈陽(yáng)110819;

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

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

李貴華1,2,黃 敏1

(1.東北大學(xué)信息科學(xué)與工程學(xué)院流程工業(yè)綜合自動(dòng)化國(guó)家重點(diǎn)實(shí)驗(yàn)室,沈陽(yáng)110819;

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

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

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

1 概述

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

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

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

2 問(wèn)題描述與建模

2.1 第四方物流路徑問(wèn)題

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

圖1 第四方物流路徑問(wèn)題的多重圖模型

圖2 基于多種運(yùn)輸方式的兩點(diǎn)間多重圖模型

2.2 模型建立

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

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

Df為任務(wù)f的貨運(yùn)量;K為客戶要求的信譽(yù);Tf為任務(wù)f的時(shí)間期限。

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

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

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

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

3.1 MMAS數(shù)學(xué)模型

信息素全局更新公式為:

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

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

3.2 蟻群算法步驟

蟻群算法步驟如下:

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

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

Step4令螞蟻禁忌表索引號(hào)q=1,f=1。

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

Step6t=t+1。

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

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

Step9若禁忌表Tabuqf中包含了目的節(jié)點(diǎn),在路徑表Rqf中會(huì)獲得一條完成某一任務(wù)的可行路徑,轉(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在所有生成的可行解中,找出目標(biāo)函數(shù)最優(yōu)解和最優(yōu)螞蟻組。

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

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

4 算例驗(yàn)證

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

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

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

圖4 各種運(yùn)輸方式間的轉(zhuǎn)換費(fèi)用和時(shí)間

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

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

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

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

任務(wù)3:R3=1,12,2,12,8,12,12,21,15};

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

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

5 結(jié)束語(yǔ)

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

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

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

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

［4]范志強(qiáng),莊佳芳.基于多維權(quán)有向圖的多式聯(lián)運(yùn)中運(yù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]熊桂武.具有模糊時(shí)間窗的多模式聯(lián)運(yùn)建模及優(yōu)化［J］.工業(yè)工程,2012,15(4):7-11

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

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

［11]陳 琪,寧 博.MMAS在帶時(shí)間窗的車(chē)輛路線問(wèn)題中的應(yīng)用［J］.江蘇科技大學(xué)學(xué)報(bào):自然科學(xué)版,2009, 23(3):263-266.

［12]張兆軍,馮祖仁,陳竹青.簡(jiǎn)化蟻群算法［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ùn)輸方式的第四方物流路徑優(yōu)化算法［J］.計(jì)算機(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

國(guó)家自然科學(xué)基金資助項(xiàng)目(71071028);國(guó)家杰出青年科學(xué)基金資助項(xiàng)目(71325002,61225012);高等學(xué)校博士學(xué)科點(diǎn)專(zhuān)項(xiàng)科研基金資助項(xiàng)目(20120042130003,20110042110024);中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)基金資助項(xiàng)目(N110204003,N120104001);流程工業(yè)綜合自動(dòng)化國(guó)家重點(diǎn)實(shí)驗(yàn)室基礎(chǔ)科研業(yè)務(wù)費(fèi)基金資助項(xiàng)目(2013ZCX11)。

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

2014-04-04

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