基于改進遺傳算法的帶軟時間窗果蔬運輸路徑選擇問題?

李培慶何 杰▲黃永升范晨昊高海丹

(1.東南大學交通學院 南京 210096;2.東南大學自動化學院 南京 210096)

基于改進遺傳算法的帶軟時間窗果蔬運輸路徑選擇問題?

李培慶1何 杰1▲黃永升2范晨昊1高海丹2

(1.東南大學交通學院 南京 210096;2.東南大學自動化學院 南京 210096)

為了研究果蔬在運輸過程中受到的振動、沖擊和碰撞對產(chǎn)品質(zhì)量的不利影響,提出了一種包含帶軟時間窗、路面不平度和道路等級影響等因素的改進遺傳算法模型。該模型是以改進目標函數(shù)、適應度函數(shù)和交叉因子為參數(shù)設置,對配送成本進行最小優(yōu)化分析。將此模型與傳統(tǒng)OX交叉遺傳算法和組序交叉遺傳算法進行了對比,以江蘇省13個地級市之間的果蔬配送路徑為案例分析。結(jié)果表明與其傳統(tǒng)算法相比,提出的改進遺傳算法能夠?qū)Τ杀镜念A測提高15.3%。

交通管理;果蔬運輸;路徑選擇;軟時間窗;遺傳算法

0 引 言

果蔬配送與其他工業(yè)商品的運輸配送路徑相比,存在著較強的季節(jié)性、地域性、易腐性、易損性和時效性等因素,這給貯藏、運輸、銷售等物流環(huán)節(jié)帶來了較多的困難。除了果蔬易腐性和時效性外還具有較強的易損性,因為在運輸過程中的果蔬極易受到外界振動、沖擊、碰撞等,特別是粗糙的路面不平度和低等級道路很容易導致果蔬碰撞受損。此外,考慮到客戶對于產(chǎn)品的接收是一個軟時間窗,即過早運達,會造成因不能及時銷售的倉儲成本,過晚運達會造成銷售的不及時,以及果蔬的腐壞[1-4]。

針對配送車輛路徑(VRP)配送優(yōu)化問題,國內(nèi)外學者進行了諸多方法的研究和探討。文獻[1]以易腐貨物配送中時變車輛路徑問題為研究對象,提出以集成遺傳算法為優(yōu)化手段,用于搜索行駛路線問題的最優(yōu)解。文獻[2]針對果蔬運輸中遇到無法按時送達配送點的特殊情況,通過蟻群算法對其他運輸車進行路徑再規(guī)劃,得出帶時間窗的再規(guī)劃數(shù)學模型。文獻[3]采用并行遺傳算法作為易腐物品的車輛路徑問題的改進措施,通過設計交叉和變異算子,提高了算法的計算效率和性能。文獻[4]借助于RFID,GPS,GRS等現(xiàn)代科學技術,分析了在物聯(lián)網(wǎng)運輸線路調(diào)度系統(tǒng)下,解決生鮮產(chǎn)品在冷鏈物流配送下運輸路徑優(yōu)化問題,證明了基于物聯(lián)網(wǎng)的運輸線路調(diào)度系統(tǒng)是可行的。文獻[5]為了快速高效地找出最優(yōu)的聯(lián)運路徑,建立了帶有時間窗約束的多目標、多運輸方式、多貨種的Martins算法路徑選擇改進模型,進而縮小了解空間和避免了生成無效路徑。文獻[6]建立了以路徑稅收政策為強化學習導向的?；愤\輸路徑選擇的演化博弈模型,對降低危化品運輸風險具有實際意義。文獻[7]采用動態(tài)線性標定方式,對遺傳算法中的交叉算子采用大變異操作設計,建立和優(yōu)化了車輛路徑問題的數(shù)學模型,得出較為滿意結(jié)果。文獻[8-9]分析了具有易腐性的新鮮蔬菜配送特點,提出了基于禁忌搜索的啟發(fā)式算法求解策略,顯著地提高了易腐產(chǎn)品的配送效率。文獻[10-11]針對高度易腐食品和持續(xù)性食品供應鏈為研究對象,以多目標規(guī)劃模型為理論,通過進化算法權衡了配送成本情況與新鮮度之間的關系。文獻[12-13]主要對易腐性食品和農(nóng)產(chǎn)品供應鏈的配送方法進行了回顧和總結(jié)。

