程 博，楊 育，劉愛(ài)軍，陳 偉，邢青松

（1．重慶大學(xué) 機(jī)械傳動(dòng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，重慶 400030；2．西南交通大學(xué) 機(jī)械工程學(xué)院，四川 成都 610031）

0 引言

在我國(guó)國(guó)民經(jīng)濟(jì)不斷穩(wěn)定發(fā)展的新形勢(shì)下，國(guó)家重點(diǎn)建設(shè)工程項(xiàng)目的數(shù)量和規(guī)模都在不斷增長(zhǎng)，通過(guò)公路運(yùn)輸特大、特重型工業(yè)設(shè)備（如電機(jī)轉(zhuǎn)子、變壓器和反應(yīng)器等）已日趨頻繁。大件產(chǎn)品由于價(jià)格高昂，運(yùn)輸技術(shù)要求復(fù)雜，對(duì)運(yùn)輸安全有極高的要求，決定了大件產(chǎn)品要以最安全最經(jīng)濟(jì)的方式送達(dá)到客戶(hù)手中，這對(duì)決策者提出了選擇最優(yōu)路徑的難題。

楊春蘭等［1］研究了大件產(chǎn)品公路運(yùn)輸?shù)陌踩绊懸蛩?，通過(guò)數(shù)學(xué)建模，開(kāi)發(fā)出大件運(yùn)輸計(jì)算機(jī)決策系統(tǒng)，但沒(méi)有考慮大件公路運(yùn)輸路徑選擇問(wèn)題；徐永能等［2］分析了超載運(yùn)輸與路面可靠度的關(guān)系，并建立了基于路面可靠度的超載運(yùn)輸管理模型，但是沒(méi)有針對(duì)具體的路面可靠度進(jìn)行分析；胡明偉等［3］以最大化服務(wù)客戶(hù)數(shù)、最小化客戶(hù)等待時(shí)間和最小化總旅行時(shí)間為目標(biāo)，采用改進(jìn)局部搜索啟發(fā)式算法對(duì)動(dòng)態(tài)車(chē)輛路徑規(guī)劃問(wèn)題進(jìn)行求解，但沒(méi)有涉及大件運(yùn)輸?shù)奶厥庑裕粶鼗萦⒌确謩e對(duì)遺傳算法［4］和粒子群算法［5］進(jìn)行了改進(jìn)，并采用改進(jìn)后的算法對(duì)物流配送車(chē)輛導(dǎo)航路徑優(yōu)化問(wèn)題進(jìn)行研究，有效地解決了點(diǎn)到點(diǎn)的配送優(yōu)化問(wèn)題，提高了求解效率，但研究沒(méi)有考慮運(yùn)輸?shù)奶厥庑詥?wèn)題；孟凡江［6］采用線(xiàn)性規(guī)劃方法對(duì)鐵路運(yùn)輸多路徑優(yōu)化問(wèn)題進(jìn)行了研究；高輝等［7］采用改進(jìn)量子進(jìn)化算法對(duì)路徑進(jìn)行了優(yōu)化；CESCHIA等［8］采用禁忌搜索算法對(duì)包含時(shí)間窗和運(yùn)載成本的混雜路徑優(yōu)化問(wèn)題進(jìn)行了研究。后續(xù)學(xué)者分別采用局部遺傳算法［9］、虛擬多項(xiàng)式算法［10］、分支定界法［11］、新的啟發(fā)式算法［12］、并行算法［13］等對(duì)確定和非確定環(huán)境下的運(yùn)輸路徑問(wèn)題進(jìn)行了優(yōu)化。

綜上所述，目前研究大件運(yùn)輸路徑優(yōu)化的文獻(xiàn)較少，僅有的基本上也是以最短路徑作為最優(yōu)路徑，沒(méi)有考慮大件運(yùn)輸?shù)奶厥庑?。所采用的?yōu)化方法多是對(duì)單一算法初始化或者算法結(jié)構(gòu)的改進(jìn)，缺少基于融合思想的算法改善研究。因此，本文在考慮影響大件公路運(yùn)輸路徑選擇相關(guān)因素的基礎(chǔ)上，建立了以最小化成本為目標(biāo)的規(guī)劃模型，并采用改進(jìn)模擬退火算法對(duì)大件公路運(yùn)輸路徑選擇問(wèn)題進(jìn)行求解，以確定最佳運(yùn)輸路徑方案，為大件公路運(yùn)輸決策者提供參考和支持。

1 大件公路運(yùn)輸路徑選擇的相關(guān)因素

大件產(chǎn)品的公路運(yùn)輸過(guò)程非常復(fù)雜、技術(shù)難度大、耗時(shí)長(zhǎng)、運(yùn)輸成本十分昂貴，并且對(duì)運(yùn)輸?shù)陌踩砸髽O高。根據(jù)工程實(shí)際，影響大件公路運(yùn)輸路徑選擇的因素主要包括車(chē)輛安全通過(guò)性和運(yùn)輸成本兩個(gè)方面。

