混合軸輻式零擔快運網絡車輛調度設計與實現

繆桂根

（湖南現代物流職業技術學院 物流管理學院，湖南 長沙 410131）

0 引言

零擔運輸是指貨主一次托運的貨量不足一車時，與其他貨物拼裝的運輸方式，特別適用于貨物批量較小、發貨頻次較高、發貨范圍較廣等商業情境。在零擔貨運中，如何合理組織運輸網絡十分重要。零擔運輸網絡以軸輻式網絡為主。軸輻式網絡又分為不允許網點直通的純軸輻式和允許直通的混合軸輻式。混合軸輻式零擔快運網絡中既有直達線路又有轉運線路，如何合理安排車輛路線及車型是混合軸輻式網絡運營規劃中極其重要的方面。車輛路線及車型安排問題屬于物流運籌學中的經典問題車輛調度問題（Vehicle Routing Problem，VRP）。車輛調度是將車輛選擇、路線規劃問題結合起來考慮，以保證在達成服務承諾的前提下最大限度降低運營成本。相較于傳統車輛調度問題，混合軸輻式網絡下的車輛調度問題具有更多的約束條件，如表現出多時間窗、循環取貨、直達與中轉并存、軸輻節點功能不同等特點，模型更為復雜求解難度更大。混合軸輻式網絡下的車輛調度問題研究細分領域較多，如網絡末端的集配送車輛調度、不同指派關系不同樞紐數量網絡車輛路線安排、涉及不同車型的網絡車輛路線安排、考慮時間窗的車輛路線安排等。本文研究單一指派的多樞紐混合軸輻式網絡中車輛安排問題，旨在針對節點間確定的運輸需求，安排合理的運輸路線及車型。以節點的操作處理成本、節點間的運輸成本之和最低為目標，構建具有多重時效要求的車輛調度模型，設計遺傳算法并在Matlab 中予以仿真實現。

1 模型構建

1.1 問題描述

網絡中節點分為貨運站和樞紐站，每個貨運站與樞紐站的指派關系是確定的，且每個貨運站只能指派給一個樞紐站。貨運站與貨運站之間允許直達運輸，也可以通過樞紐站中轉運輸。貨運站之間的運輸最多經過兩次中轉即可到達。這是一個典型的單一指派多樞紐混合軸輻式網絡，如圖1 所示。

圖1 單一指派多樞紐混合軸輻式網絡結構圖

1.2 數學模型

本文研究的單一指派多樞紐混合軸輻式網絡的運輸方式有兩個大類：直達運輸和中轉運輸，其中按照節點與指派樞紐的從屬關系而形成的區域，可以進一步細分為四種運輸類型，分別是區域內直達、區域間直達、區域內單樞紐中轉、區域間雙樞紐中轉。考慮到問題中網絡的節點已經建立，所以節點相關的固定成本屬于沉沒成本，在此不予考慮。總的運營成本主要考慮節點的操作處理成本、節點間的運輸成本。中轉運輸方式相較直達運輸方式，增加了樞紐的操作處理成本及起訖點間的運輸時間，但由于可以將較為分散的貨量集中起來轉運，產生了一定的規模經濟，樞紐的操作處理成本較貨站處理成本要低，轉運路段上通過使用更大車型也能夠獲得更低的單位運輸成本。在貨運站和樞紐站產生的成本主要包括裝卸、搬運、分揀、保管等帶來的費用。節點間的運輸成本包括車輛折舊費、維修費、燃料費、路橋費、駕駛員工資、稅金、管理費用等。以上運輸成本可以進一步劃分為與行駛距離相關的公里成本，如車輛折舊費、維修費、燃料費、路橋費等，以及與運輸時間相關的小時成本如駕駛員工資、稅金、管理費用等。不同車型的公里成本、小時成本不相同，相同車型在不同線路上的公里成本和小時成本也不相同。本文出于簡化問題考慮，不考慮相同車型在不同線路上的成本差異，默認各車型成本是固定值。

貨運站之間的日均貨運量已知且是確定的，可用車型已知且固定，發車班次根據路段貨量確定，且滿足各貨運站的時間窗要求。兩個貨運站之間的貨量不可拆分。在這樣一個貨運站與樞紐站指派關系確定的多樞紐軸輻式網絡中，如何合理安排各節點間線路上每日的車型及發車頻次，以達成網絡總運營成本最低的目標，就是本文擬解決的問題。綜合考慮混合軸輻式零擔網絡運營的運輸成本及節點處理成本，構建以總網絡運營成本最小為目標的數學模型如下：

目標函數的第一部分表示貨運站產生的處理成本，第二部分表示在第一轉運樞紐產生的處理成本，第三部分表示在第二轉運樞紐產生的處理成本，第四部分表示貨運站間采用直達運輸時的路段運輸成本，第五部分表示貨運站間采用中轉運輸時發生在支線上的運輸成本，第六部分表示貨運站間采用中轉運輸時發生在干線上的運輸成本。

約束條件如下：

式（2）保證各樞紐站所屬貨運站數之和等于總貨運站數量。式（3）限定了k 樞紐區域內運輸時各節點的運輸時效。式（4）限定了區域間運輸時各節點間的運輸時效；式（5）、式（6）、式（7）表示路段容量限制，限定了直達線路、支線、干線可用車型裝載量及最大車型數量；式（6）表示決策變量的含義。

2 遺傳算法設計

