考慮駕駛員需求的定位運輸線路安排問題

(華南理工大學(xué)土木與交通學(xué)院， 廣東廣州510640)

0 引言

定位運輸線路安排問題(location routing problem，LRP)是在車輛路徑問題上的拓展，都屬于NP-hard難題，在該問題的模型研究和求解上國外學(xué)者起步較早。1959年DANTZIG等[1]在針對運輸問題的研究過程中，首次提出了對于車輛路徑問題的探討，MARANZANA[2]研究了對于最小化運輸成本問題的求解辦法和思路，并在研究中考慮了貨物供應(yīng)點的位置確定；WEBB[3]針對可能涉及到的倉庫選址進行了函數(shù)的描述和分析；通過系統(tǒng)的歸納和總結(jié),COOPER等[4-5]將這一涉及到倉庫選址的車輛路徑問題概括為了運輸—定位問題(transportation-location problem, TLP )，并描述了準確的目標函數(shù)，其中已經(jīng)涉及到對于設(shè)施的選址和車輛路徑的優(yōu)化。

定位運輸線路安排問題首先要涉及到對于車輛運輸服務(wù)中心(或稱為倉庫)的選址，隨后就是車輛運輸路徑的確定，與車輛路徑問題相比需要考慮的限制條件和目標函數(shù)也更為復(fù)雜。GUERRERO等[6]學(xué)者提出了定位運輸問題涉及的配送中心的混合整數(shù)線性模型；NEKOOGHADIRLI等[7]提出了一個雙目標的LRP庫存模型，該模型中包含了多形式貨物時間周期以及多形式的運輸貨物；MARINAKIS[8]針對定位運輸問題展開了涉及隨機需求量的規(guī)劃研究；GOODARZI等[9]研究了包含部分貨物供應(yīng)點、交叉貨物對接中心，交通樞紐多路徑的可能性的一種對LRP問題的拓展研究。RUI等[10]在該類LRP問題上設(shè)計了一種混合式的遺傳算法進行智能算法的求解；RIQUELME-RODRGUEZ等[11]針對露天煤礦區(qū)的水庫選址的實際問題探討了帶庫存約束的定位運輸問題；YAKICI[12]將無人機的飛行路徑規(guī)劃與定位運輸問題相結(jié)合；MOSHREF-JAVADI等[13]提出了以最小化等待時間為目標的定位運輸問題，在模型中充分考慮了運輸時間的因素，該模型能應(yīng)用到災(zāi)后救援中；SCHIFFE等[14]探討了包含時間窗的電動汽車商業(yè)化環(huán)境下帶充電基礎(chǔ)設(shè)施選址的定位運輸問題，并運用了一種帶自適應(yīng)的大鄰域搜索算法來求解。

國內(nèi)現(xiàn)階段針對LRP問題的研究開展較晚，現(xiàn)有的文獻也比較有限，張潛等[15-16]從多角度來分析定位運輸問題并利用遺傳算法求解相應(yīng)模型；杜綱等[17]構(gòu)建了定位—運輸路線安排問題的雙層規(guī)劃模型；王紹仁等[18]將定位運輸問題應(yīng)用在災(zāi)后應(yīng)急響中，王永等[19]也針對地震后的定位運輸問題進行了分析。

