物流視角下的線性運輸問題的算法分析

胡修宇 王君悅 傅馨嶠

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

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

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

一、運輸問題模型及求解概述

1.運輸問題基本模型

2.求解概述

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

二、算法探索

算法分析：

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

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

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

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

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

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

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

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

算法3 遺傳算法

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

在本問題的遺傳算法中，染色體是基于矩陣的表達。

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

算法分析：

對于以上三種算法，我們從準確性，算法效率兩個角度來評價：

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

2.從算法效率上來說，我們做了以下實驗，對同一個問題，不同的規(guī)模下，程序消耗時間的多少（計算100次）

三、案例分析

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

針對這個實際問題，本文考慮了三種情況：

（1）無時間窗約束下的轉運

（2）有時間窗約束下的轉運

（3）對轉運站的合理利用條件下上述約束的轉運

注：時間窗是指一定的時間約束。

1.必須過轉運站無時間窗問題

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

2.不必過轉運站且無時間窗問題

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

這樣就化為無時間約束的運輸問題，就可以進行求解。

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

4.不必過轉運站有時間窗問題

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

四、總結

1.在處理無時間窗的運輸問題時，無論是否帶有轉運站，都可以將其轉化為一般運輸問題進行求解，然后求解。

2.在處理有時間窗的運輸問題時，通過增加懲罰函數(shù)，將其轉化為單目標函數(shù)進行求解。

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

參考文獻：

[1]鄒宗峰，張保全.帶混合時間窗的多目標危險化學品運輸路徑優(yōu)化.中國安全科學學報，2012，22（04）：第83-89頁.

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

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

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

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

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