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

胡修宇 王君悅 傅馨嶠

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

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

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

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

1.運輸問題基本模型

2.求解概述

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

二、算法探索

算法分析：

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

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

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

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

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

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

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

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

算法3 遺傳算法

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

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

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

算法分析：

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

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

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

三、案例分析

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

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

（1）無時間窗約束下的轉(zhuǎn)運

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

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

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

1.必須過轉(zhuǎn)運站無時間窗問題

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

2.不必過轉(zhuǎn)運站且無時間窗問題

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

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

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

4.不必過轉(zhuǎn)運站有時間窗問題

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

四、總結(jié)

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

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

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

參考文獻：

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

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

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

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

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

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