（1）車(chē)輛安全通過(guò)性因素

在大件產(chǎn)品的運(yùn)輸過(guò)程中，最重要的就是要保證運(yùn)輸車(chē)輛能夠安全通過(guò)所選路段。一旦在大件運(yùn)輸過(guò)程中發(fā)生安全事故，事故所造成的損失將是巨大且不可挽回的。影響車(chē)輛安全通過(guò)性的因素可分為內(nèi)在因素和外在因素，內(nèi)在因素主要指車(chē)組運(yùn)行穩(wěn)定性，外在因素主要指道路通過(guò)性和橋梁通過(guò)性。

車(chē)組運(yùn)行穩(wěn)定性又分為橫向穩(wěn)定性和縱向穩(wěn)定性。貨物重心太高，將導(dǎo)致車(chē)組允許通過(guò)的最大橫坡坡度和縱坡坡度減小，一旦所選擇的路段含有較多的橫坡或縱坡且坡度較大，則很難保證車(chē)組的運(yùn)行穩(wěn)定性，從而降低運(yùn)輸車(chē)輛的安全通過(guò)性。

道路通過(guò)性主要考慮沿線(xiàn)道路及結(jié)構(gòu)物的路面凈空寬度、道路彎道處的轉(zhuǎn)彎半徑。由于大件產(chǎn)品一般是超高、超寬、超長(zhǎng)的貨物，對(duì)所選路段的路面凈空、寬度和彎道半徑有嚴(yán)格要求。若所選路段的路面凈空不足，彎道較多，且彎道內(nèi)外半徑不滿(mǎn)足車(chē)輛轉(zhuǎn)彎所需要的最小道路內(nèi)外半徑，則運(yùn)輸車(chē)輛不能順利轉(zhuǎn)彎，表明車(chē)輛在該路段的安全通過(guò)性較差。

橋梁通過(guò)性主要判別大件運(yùn)輸車(chē)輛通過(guò)橋梁的可能性，工程中可以采用下式判別車(chē)輛的通行能力：其中：S大件表示大件運(yùn)輸車(chē)輛產(chǎn)生的截面內(nèi)力，S標(biāo)準(zhǔn)表示標(biāo)準(zhǔn)載荷產(chǎn)生的截面內(nèi)力。當(dāng)θ≤0時(shí)，表示運(yùn)輸車(chē)輛可以安全通過(guò)橋梁；當(dāng)0＜θ≤5%時(shí)，表示運(yùn)輸車(chē)輛容許通過(guò)橋梁，當(dāng)θ＞5%時(shí)，表示運(yùn)輸車(chē)輛不能安全通過(guò)橋梁。若所選路段的橋梁數(shù)量較多，橋梁承載能力較差，則車(chē)輛在該路段的安全通過(guò)性較差。

（2）運(yùn)輸成本因素

在進(jìn)行路徑選擇時(shí)，也要充分考慮運(yùn)輸成本對(duì)路徑選擇的影響。大件運(yùn)輸所要考慮的運(yùn)輸成本不僅包含正常的運(yùn)輸費(fèi)用，還包括為了增加路段安全通過(guò)性而采取的清障、加固、改造等所消耗的費(fèi)用，這部分費(fèi)用也可以稱(chēng)為基于車(chē)輛安全通過(guò)所發(fā)生的成本。

影響大件運(yùn)輸成本的因素主要有路段的長(zhǎng)度及路段的復(fù)雜程度兩個(gè)方面。所選路段長(zhǎng)度越長(zhǎng)，運(yùn)輸費(fèi)用就越高。路段的復(fù)雜程度是衡量大件運(yùn)輸車(chē)輛通過(guò)某路段的難易程度，具有相對(duì)性，不同的運(yùn)輸任務(wù)，同路段的復(fù)雜程度可能不同。大件運(yùn)輸車(chē)輛通過(guò)路段的坡道越多、彎道的內(nèi)外半徑越小、需要清除的路障越多、橋梁加固越復(fù)雜，表明該路段的復(fù)雜程度越高。運(yùn)輸車(chē)輛在復(fù)雜程度高的路段上行駛時(shí)，為了確保車(chē)輛安全通過(guò)，需要清除障礙（交通標(biāo)志、管廊、樹(shù)木、建筑物等）、拓寬道路、加固橋梁等，這些保障措施使得運(yùn)輸成本進(jìn)一步增加。因此，路段的復(fù)雜程度越高，所需要的運(yùn)輸成本越高。

2 問(wèn)題描述及模型建立

2．1 問(wèn)題描述