人工蜂群算法提出相對于其他智能體算法的提出較晚，由KARABOGA等[20]于2004提出，運用大量函數(shù)進行了測試并證明了人工蜂群算法(artificial bee colony algorithm，ABC)的優(yōu)越性。CHEN等[21]在傳統(tǒng)二級定位運輸問題(LRP)的研究上采用了變鄰域搜索的人工蜂群算法進行了拓展研究，并在仿真對比研究中證明了該算法一定程度上的有效性。隨后人工蜂群算法快速發(fā)展并逐步用于多個鄰域的研究和分析，HUO等[22]在針對黑河的文水研究上采用了改進了的并行計算的MPABC算法從而提高人工蜂群算法的性能；ZHANG等[23]針對車輛路徑問題的研究上結(jié)合考慮了時間窗的約束以及貨物托盤的容量限制條件，并運用人工蜂群算法進行求解研究；WABG等[24]提出了一種改進的基于記憶的人工蜂群算法(IABCM)，并將該算法用于信息數(shù)據(jù)的代表性特征選擇；ZHANG等[25]提出了一種混合式的人工蜂群算法，將人工免疫系統(tǒng)算法(AIS)與人工蜂群算法融合，并運用此改進算法解決了針對飽和異構(gòu)車隊容量限制的二維負載約束車輛路徑問題(2L-HFCVRP)；GUO等[26]將人工蜂群算法運用到了逆向物流(RL)涉及的車輛路徑問題(VRP)和定位運輸問題(LRP)的研究中，提出了鄰域貪婪調(diào)整的人工蜂群算法；近幾年內(nèi)國內(nèi)的文獻也針對人工蜂群算法展開了研究，畢曉君等[27]結(jié)合自由搜索算法中的信息素、靈敏度模型以及OBL策略對人工蜂群算法進行提高和改進，并運用標準測試函數(shù)進行校驗；王志剛等[28]采用鄰域倒位的人工蜂群算法針對車輛路徑問題(VRP)提出了求解的思路；毛聲等[29]學(xué)者提出了雙重進化的半隨機式搜索的人工蜂群算法來求解車輛路徑問題，并根據(jù)是否有載重限制進行了分別的計算研究。

綜上所述，現(xiàn)階段的LRP問題研究中主要以構(gòu)建整個系統(tǒng)的成本最優(yōu)化為出發(fā)點，均沒有涉及到對駕駛員的生理和心理的需求，以及車輛排班、到發(fā)計劃的人性化設(shè)計。且現(xiàn)階段尚未有文獻嘗試利用人工蜂群算法對于這類LRP問題進行求解和分析，因此本文也為人工蜂群算法的應(yīng)用范圍的拓展提供了有效嘗試，同時也為求解LRP問題提供了新方法。根據(jù)在長途的駕駛中，駕駛員需要合理的休息時間，主要包括連續(xù)長途駕駛的時間限制、午飯時間、午休時間等，本文搭建了考慮駕駛員需求的LRP問題(location routing problem with driver needs, LRPDN)模型，根據(jù)該問題提出了一種改進的交叉鄰域生成的人工蜂群算法(artificial bee colony algorithm with cross-neighborhood search，ABCCNS)進行該問題的求解和分析，并進行了算例的驗證。

1 考慮駕駛員需求的LRP問題模型建立

1.1 問題描述

定位運輸線路安排問題(location routing problem, LRP)可以表述為：在已知的多個運輸服務(wù)中心的備選地址中選取一個或多個地址，并根據(jù)已知的多個客戶點確定出相應(yīng)的運輸路徑，在滿足限制條件的基礎(chǔ)下保證整個物流網(wǎng)絡(luò)的總成本最小化。但在現(xiàn)實的運輸過程中，駕駛員不可能高強度的連續(xù)工作，駕駛員在長期的駕車中基本的生理需求和心理需求也難以得到滿足。該考慮駕駛員需求的LRP問題模型中重點增加了車輛走行路徑中對駕駛員休息需求的限制以及對應(yīng)產(chǎn)生的復(fù)雜時間窗限制，保證每一條路徑在生成時都合理預(yù)留了駕駛員的休息時間，在保證駕駛員的健康的情況下盡可能的追求物流網(wǎng)絡(luò)總成本的最小化。

該考慮駕駛員需求的LRP模型基于以下假設(shè)：①在整個物流網(wǎng)絡(luò)中，存在多個配送服務(wù)中心的備選地址，可以選取一個或多個地址短期租用或長期建設(shè)配送服務(wù)中心；②每一個客戶點的需求量、位置以及需求點之間的車輛走行距離已知，且每一個客戶點只能由一輛車來完成配送任務(wù)；③車輛、配送服務(wù)中心的固定成本、各個客戶點之間的運輸成本，時間窗的懲罰費用是已知可計算的；④駕駛員的休息時間是提前假定好可估計的。

1.2 模型符號及建立