上述文獻采用了多類算法對運輸路徑進行了優(yōu)化分析,這為進一步研究特定條件下果蔬運輸路徑優(yōu)化問題提供了理論基礎。由于果蔬具有含水量高、保鮮期短、銷售和消費都存在很強的時效性特點,而且在運輸過程中極易受到路面不平度和低等級道路產(chǎn)生的振動與沖擊對其易損性的影響,以及選取不同運輸路徑時道路等級收費標準的影響,因此,要用科學的方法確定合理的果蔬車輛配送路線,然而產(chǎn)品過包裝又會增加運輸成本。為了解決這一類果蔬配送路徑與成本優(yōu)化問題,將針對果蔬的運輸特性,即易損性、易腐性和時效性等因素,并考慮配送中的帶軟時間窗、運輸路面不平度對果蔬質(zhì)量造成的影響及公路收費等級差異性等因素,構建了適合果蔬運輸?shù)母倪M遺傳算法的數(shù)值模型。將此模型與原始OX交叉遺傳算法和組序交叉遺傳算法進行了對比,以江蘇省13個地級市之間的果蔬配送路徑為案例分析,說明了改進后算法的有效性和可行性。

1 數(shù)學模型構建

提出了一個帶有路面不平度等級系數(shù),以及不同道路收費等級的數(shù)學模型,在這個模型里供應商要確定每個零售商所需的配送需求量,以及配送時的路徑選擇。配送的目標就是怎樣使在一次完整的配送之后所需成本最少。假設配送中心有m個同一類型的車輛,給分布在區(qū)域內(nèi)的不同的n個客戶配送貨物,每輛車的最大運輸容量和運行距離分別用L和Q表示。因此,基于總的最少成本的目標函數(shù)C可以用公式表示為

式中:qi為客戶i的果蔬需求量;δij為客戶i至客戶j之間道路路面不平度等級系數(shù),取值見表1[14-15]; dij為客戶i與客戶j 2地點距離;[TEj,TLj]為第j個客戶的接收時間窗;Tj為車輛從配送中心運行至第j個客戶地點的時間,L為不同g公路等級的每公里收費成本[16];m為配送車輛總數(shù);n為配送客戶總數(shù);Q為每輛車的最大容量;L為每輛車的最大行駛距離。

表1 道路路面不平度等級系數(shù)Tab.1 Road level and roughness evaluation coefficient萬人·km/d

式(1)中,第1項為m輛果蔬運輸車輛的固定成本,第2、3項為運輸車輛行駛消耗成本,第4項為由于路面不平度對果蔬振動與沖擊產(chǎn)生的損耗成本,第5項為運輸車輛超出客戶要求時間窗時支付的懲罰成本,目標函數(shù)是使4項之和,即總成本最小。其約束條件為

式(3)說明所有車輛均從配送中心出發(fā),完成配送后返回配送中心;式(4)保證每輛車的載重量不能大于其最大載重量;式(5)保證每個客戶僅由一輛車配送;式(6)保證每輛車的行駛距離不能大于其最大行駛距離;式(7)和(8)為客戶時間窗要求,當運輸能在時間窗內(nèi)送達,則可以由該車進行配送。

2 改進遺傳算法

2.1 遺傳算法