大件公路運(yùn)輸路徑選擇問(wèn)題為車(chē)輛路徑問(wèn)題（Vehicle Routing Problem，VRP），屬于典型的復(fù)雜組合優(yōu)化問(wèn)題。大件公路運(yùn)輸路徑選擇指根據(jù)大件運(yùn)輸?shù)奶厥庑裕瑢⒋蠹a(chǎn)品按客戶(hù)要求在規(guī)定時(shí)間T0內(nèi)從出發(fā)地O運(yùn)往目的地D，主要以車(chē)輛及貨物的安全通過(guò)和降低運(yùn)輸成本兩個(gè)目標(biāo)為前提，建立尋找大件公路運(yùn)輸最優(yōu)路徑的模型，為大件運(yùn)輸方提供決策方案。因?yàn)樵诖蠹\(yùn)輸過(guò)程中，發(fā)生安全事故會(huì)造成巨大且不可挽回的損失，所以車(chē)輛及貨物的安全通過(guò)必須作為優(yōu)先優(yōu)化的目標(biāo)。

2．2 大件運(yùn)輸配送調(diào)度數(shù)學(xué)模型

在建立路徑優(yōu)化模型之前，首先要建立運(yùn)輸網(wǎng)絡(luò)模型。根據(jù)運(yùn)輸任務(wù)建立從出發(fā)地O到目的地D具有k個(gè)節(jié)點(diǎn)的運(yùn)輸網(wǎng)絡(luò)圖G＝（V，E）。其中：V表示節(jié)點(diǎn)集，E表示網(wǎng)絡(luò)的邊集。圖G中的節(jié)點(diǎn)Vi與節(jié)點(diǎn)Vj之間路段Eij的長(zhǎng)度為dij。在選擇路徑之前，邀請(qǐng)10～15位在大件運(yùn)輸方面有豐富經(jīng)驗(yàn)的技術(shù)人員和專(zhuān)家評(píng)估各路段的安全通過(guò)性（指道路在清障拓寬加固后的安全通過(guò)性）和路段復(fù)雜程度對(duì)成本及車(chē)速的影響大小，并分別建立路段安全通過(guò)性集合S、路段復(fù)雜程度對(duì)成本影響系數(shù)集合A＝｛Aij｜0＜Aij≤1｝和路段復(fù)雜程度對(duì)車(chē)速影響系數(shù)集合B＝｛Bij｜0＜Bij≤1｝。一般情況下，路段復(fù)雜程度越高，對(duì)成本、車(chē)速的影響越大，成本影響系數(shù)和車(chē)速影響系數(shù)的取值越低。

大件物流配送調(diào)度問(wèn)題描述為：有M個(gè)車(chē)場(chǎng)，各自擁有Km（m＝1，2，…，M）輛車(chē)，負(fù)責(zé)對(duì)N個(gè)用戶(hù)進(jìn)行大件貨物的配送工作，以最小化運(yùn)輸成本、最大化運(yùn)輸安全性為目標(biāo)，尋求滿(mǎn)足所有客戶(hù)需求的調(diào)度方案。

為了方便建模和求解，需要對(duì)現(xiàn)實(shí)問(wèn)題進(jìn)行抽象和簡(jiǎn)化［14］：

（1）配送中心向多個(gè)客戶(hù)提供送貨服務(wù)，每個(gè)客戶(hù)的配送需求僅能由一輛大件運(yùn)輸車(chē)完成，不允許分批分車(chē)配送。

（2）客戶(hù)需要的貨物可以混合配裝，但當(dāng)每個(gè)車(chē)輛載重的客戶(hù)貨物的總重量超過(guò)該配送車(chē)輛的最大載重量時(shí)就要給予一定懲罰。

（3）配送時(shí)每臺(tái)車(chē)輛都從配送中心出發(fā)，最終返回原配送中心。

（4）配送中心與客戶(hù)之間以及客戶(hù)相互之間的距離已知。

（5）對(duì)于客戶(hù)要求在指定時(shí)間窗內(nèi)完成的配送任務(wù)，配送作業(yè)提前或者推遲完成都要給予一定懲罰。

（6）路段復(fù)雜程度對(duì)成本影響系數(shù)集合A和路段復(fù)雜程度對(duì)車(chē)速影響系數(shù)集合B已知。

（7）配送車(chē)輛在配送中心、客戶(hù)間的行駛時(shí)間根據(jù)距離和車(chē)輛速度可求。

設(shè)用戶(hù)編號(hào)為1，2，…，N，車(chē)場(chǎng)編號(hào)為N＋1，N＋2，…，N＋M，大件公路運(yùn)輸路徑優(yōu)化數(shù)學(xué)模型表示如下：

其中：FCmk表示使用車(chē)場(chǎng)m的車(chē)輛k的固定成本；LWmk表示車(chē)場(chǎng)m 的車(chē)輛k的載重量限制；［ETi，LTi］表示第i個(gè)用戶(hù)的服務(wù)時(shí)間窗，ETi為用戶(hù)i的服務(wù)最早開(kāi)始時(shí)間，LTi為用戶(hù)i的服務(wù)最遲開(kāi)始時(shí)間，如果車(chē)輛到達(dá)i的時(shí)間早于ETi，則車(chē)輛需在i處等待，如果車(chē)輛到達(dá)時(shí)間晚于LTi，則要延遲進(jìn)行；SEi表示第i個(gè)用戶(hù)的實(shí)際服務(wù)開(kāi)始時(shí)間；PE為提前懲罰系數(shù)，PL為延遲懲罰系數(shù)；LP為超重懲罰系數(shù)；Cij表示從用戶(hù)i到用戶(hù)j的運(yùn)輸成本；Vij表示從用戶(hù)i到用戶(hù)j的運(yùn)輸速度；velocityij表示考慮路段復(fù)雜程度以后的校正車(chē)速。

