胡修宇 王君悅 傅馨嶠

摘 要：隨著物流行業(yè)的快速發(fā)展，運(yùn)輸問(wèn)題也受到廣泛關(guān)注。針對(duì)運(yùn)輸問(wèn)題的一般模型，本文對(duì)表上作業(yè)法、圖與網(wǎng)絡(luò)算法和遺傳算法三種算法并進(jìn)行了對(duì)比分析。同時(shí)通過(guò)結(jié)合某運(yùn)輸企業(yè)的實(shí)例，對(duì)模型添加了時(shí)間窗和轉(zhuǎn)運(yùn)站的約束，并利用MATLAB進(jìn)行求解。在有時(shí)間窗約束下，通過(guò)引入懲罰函數(shù)使問(wèn)題得到簡(jiǎn)化，從而實(shí)現(xiàn)多角度尋找最優(yōu)解。

關(guān)鍵詞：運(yùn)輸問(wèn)題;圖與網(wǎng)絡(luò);遺傳算法;時(shí)間窗約束;懲罰函數(shù)

運(yùn)輸問(wèn)題是社會(huì)經(jīng)濟(jì)生活和軍事活動(dòng)中經(jīng)常出現(xiàn)的優(yōu)化問(wèn)題。隨著物流行業(yè)的快速崛起，其中涉及的運(yùn)輸問(wèn)題受到了廣泛的關(guān)注。如何制定調(diào)運(yùn)方案，將物資運(yùn)往指定地點(diǎn)，而且實(shí)現(xiàn)運(yùn)輸成本最小，即為運(yùn)輸問(wèn)題。運(yùn)輸問(wèn)題是特殊的線性規(guī)劃問(wèn)題，它是早期的線性網(wǎng)絡(luò)最優(yōu)化的一個(gè)例子。本文通過(guò)對(duì)比表上作業(yè)法、圖與網(wǎng)絡(luò)算法和遺傳算法三種算法并考慮轉(zhuǎn)運(yùn)站和時(shí)間窗約束從多角度分析物流過(guò)程中存在的運(yùn)輸問(wèn)題。

一、運(yùn)輸問(wèn)題模型及求解概述

1.運(yùn)輸問(wèn)題基本模型

2.求解概述

本文只討論線性運(yùn)輸問(wèn)題，線性運(yùn)輸問(wèn)題的含義是：從不同的供給起點(diǎn)或來(lái)源向不同的終點(diǎn)運(yùn)送同一種物品，每個(gè)終點(diǎn)需要特定數(shù)量的物品。問(wèn)題是：如何分配在每個(gè)起點(diǎn)的供給，以便在滿足每個(gè)終點(diǎn)需求的條件下，優(yōu)化某一個(gè)或幾個(gè)目標(biāo)，例如運(yùn)輸費(fèi)用最小，運(yùn)輸時(shí)間最短等。

二、算法探索

算法分析：

對(duì)于最基本的運(yùn)輸問(wèn)題模型，可以使用運(yùn)籌學(xué)求解器GAMS、Lingo進(jìn)行求解，求解器其本身調(diào)用的IP或MIP求解的算法，為了探究更高效的算法，本文總結(jié)比較了三種算法。

算法1 表上作業(yè)法

表上作業(yè)法是一種依賴于手工作業(yè)的方法，算法的流程圖如下：

表上作業(yè)法通常情況下只適用于規(guī)模比較小的問(wèn)題進(jìn)行直觀地演算，當(dāng)規(guī)模較大時(shí)，表上作業(yè)法的效率很低，而且易于出錯(cuò)，對(duì)于實(shí)際問(wèn)題而言不宜于實(shí)際操作，僅在教學(xué)中方便演示線性規(guī)劃問(wèn)題的細(xì)節(jié)。

算法2 圖與網(wǎng)絡(luò)方法

該算法拋棄了圖上作業(yè)表格的想法，從圖論的角度出發(fā)，將產(chǎn)地和銷售地視為網(wǎng)絡(luò)中的節(jié)點(diǎn)，節(jié)點(diǎn)之間的有向弧表示兩地之間可以連接，并且弧上的權(quán)值代表兩地之間的運(yùn)輸費(fèi)用或者運(yùn)輸時(shí)間，同時(shí)，在產(chǎn)地和銷地兩側(cè)分別加上虛擬節(jié)點(diǎn)s，t（如圖2），虛擬節(jié)點(diǎn)與產(chǎn)銷地節(jié)點(diǎn)之間權(quán)值為0。

