求解煙草配送路徑規(guī)劃問題的新型智能優(yōu)化算法

高怡杰，何湘竹*，石英，王建樹

（1 中南民族大學 電子信息工程學院，武漢 430074；2 湖北省煙草公司 物流處，武漢 430074）

近年，煙草行業(yè)在我國財政收入中占比不斷加大，然而，作為其核心業(yè)務(wù)的煙草物流，目前仍主要采用傳統(tǒng)的配送方式，導致出現(xiàn)：從業(yè)人員數(shù)量大，配送車輛以及送貨線路多，單車日送貨客戶數(shù)明顯不足的問題.究其原因之一，為缺乏對配送車輛及配送線路的改良及優(yōu)化［1］.針對此，本文研究新型智能優(yōu)化算法，對煙草配送方式及路徑進行優(yōu)化，以提高配送效率，節(jié)約配送成本.

近年來，隨著人工智能技術(shù)的發(fā)展，研究者從仿真機制中得到了求解該問題的啟示，提出了一系列智能優(yōu)化算法.高等［2］梳理了許多針對TSP問題的算法方案，如遺傳算法（GA），模擬退火算法（SA），蟻群算法（ACO），禁忌搜索算法（TS）等，并求解于TSP問題.周等［3］中提出了離散型螢火蟲群優(yōu)化算法（DGSO）算法，該算法一方面結(jié)合TSP問題本身的特點，提出了一種新的有效編碼方法，并給出其相應(yīng)的解碼方法，同時定義個體間距離計算公式和編碼更新公式，另一方面算法使用了2-opt優(yōu)化算子，該算法在種群規(guī)模較小，迭代次數(shù)較少的情況下可以收斂得到最優(yōu)解，但仍有提升空間.馬等［4］提出了一種求解旅行商問題的文化混合優(yōu)化算法，該算法將遺傳算法和模擬退火算法相結(jié)合并納入文化算法體系，并將算法求解空間分為種群空間和信度空間，通過兩個空間的相互配合引導種群進化，該算法優(yōu)化效果雖然有一定提升，但非常有限.

TLBO（Teaching-Learning-Based Optimization）算法是RAO受課堂知識傳授現(xiàn)象啟發(fā)于2010年提出的一種新智能算法［5］，控制參數(shù)少且全局尋優(yōu)能力強大，已成功求解許多連續(xù)優(yōu)化問題［6-9］.然而，TLBO算法在組合優(yōu)化領(lǐng)域的應(yīng)用研究卻相對較少，XIE［10］和SHEN［11］等人嘗試將TLBO算法本身進行改進或者與其它算法混合，并用于求解車間調(diào)度問題，均取得很好的效果.WU［12］等將TLBO離散化，提出離散教與學優(yōu)化算法并用來解決旅行商問題，但其實驗驗證部分的結(jié)果表明，TLBO算法還有很大的改進空間.

本文針對煙草配送路徑規(guī)劃問題，基于傳統(tǒng)TLBO算法的基本框架，提出了一種新型智能優(yōu)化（Improved Teaching-Learning-Based Optimization，ITLBO）算法并用于求解該問題.首先，重新定義了學生的表示方式，具體到TSP問題，班級中的每個學生都對應(yīng)一個由訪問城市編碼組成的序列.其次，考慮到組合優(yōu)化問題的特點，重新設(shè)計新的學習方式，引入線性順序交叉［13］（Linear order crossover，LOX）算子模擬教師授課和學生互動的學習過程.另外，為了有效平衡算法搜索過程中的集中性和多樣性，新開發(fā)了教師培訓、學生自學以及教師反向?qū)W習階段，并引入多種算子，結(jié)合自適應(yīng)退火機制和禁忌策略，實現(xiàn)算法的學習進化過程.基于TSPLIB標準測試用例的仿真實驗，及某市煙草公司煙草配送單車輛及多車輛的路徑規(guī)劃求解，均驗證了所提出的ITLBO算法的有效性.

1 煙草配送路徑規(guī)劃問題建模

煙草配送路徑規(guī)劃可建模為車輛路徑問題，其中單車輛路徑規(guī)劃問題可描述為：在已知N個客戶及各個客戶間距離的前提下，一配送車輛從倉庫出發(fā)，訪問完N個客戶之后再回到出發(fā)倉庫，如何尋找到一條最短訪問路徑，保證每一個客戶都被訪問到且只被訪問一次，其數(shù)學模型如下：