配送調(diào)度問(wèn)題除了要滿(mǎn)足以上目標(biāo)函數(shù)和約束以外，還要滿(mǎn)足以下性能：

（1）空駛里程Z

配送車(chē)輛把貨物配送完成返回車(chē)場(chǎng)的路途長(zhǎng)度就是空駛里程，空駛里程對(duì)配送中心來(lái)說(shuō)是不產(chǎn)生任何價(jià)值的浪費(fèi)環(huán)節(jié)，因此在配送優(yōu)化滿(mǎn)足目標(biāo)的方案中，空駛里程越短，方案越優(yōu)。

（2）線(xiàn)路平均長(zhǎng)度L－

線(xiàn)路的平均長(zhǎng)度反映了車(chē)輛運(yùn)行負(fù)荷的基本情況，在滿(mǎn)足目標(biāo)的情況下，線(xiàn)路平均長(zhǎng)度越短，方案越優(yōu)。

（3）線(xiàn)路均衡度ψ

線(xiàn)路均衡度是最短線(xiàn)路長(zhǎng)占最長(zhǎng)線(xiàn)路長(zhǎng)的百分比，反映最長(zhǎng)與最短線(xiàn)路的差異性。

3 改進(jìn)遺傳模擬退火算法

目前，物流配送領(lǐng)域的相關(guān)研究多采用性能穩(wěn)定的遺傳或模擬退火算法為基礎(chǔ)組成的混合算法，這兩類(lèi)算法分別具有優(yōu)良的搜索優(yōu)點(diǎn)：① 遺傳算法具有自組織、自適應(yīng)、自學(xué)習(xí)能力及搜索并行性的優(yōu)點(diǎn)；②模擬退火算法具有優(yōu)良的局部搜索能力，即在搜索最優(yōu)解的過(guò)程中，除了可以接受優(yōu)化解外，還可以有限度地接受部分惡化解，并且可以使接受惡化解的概率逐漸趨向于0，從而使算法有可能從局部極值區(qū)域中跳出，找到全局最優(yōu)解，并保證算法的收斂性。這樣，通過(guò)兩種算法混合構(gòu)造新的遺傳模擬退火算法可以達(dá)到揚(yáng)長(zhǎng)避短的作用。

綜上所述，本文將在已有遺傳模擬退火算法研究的基礎(chǔ)上，通過(guò)折中優(yōu)化質(zhì)量和優(yōu)化效率的策略確定初始溫度，改善搜索冗長(zhǎng)的現(xiàn)象，增強(qiáng)進(jìn)化速度；采用自適應(yīng)交叉和變異處理方法，提高遺傳算法局部搜索性能，增強(qiáng)進(jìn)化能力；通過(guò)對(duì)交叉和變異后的個(gè)體實(shí)施接受策略，增強(qiáng)遺傳算法的全局收斂性，加快進(jìn)化后期的收斂速度，采用在每次迭代結(jié)束前進(jìn)行降溫處理的方法，保證遺傳算法和模擬退火算法具有相同的收斂方向和速度。算法結(jié)構(gòu)如圖1所示。

具體操作步驟如下：

步驟1 給定種群規(guī)模popsize，k＝0；從產(chǎn)生的初始解中選擇最大、最小目標(biāo)函數(shù)值f0，max和f0，min，計(jì)算初始溫度，產(chǎn)生滿(mǎn)足載重和體積約束的初始群體pop（popsize）；計(jì)算目標(biāo)值f（i），找出使目標(biāo)函數(shù)值最小的染色體i和該函數(shù)值f，記i＊＝i，f＊＝f；其中，i為當(dāng)代群體中的一個(gè)染色體。

步驟2 若滿(mǎn)足約束，則輸出最優(yōu)染色體i＊和最優(yōu)解f＊，運(yùn)算停止；否則在群體pop（popsize）的每一個(gè)染色體i的鄰域中隨機(jī)選取一個(gè)狀態(tài)j∈N（i），按照模擬退火中的接受概率

接受或拒絕j，其中fi（tk）和fj（tk）分別表示狀態(tài)i和j在溫度為tk時(shí)的目標(biāo)值。這一階段共需popsize次迭代來(lái)選出新群體pop1（popsize）。

步驟4 分別以自適應(yīng)pC和pM對(duì)pop2（popsize）進(jìn)行交叉和變異操作。

步驟5 計(jì)算pop2（popsize）中個(gè)體的目標(biāo)函數(shù)值，找出函數(shù)值最小的染色體χ及該函數(shù)值λ，如果λ＜f＊，則令i＊＝χ，f＊＝λ，μ為退火率，tk＋1＝μtk，k＝k＋1，返回步驟2。