G{r|r=1,…,R}表示有R處位置可以作為運輸服務(wù)中心；H{i|i=R+1,…,R+N}表示多個客戶點；S{G}∪{H}表示運輸服務(wù)中心和客戶點的位置點集合；V{vk|k=1,…,K}表示運輸工具能通過的可以行走的路徑或是道路，其中運輸工具的數(shù)量為K個；Cij表示從點i到另一點j的單位距離運輸成本；Fr表示當在某一地點r處建立運輸服務(wù)中心所需要的建設(shè)成本或租用成本；qj表示某一客戶點對需要運輸貨物的需求量；Qk表示某一運輸工具k的容量；dij表示從客戶點i到客戶點j的運輸距離；yi表示在規(guī)劃的車輛路徑上車輛到達i點的次序；Ck表示使用第k輛車輛所對應(yīng)的固定成本；ai表示車輛到達客戶點i的最早時間又稱之為時間窗上限；si表示車輛實際到達客戶點i的時間；bi表示車輛到達客戶點i的最晚時間又稱之為時間窗下限；αi表示車輛到達客戶點i進行等待的時間懲罰成本；βi表示車輛到達客戶點i遲到的時間懲罰成本；tij表示車輛從點i到點j的行駛時間；fi表示車輛在i點進行服務(wù)的時間，包括車輛貨物的裝卸耗時等；LT表示駕駛員午休所需要的最短時間；L1k表示第k輛車的司機開始午休的時刻；L2k表示第k輛車的司機結(jié)束午休的時刻；LE表示駕駛員最早可以開始午休的時間窗上限；LL表示駕駛員最晚結(jié)束午休的時間窗下限；ST表示駕駛員可連續(xù)駕駛的最長安全時間；RT表示當駕駛員連續(xù)駕駛時長超過ST時需要中途休息的時間。

對于考慮駕駛員需求的LRP問題模型，其物流網(wǎng)絡(luò)的總成本主要包括自營車輛的固定成本和可變運輸成本、配送服務(wù)中心建設(shè)的固定成本、時間窗約束所帶來的延誤懲罰成本。因此，模型的目標函數(shù)和限制條件表示如下：

(1)

(2)

Subject to

(3)

(4)

(5)

(6)

(7)

(8)

(9)

si+fi+tij-M(1-Xijk)≤sj, ?i∈H,j∈H,k∈V,

(10)

(11)

Wijk=1?si+fi+tij+L2k-L1k≤sj, ?i∈S,j∈S,k∈V,

(12)

Wijk≤Xijk, ?i∈S,j∈S,k∈V,

(13)

LE≤L1k+LT≤L2k≤LL, ?k∈V,

(14)

(15)

yi-yj+(R+N)·Xijk≤R+N-1, ?R+1≤i≠j≤R+N,k∈V,

(16)

Xrjk=0,1, ?i,j∈S,k∈V,

(17)

Wijk=0,1, ?i,j∈S,k∈V,

(18)

Zr=0,1, ?r∈G,

(19)

Xk=0,1, ?k∈V,

(20)

其中:式(3)表示所有的客戶點都只有一部車進出，即一個客戶點只能由一部車來服務(wù)；式(4)表示進出某客戶點或運輸服務(wù)中心的車輛為同一輛車，保證線路的連續(xù)性；式(5)某一輛車最多從一個運輸服務(wù)中心出發(fā)；式(6)表示一條線路上所有客戶點需求量之和不能超過該車輛的容量限制；式(7)表示任意兩個運輸服務(wù)中心之間沒有其他線路的連接方式；式(8)、(9)表示每輛運輸車都從僅有的一個運輸服務(wù)中心出發(fā)；式(10)表示某一車輛k從i點到達j時對應(yīng)的到達時刻滿足車輛行駛、裝卸、午休(當存在時)的需要；式(11)表示要求每輛車都有且僅有一次午休時間；式(12)表示當客戶點i與客戶點j之間出現(xiàn)了駕駛員的午休時，后續(xù)的時間約束內(nèi)考慮午休時間的存在；式(13)表示了當客戶點i與客戶點j之間車輛路徑安排存在時，才考慮駕駛員的午休問題；式(14)表示駕駛員午休時段選取的時間窗限制；式(15)表示當駕駛員連續(xù)行駛時間超過連續(xù)駕駛的最長安全時間時強制駕駛員進行中途休息；式(16)避免子回路的產(chǎn)生；式(17)、(18)、(19)、(20)為0和1整數(shù)限制。

