路 婷 （鄭州工商學(xué)院 信息工程學(xué)院，河南 鄭州 451400）

0 引 言

與傳統(tǒng)的單一運輸方式相比，多式聯(lián)運可以發(fā)揮各種運輸方式的優(yōu)勢，使貨物運輸更加經(jīng)濟、靈活，因此多式聯(lián)運的路徑優(yōu)化問題也受到了越來越多的關(guān)注[1]。文章建立了智能物流網(wǎng)絡(luò)問題的數(shù)學(xué)模型，并用約束方法求解，研究了道路擁擠條件下不同碳排放政策對多式聯(lián)運路線選擇的影響，研究了在貨物需求不同時多式聯(lián)運路線的優(yōu)化問題。鄭強提出了一種帶精英策略的非支配排序遺傳算法的研究與應(yīng)用[2]，并設(shè)計了一種多信息密集算法來解決多式運輸路徑優(yōu)化的問題。雷定猷等建立了多式運輸路徑再利用規(guī)劃模型，解決了大宗貨物收益投資比最大化的問題[3]。劉學(xué)之等建立了一個考慮客戶服務(wù)時間窗口的包含環(huán)境成本的多式運輸模型并求解[4]。雷異考慮了時間表對多式運輸路線選擇的影響，所以將所有中轉(zhuǎn)節(jié)點的時間表都設(shè)成相同的[5]。

在現(xiàn)實生活中，鐵路運輸和水路運輸通常都有固定的時間表，一旦錯過，就要等待下一次發(fā)車時間。在不同的城市之間使用不同的交通方式可能會有不同的時間表。因此，本文將建立一個在相同時間限制下的多式運輸路線優(yōu)化模型?？紤]到智能算法在這類問題中的優(yōu)越性，設(shè)計了一種具有保存策略和轉(zhuǎn)移策略的遺傳算法來求解該模型。

多式聯(lián)運系統(tǒng)的目的是提供各種出行方式。如何在這些出行方式之間做出明智的選擇，或者將某些出行方式結(jié)合起來，正成為一個棘手的問題。多模式路線被定義為包含兩種或兩種以上不同模式的路線，不同出行方式的自由組合是其本質(zhì)特征。然而，很少有研究專注于此。出于自由組合的考慮，戰(zhàn)略驅(qū)動的時間消耗已經(jīng)接近于一個硬負(fù)擔(dān)。如何以最小的計算代價組合不同模式，以滿足出行者的個性化需求是多聯(lián)式最優(yōu)路徑規(guī)劃的瓶頸。

將路徑規(guī)劃問題歸為一個優(yōu)化問題，目的是在確定需求下提供可行路徑。在單一標(biāo)準(zhǔn)時代(最短路問題)，該算法被認(rèn)為是一種有代表性的解決方案，是一種精確的算法。然而，現(xiàn)實世界中的優(yōu)化問題很難用一個標(biāo)準(zhǔn)、一個結(jié)果來表示。在考慮多準(zhǔn)則時，經(jīng)常會出現(xiàn)沖突，即一個準(zhǔn)則的改進可能導(dǎo)致另一個準(zhǔn)則的惡化，精確的算法也無法很好地處理這種沖突。由于遺傳算法同時處理一組解，并且在一個過程中有多個不同的解，因此它是處理多準(zhǔn)則優(yōu)化問題的一種有效算法。在多模式旅行環(huán)境中，利用具有多個部分的變長染色體(子染色體)來表征各個部分所描述的一種運輸方式。在單模式下重新定義了交叉和變異算子，將超交叉和超變異兩種新算子定義為模式間操作。在選擇最優(yōu)解時，可以采用具有支配概念的代表多個準(zhǔn)則的p維向量。

本文的結(jié)構(gòu)組織如下：首先介紹相關(guān)工作，其次描述了所關(guān)注問題，然后介紹一種多模態(tài)網(wǎng)絡(luò)模型，接著提出了一種改進的多準(zhǔn)則路徑規(guī)劃方法，并給出了實驗和結(jié)果，最后歸納出結(jié)論。

1 問題描述和模型建立

1.1 問題描述