其中，i，j∈{1，2，...N}=V，cij代表車輛從第i個客戶訪問第j個客戶，cij∈{0，1}，取值為1表明i到j(luò)的邊屬于訪問路徑，0則代表不屬于，dij代表i和j兩個客戶之間的距離，D為訪問路線的總距離.式（1）為目標函數(shù)，表明路徑規(guī)劃問題優(yōu)化的目標為總路徑長度最短，式（2）為約束條件，意味著每個客戶只能被訪問一次.本文中，客戶i的位置用二維平面的坐標對(xi，yi)表示，兩個相鄰客戶之間的距離dij采用歐式距離公式計算.

2 傳統(tǒng)TLBO算法

TLBO算法是RAO于2010年提出的一種自然啟發(fā)式算法，該算法模擬課堂教學過程，通過教師教授知識和同學互助學習來提高整個班級的成績.TLBO算法的主要過程如下［5］.

第一步初始化班級.首先，隨機生成N個學生，每個學生代表問題的一個解.所有學生通過成績好壞來評價.成績最好的學生被選為教師，其余均作為該教師的學生，教師和學生一起構(gòu)成一個班級.

第二步教學階段.此階段模擬教師授課過程，班級形成后，教師向?qū)W生傳授知識，通過采用讓班級中的每一個學生都向教師學習的方式，使整個班級成績得以提高.這一過程中的每一次迭代均可通過式（3）和式（4）實現(xiàn)，其中，r是一個［0，1］之間的隨機數(shù)，c是教學因子，用來反映教師的教學水平.Ms代表整個班級學生的平均值，T代表教師，通過式（3）求出班級平均水平和教師之間的差距Diff，之后再根據(jù)式（4）將每位同學的原值加上差距Diff獲得新值.

最后一步學習階段.此階段模擬學生相互學習的過程.隨機選取班級中的一個學生，該生通過與班級中另一位學生交流，來提升自身水平.這一階段的學習過程可通過式（5）實現(xiàn)，Si和Sj代表隨機挑選的兩個學生，比較他們的成績，選出成績較好的學生，成績較差的學生通過向其學習提高原有成績.

TLBO算法運行時，先進行第一個階段的初始化，再通過多次重復第二個階段和第三個階段完成教與學過程迭代，使得整個班級的成績進化，最終尋找到全局范圍內(nèi)的最優(yōu)解.

3 ITLBO算法

本文針對路徑規(guī)劃問題，在對傳統(tǒng)TLBO改進和重構(gòu)的基礎(chǔ)上提出ITLBO算法，具體措施如下.

第一，傳統(tǒng)TLBO中，學生是一個由連續(xù)值組成的向量，這種表達不適用與組合優(yōu)化問題.針對此現(xiàn)狀，在ITLBO算法中，重新定義學生的表示方式，在對將各個城市統(tǒng)一編碼后，將學生表示為由訪問城市對應(yīng)編碼組成的正整數(shù)序列.

第二，傳統(tǒng)TLBO中，無論是教學階段還是學習階段，其學習方式均是通過給學生原有的成績加上他與教師（或同學）之間的差值來實現(xiàn)，這種學習方式無法直接應(yīng)用于組合優(yōu)化問題.針對此現(xiàn)狀，ITLBO算法中重新設(shè)計學習方式，保留了傳統(tǒng)TLBO中教與學的基本原理，但將學習過程更新為解結(jié)構(gòu)更相似的進化過程，并通過引入LOX算子實現(xiàn)學生向教師學習及學生之間的相互學習.

第三，傳統(tǒng)TLBO中，只包含教學階段和學習階段兩個進化步驟，學習方式過于單一，影響了算法的全局尋優(yōu)能力.針對此缺陷，ITLBO算法將TLBO中原有的兩個階段的教學過程擴展優(yōu)化為教師培訓、教師教學、學生互學、學生自學、教師反向?qū)W習五個階段.首先在教學階段之前增加教師培訓階段，該過程的作用為，對選出的教師進行崗前培訓并擇優(yōu)上崗，引入激勵競爭機制以提高教師的教學水平，也保證在后續(xù)的教學環(huán)節(jié)中，學生能從老師那里獲得更為豐富的知識，從而增強算法的尋優(yōu)能力.其次在學習階段之后增加學生自學階段，除了教師傳授及同學間互助，學生還可以通過自身的努力來快速提高成績，這一階段利用2-opt算子［14］，實現(xiàn)學生的自我優(yōu)化操作，從而加快算法的收斂速度.最后，在自學階段之后增加教師反向?qū)W習階段.通過引入禁忌策略，限制教師在禁忌時間內(nèi)再次當選，且允許教師在禁忌期間向最差的學生反向?qū)W習以獲取新知識，從而有效增加算法的多樣性，平衡其全局勘探和局部搜索的能力.

