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

胡修宇 王君悅 傅馨嶠

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

關鍵詞：運輸問題;圖與網絡;遺傳算法;時間窗約束;懲罰函數

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

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

1.運輸問題基本模型

2.求解概述

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

二、算法探索

算法分析：

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

算法1 表上作業法

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

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

算法2 圖與網絡方法

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

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

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

算法3 遺傳算法

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

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

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

算法分析：

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

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

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

三、案例分析

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

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

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

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

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

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

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

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

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

首先，將帶有轉運環節運輸平衡問題轉化為一般運輸平衡問題，其步驟如下：

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

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

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

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

四、總結

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

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

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

參考文獻：

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

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

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

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

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

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