遺傳算法相比較于傳統(tǒng)的算法,遺傳算法從串集開始搜索,覆蓋面更大,利于從全局考慮選擇最優(yōu)方案,具有良好的并行性,能夠同時處理多個個體,即同時評估搜索空間中的多個解,減少了陷入局部最優(yōu)解的風險。遺傳算法具有自組織、自適應和自學習性。在車輛路徑選擇問題上,遺傳算法顯示出了其特有的優(yōu)勢。隨著求解規(guī)模擴大,精確算法的復雜程度和求解時間都大大增加。遺傳算法是一種具有較強魯棒性的優(yōu)化算法,擁有良好的全局搜索能力和并行性,適合解決此類運輸路徑優(yōu)化問題。

2.2 改進遺傳算法設計

2.2.1 染色體編碼方式

采用整數(shù)編碼方式,假設由m輛車完成k個客戶的配送任務,則構造1條長度為k＋m＋1的染色體,其編碼形式如:(0,i1,i2,…,ik,0,il,…, im,0)。式中:0為配送中心,ik為客戶。其意義解釋如下:第1輛車從配送中心出發(fā),經(jīng)過i1,i2,…,ik這些客戶后回到配送中心;第2輛車從配送中心出發(fā)后,經(jīng)過i1,i2,…,im客戶后回到配送中心……,k輛車1次出發(fā),完成所有的運輸任務,就構成了k條子路徑。這樣編碼的優(yōu)點在于直觀地給出了子路徑及客戶順序。

如染色體編碼為0630189025740,表示由3輛車完成9個客戶的配送任務。

車輛1的路線。配送中心(0)→客戶6→客戶3→配送中心。車輛2的路線:配送中心(0)→客戶1→客戶8→客戶9→配送中心。車輛3的路線:配送中心(0)→客戶2→客戶5→客戶7→客戶4→配送中心。

2.2.2 適應度函數(shù)

考慮到計算中會出現(xiàn)不可行解,對這些不可行解的處理可以通過引入懲罰策略。定義適應度函數(shù)Z為式中:C為目標函數(shù);M1為當一輛車的實際貨運量超過其最大承載量Q時的懲罰因子,M2為當一輛車的實際行駛距離超過其最大行駛距離L時的懲罰因子,M1和M2是2個大的正數(shù)。

2.2.3 產(chǎn)生初始種群

采用搜索啟發(fā)式方算法sweep方法將客戶分成m組,每組滿足所給出的約束條件,在每組的第一個元素前和最后一組的后面各加一個0,則組成了一個染色體編碼。例如,將9個客戶分成了3組:(6,8,1),(2,9,7),(4,5,3),則染色體編碼為0681029704530。如此可產(chǎn)生初始種群。

2.2.4 判斷停止條件

判斷迭代的代數(shù)是否為預設的N,若是,則停止進化,選出當前性能最好的染。

2.2.5 自然選擇

采用精英和比例結(jié)合的選擇策略,將每代x個染色體中的最優(yōu)染色體復制一個直接進入到下一代,下一代種群中剩下的x-1染色體采用輪盤賭選擇法產(chǎn)生。

2.2.6 染色體交叉重組

筆者在基于組序交叉的基礎上提出了一種改進的多種群的交叉方式。假設隨機選取2父體A和B,將A和B中的各組分別求交,得到一個稱為子體核心的部分,這樣保證了子體繼承父體中一些元素的相對位置,也可使各回路達到一定的均衡且不會出現(xiàn)總路程太長的情況。對于剩余的基因來說,利用貪婪法則將其相繼插到離其最近的基因之前,構成子體A’,而對于子體B’的形成,則將剩余的基因按照相反的順序插入到離其最近距離的基因之后,從而形成子體B’。

那么染色體O1的第1組、第2組與染色體O2第1組、第2組分別求交后得O1∩O2的核心為O＝{(0,1,3),(0,4,5)},待定的元素由2,6, 7,8組成。首先構成子體A’:按照2→6→7→8的順序依次插入O中。假如O中第1組離2最近的點為1距離是5,而第2組離2最近的點為4距離8,則將2放人第1組1之后,檢查是否滿足約束條件。其它元素處理的方法一樣,只是如果一個元素加人使得不滿足約束,則將它歸入另一組中,而對于子體B’的構成,則按照8→7→6→2的順序依次插入。