第四，傳統(tǒng)TLBO中，采用了單一的精英策略，使得搜索方向過于集中，算法缺乏多樣性且容易“早熟”.針對此缺陷，ITLBO算法中，設(shè)計自適應(yīng)模擬退火機制并將其引入各個學習階段，每次迭代前計算班級的最好與最差成績，以此為依據(jù)求出退火溫度t，采用Metropolis準則［15］以一定概率接收尋優(yōu)過程中的差解，避免算法過早收斂而陷入局部最優(yōu).

3.1 初始化階段

在初始化階段，算法隨機生成N個學生Si，并將其禁忌時間Time(Si)置為0.之后，依據(jù)公式（6）計算每位Si的成績.

其中，gi表示第i個學生的成績，Pi表示第i個學生對應(yīng)的訪問城市序列，dis(Pi)表示此訪問順序下求出的路徑總長度.

3.2 培訓階段

在培訓階段，教師通過對自身解結(jié)構(gòu)進行變換來實現(xiàn)自我優(yōu)化.首先，根據(jù)成績選出排名靠前的Nt個學生做為備用教師，之后采用迭代變換法［16］對其培訓，最終選出成績最好的教師參加后續(xù)教學活動，具體步驟如下.

Step1：按照成績好壞對個體從大到小排序，計算最大路徑長度dismax與最短路徑長度dismin，設(shè)置退火溫度t=dismax-dismin.并選擇排名前Nt且禁忌時間為0的Nt個學生作為培訓備選教師.

Step2：從Nt個備選教師中選擇一個教師Ti參加培訓，并設(shè)置計數(shù)器count記錄未參加培訓的老師個數(shù)，count初值為Nt.

Step3：從Ti中隨機選出兩個交換城市ci和cj，其中，1

Step4：交換ci和cj處城市產(chǎn)生一個備選解T1i.

Step5：分別將ci和cj處的城市與其前后的城市交換，產(chǎn)生四個鄰域解T2i，T3i，T4i，T5i.

Step6：計算Step3和Step4中產(chǎn)生的5個解的成績，比較后得到成績最好的新解Ti′.

Step7：比較新解Ti′和原解Ti的成績，若Ti′成績優(yōu)于Ti，用Ti′替換Ti，否則Ti保持不變.

Step8：count=count-1，若count≠0，重復執(zhí)行Step2-Step8，否則轉(zhuǎn)入Step9.

Step9：對培訓結(jié)束的Nt個教師按成績排序，選出成績最好的教師Tbest作為下一個階段的授課教師，并將其禁忌時間Time(Tbest)設(shè)置為一個常數(shù)T，以限制其在禁忌期再次當選.

上述步驟中，Step3至Step5的具體示例如圖1所示.

圖1 培訓階段迭代變換示意圖Fig.1 Iterative transformation in the training phase

3.3 教學階段

在教學階段，每位學生通過模仿教師Tbest的結(jié)構(gòu)來實現(xiàn)優(yōu)化.本算法采用LOX算子實現(xiàn)教學過程，具體步驟如下.

Step1：從Ns個學生中選一個學生Si參加教學階段的學習，并設(shè)置計數(shù)器count記錄未參加教學過程的學生個數(shù)，其中，Ns=N-1，count初值為Ns.

Step2：在Si中隨機選擇一段保留序列；

Step3：從Tbest中刪除Si保留序列內(nèi)的城市坐標；

Step4：將Si保留序列按原位復制到Si′，再將Tbest剩余城市按先后順序依次插入到Si′的空缺位置.

Step5：計算教學前后該學生的路徑長度之差ΔC=dis(Si)-dis(Si′).

Step6：若ΔC>0，Snewi=Si′.否則，產(chǎn)生隨機數(shù)r∈[0，1]，當滿足r≤min{1，exp(-ΔC/t)}時，Snewi=Si′，不滿足時，Snewi=Si.

Step7：count=count-1，若count≠0重復執(zhí)行Step1-Step6，否則結(jié)束教學階段.