2 考慮駕駛員需求的LRP問題的改進交叉鄰域生成人工蜂群算法求解

2.1 人工蜂群算法

人工蜂群算法在求解過程中不斷的派出雇傭蜂(employed bees)、觀察蜂(onlookers)和偵察蜂(Scouts)三種類型的蜜蜂通過不同的行為方式尋找最佳的蜜源實現(xiàn)對于NP難題的求解。雇傭蜂會在蜜源的附近搜索新的蜜源，并將自己采蜜得來的信息通過舞蹈的方式傳遞給其他的觀察蜂和偵察蜂，觀察蜂會根據(jù)雇傭蜂給的信息達到相應(yīng)的蜜源并自主搜尋來采蜜，偵察蜂通過其他蜜蜂傳遞而來的信息來判斷是否需要去尋找新的蜜源。

本文針對考慮駕駛員需求的LRP問題，利用人工蜂群算法的基本原理，提出了一種對應(yīng)該LRP問題的蜜源編碼設(shè)計，拓展了人工蜂群算法應(yīng)用范圍。并針對使用傳統(tǒng)人工蜂群算法鄰域公式在該LRP問題求解上最優(yōu)解的搜尋效果不佳現(xiàn)象，提出了一種改進的交叉鄰域生成人工蜂群算法。

2.2 改進的交叉鄰域生成人工蜂群算法流程

針對考慮駕駛員需求的LRP問題的改進的交叉鄰域生成人工蜂群算法流程如下：

Begin

Step1：數(shù)據(jù)初始化，其中包括初始化蜂群數(shù)量NP、雇傭峰、觀察蜂數(shù)目均NP/2、偵查計數(shù)Bas、偵查蜂偵查閾值limit、最大循環(huán)數(shù)Maxcycle、D維解空間，并且在解空間隨機產(chǎn)生初始蜂蜜源Xi(i=1,2,…,NP)=(Xi1,Xi2,…,XiD)。

Repeat迭代次數(shù)Cycle=0

Step2：雇傭蜂鄰域?qū)ふ译A段，雇傭蜂根據(jù)交叉鄰域生成法在蜜源附近尋找新蜜源，并將好的蜜源替代原始的差蜜源，當某Xi的蜜源未被更新時，該i位置的Bas=Bas+1。

Step3：觀察蜂跟隨雇傭蜂階段，觀察蜂根據(jù)雇傭蜂反饋的信息按照一定概率選擇雇傭蜂進行跟隨。

Step4：觀察蜂進行蜜源鄰域?qū)ふ译A段，觀察峰根據(jù)雇傭峰引領(lǐng)到達相應(yīng)的蜜源進行蜜源的鄰域搜索，并根據(jù)貪婪法則擇優(yōu)替換差的蜜源，并同時記錄Bas值，當某Xi的蜜源未被更新時，該i位置的Bas=Bas+1。

Step5：記錄本次Cycle循環(huán)的最優(yōu)解。

Step6：根據(jù)Bas判斷是否進入偵查蜂階段。

If某i位置的蜜源Bas>limit than進入偵察蜂階段，偵察蜂出動隨機搜尋新的蜜源并替代該為位置的舊蜜源。

End if

Until迭代次數(shù)Cycle大于最大迭代次數(shù)Maxcycle，即Cycle>Maxcycle

Output輸出最優(yōu)解

End。

2.3 對應(yīng)蜜源編碼的設(shè)計