4 算法設(shè)計(jì)

4．1 算法編碼

由于遺傳模擬退火算法不能直接處理解空間的數(shù)據(jù)，必須通過(guò)編碼將其表示成基因型串結(jié)構(gòu)數(shù)據(jù)［15］。本文以客戶(hù)為中心，提出三層染色體編碼新方法，能夠表示不同數(shù)量的車(chē)場(chǎng)、車(chē)輛和線(xiàn)路安排信息值，使算法可以對(duì)車(chē)場(chǎng)、車(chē)輛及路線(xiàn)進(jìn)行自動(dòng)尋優(yōu)。

染色體采用自然數(shù)編碼，即序數(shù)編碼，染色體表示為基因序列 （G1，G2，…，GN），其中Gi由車(chē)場(chǎng)編號(hào) M－number、車(chē) 輛 編 號(hào) Km－number 和 排 序 值Val－number三部分組成。該染色體表示了車(chē)場(chǎng)、車(chē)輛和線(xiàn)路安排信息，如編號(hào)為i的客戶(hù)需要由車(chē)場(chǎng)M－number的編號(hào)為Km－number的車(chē)輛運(yùn)載，其在路徑中的位置由排序值Val－number的大小來(lái)決定。這種方法沒(méi)有明確地表示出每輛車(chē)的確切路徑，但是每輛車(chē)的確切路徑隱含在Val－number排序中。

4．2 選擇算子

輪盤(pán)賭用來(lái)從染色體群體中選擇成員，被選中的幾率與其適應(yīng)性分?jǐn)?shù)成比例。該方法的基本思想是：生成一個(gè)隨機(jī)數(shù)γ∈［0，1］，并計(jì)算個(gè)體的相對(duì)適應(yīng)度值pi＝fi／∑fi，如果p0＋p1＋…＋pi－1＜γ≤p0＋p1＋…＋pi，則第i個(gè)個(gè)體被選擇到下一代?？梢?jiàn)，個(gè)體的適應(yīng)度值越大，被選擇到下一代的機(jī)會(huì)也越多。

4．3 交叉與變異算子

遺傳算法的參數(shù)中，交叉概率PC和變異概率PM的選擇直接影響算法的收斂性，是影響遺傳算法行為和性能的關(guān)鍵。PC越大，產(chǎn)生新個(gè)體的速度就越快，會(huì)很快破壞具有高適應(yīng)度的個(gè)體結(jié)構(gòu)；若PC過(guò)小，則會(huì)使搜索過(guò)程變得緩慢，甚至停滯不前。對(duì)于變異率PM，如果PM過(guò)小，則不能維持種群的多樣性，造成算法過(guò)早收斂；如果PM取值過(guò)大，則會(huì)破壞接近最優(yōu)解的遺傳模式。為了避免選用這種固定交叉和變異概率，本文采用一種自適應(yīng)調(diào)整交叉和變異概率的方法，具體方法如下：

（1）自適應(yīng)交叉算子

交叉操作是遺傳算法中增加種群多樣性、防止算法早熟和停滯的操作。研究發(fā)現(xiàn)，在進(jìn)化的過(guò)程中，當(dāng)前代種群中個(gè)體的適應(yīng)度值低于平均適應(yīng)度值時(shí)，需要提高交叉概率；當(dāng)適應(yīng)度值高于平均適應(yīng)度值時(shí)，則需要降低交叉概率。這樣就使交叉概率隨著適應(yīng)度值自動(dòng)地調(diào)整，既克服了不成熟的收斂，又避免破壞優(yōu)秀染色體。為此，本文提出交叉概率動(dòng)態(tài)調(diào)整策略，交叉概率的自適應(yīng)調(diào)整公式為

（2）自適應(yīng)變異算子

變異是按一定的概率改變個(gè)體基因鏈，變異操作也是增加種群多樣性的一種進(jìn)化手段，適度的變異既能保持種群內(nèi)個(gè)體的多樣化，又能提高算法的效率，克服遺傳操作可能限于局部解的弊端。為了克服PM過(guò)大或過(guò)小的弊端［16］，本文采用與PC相似的處理方式自適應(yīng)調(diào)整PM，變異概率的自適應(yīng)調(diào)整公式為：

式中：fmax為群體中最大的適應(yīng)度值，favg為每代群體的平均適應(yīng)度值，f為交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值，f＊為要變異的個(gè)體的適應(yīng)度值。

由上述自適應(yīng)交叉和變異概率可實(shí)現(xiàn)種群的多樣性，保證算法搜索空間的廣泛性，在此基礎(chǔ)上對(duì)本文的配裝配送調(diào)度問(wèn)題實(shí)施雙點(diǎn)交叉，在個(gè)體編碼串中隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)，然后再進(jìn)行部分基因的交換。設(shè)選擇進(jìn)行交叉的父、母體分別為X和Y，經(jīng)雙點(diǎn)交叉得到后代X′和Y′，雙點(diǎn)交叉示意圖如2所示。