下面根據(jù)圖論中的最小費(fèi)用流算法，通過(guò)在原圖上建立增廣鏈，并在增廣鏈上進(jìn)行調(diào)整，循環(huán)迭代，直到找不到增廣鏈，即找到滿足條件的最小費(fèi)用流。

使用圖論的方法，大大簡(jiǎn)化了問(wèn)題的本身，易于編程實(shí)現(xiàn)，使用范圍很廣闊，理論上可以求出任何一個(gè)問(wèn)題的最優(yōu)解（在存在最優(yōu)解的條件下），但往往會(huì)耗費(fèi)大量的計(jì)算資源，但是在實(shí)際工程中有時(shí)不需要十分精確，在較少的計(jì)算資源條件下獲得最大的效益是實(shí)際中追求的目標(biāo)。

算法3 遺傳算法

遺傳算法是計(jì)算數(shù)學(xué)中用于解決最優(yōu)化的搜索算法，是進(jìn)化算法的一種。遺傳算法通常實(shí)現(xiàn)方式為一種計(jì)算機(jī)模擬。進(jìn)化從完全隨機(jī)個(gè)體的種群開(kāi)始，之后一代一代發(fā)生。在每一代中，整個(gè)種群的適應(yīng)度被評(píng)價(jià)，從當(dāng)前種群中隨機(jī)地選擇多個(gè)個(gè)體（基于它們的適應(yīng)度），通過(guò)自然選擇和突變產(chǎn)生新的生命種群，該種群在算法的下一次迭代中成為當(dāng)前種群。

在本問(wèn)題的遺傳算法中，染色體是基于矩陣的表達(dá)。

由于遺傳算法本身依賴于一定的初始種群特征，如果初始種群的生成效果不好，有可能會(huì)導(dǎo)致收斂過(guò)快或過(guò)慢，為了減少這種影響，我們認(rèn)為規(guī)定只迭代50次，如果在50次之內(nèi)就收斂了，那么就以那個(gè)為準(zhǔn)，如果沒(méi)有，就在第50代中尋找最好的那個(gè)解。

算法分析：

對(duì)于以上三種算法，我們從準(zhǔn)確性，算法效率兩個(gè)角度來(lái)評(píng)價(jià)：

1.從準(zhǔn)確性來(lái)說(shuō)，表上作業(yè)法和圖論中最小費(fèi)用流的方法都是對(duì)于問(wèn)題的精確求解，而遺傳算法本身屬于啟發(fā)式的搜索算法，當(dāng)?shù)螖?shù)足夠多的時(shí)候，其最優(yōu)解和精確解差異不大;反之，迭代次數(shù)或者中間某些參數(shù)選取的不合適的時(shí)候，其準(zhǔn)確性上有所欠缺。

2.從算法效率上來(lái)說(shuō)，我們做了以下實(shí)驗(yàn)，對(duì)同一個(gè)問(wèn)題，不同的規(guī)模下，程序消耗時(shí)間的多少（計(jì)算100次）

三、案例分析

某運(yùn)輸企業(yè)主要從南京倉(cāng)庫(kù)、北京倉(cāng)庫(kù)、成都倉(cāng)庫(kù)、廣州倉(cāng)庫(kù)、沈陽(yáng)倉(cāng)庫(kù)發(fā)貨提供給全國(guó)各地區(qū)的主要58個(gè)門店，中途有3個(gè)中轉(zhuǎn)站，運(yùn)轉(zhuǎn)貨物到門店。

針對(duì)這個(gè)實(shí)際問(wèn)題，本文考慮了三種情況：

（1）無(wú)時(shí)間窗約束下的轉(zhuǎn)運(yùn)

（2）有時(shí)間窗約束下的轉(zhuǎn)運(yùn)

（3）對(duì)轉(zhuǎn)運(yùn)站的合理利用條件下上述約束的轉(zhuǎn)運(yùn)

注：時(shí)間窗是指一定的時(shí)間約束。

1.必須過(guò)轉(zhuǎn)運(yùn)站無(wú)時(shí)間窗問(wèn)題