上述交叉方式雖然保證了核心元素的相對位置不變以及種群的多樣性,但卻對子串有著很大的破壞。為此,引入常用的類OX法與之結(jié)合,類OX法可以將交配區(qū)完整保留。并且將染色體群分成兩部分,一部分用上面的方法交叉,另一部分用OX法交叉,每過一定的代數(shù)就交換其中的一部分。

2.2.7 染色體變異

這里選區(qū)逆轉(zhuǎn)變異與對換變異相結(jié)合的方式,2種變異隔代交替出現(xiàn)。

逆轉(zhuǎn)變異。選取染色體的一個子串,將其翻轉(zhuǎn)。例如,選取了092||0157||038640中的157,則變異后的染色體為0920751038640。

對換變異。隨即選取2個染色體上的不為0的基因?qū)⑵浣粨Q位置。例如,0920157038640,選取了9和3交換位置,則形成了子代0320157098640。

3 案例分析

芒果具有營養(yǎng)價值高,產(chǎn)地主要集中我國華南地區(qū),而且芒果在運輸過程中很容易受到振動與沖擊的影響。假設有一批從華南運來的芒果,需經(jīng)以南京為配送中心向江蘇其他12個地級市進行配送,每輛車限載重12 t,車輛正常行駛里程不超過600 km,假設時間窗懲罰因子α＝3 000,β＝4 000,超載罰值為M1＝6 000,超過行駛上限距離罰值為M2＝3 000,對城市之間距離采取簡化處理并分為不同的道路等級。表2為各個城市之間的距離,表3為各個城市之間道路等級,實際上城市之間的道路等級至少是2種以上,為了便于計算,本文只列出了案例分析中配送車輛途徑線路等級。表4為各個城市需求量及時間窗要求。

表2 各城市之間距離DTab.2 Distance among different cities km

表3 各城市之間道路等級LgTab.3 Road level among different cities Lg

表4 各城市需求量及時間窗要求Tab.4 Demand among cities and time window requests

為了驗證改進遺傳算法的可行性,將改進的遺傳算法和原始OX交叉遺傳算法及組序交叉遺傳算法進行了對比分析。在Matlab中對這3種算法進行了編程和仿真,相關參數(shù)設置為配送車輛4輛,變量維數(shù)為30,遺傳代數(shù)為200,交叉率為0.8,變異率為0.2。圖1和圖2為3種算法目標值的對比圖示。

圖1 改進交叉遺傳算法和原始OX交叉遺傳算法對比圖Fig.1 Comparison chart between improved genetic algorithm and original OX crossover genetic algorithm

由圖1和圖2可見,改進交叉遺傳算法相比原始OX交叉遺傳算法與組序交叉遺傳算法,具有收斂速度快,算法能力強等優(yōu)點,其可靠性優(yōu)于后兩者。通過對改進交叉遺傳算法進行了多次試驗,可以得到的最后優(yōu)化結(jié)果為0→8→10→12→0→1→7→5→0→4→6→9→0→11→3→2→0,費用值為156 370元,其中,0為配送中心。

圖2 改進交叉遺傳算法和組序交叉遺傳算法對比圖Fig.2 Comparison chart between improved genetic algorithm and group-order crossover genetic algorithm

為了進一步研究本文提出的改進遺傳算法模型與原始OX交叉法和組序交叉法的對比分析以及改進遺傳算法中路面不平度系數(shù)和公路收費等級對分析結(jié)果的相關性程度,將根據(jù)均方根誤差(RMSE)、絕對誤差(Eabs)和相關系數(shù)(Rcor)對其進行評估分析,見式(10)～(12)。