上述步驟中，Step2至Step4的具體示例如圖2.

圖2 教學階段LOX算子示意圖Fig.2 LOX operator in the teaching phase

教學階段中，Step5和Step6為自適應(yīng)退火機制，其目的在于增加解的多樣性，避免算法過早陷入局部最優(yōu).

3.4 學習階段

在學習階段，較差的學生通過模仿較好學生的結(jié)構(gòu)以提高成績.與教學階段類似，采用LOX算子，將每個學生與隨機選擇的其它學生進行交叉，具體過程如下.

Step1：從Ns個學生中選出一名參加學習的學生Si，設(shè)置計數(shù)器count記錄未參加學習的學生個數(shù)，count初值為Ns.

Step2：從其它學生中隨機選擇另一名學生Sj.

Step3：將Si與Sj以類似于圖2的方式進行LOX交叉，得到Si′.

Step4：執(zhí)行與教學階段類似的自適應(yīng)退火步驟，得到學習后的新解Snewi.

Step5：count=count-1，若count≠0重復執(zhí)行Step1-Step4，否則結(jié)束學習階段.

3.5 自學階段

在自學階段，學生主動改善自身成績以實現(xiàn)快速自我優(yōu)化.本文采用2-opt算子對學生的結(jié)構(gòu)進行調(diào)整，具體步驟如下.

Step1：從Ns個學生中選擇成績排名前50%的學生參加自學.

Step2：對每一個參加自學的學生個體Si，隨機選擇兩個交換城市ci和cj，反轉(zhuǎn)ci和cj及其之間的城市得到Si′.

Step3：執(zhí)行自適應(yīng)退火步驟，得到新解Snewi.

Step4：重復執(zhí)行Step1-Step3，直到Step1中的所有學生都完成自學.

上述步驟中，Step2具體示例如圖3所示.

圖3 自學階段2-opt算子示意圖Fig.3 2-opt operator in the self-learning phase

3.6 反向?qū)W習階段

在反向?qū)W習階段，所有禁忌時間不為0的教師，均通過LOX算子向班級中成績最差的學生反向?qū)W生，具體步驟如下.

Step1：對Time(Ti)≠0將其與班級成績最差的學生LOX交叉得到Ti′，并比較Ti′和Ti的成績.若Ti′成績大于Ti的成績，則T newi=Ti′，否則T newi=Ti.

Step2：Time(Ti)=Time(Ti)-1

3.7 ITLBO算法流程

ITLBO算法流程圖如圖4所示.

圖4 ITLBO算法流程圖Fig.4 Flow-chart of ITLBO

4 基于ITLBO算法的煙草物流路徑規(guī)劃

從兩個方面對所提出ITLBO算法的性能進行驗證和分析.針對9個TSPLIB標準用例，將ITLBO與未改進前的基本DTLBO算法及ACO算法的計算結(jié)果進行比較分析；將算法用于某市煙草物流配送路徑優(yōu)化，為其提供有效的決策指導.本文實驗環(huán)境為MATLAB2018b，操作系統(tǒng)為Windows10，處理器為主頻2.50 GHz，內(nèi)存4GB內(nèi)存的Intel（R）Core（TM）i5-7200U.

4.1 ITLBO算法與DTLBO及ACO算法比較

本節(jié)將所提出的ITLBO算法與ACO［17］、DTLBO算法［12］進行比較，以證明改進的必要性和有效性.參數(shù)設(shè)置與DTLBO保持一致，即：N=100，G=500，對于每一個實例算法均獨立運行20次，比較結(jié)果見表1.

表1 ITLBO與DTLBO及ACO比較Tab.1 ITLBO compared with DTLBO and ACO

表1中，Best代表最好解，Mean代表算法獨立運行20的平均解，σ代表偏差率，t代表平均運行時間.偏差率計算公式為算法所得解與最優(yōu)解的差值除以最優(yōu)解.DTLBO和ACO文獻中只給出了最優(yōu)解，ITLBO算法對于每一個實例均統(tǒng)計了最優(yōu)解、平均解和平均運行時間.分析表1可知，針對表中9個測試樣例，ITLBO的最優(yōu)解均優(yōu)于DTLBO算法，其中，DTLBO僅在Att48和Chn31測試樣例中取得了較好的結(jié)果，但對于其它用例，尤其是Rand75，Eil51和Eil76，算法偏差率均在1%以上，意味著沒有獲得最優(yōu)解.相反，ITLBO算法除了Eil76偏差率在1%以上，除Rand75接近最優(yōu)解外，其他測試用例都取得了全局最優(yōu)解.ACO除了在Oliver30和Berkin52測試樣例中較優(yōu)外，其他用例均差于ITL?BO.同時，觀察ITLBO算法的平均解可以發(fā)現(xiàn)，針對Oliver30和Eil76算例，ITLBO獲得的平均解甚至比DTLBO的最優(yōu)解都好，對Chn31和Eil51其平均解也接近DTLBO的最優(yōu)解，這說明ITLBO算法穩(wěn)定性較DTLBO更強.