該問(wèn)題等價(jià)于運(yùn)輸基本模型問(wèn)題套用兩次，可以利用圖與網(wǎng)絡(luò)方法快速求解，在這里不再一一贅述。

2.不必過(guò)轉(zhuǎn)運(yùn)站且無(wú)時(shí)間窗問(wèn)題

首先，將帶有轉(zhuǎn)運(yùn)環(huán)節(jié)運(yùn)輸平衡問(wèn)題轉(zhuǎn)化為一般運(yùn)輸平衡問(wèn)題，其步驟如下：

這樣就化為無(wú)時(shí)間約束的運(yùn)輸問(wèn)題，就可以進(jìn)行求解。

對(duì)于新增加的時(shí)間窗約束，可以用一個(gè)新的函數(shù)來(lái)轉(zhuǎn)化，本文稱之為時(shí)間約束函數(shù)，每當(dāng)找出一條最小費(fèi)用增廣鏈的時(shí)候，就利用該函數(shù)來(lái)進(jìn)行判斷，是否滿足時(shí)間窗的條件，如果早到或者晚到，都需要進(jìn)行懲罰即費(fèi)用的增加，不斷循環(huán)，直到找不到最小費(fèi)用增廣鏈為止。最后計(jì)算總的費(fèi)用。

4.不必過(guò)轉(zhuǎn)運(yùn)站有時(shí)間窗問(wèn)題

該問(wèn)題可以由上述問(wèn)題三經(jīng)過(guò)變換求解，同樣可以利用圖論快速求解，這里就不再贅述。

四、總結(jié)

1.在處理無(wú)時(shí)間窗的運(yùn)輸問(wèn)題時(shí)，無(wú)論是否帶有轉(zhuǎn)運(yùn)站，都可以將其轉(zhuǎn)化為一般運(yùn)輸問(wèn)題進(jìn)行求解，然后求解。

2.在處理有時(shí)間窗的運(yùn)輸問(wèn)題時(shí)，通過(guò)增加懲罰函數(shù)，將其轉(zhuǎn)化為單目標(biāo)函數(shù)進(jìn)行求解。

3.由問(wèn)題案例出發(fā)，深入探討運(yùn)輸問(wèn)題，對(duì)于有無(wú)時(shí)間窗，有無(wú)轉(zhuǎn)運(yùn)站的情況分別進(jìn)行了討論研究，從特殊問(wèn)題一般化等角度分別切入，分別應(yīng)用遺傳算法，轉(zhuǎn)化問(wèn)題等多種算法進(jìn)行運(yùn)算，得到最終結(jié)果，對(duì)比不同算法發(fā)現(xiàn)，在處理運(yùn)輸問(wèn)題時(shí)更應(yīng)該突破傳統(tǒng)課本束縛，從更多角度進(jìn)行求解，對(duì)比得到最接近最優(yōu)解的可行解。

參考文獻(xiàn)：

[1]鄒宗峰，張保全.帶混合時(shí)間窗的多目標(biāo)危險(xiǎn)化學(xué)品運(yùn)輸路徑優(yōu)化.中國(guó)安全科學(xué)學(xué)報(bào)，2012，22（04）：第83-89頁(yè).

[2]呂學(xué)偉，楊斌，黃振東.混合時(shí)間窗約束下多式聯(lián)運(yùn)最優(yōu)路徑選擇研究.鐵道運(yùn)輸與經(jīng)濟(jì)，2018，40（08）：第6-11頁(yè).

[3]王曉林.時(shí)間窗約束運(yùn)輸問(wèn)題的一種算法，中國(guó)企業(yè)運(yùn)籌學(xué)學(xué)術(shù)交流大會(huì)，2007.中國(guó)重慶：第4頁(yè).

[4]周婷，周愛(ài)蓮.基于時(shí)間成本的地下物流配送路線優(yōu)化模型.物流工程與管理，2016，38（08）：第60-62+87頁(yè).

[5]覃運(yùn)梅，郝忠娜，王玲玲.零擔(dān)貨物的物流配送優(yōu)化方法.柳州職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2006（02）：第24-26頁(yè).

作者簡(jiǎn)介：胡修宇（1998.12- ），男，漢族，山東菏澤人，北京交通大學(xué)，本科在讀，研究方向：交通運(yùn)輸（鐵道運(yùn)輸方向）