混合軸輻式零擔(dān)快運(yùn)網(wǎng)絡(luò)車輛調(diào)度設(shè)計與實(shí)現(xiàn)

繆桂根

（湖南現(xiàn)代物流職業(yè)技術(shù)學(xué)院 物流管理學(xué)院，湖南 長沙 410131）

0 引言

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

1 模型構(gòu)建

1.1 問題描述

網(wǎng)絡(luò)中節(jié)點(diǎn)分為貨運(yùn)站和樞紐站，每個貨運(yùn)站與樞紐站的指派關(guān)系是確定的，且每個貨運(yùn)站只能指派給一個樞紐站。貨運(yùn)站與貨運(yùn)站之間允許直達(dá)運(yùn)輸，也可以通過樞紐站中轉(zhuǎn)運(yùn)輸。貨運(yùn)站之間的運(yùn)輸最多經(jīng)過兩次中轉(zhuǎn)即可到達(dá)。這是一個典型的單一指派多樞紐混合軸輻式網(wǎng)絡(luò)，如圖1 所示。

圖1 單一指派多樞紐混合軸輻式網(wǎng)絡(luò)結(jié)構(gòu)圖

1.2 數(shù)學(xué)模型

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

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

目標(biāo)函數(shù)的第一部分表示貨運(yùn)站產(chǎn)生的處理成本，第二部分表示在第一轉(zhuǎn)運(yùn)樞紐產(chǎn)生的處理成本，第三部分表示在第二轉(zhuǎn)運(yùn)樞紐產(chǎn)生的處理成本，第四部分表示貨運(yùn)站間采用直達(dá)運(yùn)輸時的路段運(yùn)輸成本，第五部分表示貨運(yùn)站間采用中轉(zhuǎn)運(yùn)輸時發(fā)生在支線上的運(yùn)輸成本，第六部分表示貨運(yùn)站間采用中轉(zhuǎn)運(yùn)輸時發(fā)生在干線上的運(yùn)輸成本。

約束條件如下：

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

2 遺傳算法設(shè)計

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

2.1 編碼并生成初始種群

本文采取二進(jìn)制染色體編碼方式。當(dāng)貨運(yùn)站i 到貨運(yùn)站j 之間的運(yùn)輸采用直達(dá)方式時，編碼為0；當(dāng)貨運(yùn)站i 到貨運(yùn)站j 之間的運(yùn)輸采用中轉(zhuǎn)方式時，編碼為1。由于本文構(gòu)造的網(wǎng)絡(luò)模型中各節(jié)點(diǎn)與樞紐之間的指派關(guān)系是單一且明確的，且以各樞紐為中心形成若干小型區(qū)域網(wǎng)絡(luò)，區(qū)域內(nèi)節(jié)點(diǎn)間運(yùn)輸僅直達(dá)和單點(diǎn)中轉(zhuǎn)兩種，區(qū)域間節(jié)點(diǎn)間的運(yùn)輸僅直達(dá)和兩點(diǎn)中轉(zhuǎn)兩種。因此，區(qū)域內(nèi)節(jié)點(diǎn)間編碼為1 表示單點(diǎn)中轉(zhuǎn)，區(qū)域間節(jié)點(diǎn)間編碼為1 表示兩點(diǎn)中轉(zhuǎn)。由于網(wǎng)絡(luò)中貨運(yùn)站節(jié)點(diǎn)總數(shù)為n，因此，染色體為n×n 規(guī)模的0～1 矩陣。

種群規(guī)模對遺傳算法運(yùn)行結(jié)果和效率有著直接重要影響，種群規(guī)模過大，算法運(yùn)行時間受影響，種群規(guī)模過小問題易陷入局部最優(yōu)。本文以0～1 隨機(jī)數(shù)方式生成初始種群，種群規(guī)模根據(jù)問題規(guī)模通過算法試運(yùn)行予以調(diào)整到較合理的狀態(tài)。

2.2 評估適應(yīng)度

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

2.3 選擇、交叉、變異

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

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

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

通過上述遺傳選擇、交叉、變異等操作可以得到新的種群，新的種群經(jīng)過運(yùn)算迭代后得到最優(yōu)解。

3 算例仿真

以一家小型零擔(dān)貨運(yùn)企業(yè)的網(wǎng)絡(luò)為例，依據(jù)上述算法，用Matlab 編寫程序?qū)υ撈髽I(yè)的零擔(dān)運(yùn)輸網(wǎng)絡(luò)車輛調(diào)度問題進(jìn)行仿真模擬。該企業(yè)零擔(dān)業(yè)務(wù)主要集中在4 個省份。共設(shè)置3 個轉(zhuǎn)運(yùn)樞紐、10 個貨運(yùn)站。各貨運(yùn)站之間的日平均貨物量如表1 所示。貨運(yùn)站間及貨運(yùn)站與指派樞紐間、樞紐站間的距離、貨運(yùn)站和樞紐站的單位處理成本已知。各貨站的時效分為區(qū)域內(nèi)到達(dá)時效和區(qū)域外到達(dá)時效。直達(dá)線路和區(qū)域內(nèi)轉(zhuǎn)運(yùn)線路可用車型為3 噸、8 噸、17 噸三種，區(qū)域間的干線運(yùn)輸可用車型為17 噸、25噸、30 噸三種。直達(dá)線路限定一輛車、轉(zhuǎn)運(yùn)線路限定兩輛車。各車型成本信息如表2 所示。

表1 貨運(yùn)站間日均貨運(yùn)量 單位：噸

表2 車型成本信息

選取不同的算法參數(shù)進(jìn)行模擬運(yùn)行，當(dāng)參數(shù)設(shè)置交叉概率為0.6，變異概率為0.08，種群數(shù)為300，進(jìn)化迭代次數(shù)為500時，算法運(yùn)行效果最好，此時的混合軸輻式網(wǎng)絡(luò)最小總成本是72 330 元，目標(biāo)函數(shù)運(yùn)算結(jié)果如圖2 所示，各路段車輛調(diào)度方案如表3 所示。

表3 路段車輛調(diào)度方案

圖2 目標(biāo)函數(shù)運(yùn)算結(jié)果

經(jīng)計算純軸輻式網(wǎng)絡(luò)的運(yùn)營成本為75 072 元，相較純軸輻式網(wǎng)絡(luò)，混合軸輻式網(wǎng)絡(luò)成本約節(jié)約3.65%，考慮到純軸輻式網(wǎng)絡(luò)部分路段容量超出現(xiàn)有閾值，網(wǎng)絡(luò)服務(wù)水平有所下降，混合軸輻式網(wǎng)絡(luò)相較純軸輻式網(wǎng)絡(luò)的成本節(jié)約實(shí)際將超過3.65%。因此，混合軸輻式網(wǎng)絡(luò)可以降低網(wǎng)絡(luò)運(yùn)營成本、提高服務(wù)水平。

4 結(jié)束語

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