在該改進的人工蜂群算法中每一蜜源就相當于考慮駕駛員需求的LRP問題的一個解，這個解包含完整的車輛安排路徑以及相應(yīng)的成本等。其中可以根據(jù)LRP問題規(guī)模的大小來設(shè)置不同的蜂群數(shù)量NP、偵查計數(shù)Bas、偵查蜂偵查閾值limit、最大循環(huán)數(shù)Maxcycle、D維解空間。由于LRP問題為離散問題不同于簡單的函數(shù)求解，因此蜜源編碼不能采用傳統(tǒng)的實數(shù)編碼，假設(shè)在模型中客戶點的數(shù)量為N，最多使用的車輛數(shù)為K，運輸服務(wù)中心數(shù)為R的情況下蜜源的編寫方式采用D=N+N+K維，編寫為包含三段信息的蜜源，從而使每一個蜜源可以得出一個完整的車輛路徑的解。

第一段蜜源包含的N個維度表示每個客戶點使用的車輛，利用自然數(shù)編碼的方式客戶點從1到K依此對應(yīng)1，2，3，…，K基因位。第二段蜜源包含的N個維度對應(yīng)表示客戶點的被服務(wù)順序，利用1～0之間的實數(shù)編碼，隨后根據(jù)實數(shù)的大小排序從而得出服務(wù)順序。第三段的K個維度對應(yīng)表示客戶點使用的運輸服務(wù)中心的序號。

利用圖1某蜜源的構(gòu)成案例來詳細說明蜜源的編碼方式，假設(shè)有一物流網(wǎng)絡(luò)使用3輛車，K=3，有5個客戶點(N=5)，和3個設(shè)施點(R=3)(該范例中蜜源的第二段實數(shù)編碼僅保留了一位小數(shù))。

圖1 某蜜源的構(gòu)成范例Fig.1 Example of a food source composition

該蜜源的第一段蜜源包含5個維度的第1個維度表示客戶點1是被車輛2服務(wù)的，其他5個維度依次類推，可得出1號車服務(wù)客戶點：3、4；2號車服務(wù)客戶點：1、2；3號車服務(wù)客戶點：5。根據(jù)第二段蜜源上不同維度的實數(shù)從小到大排序可以得出，客戶點被服務(wù)的順序為：4-1-3-2-5。根據(jù)第三段蜜源上不同維度的自然數(shù)值可得車輛1從2號運輸服務(wù)中心出發(fā)，車輛2對應(yīng)運輸服務(wù)中心3，車輛3對應(yīng)運輸服務(wù)中心1。

最終可得出一系列完整的運輸路徑即：車輛1走行路徑(中心2-客戶4-客戶3-中心2)；車輛2走行路徑(中心3-客戶1-客戶2-中心3)；車輛3走行路徑(中心1-客戶5-中心1)。

2.4 相應(yīng)算子設(shè)計

對于蜜源的鄰域搜索方法傳統(tǒng)的方法是利用鄰域搜索公式:

vij=xij+rij(-1,1)(xij-xkj)，?(k,i)∈{1,2,…,NP},i≠k,j∈{1,2,…,D}。

(21)

通過隨機確定出i和k的值選擇出兩個不同的食物源xij與xkj，并根據(jù)隨機數(shù)實數(shù)rij(-1,1)∈[-1,1]，隨機的產(chǎn)生鄰域的蜜源，在一定程度上差值xij-xkj逐步保證了搜索空間的逐步縮小，隨機數(shù)保證蜜源的豐富程度保證算法的盡可能的進行全局搜索。但此鄰域公式在求解LRP問題時，由于LRP問題編碼的特殊性并且解的維度D普遍偏高，使用傳統(tǒng)的鄰域搜索公式最優(yōu)解的搜尋效果不佳，結(jié)合遺傳算法的思想，本文提出了利用隨機兩個維度間的蜜源交叉操作的形式進行鄰域搜索生成新的候選食物源的改進的交叉鄰域生成人工蜂群算法。