為提高收斂速度，變異過(guò)程采用簡(jiǎn)單快速的移位變異方式，如圖3所示。

經(jīng)上述雙點(diǎn)交叉和移位變異操作產(chǎn)生的新個(gè)體可能違背了載重和體積限制條件，因此必須對(duì)產(chǎn)生的新個(gè)體進(jìn)行載重和體積約束驗(yàn)證，如果不能滿(mǎn)足約束條件，則重新產(chǎn)生交叉或變異個(gè)體，直至達(dá)到popsize個(gè)個(gè)體。

5 實(shí)驗(yàn)數(shù)據(jù)與分析

基于上述改建遺傳模擬退火算法的研究，結(jié)合大件公路運(yùn)輸路徑優(yōu)化模型，以最小化總成本為目標(biāo)進(jìn)行仿真。以某公司大件公路運(yùn)輸為例，該公司具有兩個(gè)配送中心，需要將大件設(shè)備運(yùn)輸?shù)?0個(gè)客戶(hù)手中，選擇出總成本最小的運(yùn)輸路線(xiàn)。首先根據(jù)路面凈空、寬度、彎道半徑和橋梁通過(guò)性對(duì)路徑進(jìn)行初選，選擇出如表1所示的運(yùn)輸路徑。算法相關(guān)參數(shù)設(shè)置如下：種群規(guī)模popsize＝100；超載罰函數(shù)LP＝200；時(shí)間窗懲罰函數(shù)系數(shù)PE＝20，PL＝20；交叉率計(jì)算參數(shù)PC1＝0．9，PC2＝0．6；變異率計(jì)算參數(shù)PM1＝0．1，PM2＝0．001；模擬退火算法退火率μ＝0．85。各客戶(hù)貨物相關(guān)信息、各車(chē)場(chǎng)車(chē)輛信息及路段復(fù)雜程度對(duì)成本和車(chē)速的影響系數(shù)集合A和B如表2～表4所示。

表1 配送中心及客戶(hù)之間的距離

表2 各客戶(hù)貨物相關(guān)信息

續(xù)表2

表3 各車(chē)場(chǎng)車(chē)輛信息

表4中括號(hào)內(nèi)的兩個(gè)數(shù)據(jù)，前者表示成本系數(shù)，后者表示速度系數(shù)。運(yùn)用本文的改進(jìn)遺傳模擬退火算法對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行仿真優(yōu)化，種群迭代200次得到的目標(biāo)函數(shù)最優(yōu)的染色體為：

函數(shù)極值為Result＝1．430 4×103。

Solution中，三個(gè)數(shù)據(jù)為一組，依次表示10個(gè)客 戶(hù)，如 客 戶(hù) 1 的 數(shù) 據(jù) 集 （1．000 0，3．000 0，0．143 7）中的數(shù)據(jù)分別表示：客戶(hù)1的配送活動(dòng)由Ⅰ號(hào)配送中心執(zhí)行；該配送中心選擇該中心的第3輛車(chē)執(zhí)行配送活動(dòng)；客戶(hù)1在該車(chē)配送中的優(yōu)先級(jí)數(shù)為0．143 7。如最優(yōu)染色體所示，得到的調(diào)度方案為：Ⅰ號(hào)配送中心第2輛車(chē)的配送路線(xiàn)為Ⅰ－10－8－Ⅰ；第3輛車(chē)的配送路線(xiàn)為Ⅰ－3－1－Ⅰ；Ⅱ號(hào)配送中心第1輛車(chē)的配送路線(xiàn)為Ⅱ－7－2－Ⅱ；第2輛車(chē)的配送路線(xiàn)為Ⅱ－6－9－Ⅱ；第3輛車(chē)的配送路線(xiàn)為Ⅱ－5－4－Ⅱ。配送路線(xiàn)如圖4所示，有I和Ⅱ兩個(gè)配送中心完成物流的配裝配送任務(wù)，括號(hào)內(nèi)的數(shù)據(jù)表示車(chē)場(chǎng)和車(chē)輛標(biāo)志，如（Ⅰ，2）表示第Ⅰ個(gè)車(chē)場(chǎng)的第2輛車(chē)來(lái)執(zhí)行客戶(hù)10和8的配裝和配送任務(wù)，在這種調(diào)度方案下，目標(biāo)函數(shù)的最優(yōu)解為1 430。為評(píng)價(jià)本文改進(jìn)遺傳模擬退火算法的性能，將其與文獻(xiàn)［17］的基本遺傳算法（種群規(guī)模為100，交叉概率為0．75，變異概率為0．25）及文獻(xiàn)［18］的遺傳退火算法進(jìn)行比較，運(yùn)行10次得到的目標(biāo)函數(shù)值如表5所示。