單一指派多樞紐混合軸輻式網絡模型為非線性整數規劃問題，隨著問題規模增大其可行解空間也快速擴大，這類問題多采用啟發式算法求解。遺傳算法是一種經典的啟發式算法，在車輛調度等非線性規劃問題中得到較多應用。通過模擬自然界生物的自然選擇、交叉、變異等機理來搜索最優解，通過反復迭代運算得到最優解。其主要流程有編碼并生成初始種群、適應度評估、選擇/交叉/變異遺傳操作。

2.1 編碼并生成初始種群

本文采取二進制染色體編碼方式。當貨運站i 到貨運站j 之間的運輸采用直達方式時，編碼為0；當貨運站i 到貨運站j 之間的運輸采用中轉方式時，編碼為1。由于本文構造的網絡模型中各節點與樞紐之間的指派關系是單一且明確的，且以各樞紐為中心形成若干小型區域網絡，區域內節點間運輸僅直達和單點中轉兩種，區域間節點間的運輸僅直達和兩點中轉兩種。因此，區域內節點間編碼為1 表示單點中轉，區域間節點間編碼為1 表示兩點中轉。由于網絡中貨運站節點總數為n，因此，染色體為n×n 規模的0～1 矩陣。

種群規模對遺傳算法運行結果和效率有著直接重要影響，種群規模過大，算法運行時間受影響，種群規模過小問題易陷入局部最優。本文以0～1 隨機數方式生成初始種群，種群規模根據問題規模通過算法試運行予以調整到較合理的狀態。

2.2 評估適應度

種群中哪些個體能夠遺傳到下一代，需要借助適應度來進行評估。適應度用來表征種群里的個體在優化過程中達到或接近于或有助于找到最優目標值的優良程度，對應自然界的“適者生存法則”，適應度值越高的個體具有更大的概率被選中遺傳到下一代。本文用目標函數的倒數作為適應度評估值。

2.3 選擇、交叉、變異

（1）選擇算子。采用最佳個體保存與輪盤賭選擇相結合的選擇策略。操作基本過程如下：對種群進行輪盤賭選擇操作，找出適應度最高和最低的個體；如果當前種群中最佳個體適應度高于前面種群遺傳下來的最佳個體的適應度，則以當前種群適應度最佳的個體替換原來種群中適應度最低的個體。選擇概率P 計算式如下，其中npop 表示種群規模。

（2）交叉算子。通過父代染色體的交叉運算能夠產生子代，子代通過交叉遺傳父代的基本特征。設交叉概率為P。選擇單點交叉方式。將種群一分為二，前后兩個部分對應的個體進行交叉，隨機確定行交叉或列交叉，隨機確定交叉點，在交叉點后編碼互換。

（3）變異算子。變異是指通過改變個體的某些基因片段值，以使遺傳算法擴大局部的隨機搜索能力，加速問題向最優解收斂，同時擴大群體的多樣性，避免群體陷入早熟。隨機選擇個體中的行或列中的隨機位置進行反向變異，即0 變為1，1 變為0，設變異概率為P。

通過上述遺傳選擇、交叉、變異等操作可以得到新的種群，新的種群經過運算迭代后得到最優解。

3 算例仿真

以一家小型零擔貨運企業的網絡為例，依據上述算法，用Matlab 編寫程序對該企業的零擔運輸網絡車輛調度問題進行仿真模擬。該企業零擔業務主要集中在4 個省份。共設置3 個轉運樞紐、10 個貨運站。各貨運站之間的日平均貨物量如表1 所示。貨運站間及貨運站與指派樞紐間、樞紐站間的距離、貨運站和樞紐站的單位處理成本已知。各貨站的時效分為區域內到達時效和區域外到達時效。直達線路和區域內轉運線路可用車型為3 噸、8 噸、17 噸三種，區域間的干線運輸可用車型為17 噸、25噸、30 噸三種。直達線路限定一輛車、轉運線路限定兩輛車。各車型成本信息如表2 所示。

表1 貨運站間日均貨運量 單位：噸

表2 車型成本信息

選取不同的算法參數進行模擬運行，當參數設置交叉概率為0.6，變異概率為0.08，種群數為300，進化迭代次數為500時，算法運行效果最好，此時的混合軸輻式網絡最小總成本是72 330 元，目標函數運算結果如圖2 所示，各路段車輛調度方案如表3 所示。

表3 路段車輛調度方案

圖2 目標函數運算結果

經計算純軸輻式網絡的運營成本為75 072 元，相較純軸輻式網絡，混合軸輻式網絡成本約節約3.65%，考慮到純軸輻式網絡部分路段容量超出現有閾值，網絡服務水平有所下降，混合軸輻式網絡相較純軸輻式網絡的成本節約實際將超過3.65%。因此，混合軸輻式網絡可以降低網絡運營成本、提高服務水平。

4 結束語

混合軸輻式零擔快運網絡是零擔運輸網絡的發展趨勢。車輛調度問題是混合軸輻式零擔快運網絡運營規劃的一個分支，車輛調度方案的優劣對網絡運營成本及服務水平有較大影響。分析單一指派多樞紐軸輻式零擔快運網絡運輸方式特點的基礎上，在車輛種類和路段容量一定且節點多時間窗的前提下，構建了網絡車輛調度模型，并編寫了遺傳算法程序在Matlab 中予以實現，實現了快速制定車輛運輸方案，從而達到降低網絡運營成本、提高服務水平的效果。由于模型采用啟發式的遺傳算法進行求解，其中涉及若干模型參數，實際應用該模型及算法時，需要根據問題中節點規模反復多次模擬找到適合問題的最佳參數組合。