在鄰域生成前，隨機選擇兩個蜜源xi與xk且i≠k,(k,i)∈{1,2,…,NP}，根據(jù)食物源的維度D生成兩個隨機數(shù)d1和d2且d1≠d2,(d1,d2)∈{1,2,…,D}，隨后將d1和d2之間的食物源片段進行剪切互換，將xk上的d1和d2之間的食物源片段替換到蜜源xi上，生成新的蜜源vi。在人工蜂群算法中，隨后將比較原蜜源xi與新的蜜源vi的優(yōu)劣并根據(jù)貪婪法則保留最優(yōu)的蜜源。該交叉鄰域搜索法配合該LRP問題的特殊編碼方式可以做到隨機選取兩個位置點d1和d2就可以進行交換且不破化食物源編碼攜帶的車輛路徑信息，隨機選取位置點也保證了食物源的豐富性和多樣性，進一步擴大了算法的搜索范圍，保證求解的可行性和準確性。

偵察蜂階段，偵查蜂根據(jù)染色體的編碼方式對應(yīng)搜尋新的蜜源在1～N維度上vij=rij(1,K)?i∈{1,2,…,NP},j∈{1,2,…,N}，其中rij(1,K)表示生成[1,K]之間的隨機自然數(shù)，對應(yīng)食物源的編碼方式；在N+1～2N維度上vij=rij(0,1)?i∈{1,2,…,NP},j∈{N+1,N+2,…,2N}，此處rij(0,1)表示生成[0,1]之間的隨機實數(shù)；類似在食物源的2N～D維度上vij=rij(1,R)?i∈{1,2,…,NP},j∈{2N+1,2N+2,…,D}，式中rij(1,R)表示生成[1,R]之間的隨機自然數(shù)。

3 算例分析

本節(jié)利用算例來檢驗該考慮駕駛員需求的LRP問題模型和求解算法。由于該LRP問題涉及到較為復(fù)雜的時間窗和約束，在現(xiàn)有的研究文獻中均沒有合適的相關(guān)符合算例。本文算例的編寫參考其他計算實例并結(jié)合了某市某區(qū)的LRP運輸網(wǎng)絡(luò)，該網(wǎng)絡(luò)中共有客戶點14個(N=14)，待選運輸服務(wù)中心4個(R=4)，最多可使用車輛數(shù)8輛(K=8)。算例中的8輛車均為3 t的小型貨車，限載為Qk=3 000 kg，單位的運輸成本為Cij=1元/km，車輛在路網(wǎng)中平均行駛速度為v=40 km/h，車輛的固定成本折算到每日為Ck=50元/d；待選的運輸服務(wù)中心固定成本折算到每日為Fr=500元/d；車輛從點i到點j的行駛時間為tij=dij/v車輛從點i到點j的行駛時間：駕駛員午休所需要的最短時間為LT=1 h，且駕駛員午休時間的硬時間窗為(11∶30-13∶30)，LE為11∶30，LL為13∶30；駕駛員可連續(xù)駕駛的最長安全時間ST=4 h，當駕駛員連續(xù)駕駛時長超過ST時需要中途休息的時間RT=20 min(該組參數(shù)參考《道路交通安全法實施條例》第六十二條：連續(xù)駕駛機動車超過4 h應(yīng)停車休息，停車休息時間不少于20 min)。算例中的14個客戶點和4個運輸服務(wù)中心的坐標如表1所示，根據(jù)該表可計算得出從客戶點i到客戶點j的運輸距離dij；客戶點和運輸服務(wù)中心的需求量、時間窗限制，以及對應(yīng)的時間懲罰成本如表2所示。

表1 客戶點、配送服務(wù)中心的坐標Tab.1 Coordinates for each point

利用該算例進行模型的求解和算法的分析，實驗設(shè)備為常見PC計算機。算法的實驗參數(shù)設(shè)置為：GA算法設(shè)置初始種群數(shù)80個，最大迭代次數(shù)為1000次，遺傳算子中設(shè)置交叉率0.6，變異率0.05，運用MATLAB編碼并進行隨機的連續(xù)五次求解。人工蜂群算法設(shè)置雇傭峰、觀察蜂數(shù)目均為NP/2=30，偵查蜂偵查閾值limit=30，最大循環(huán)數(shù)Maxcycle=1000，同樣蜜源的維度根據(jù)該算例設(shè)置為D=N+N+K=36，同樣運用MATLAB編碼分別對傳統(tǒng)人工蜂群算法(ABC算法)和改進的交叉鄰域生成人工蜂群算法(ABCCNS算法)進行隨機的連續(xù)五次求解。將十五次的求解的耗時情況以及每次計算的成本結(jié)果匯總?cè)绫?所示，改進的ABCCNS算法求解迭代情況如圖2所示，表3中數(shù)據(jù)僅保留了兩位有效數(shù)字，其中成本的單位為元。