從表5中的數(shù)據(jù)可知，經(jīng)10次運(yùn)行，本文的改進(jìn)遺傳模擬退火算法得到的平均結(jié)果1 440．3優(yōu)于遺傳算法所得的平均結(jié)果1 529．5，同時(shí)優(yōu)于文獻(xiàn)［18］的遺傳退火算法所得的平均結(jié)果1 457．4，且有5次得到了該問(wèn)題的最優(yōu)解1 430?？梢?jiàn)，利用本文改進(jìn)遺傳模擬退火算法可以方便有效地求得多約束條件下的物流配送路徑優(yōu)化問(wèn)題的最優(yōu)解或近似最優(yōu)解。

表5 算法性能對(duì)比

為充分認(rèn)識(shí)本文改進(jìn)遺傳模擬退火算法對(duì)線(xiàn)路均衡性等配送性能的影響，多次運(yùn)行程序，得到算法性能分析如表6所示。

表6 算法性能分析

由表6可知，隨著運(yùn)算代數(shù)的增加，目標(biāo)函數(shù)值趨向最優(yōu)值，載重和體積利用率逐步得到優(yōu)化；在最小化目標(biāo)函數(shù)值的條件下，派出車(chē)輛數(shù)、空駛里程長(zhǎng)度和線(xiàn)路平均長(zhǎng)度經(jīng)歷變化，最后收斂到較優(yōu)值；由于目標(biāo)函數(shù)的影響，線(xiàn)路最大偏差度和線(xiàn)路均衡度向理論最優(yōu)值的反方向變化。由上述分析，調(diào)度者可以根據(jù)物流配送的實(shí)際情況做出費(fèi)用決策和距離決策的權(quán)衡。

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

本文針對(duì)大件公路運(yùn)輸路徑優(yōu)化問(wèn)題，建立了多目標(biāo)物流配送數(shù)學(xué)模型，提出了改進(jìn)的遺傳模擬退火算法，通過(guò)大量的仿真試驗(yàn)計(jì)算，取得以下成果：

（1）在求解大件公路運(yùn)輸路徑優(yōu)化問(wèn)題方面，本文結(jié)合大件物流運(yùn)輸?shù)奶攸c(diǎn)，克服了目前研究只針對(duì)配送路徑進(jìn)行優(yōu)化的缺陷，建立了帶配送時(shí)間窗、客戶(hù)服務(wù)時(shí)限、車(chē)輛超載懲罰、車(chē)輛服務(wù)時(shí)限、車(chē)輛載重限制、車(chē)輛容積限制、車(chē)輛安全通過(guò)性等多約束條件下的大件公路運(yùn)輸路徑優(yōu)化模型，給出了求解該類(lèi)問(wèn)題的思路。

（2）在該算法的設(shè)計(jì)和實(shí)現(xiàn)方面，采用三層序數(shù)編碼方法產(chǎn)生滿(mǎn)足載重和體積約束條件的初始種群，保證每個(gè)染色體的可行性，通過(guò)模擬退火操作和遺傳算法的選擇、交叉、變異等操作，對(duì)整個(gè)群體進(jìn)行優(yōu)化。其中，引入自適應(yīng)參數(shù)策略，動(dòng)態(tài)調(diào)整交叉和變異概率，既克服了不成熟的收斂，又避免了優(yōu)秀染色體被破壞。

（3）在算法性能方面，以大件公路運(yùn)輸問(wèn)題為例，分別采用遺傳算法、遺傳退火算法和改進(jìn)遺傳退火算法進(jìn)行求解，通過(guò)對(duì)調(diào)度結(jié)果進(jìn)行分析發(fā)現(xiàn)，改進(jìn)遺傳退火算法具有更好的全局尋優(yōu)能力和更小的標(biāo)準(zhǔn)偏差，同時(shí)驗(yàn)證了本文提出的改進(jìn)遺傳模擬算法在求解多約束條件多目標(biāo)配送優(yōu)化問(wèn)題時(shí)的優(yōu)越性。

本文針對(duì)公路大件運(yùn)輸路徑優(yōu)化問(wèn)題進(jìn)行了深入研究，在建模過(guò)程中，對(duì)路徑選擇方法進(jìn)行了必要的簡(jiǎn)化處理。下一步可以圍繞路徑通過(guò)性問(wèn)題，將路徑的路面承載能力、摩擦系數(shù)、最大上坡坡度、最大下坡坡度及彎道半徑等因素考慮到優(yōu)化模型中，以期進(jìn)一步提升該算法的工程指導(dǎo)意義。

［1］YANG Chunlan，HUANG Dongsheng，ZHANG Yu，et al．Modeling and software developing for computer decision making system of road massive products transportation［J］．Journal of Wuhan University of Technology：Transportation Science＆Engineering，2003，27（1）：106－108（in Chinese）．［楊春蘭，黃東勝，張 雨，等．公路大件運(yùn)輸計(jì)算機(jī)決策系統(tǒng)建模與軟件開(kāi)發(fā)［J］．武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版，2003，27（1）：106－108．］