通過對均方根誤差、絕對誤差、相關系數(shù)和運行時間的分析比較可以得出以下結(jié)果:①3種算法的精確度從高到低依次為本文提出的改進遺傳算法、組序交叉遺傳算法和原始OX交叉遺傳算法;②從相關系數(shù)的改進可以看出,將運輸時的路面不平度系數(shù)對果蔬質(zhì)量造成的振動與沖擊影響和公路等級及收費差異性因素考慮到改進模型算法中,可以有效地提高運輸成本預測精度?？傊?通過改進目標函數(shù)、適應度函數(shù)和交叉因子,構建的改進遺傳算法的果蔬本預測模型是可行的和有效的,能夠減少果蔬碰撞損失和降低運輸成本。

表5 3種算法的比較Tab.5 Comparative analyses between the 3 algorithms

4 結(jié)束語

依據(jù)提出改進算法分析,解決物流配送中的路徑選擇問題時,原始OX交叉遺傳算法不容易快速收斂到滿意值,而采用組序交叉法和原始OX交叉法相結(jié)合的改進交叉遺傳算法,其組序交叉可以保證核心元素的相對位置不變以及種群的多樣性,而OX法可以使交配區(qū)完整保留,二者結(jié)合,通過改進目標函數(shù)、適應度函數(shù)和交叉因子,算法能力和優(yōu)越性得到了顯著改善?？紤]路面不平度系數(shù)對果蔬質(zhì)量造成的振動與沖擊影響和公路等級及收費差異性因素到改進模型算法中,從實驗結(jié)果中可以看出,構建的改進遺傳算法的果蔬預測模型是可行的和有效的,能夠減少果蔬碰撞損失和降低運輸成本。筆者主要針對同類果蔬的配送問題進行了相關的研究,對于多種果蔬的聯(lián)合運輸最優(yōu)路徑規(guī)劃是否能取得滿意的結(jié)果有待進一步的研究。

[1] 李鋒,魏瑩.易腐貨物配送中時變車輛路徑問題的優(yōu)化算法[J].系統(tǒng)工程學報,2010,25(4):492-498.

LI Feng,WEI Ying.Time-dependent vehicle routing algorithm for perishable goods delivery[J].Journal of Systems Engineering,2010,25(4):492-498.(in Chinese)

[2] 黃華芳,王以忠,李達,等.果蔬運輸車輛路徑再規(guī)劃[J].農(nóng)業(yè)機械學報,2012(4):113-118.

HUANG Huafang,WANG Yizhong,LI Da,et al.Vehicle route replanning for fruit and vegetable delivery[J].Transactions of the Chinese Society of Agricultural Machinery,2012(4):113-118.(in Chinese)

[3] 謝小良,符卓,楊光華.易腐物品車輛路徑問題的并行遺傳算法[J].計算機工程與科學,2009,31 (9):64-67.

XIE Xiaoliang,FU Zhuo,YANG Guanghua.A parallel genetic algorithm for the vehicle routing problem of perishable items[J].Computer Engineering &Science,2009,31(9):64-67.(in Chinese)

[4] 劉文佳,李芳.基于物聯(lián)網(wǎng)的生鮮產(chǎn)品運輸路徑優(yōu)化[J].物流工程與管理,2015,37(1):92-94.

LIU Wenjia,LI Fang.Fresh products’distribution path optimization based on the internet of things [J].Logistics Engineering and Management,2015, 37(1):92-94.(in Chinese)

[5] 林楓.基于Martins算法的聯(lián)合運輸最優(yōu)路徑規(guī)劃[J].西南交通大學學報,2015,50(3):543-549.

LIN Feng.Optimal intermodal transport path planning based on martins algorithm[J].Journal of Southwest Jiaotong University,2015,50(3):543-549.(in Chinese)

[6] 吳軍,王丹,李健,等.基于強化學習的?；愤\輸路徑選擇博弈分析[J].系統(tǒng)工程理論實踐, 2015,35(2):388-393.(in Chinese)

WU Jun,WANG Dan,LI Jian,et al.Game analysis of hazardous chemicals transport route selection based on reinforcement learning-model[J].Systems Engineering—Theory and Practice,2015,35(2): 388-393.(in Chinese)