從求解的迭代情況可以看出該改進的人工蜂群算法(ABCCNS)的收斂較快，在迭代約100次后快速收斂，快速收斂后還有多次明顯的跳躍式進化過程，這是由于該算法在運行中利用偵查蜂進行了新蜜源的搜索保證的求解的盡可能全域搜索，該算法找出了十五次計算中的最優(yōu)解1 320.20。經(jīng)過對比分析遺傳算法(GA)、傳統(tǒng)人工蜂群算法(ABC)、改進的人工蜂群算法(ABCCNS)的求解結(jié)果可看出，在最優(yōu)解、解的平均值、解的方差和標準差上改進人工蜂群算法的性能最優(yōu)，其次遺傳算法在對于該問題的求解上優(yōu)于傳統(tǒng)ABC算法。此外在求解的平均耗時上，改進的人工蜂群算法(ABCCNS)耗時較其他兩種算法較長，但計算速度還是比較快的僅耗時199.92 s。

表2 客戶點的時間窗、懲罰系數(shù)以及需求量Tab.2 Time window, penalty factor, and cargo demand for customer sites

表3 三種算法的運輸總成本計算結(jié)果Tab.3 The results of the three intelligent algorithms on total transportation cost 元

圖2 改進的ABCCNS算法連續(xù)五次求解迭代情況
Fig.2 Five iteration examples of using Artificial Bee Colony Algorithm with Cross-neighborhood search

圖3 車輛走行路徑示意圖Fig.3 Vehicle route map

最優(yōu)解1320.20對應(yīng)的車輛走行路徑示意圖、車輛路徑情況、時刻表情況、最優(yōu)解的成本構(gòu)成情況，如圖3、表4、表5所示(表中數(shù)據(jù)僅保留了兩位有效數(shù)字)。該最優(yōu)解共選用了三輛車一個運輸服務(wù)中心進行配送，總成本中時間懲罰成本所占的比重較小僅為4.07元，占總成本的0.3 %左右。整體上來說該最優(yōu)解盡可能的服從客戶點時間窗的要求，有效避開懲罰系數(shù)較高幾個客戶點時間窗限制，且每條車輛的走行路徑中都給駕駛員預(yù)留了滿足駕駛員午休時間窗限制的中午休息時間，該線路的設(shè)計也較符合人性化，司機的出車時間和返航時間都較合適，每日的工作量也符合人體健康的需求。

表4 車輛路徑與相應(yīng)時刻表Tab.4 Vehicle route and corresponding timetable

表5 最優(yōu)解成本構(gòu)成Tab.5 Optimal solution’s cost structure

4 結(jié)論

本文結(jié)合實際運輸網(wǎng)絡(luò)和駕駛員排班中存在的駕駛員需求現(xiàn)象對定位運輸線路規(guī)劃問題展開了拓展研究，搭建了可行的考慮駕駛員需求的LRP問題模型，模型中重點考慮了客戶點的復(fù)雜時間窗以及駕駛員的休息時間與合理運輸路徑的結(jié)合。并根據(jù)算例驗證了該模型的可靠性以及對應(yīng)改進的交叉鄰域生成式的人工蜂群算法在該問題求解上的可行性。利用算例對比分析了三種算法的優(yōu)劣，結(jié)果表明該改進交叉鄰域生成人工蜂群算法的能有效解決鄰域公式最優(yōu)解搜尋效果不佳的現(xiàn)象，并且該算法最優(yōu)解的求解精度明顯提高。此外，本文也為人工蜂群算法的應(yīng)用范圍的拓展提供了有效嘗試。