［2］ZHONG Shiquan，DU Gang．Open vehicle routing problem based on kernel route tabu search algorithm［J］．Computer Integrated Manufacturing Systems，2007，23（4）：132－142（in Chinese）．［鐘石泉，杜 綱．基于核心路徑禁忌算法的開(kāi)放式車(chē)輛路徑問(wèn)題研究［J］．計(jì)算機(jī)集成制造系統(tǒng)，2007，23（4）：132－142．］

［3］HU Mingwei，TANG Hao．Multi－objective optimization model of dynamic vehicle routing problem［J］．Journal of Shenzhen University Science and Engineering，2010，27（2）：230－235（in Chinese）．［胡明偉，唐 浩．動(dòng)態(tài)車(chē)輛路徑問(wèn)題的多目標(biāo)優(yōu)化模型與 算 法 ［J］．深 圳 大 學(xué) 學(xué) 報(bào)：理 工 版，2010，27（2）：230－235．］

［4］WEN Huiying，XU Jianmin，LIN Zhengchun．Genetic algorithm for route optimization of vehicle navigationin logistics distribution［J］．Journal of South China University of Technology：Natural Science Edition，2009，37（2）：82－91（in Chinese）．［溫惠英，徐建閩，林正春．適于物流配送車(chē)輛導(dǎo)航路徑優(yōu)化的遺傳算法［J］．華南理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，37（2）：82－91．］

［5］WEN Huiying，LI Junhui，ZHOU Weiming．Improved particle swarm optimization algorithm for vehicle routing planning［J］．Journal of South China University of Technology：Natural Science Edition，2009，37（7）：1－5（in Chinese）．［溫惠英，李俊輝，周瑋明．適于車(chē)輛路徑規(guī)劃的改進(jìn)型粒子群優(yōu)化算法［J］．華南理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，37（7）：1－5．］

［6］LI Yanhui，LIU Xiang．Modelling and its ant colony algorithm for multi－depot open vehicle routing problem with replenishment on the way［J］．Computer Integrated Manufacturing Systems，2008，11（3）：25－34（in Chinese）．［李延暉，劉 向．沿途補(bǔ)貨的多車(chē)場(chǎng)開(kāi)放式車(chē)輛路徑問(wèn)題及蟻群算法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2008，11（3）：25－34．］

［7］JIANG Changhua，DAI Shugui，HU Youhua．Hybrid genetic algorithm for capacitated vehicle routing problem ［J］．Computer Integrated Manufacturing Systems，2007，14（10）：237－248（in Chinese）．［姜昌華，戴樹(shù)貴，胡幼華．求解車(chē)輛路徑問(wèn)題的混合遺傳算法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2007，14（10）：237－248．］

［8］CESCHIA S，DI G L，SCHAERF A．Tabu search techniques for the heterogeneous vehicle routing problem with time windows and carrier－dependent costs［J］．Journal of Scheduling，2011，14（6）：601－615．

［9］URSANI Z，ESSAM D，CORNFORTH D．Localized genetic algorithm for vehicle routing problem with time windows［J］．Applied Soft Computing，2011，11（8）：5375－5390．

［10］ZIAUDDIN U，DARY E，DAVID C，et al．Localized genetic algorithm for vehicle routing problem with time windows［J］．Applied Soft Computing，2011，11（8）：5375－5390．

［11］MACEDO R，ALVES C，VALERIO D．Solving the vehicle routing problem with time windows and multiple routes exactly using apseudo－polynomial model［J］．European Journal of Operational Research，2011，214（3）：536－545．

［12］SALANI M，VACCA I．Branch and price for the vehicle routing problem with discrete split deliveries and time windows［J］．European Journal of Operational Research，2011，213（3）：470－477．

［13］LIN C．A vehicle routing problem with pickup and delivery time windows，and coordination of transportable resources［J］．Computers ＆ Operations Research，2011，38（11）：1596－1609．

［14］MENDOZA J．Solving real－world vehicle routing problems in uncertain environments［J］．4OR－A Quarterly Journal of Operations Research，2011，9（3）：321－324．

［15］GULCZYNSKI D，GOLDEN B．WASIL E．The period vehicle routing problem：new heuristics and real－world variants［J］．Transportation Research Part E－Logistics and Transportation Review，2011，47（5）：648－668．

［16］GROER C，GOLDEN B，WASIL E．A parallel algorithm for the vehicle routing problem［J］．Informs Journal on Computing，2011，23（2）：315－330．

［17］WU Jingli，LIU Renhui．Genetic algorithm for batch vehicle routing problem with time windows［J］．Computer Engineering，2006，32（8）：213－218（in Chinese）．［吳璟莉，劉仁輝．分批配送的有時(shí)間窗車(chē)輛路徑問(wèn)題的遺傳算法［J］．計(jì)算機(jī)工程，2006，32（8）：213－218．］

［18］WANG Pengtao，LIU Yanliang，WU Jing．Solving logistics transportation based on genetic simulated annealing algorithm［J］．Journal of Computational Information Systems，2008，4（2）：559－564．