4.2 單一車輛煙草配送路徑規(guī)劃

為了探索算法在實際問題中的應(yīng)用，以某市煙草公司旺季期間煙草配送為實例，首先，選取一個倉庫及其輻射到的104個客戶的數(shù)據(jù)；其次，將倉庫即客戶位置的經(jīng)緯度數(shù)據(jù)轉(zhuǎn)換為距離；然后，采用ITLBO算法求取最優(yōu)送貨路徑，并和煙草公司現(xiàn)采用的未優(yōu)化前的配送路徑進行比對；最后，通過百度地圖API將配送路徑可視化，優(yōu)化前后的配送路徑對比如圖5所示.結(jié)果分析可知，未優(yōu)化前該車輛配送完所有顧客的行駛距離為140.46 km，經(jīng)過ITL?BO算法優(yōu)化后，配送路徑為99.81 km，較之前減少了40.65 km，節(jié)省了28.94%的距離成本.使用經(jīng)緯度數(shù)據(jù)雖不能準確的反映現(xiàn)實中的路徑規(guī)劃，但對經(jīng)緯坐標相對距離的規(guī)劃仍對現(xiàn)實中的路徑規(guī)劃具有指導意義.

圖5 優(yōu)化前后配送路徑對比圖Fig.5 Comparison of distribution routes before and after optimization

4.3 多車輛煙草配送路徑規(guī)劃

實際煙草公司配送系統(tǒng)中，往往不止一輛車，所以多輛車的路徑規(guī)劃顯得尤為重要且更為實際，本環(huán)節(jié)基于新型智能優(yōu)化算法對前述煙草公司的多車輛煙草配送路徑求解，結(jié)果如圖6所示.本環(huán)節(jié)求解多車輛路徑規(guī)劃的框架是基于TSP問題，并輔以聚類算法實現(xiàn)，其中車輛路徑規(guī)劃節(jié)點由聚類算法對送貨客戶聚類后獲得，之后利用ITLBO算法對配送車輛路徑進行優(yōu)化，未優(yōu)化前路線較為雜亂，優(yōu)化后路徑更為清晰.計算優(yōu)化前后路徑可得，優(yōu)化前該公司4輛車總行駛236.47 km，優(yōu)化后為175.48 km，較之前減少了60.99 km，節(jié)省了25.79%的距離成本.

圖6 多車輛配送路徑優(yōu)化前后對比圖Fig.6 Comparison of multiple vehicle distribution routes before and after optimization

5 結(jié)語

TLBO算法是一種新型自然啟發(fā)式算法，由于其控制參數(shù)少且實現(xiàn)簡單，已被廣泛應(yīng)用于求解各類連續(xù)優(yōu)化問題.為了使該算法更好的應(yīng)用于煙草路徑規(guī)劃問題求解，本文基于傳統(tǒng)TLBO算法的框架，提出了一種新型的智能優(yōu)化算法ITLBO.重新定義了一種有效的學生表達方法；教學和學習階段采用LOX算子離散化學習過程，以提高算法的集中性；加入教師培訓階段，引入迭代變換法提高解的質(zhì)量；增加學生自學過程，加快算法的收斂速度；采用教師反向?qū)W習方式，改善種群的多樣性；在教學、學習及自學階段引入自適應(yīng)模擬退火機制，有效平衡算法的局部搜索和全局勘探能力.

針對某市煙草公司的單車輛和多車輛煙草配送路徑問題，所設(shè)計的ITLBO算法求出的優(yōu)化路徑大幅縮短了配送距離，降低了配送成本.未來將結(jié)合更多算例對ITLBO進行改進，并開展參數(shù)設(shè)置對算法性能影響的研究工作，同時，將ITLBO算法應(yīng)用于求解更多的車輛路徑問題，如：帶時間窗的送貨路徑規(guī)劃等.