萬?杰,魏?爽
?
基于混合算法的多目標(biāo)多式聯(lián)運(yùn)路徑選擇問題研究
萬?杰,魏?爽
(河北工業(yè)大學(xué)經(jīng)濟(jì)管理學(xué)院,天津 300401)
針對多目標(biāo)多式聯(lián)運(yùn)路徑選擇問題,在綜合分析多式聯(lián)運(yùn)現(xiàn)狀的基礎(chǔ)上,集成考慮運(yùn)輸成本、運(yùn)輸時(shí)間以及物流服務(wù)質(zhì)量3個(gè)方面因素,構(gòu)建混合整數(shù)規(guī)劃模型,其優(yōu)化的目標(biāo)是最小化運(yùn)輸成本、運(yùn)輸時(shí)間的同時(shí),最大化物流服務(wù)質(zhì)量;考慮到客戶的不同側(cè)重點(diǎn)和差異化需求,確定3個(gè)目標(biāo)的權(quán)重,設(shè)計(jì)遺傳算法和蟻群算法相結(jié)合的混合算法對模型進(jìn)行求解.以“西安—柏林”為例進(jìn)行算例分析,將所求結(jié)果與遺傳算法、蟻群算法進(jìn)行對比,結(jié)果表明:當(dāng)客戶對時(shí)間和成本重視程度較高時(shí),混合算法、遺傳算法和蟻群算法求得最優(yōu)解的迭代次數(shù)分別為164次、170次和183次,最優(yōu)路線為西安—鄭州(鐵路)—大連(鐵路)—鹿特丹(水路)—柏林(鐵路);當(dāng)客戶對時(shí)間和物流服務(wù)質(zhì)量重視程度較高時(shí),3種算法求得最優(yōu)解的迭代次數(shù)分別為112次、117次和150次,最優(yōu)路線為西安—重慶(公路)—柏林(鐵路);當(dāng)客戶對成本和物流服務(wù)質(zhì)量重視程度較高時(shí),3種算法求得最優(yōu)解的迭代次數(shù)分別為115次、120次和160次,最優(yōu)路線為西安—鄭州(鐵路)—深圳(鐵路)—鹿特丹(水路)—柏林(鐵路).研究表明:設(shè)置不同的目標(biāo)權(quán)重時(shí),模型和混合算法均能夠有效地為多目標(biāo)多式聯(lián)運(yùn)路徑選擇問題提供實(shí)用性的優(yōu)化方案和路線參考.
多目標(biāo);多式聯(lián)運(yùn);路徑問題;混合算法
隨著“一帶一路”倡議的提出和國際貿(mào)易的加大,多式聯(lián)運(yùn)在運(yùn)輸領(lǐng)域占有越來越重要的地位.多目標(biāo)多式聯(lián)運(yùn)路徑選擇問題也成為該領(lǐng)域的研究熱點(diǎn)與難點(diǎn).多式聯(lián)運(yùn)是指將貨物采用兩種或兩種以上的運(yùn)輸方式運(yùn)送到目的地.隨著物流技術(shù)的不斷發(fā)展,以及多式聯(lián)運(yùn)貨運(yùn)需求不斷增加,國內(nèi)外學(xué)者對多式聯(lián)運(yùn)的路徑優(yōu)化研究也逐漸深入.
綜合目前的研究成果,物流路徑選擇問題是多式聯(lián)運(yùn)的核心問題,即在不同的因素情況下的模型構(gòu)建和算法優(yōu)化.多式聯(lián)運(yùn)物流路徑選擇受運(yùn)輸費(fèi)用、運(yùn)輸時(shí)間、服務(wù)質(zhì)量、運(yùn)輸風(fēng)險(xiǎn)、技術(shù)水平、環(huán)境因素以及行程利用率等因素的影響[1],例如Cho等[2]選取成本和時(shí)間為目標(biāo),應(yīng)用從釜山到鹿特丹的實(shí)際運(yùn)輸路線來驗(yàn)證標(biāo)簽算法;Seo等[3]選取運(yùn)輸費(fèi)用、運(yùn)輸時(shí)間以及信心指數(shù)研究重慶到荷蘭鹿特丹的筆記本電腦出口多式聯(lián)運(yùn)路線選擇問題;付新平等[4]選取運(yùn)輸時(shí)間和運(yùn)輸費(fèi)用,研究從武漢到歐洲的國際集裝箱多式聯(lián)運(yùn)線路問題;李玉民等[5]選取運(yùn)輸時(shí)間、運(yùn)輸費(fèi)用和碳排放,構(gòu)建中多式聯(lián)運(yùn)路徑優(yōu)化的多目標(biāo)優(yōu)化模型.目前國內(nèi)外對于物流服務(wù)質(zhì)量概念界定和構(gòu)成要素還沒有統(tǒng)一的見解,最廣泛使用的以時(shí)間、地點(diǎn)、效率、倉儲為基礎(chǔ)的物流服務(wù)質(zhì)量.如Limbourg 等[6]設(shè)計(jì)了SERVQ UAL量表,將物流服務(wù)質(zhì)量劃分為4個(gè)維度,用越南峴港市的200家物流客戶進(jìn)行實(shí)證研究;鄭茜[7]將運(yùn)輸時(shí)效性作為物流服務(wù)質(zhì)量指標(biāo),構(gòu)建多式聯(lián)運(yùn)優(yōu)化模型.對于多式聯(lián)運(yùn)路徑選擇優(yōu)化研究的求解算法多為啟發(fā)式算法,其中包括蟻群算法[8]、遺傳算法[9]、模擬退火算法[10]和聲搜索算?法[11]等,目前國內(nèi)外對于多式聯(lián)運(yùn)混合算法的研究較少,Wang等[12]研究了集裝箱多式聯(lián)運(yùn)系統(tǒng)中集裝箱類型的選擇和運(yùn)輸方式的組合優(yōu)化,構(gòu)建了模糊需求下運(yùn)輸成本最小化的數(shù)學(xué)模型,并利用改進(jìn)的粒子-蟻群優(yōu)化算法進(jìn)行求解;Jiang等[13]研究了尋求運(yùn)輸成本、轉(zhuǎn)運(yùn)費(fèi)用等最小化的多式聯(lián)運(yùn)運(yùn)輸方案選擇問題,并提出采用混合交叉熵算法來對模型進(jìn)行求解.
通過以上國內(nèi)外文獻(xiàn)的研究發(fā)現(xiàn),多數(shù)研究成果考慮運(yùn)輸成本、運(yùn)輸時(shí)間建立模型,且少有文獻(xiàn)考慮多式聯(lián)運(yùn)中物流服務(wù)質(zhì)量.針對以上問題,本文綜合考慮運(yùn)輸成本、運(yùn)輸時(shí)間以及物流服務(wù)質(zhì)量3個(gè)因素,構(gòu)建混合型整數(shù)規(guī)劃模型,將遺傳算法和蟻群算法相結(jié)合對模型進(jìn)行求解,結(jié)合不同的貨物需求,求解不同的運(yùn)算結(jié)果,將混合算法的結(jié)果與蟻群算法以及遺傳算法做對比,驗(yàn)證了該算法的可行性與正確性.
圖1?傳統(tǒng)多式聯(lián)運(yùn)網(wǎng)絡(luò)
(1) 貨物的轉(zhuǎn)載只能發(fā)生在城市節(jié)點(diǎn),且在城市節(jié)點(diǎn)只能轉(zhuǎn)載一次.
(2) 貨物在運(yùn)輸途中不能分割.
(3)貨物在城市節(jié)點(diǎn)之間只能選擇一種運(yùn)輸方式.
表1?符號說明
Tab.1?Symbol description
多式聯(lián)運(yùn)選擇不同的運(yùn)輸路線會(huì)導(dǎo)致不同的服務(wù)質(zhì)量.本文使用物流服務(wù)能力系數(shù)來衡量各城市節(jié)點(diǎn)的物流服務(wù)能力.各城市節(jié)點(diǎn)依據(jù)自身資源(如基礎(chǔ)設(shè)施建設(shè)、經(jīng)濟(jì)條件和運(yùn)輸組織資源等)與各種能力(如安全性、可靠性以及便利性等)為貨物提供物流服務(wù),對于不同的城市節(jié)點(diǎn)來說,自身資源和能力越好,所提供的物流服務(wù)質(zhì)量越好.因此,綜合各城市節(jié)點(diǎn)狀況與特點(diǎn),選取基礎(chǔ)設(shè)施建設(shè)水平、經(jīng)濟(jì)發(fā)展水平以及多式聯(lián)運(yùn)物流服務(wù)水平來對城市節(jié)點(diǎn)進(jìn)行分析.
本文多目標(biāo)多式聯(lián)運(yùn)問題的混合整數(shù)規(guī)劃包括以下3個(gè)函數(shù).
(1)運(yùn)輸費(fèi)用為
(1)
?(2)
(2) 運(yùn)輸時(shí)間為
???(3)
(3) 物流服務(wù)質(zhì)量為
?(4)
其中
?(5)
?(6)
約束條件為
???? (7)
????(8)
??(9)
?(10)
蟻群算法根據(jù)螞蟻群體之間的信息傳遞達(dá)到尋優(yōu)的目的,其具有正反饋機(jī)制、分布式全局優(yōu)化的特點(diǎn),但會(huì)因?yàn)槌跗谛畔⑺貐T乏,導(dǎo)致求解速度慢.遺傳算法具有全局搜索能力,搜索過程簡單易理解,但存在對反饋信息利用不夠的問題,且當(dāng)求解到一定的范圍,會(huì)出現(xiàn)冗余迭代的現(xiàn)象,求精確解的效率低.
為了克服這兩種算法各自的缺陷,使其優(yōu)勢互補(bǔ),在算法的設(shè)計(jì)過程中,首先評估個(gè)體序值,選取前20%通過遺傳算法的隨機(jī)搜索、快速、全局收斂性產(chǎn)生初始解,為了保證種群的多樣性,在后80%的個(gè)體中隨機(jī)選取個(gè)體,共同作為新一代個(gè)體作為蟻群算法的初始信息素,然后利用蟻群算法正反饋機(jī)制與求解精確度高的特點(diǎn)來求最優(yōu)解[14].同時(shí),在混合算法中,通過合理設(shè)置遺傳算法的迭代次數(shù),避免由于過早或者過晚的迭代而影響混合算法的性能.混合算法同時(shí)發(fā)揮了遺傳算法和蟻群算法的優(yōu)勢,提高了求解效率和時(shí)間效率.混合算法流程如圖2所示.
(1)統(tǒng)一量綱:因本文3個(gè)目標(biāo)函數(shù)之間存在相互約束的關(guān)系,一個(gè)目標(biāo)結(jié)果最優(yōu)則會(huì)導(dǎo)致其他兩個(gè)目標(biāo)達(dá)不到最優(yōu),而作為一個(gè)系統(tǒng)需要考慮整體最優(yōu).所以應(yīng)將多目標(biāo)轉(zhuǎn)化為單目標(biāo)優(yōu)化,即
圖2?混合算法流程
?(11)
且對于不同的客戶和貨物,影響路徑選擇的因素對其的重要程度是不同的,例如急于交貨的貨物更注重時(shí)效性、普通大宗貨物更注重價(jià)格便宜、電子類產(chǎn)品更注重物流服務(wù)質(zhì)量等,因此不同的因素在進(jìn)行路徑選擇時(shí)擁有不同的權(quán)重.對于每一個(gè)評估者可以根據(jù)個(gè)性化的需求和重視程度確定相應(yīng)的權(quán)重.本文將敏感度進(jìn)行等級劃分:{極強(qiáng)、較強(qiáng)、一般、較弱、極弱},對應(yīng)的數(shù)值分別為{9、7、5、3、1}.
其次由于目標(biāo)函數(shù)單位不一致,需要通過統(tǒng)一量綱規(guī)范化各目標(biāo)函數(shù)
?(12)
?(13)
(2)隨機(jī)選取城市節(jié)點(diǎn)與運(yùn)輸方式,初始化條路線,并對其函數(shù)值進(jìn)行排序,并選取20%個(gè)體進(jìn)行遺傳操作,在后80%個(gè)體中隨機(jī)產(chǎn)生條個(gè)體進(jìn)入下一代.遺傳算法操作步驟如下.
步驟1?編碼.對節(jié)點(diǎn)城市和運(yùn)輸方式進(jìn)行采用二進(jìn)制編碼,具體編碼方式見圖3.每一條染色體被分為兩個(gè)部分:在城市節(jié)點(diǎn)部分,0、1變量表示是否通過該城市節(jié)點(diǎn),在運(yùn)輸方式部分,0、1、2、3表示鐵路、公路、水路和航運(yùn)4種運(yùn)輸方式.
圖3?染色體編碼示意
步驟2?選擇.為了能將更好的信息傳遞給下一代同時(shí)保證種群的多樣性,本文使用輪盤賭選擇法進(jìn)行操作.選擇概率的公式為
?(14)
步驟3?交叉.為了防止當(dāng)前群體的最優(yōu)個(gè)體在下一代發(fā)生丟失,導(dǎo)致遺傳算法不能收斂到全局最優(yōu)解,本文采用單點(diǎn)交叉方式.選擇的父輩個(gè)體通過交換部分信息,從而產(chǎn)生新的運(yùn)輸方案.詳見圖4.
101…100321…312 110010312…121
↓
101…100322…121 110010311…312
步驟4?變異.本文中采用單點(diǎn)變異方法.在隨機(jī)選取的個(gè)體中上按一定的概率改變基因,從而會(huì)產(chǎn)生新的個(gè)體.
(3)遺傳算法終止:為了保證上一代個(gè)體與蟻群算法有效的融合,在遺傳算法中設(shè)置最最大迭代次數(shù),同時(shí)在迭代過程中計(jì)算群體的進(jìn)化率,設(shè)置子代群體的最小進(jìn)化率.如果在設(shè)置的迭代次數(shù)的范圍內(nèi),群體的進(jìn)化率小于最小進(jìn)化率,則說明遺傳算法的優(yōu)化速度已經(jīng)大大降低,終止遺傳算法,進(jìn)入蟻群算法.
?(15)
步驟2?將只螞蟻放在個(gè)城市節(jié)點(diǎn)上,使只螞蟻隨機(jī)生成一個(gè)城市節(jié)點(diǎn)作為螞蟻下一個(gè)要走的城市節(jié)點(diǎn),按照概率選取第3個(gè)城市,即
(16)
步驟3?采用蟻周模型對信息素進(jìn)行更新,要求一周內(nèi)只有當(dāng)前最優(yōu)解進(jìn)行更新,路徑軌跡更新規(guī)則為
?(17)
?(18)
(4)輸出最優(yōu)解及目標(biāo)函數(shù)值.本文采用最大代數(shù)為終止條件,算法迭代到最大代數(shù)時(shí)迭代終止.
表2?3種運(yùn)輸方式所需的數(shù)據(jù)及其來源
Tab.2?Data required for the three modes of transport and their sources
表3?3種運(yùn)輸方式中轉(zhuǎn)時(shí)間以及中轉(zhuǎn)費(fèi)用
Tab.3 Transit time and transfer fee for three modes of transportation
運(yùn)輸中轉(zhuǎn)中轉(zhuǎn)時(shí)間/(h·m-1)中轉(zhuǎn)費(fèi)用/(¥·m-1) 公路—鐵路30.41219.2 鐵路—水路54.91676.4 水路—公路42.71371.6
圖5?對時(shí)間以及成本重視程度較高時(shí)3種算法的迭代示意
圖6?對時(shí)間以及物流服務(wù)質(zhì)量重視程度較高時(shí)3種算法的迭代示意
圖7?對成本以及物流服務(wù)質(zhì)量重視程度較高時(shí)3種算法的迭代示意
表4給出了3種算法的求解結(jié)果,從仿真結(jié)果可以看出,3種方法求解問題的最終結(jié)果比較一致,但混合算法具有更快的收斂能力,說明了混合算法可以得到更加合理的尋優(yōu)結(jié)果,具有更好的優(yōu)化性能.
表4?3種算法求解結(jié)果的比較
Tab.4?Comparion of the results of the three algorithms
本文構(gòu)建了綜合考慮運(yùn)輸成本、運(yùn)輸時(shí)間以及物流服務(wù)質(zhì)量的混合整數(shù)規(guī)劃模型,提出了混合算法來求解該模型,設(shè)計(jì)了西安—柏林的算例進(jìn)行測試,定量地分析了在不同重要程度下的不同運(yùn)輸方案的選擇,結(jié)果表明,當(dāng)對運(yùn)輸成本、運(yùn)輸時(shí)間以及物流服務(wù)質(zhì)量3方面的不同要求下,模型與算法能夠有效地提供優(yōu)化方案.
由于數(shù)據(jù)的限制,本文隨機(jī)生成客戶的期望與實(shí)際物流服務(wù)水平,但在實(shí)際情況下,客戶對物流服務(wù)質(zhì)量的打分可能分為多個(gè)等級,在未來的研究中,可以基于實(shí)際情況設(shè)計(jì)調(diào)查問卷對模型進(jìn)行改進(jìn)與?完善.
[1] 伍轉(zhuǎn)青. 物流企業(yè)多式聯(lián)運(yùn)運(yùn)輸線路選擇研究[J]. 鐵路采購與物流,2011,6(2):52-54.
Wu Zhuanqing. Research on selection of multimodal transport routes in logistics enterprises[J]. Railway Purchasing and Logistics,2011,6(2):52-54(in Chinese).
[2] Cho J H,Kim H S,Choi H R. An intermodal transport network planning algorithm using dynamic programming—A case study:From Busan to Rotterdam in intermodal freight routing[J]. Applied Intelligence,2012,36(3):529-541.
[3] Seo Y J,Chen F,Roh S Y. Multimodal transportation:The case of laptop from Chongqing in China to Rotterdam in Europe[J]. Asian Journal of Shipping & Logistics,2017,33(3):155-165.
[4] 付新平,何瑜莎,鄒?敏,等. 國際集裝箱多式聯(lián)運(yùn)線路選擇研究[J]. 鐵道運(yùn)輸與經(jīng)濟(jì),2017,39(12):12-17.
Fu Xinping,He Yusha,Zou Min,et al. A study on the route selection of international container transport in the multimodal scenario[J]. Railway Transport and Economy,2017,39(12):12-17(in Chinese).
[5] 李玉民,郭曉燕,楊?露. 考慮多目標(biāo)的中歐集裝箱多式聯(lián)運(yùn)路徑選擇[J]. 鐵道科學(xué)與工程學(xué)報(bào),2017,14(10):2239-2248.
Li Yumin,Guo Xiaoyan,Yang Lu. Route optimization of China-EU container multimodal transport considering various factors[J]. Journal of Railway Science and Engineering,2017,14(10):2239-2248(in Chinese).
[6] Limbourg S,Giang H T Q,Cools M. Logistics service quality:The case of Danang City[J]. Procedia Engineering,2016,142∶124-130.
[7] 鄭?茜. 低碳約束下多式聯(lián)運(yùn)路徑優(yōu)化問題研究[D]. 杭州:浙江工商大學(xué)經(jīng)濟(jì)管理學(xué)院,2017.
Zheng Qian. Research on Multi-modal Transport Path Optimization Problem under Low Carbon Constraints [D]. Hangzhou:School of Economics and Manage-ment,Zhejiang Gongshang University,2017 (in Chinese).
[8] 劉維林. 基于動(dòng)態(tài)蟻群算法的集裝箱國際多式聯(lián)運(yùn)路徑優(yōu)化研究[J]. 北京交通大學(xué)學(xué)報(bào):社會(huì)科學(xué)版,2012,11(3):57-62.
Liu Weilin. Route optimization of international multimodal container transportation based on dynamic ant colony algorithm[J]. Journal of Beijing Jiaotong University:Social Sciences Edition,2012,11(3):57-62(in Chi-nese).
[9] 龔景海,劉錫良. 基于遺傳算法的網(wǎng)格結(jié)構(gòu)優(yōu)化方法[J]. 天津大學(xué)學(xué)報(bào),2000,33(1):93-96.
Gong Jinghai,Liu Xiliang. Grid structure optimization method based on genetic algorithm[J]. Journal of Tianjin University,2000,33(1):93-96(in Chinese).
[10] 郭丹丹. 基于模擬退火混合遺傳算法的多式聯(lián)運(yùn)優(yōu)化問題的研究[D]. 大連:大連海事大學(xué)理學(xué)院,2012.
Guo Dandan. Research on Multi-modal Transport Opti-mization Problem Based on Simulated Annealing Hybrid Genetic Algorithm[D]. Dalian:School of Science,Dalian Maritime University,2012(in Chinese).
[11] 賴志柱. 和聲搜索算法優(yōu)化多時(shí)間窗多式聯(lián)運(yùn)運(yùn)輸方案[J]. 計(jì)算機(jī)應(yīng)用,2013,33(9):2640-2642,2693.
Lai Zhizhu. Harmony search algorithm for solving selec-tion ofmultimodal transportation scheme with several time windows[J]. Journal of Computer Applications,2013,33(9):2640-2642,2693(in Chinese).
[12] Wang H,Wang C. Selection of container types and transport modes for container multi-modal transport with fuzzy demand[J]. Journal of Highway & Transportation Research & Development,2012,12(3):65-74.
[13] Jiang Y,Zhang X,Wang Y. A cross-entropy method for solving selection of multimodal transportation scheme [J]. Journal of Transportation Systems Engineering and Information Technology,2012,12(5):20-25.
[14] 陳亞云,韓文濤,崔鶴平. 遺傳算法與蟻群算法的改進(jìn)融合[J]. 中國農(nóng)機(jī)化學(xué)報(bào),2014,35(4):246-249.
Chen Yayun,Han Wentao,Cui Heping. Improved fusion of genetic algorithm and ant colony algorithm[J]. Journal of Chinese Agricultural Mechanization,2014,35(4):246-249(in Chinese).
[15] 付新平,張?雪,鄒?敏,等. 基于價(jià)值量模型的中歐班列經(jīng)濟(jì)性比較分析[J]. 鐵道運(yùn)輸與經(jīng)濟(jì),2016,38(11):1-5.
Fu Xinping,Zhang Xue,Zou Min,et al. Analysis on economics of China-Europe block trains based on the value model[J]. Railway Transport and Economy,2016,38(11):1-5(in Chinese).
(責(zé)任編輯:孫立華)
Multi-Objective Multimodal Transportation Path Selection Based on Hybrid Algorithm
Wan Jie,Wei Shuang
(School of Economics and Management,Hebei University of Technology,Tianjin 300401,China)
To address the problem of multi-objective and multimodal transport path selection,a mixed integer programming model is constructed by integrating transportation cost,transportation time,and logistics service quality. The optimization goal is to minimize transportation cost and transportation time and maximize logistics service. Owing to the different priorities and needs of customers,the weights of the three targets are determined by using a hybrid algorithm that combines genetic algorithm and ant colony algorithm,to solve the model. Taking Xi’an-Berlin path as an example,the analysis result of the hybrid algorithm is compared with those of the genetic algorithm and the ant colony algorithm. The results show that when the customer pays more attention to time and cost,the hybrid algorithm,genetic algorithm,and ant colony algorithms require 164,170,and 183 iterations,respectively,to obtain the optimal solution. In this case,the optimal route is Xi’an-Zhengzhou(railway)-Dalian(railway)-Rotterdam (waterway)-Berlin(railway). When the customer pays more attention to the time and logistics service quality,the hybrid,genetic,and ant colony algorithms require 112,117,and 150 iterations,respectively,to obtain the optimal solution,and the optimal route is Xi’an-Chongqing(highway)-Berlin (railway). When the customer pays more attention to the cost and logistics service quality,the hybrid,genetic,and ant colony algorithms require 115,120,and 160 iterations,respectively,to obtain the optimal solution,and the optimal route is Xi’an-Zhengzhou(railway)-Shenzhen(railway)-Rotterdam(waterway)-Berlin (railway). The research shows that both models and hybrid algorithms can effectively provide practical optimization schemes and route references for multi-objective multimodal transport path selection problems when setting different target weights.
multi-objective;multimodal transportation;path problem;hybrid algorithm
10.11784/tdxbz201807034
U15
A
0493-2137(2019)03-0285-08
2018-07-26;
2018-09-03.
萬?杰(1972—??),女,博士,教授,jeanwan1218@163.com.
魏?爽,1224871115@qq.com.
河北省高等教育教學(xué)改革研究與實(shí)踐項(xiàng)目(2017GJJG021).
Hebei Province Higher Education Teaching Reform Research and Practice Project(No. 2017GJJG021).