[7] 張華慶,張喜.改進遺傳算法在車輛路徑問題中的應用[J].交通信息與安全,2012,30(5):81-86.

ZHANG Huaqing,ZHANG Xi.Application of improved genetic algorithm in vehicle routing problem [J].Journal of Transport Information and Safety 2012,30(5):81-86.(in Chinese)

[8] OSVALD A,STIRN L Z.A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food[J].Journal of Food Engineering,2008,85(2):285-295.

[9] CHEN H K,HSUEH C F,CHANG M S.Production scheduling and vehicle routing with time windows for perishable food products[J].Computers &Operations Research,2009,36(7):2311-2319.

[10] AMORIM P,ALMADA-LOBO B.The impact of food perishability issues in the vehicle routing problem[J].Computers&Industrial Engineering,2014(67):223-233.

[11] VALIDI S,BHATTACHARYA A,BYRNE P J.A case analysis of a sustainable food supply chain distribution system—A multi-objective approach [J].International Journal of Production Economics,2014(152):71-87.

[12] HSU C I,HUNG S F,LI H C.Vehicle routing problem with time-windows for perishable food delivery[J].Journal of Food Engineering,2007,80 (2):465-475.

[13] AHUMADA O,VILLALOBOS J R.Application of planning models in the agri-food supply chain: A review[J].European Journal of Operational Research,2009,196(1):1-20.

[14] JTG B01－2014,公路工程技術標準[S].北京:人民交通出版社,2014.JTG B01－2014,Technical standard of highway engineering[S].Beijing:People Communication Press,2014.(in Chinese)

[15] LIN J H.Variations in dynamic vehicle load on road pavement[J].International Journal of Pavement Engineering,2014,15(6):558-563.

[16] 江蘇省交通運輸廳.江蘇高速公路收費費率標準[S].南京:江蘇省交通運輸廳,2013.

Jiangsu Provincial Communication Department.Jiangsu expressway toll rate standard[S].Nangjing:Jiangsu Provincial Communication Department,2013.(in Chinese)

Fruit and Vegetable Distribution with Soft Time Windows Based on an Improved Genetic Algorithm

LI Peiqing1HE Jie1▲HUANG Yongsheng2FAN Chenhao1GAO Haidan2
(1.School of Transportation,Southeast University,Nanjing 210096,China; 2.School of Automation,Southeast University,Nanjing 210096,China)

In order to investigate the impacts of vibration,shock and collision on fresh fruits and vegetables during transportation,an improved genetic algorithm model is developed based on the soft time windows,pavement roughness and road grades.The objective of this model is to minimize the delivery costs of the suppliers by improving objective function,fitness function and crossover operator.Furthermore,comparison analyses are conducted among improved genetic algorithm,original order crossover(OX)genetic algorithm and group-order crossover genetic algorithm with a focus on the transport routes of fresh fruits and vegetables among 13 cities in the Jiangsu province as a case study.The results indicate that the proposed model provide 15.3%higher accuracy of delivery cost estimation over the conventional models.

transportation management;fruits and vegetables transport;distribution;soft time windows;genetic algorithm

U491

A

10.3963/j.issn 1674-4861.2015.05.005

2013-10-12

2015-09-18

?國家自然科學基金項目(批準號:51078087)、中央高校基本科研業(yè)務費專項資金項目(批準號:CXLX12_0111)、2015年度河南省重點科技攻關項目(批準號:152102310255)、江蘇省高?！扒嗨{工程”中青年學術帶頭人培養(yǎng)對象項目(批準號:2014)、浙江省交通運輸廳科技計劃項目(批準號:2012H12)資助

李培慶(1986－),博士研究生.研究方向:交通運輸安全與物流路徑優(yōu).E-mail:lpqing＠163.com

▲通信作者:何 杰(1973－),博士,教授.研究方向:交通安全與評價.E-mail:hejie＠seu.edu.cn