在起始城市有一批貨物需要在規(guī)定時間內(nèi)運送到目的地城市。中心城市為多節(jié)點城市，各城市之間的公路、水路、鐵路至少有一種交通方式。當(dāng)選擇公路運輸時，可以直接離開。但是當(dāng)選擇鐵路運輸和水路運輸時，發(fā)車時間受到固定時間表的限制。以總運輸成本最小為目標(biāo)確定多式聯(lián)運方案，假設(shè)條件如下: 貨物在運輸過程中不能分離；運輸方式的轉(zhuǎn)換只發(fā)生在節(jié)點城市，轉(zhuǎn)運作業(yè)在到達城市后立即開始；不同運輸方式的速度和成本在不同的城市之間是相同的。

1.2 優(yōu)化模式有時間限制的多式運輸路線優(yōu)化模式

目標(biāo)函數(shù)(1)最小化總成本，包括運輸成本、運輸成本、等待成本和碳排放成本。

約束(2)意味著任意兩個節(jié)點最多只能通過一種運輸方式進行運輸。約束(3)意味著在任意一個節(jié)點只能進行一種運輸方式的轉(zhuǎn)換。約束(4)表示節(jié)點貨流平衡，起點城市為o，目的地城市為d。約束(1)意味著節(jié)點i處的貨物進入運輸方式k，當(dāng)貨物離開運輸方式l 時，運輸方式轉(zhuǎn)換發(fā)生在節(jié)點i，保證了運輸方式的連續(xù)性。約束(2)表示使用運輸方式k在不同城市之間的運輸時間。約束(3)表示貨物在節(jié)點i等待中轉(zhuǎn)的時間。它意味著如果貨物比中轉(zhuǎn)操作時間早到達節(jié)點i，將支付等待費用。約束(4)表示貨物在節(jié)點完成過境操作時等待運輸方式l 離開的時間。約束(1)表示貨物的總運輸時間。貨物離開一個節(jié)點轉(zhuǎn)移到下一個節(jié)點的時間包括運輸時間、等待轉(zhuǎn)運時間、轉(zhuǎn)運時間和裝貨后等待離開的時間。約束條件(2)以確保貨物在規(guī)定的時間窗口內(nèi)運送到目的地城市d。約束(3)意味著決策變量是0～1 個變量。

2 設(shè)計算法

多式運輸路徑最佳化問題是一個難題，可以用智能算法來解決。遺傳算法具有良好的全局搜索能力，在求解該問題時更加方便。因此，本文將采用遺傳算法對上述模型進行求解。與傳統(tǒng)的遺傳算法相比，在算法設(shè)計中采用了保持策略和轉(zhuǎn)移策略。保持策略可以確保種群中的優(yōu)勢個體能夠在下一代繼續(xù)存在，從而使整個優(yōu)化過程朝著更好的方向發(fā)展。轉(zhuǎn)移策略可以保證人口的多樣性，避免過早地陷入局部最優(yōu)解。具體的設(shè)計思路如下。

2.1 多式聯(lián)運路徑優(yōu)化組合

考慮到多式聯(lián)運路徑優(yōu)化問題是一個組合優(yōu)化的問題，運輸路徑和運輸方式的選擇會影響結(jié)果，因此采用雙層編碼結(jié)構(gòu)，兩者均為實數(shù)編碼。第一層是運輸路徑的編碼，長度是n，第二層是運輸方式的編碼，長度是n-1。這兩部分的代碼共同形成一個完整的染色體代碼，如下所示。

在解碼時，代碼的第一部分表示貨物依次通過的節(jié)點數(shù)，代碼的第二部分表示相鄰節(jié)點之間選擇的運輸方式。應(yīng)注意的是，編碼中目標(biāo)城市d后面的節(jié)點都是無效節(jié)點，因此只有前面的節(jié)點會被解碼。

2.2 交通路線生成初始種群

第一個數(shù)字固定為1，表示出發(fā)城市，然后對剩余的節(jié)點進行隨機排序。在交通方式方面，根據(jù)鄰近城市之間可以選擇的交通方式隨機生成一個數(shù)字，目的地城市之后的數(shù)字均為0。根據(jù)上述原則，生成初始個體，直到滿足人口數(shù)量的要求。

2.3 計算適應(yīng)度

由于本文所尋求的是最小化問題，并且在后續(xù)的選擇算子中采用了取大原則，因此每個個體所計算的總成本的倒數(shù)被作為適應(yīng)度。此外，為了確保貨物按時交付，在到達時間窗口之外的計劃目標(biāo)值過程中增加了足夠大的罰金值。這意味著貨物不能早于或晚于指定的時間段到達。

