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

(1.東南大學(xué)交通學(xué)院 南京 210096;2.東南大學(xué)自動(dòng)化學(xué)院 南京 210096)

基于改進(jìn)遺傳算法的帶軟時(shí)間窗果蔬運(yùn)輸路徑選擇問題?

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

(1.東南大學(xué)交通學(xué)院 南京 210096;2.東南大學(xué)自動(dòng)化學(xué)院 南京 210096)

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

交通管理;果蔬運(yùn)輸;路徑選擇;軟時(shí)間窗;遺傳算法

0 引 言

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

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

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

1 數(shù)學(xué)模型構(gòu)建

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

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

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

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

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

2 改進(jìn)遺傳算法

2.1 遺傳算法

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

2.2 改進(jìn)遺傳算法設(shè)計(jì)

2.2.1 染色體編碼方式

采用整數(shù)編碼方式,假設(shè)由m輛車完成k個(gè)客戶的配送任務(wù),則構(gòu)造1條長(zhǎng)度為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ā),完成所有的運(yùn)輸任務(wù),就構(gòu)成了k條子路徑。這樣編碼的優(yōu)點(diǎn)在于直觀地給出了子路徑及客戶順序。

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

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

2.2.2 適應(yīng)度函數(shù)

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

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

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

2.2.4 判斷停止條件

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

2.2.5 自然選擇

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

2.2.6 染色體交叉重組

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

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

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

2.2.7 染色體變異

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

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

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

3 案例分析

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

[1] 李鋒,魏瑩.易腐貨物配送中時(shí)變車輛路徑問題的優(yōu)化算法[J].系統(tǒng)工程學(xué)報(bào),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] 黃華芳,王以忠,李達(dá),等.果蔬運(yùn)輸車輛路徑再規(guī)劃[J].農(nóng)業(yè)機(jī)械學(xué)報(bào),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].計(jì)算機(jī)工程與科學(xué),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ù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ùn)輸最優(yōu)路徑規(guī)劃[J].西南交通大學(xué)學(xué)報(bào),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] 吳軍,王丹,李健,等.基于強(qiáng)化學(xué)習(xí)的危化品運(yùn)輸路徑選擇博弈分析[J].系統(tǒng)工程理論實(shí)踐, 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ìn)遺傳算法在車輛路徑問題中的應(yīng)用[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,公路工程技術(shù)標(biāo)準(zhǔn)[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] 江蘇省交通運(yùn)輸廳.江蘇高速公路收費(fèi)費(fèi)率標(biāo)準(zhǔn)[S].南京:江蘇省交通運(yùn)輸廳,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

?國家自然科學(xué)基金項(xiàng)目(批準(zhǔn)號(hào):51078087)、中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(批準(zhǔn)號(hào):CXLX12_0111)、2015年度河南省重點(diǎn)科技攻關(guān)項(xiàng)目(批準(zhǔn)號(hào):152102310255)、江蘇省高?！扒嗨{(lán)工程”中青年學(xué)術(shù)帶頭人培養(yǎng)對(duì)象項(xiàng)目(批準(zhǔn)號(hào):2014)、浙江省交通運(yùn)輸廳科技計(jì)劃項(xiàng)目(批準(zhǔn)號(hào):2012H12)資助

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

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