2.4 基因操作

新的種群將來自三個部分。首先，根據(jù)初始種群中的個體數(shù)、保存率、轉(zhuǎn)移率和遺傳比確定每個新種群中的個體數(shù)。然后選擇親本群體中適合度較高的個體獲得第一個群體g1。根據(jù)先前的原理，產(chǎn)生一定數(shù)量的新群體，形成第二個種群g2。新群體經(jīng)過選擇、雜交和突變，形成第三個群體g3。選擇運算符使用選擇的輪盤賭方法，交叉計算采用單點交叉法。變異運算符使用兩點交換變異。在新種群中會產(chǎn)生一些不可行個體，最后利用修正算子對不可行個體的運輸方式編碼進行修改，使其可行。當(dāng)達到指定的迭代次數(shù)時，輸出當(dāng)前最優(yōu)個體的目標(biāo)值，算法結(jié)束。

3 案例研究

有20 噸的貨物將從起點城市被運輸?shù)降侥康牡爻鞘?，并使用一個20 英尺的集裝箱。中間有9 個節(jié)點城市。隨機生成城市之間的距離和水路、鐵路運輸?shù)臅r間表。碳排放成本為0.1 元/公斤，接收時間窗口為h/TEU，其他的相關(guān)參數(shù)值見表1和表2。

表1 各種運輸方式有關(guān)參數(shù)值

表2 轉(zhuǎn)運有關(guān)參數(shù)值

根據(jù)已建立的多式運輸路線優(yōu)化模型，采用保存策略和轉(zhuǎn)移策略的遺傳算法，通過matlab2016b 軟件編程求解。遺傳算法的相關(guān)參數(shù)為: 種群大小為100，迭代次數(shù)為500，保存率為0.1，轉(zhuǎn)移率為0.1，遺傳比為0.8，交叉概率為0.8，變異概率為0.5。計算結(jié)果如下: 運輸路線為1(o) -9-10-11(d)，運輸方式為鐵路-公路-鐵路，總運輸成本為6 722.328 元，總運輸時間為54.216 7 小時。

為了驗證出發(fā)時間是否會影響運輸計劃的選擇，接下來將選擇不同的出發(fā)時間進行計算。計算結(jié)果見表2?？梢钥吹?，當(dāng)出發(fā)時間發(fā)生變化時，交通方案的選擇也會發(fā)生變化。因此，適當(dāng)提前起飛時間可以有效地降低運輸成本。

4 結(jié) 論

制定合理的多式運輸計劃是發(fā)揮多式聯(lián)運優(yōu)勢的關(guān)鍵。本文建立的多式運輸路線優(yōu)化模型考慮了固定時間表對運輸時間和運輸成本的影響，因此更加實用。經(jīng)過大量的計算和測試，本文設(shè)計的遺傳算法能夠有效避免陷入局部最優(yōu)解，并能夠快速得到結(jié)果，從而證明算法的可行性，為多式運輸運營商制定運輸方案提供了有用的參考。

多式聯(lián)運規(guī)劃的目的是為出行者提供最優(yōu)的、可行的和個性化的出發(fā)點和目的地之間的路徑，這會涉及公共和私人出行方式。對此提出了一種改進的多模型、多準(zhǔn)則環(huán)境下的航路規(guī)劃方法，在單模型下重新定義了交叉和變異算法，將超交叉和變異定義為模型操作。針對不同的需求，采用基于向量的評價方法來表示多個指標(biāo)，通過應(yīng)用遺傳算法，給出最優(yōu)解，該方法實現(xiàn)了旅行模式與各種個體需求之間的自由組合，操作簡單，且智能化程度較高。在多模型網(wǎng)絡(luò)的基礎(chǔ)上進行了一個實驗，研究結(jié)果表明，多種模式組合能夠適應(yīng)不同情況，結(jié)果符合目標(biāo)，為了改進非唯一解的演化運算，今后需要研究多目標(biāo)優(yōu)化的問題。目前的遺傳算法是有用的，不過需要大量的運行時間。但是，研究中仍然存在一些不足之處，如沒有考慮進度、延遲等不確定因素，這些將是未來進一步研究的主題。