基于GCOA算法的帶時間窗車輛路徑規劃問題研究

張杰飛 王曉麗

摘 要：GCOA算法是對遺傳算法的重大改良，不僅加快了遺傳算法的收斂速度，而且從一定程度上避免了遺傳算法陷入局部最優，并增大了遺傳算法獲得最優解的能力。本文首先介紹了GCOA算法，然后通過具體問題的解決對比傳統遺傳算法與GCOA算法，得出GCOA算法在收斂速度及結果優化兩方面的有效性，最后將GCOA算法應用于求解VRPTW問題上，得出最優化結論。

關鍵詞：GCOA;時間窗;車輛路徑規劃

Abstract： The GCOA algorithm is an important improvement of the genetic algorithm， which not only speeds up the convergence speed of the genetic algorithm， but also avoids the genetic algorithm falling into the local optimum to some extent， and increases the ability of the genetic algorithm to obtain the optimal solution. This paper first introduced the GCOA algorithm， and then， by comparing the traditional genetic algorithm and GCOA algorithm through the solution of specific problems， obtained the effectiveness of GCOA algorithm in convergence speed and result optimization; finally， GCOA algorithm was applied to solve VRPTW problem， and obtained the optimization conclusion.

Keywords： GCOA;time window;vehicle routing problem

1 GCOA算法

美國教授霍勒德（J.H.Holland）創建的遺傳算法是根據自然界的生物進化原理所構建出的基因搜索算法。該方法根據自然界生物進化過程中“優勝劣汰，適者生存”的規律，利用某種編碼技術作用于稱為染色體的數字串，進而進行進化尋優[1]。具體來說，對于所要解決的最優解問題，要先將其解空間編碼成可以用電腦進行計算的染色體，然后利用遺傳算法的選擇、交叉、變異等規則進行一代一代的求解，直到最終找到最優解。

遺傳算法主要集中在選擇、交叉、變異三大步驟上。通過構造不同的選擇方式、交叉邏輯、變異規則，就可以對傳統的遺傳算法進行一定程度的改良，從而用于解決最優解問題。GCOA算法主要對傳統遺傳算法的選擇方式及交叉規則進行了改良，其具體的算法操作過程如下。

1.1 編碼

編碼過程是對問題進行轉換的過程，將問題的解空間轉換為可以進行算法運行的基因序列。常見的編碼方式有二進制編碼和實數編碼兩種方式，具體選擇哪種編碼方式，要根據實際情況。在GCOA算法中，編碼方式并沒有改變。

1.2 選擇方式

遺傳算法的具體操作包括優選適應性強的個體的“選擇”、個體間交換基因產生新個體的“交叉”、個體基因突變而產生新個體的“變異”[2]。

選擇就是要從上一代群體中選擇一部分群體進行復制操作，而選擇留下的群體是否優良應該以適應度函數作為考察。從生物學角度來說，適應度是指生物群體中個體適應環境的能力。對應具體問題來說，就是此個體作為所求問題的一個解，其優秀程度的高低。因此，好的選擇方式應該以能留下更多的優秀解作為目標。傳統的遺傳算法使用輪盤賭注法來進行選擇，后來又有些學者使用精英策略來進行選擇。GCOA算法使用基于群體競爭的方式進行選擇。基于群體競爭的選擇方式主要有兩種：一種是將染色體兩兩對比，從而選擇強勢染色體;另一種是使所有基因序列同時參與競爭，從而選擇最優秀的一部分染色體。從表面來看，第二種辦法似乎更能將優勢染色體流傳到下一代，但其會在無形之中破壞全局尋優的能力。因此，本文使用第一種選擇方式進行操作。

1.3 交叉邏輯

依照一定的概率從群體中選擇個體組，對于每一組中的2個個體進行部分染色體的交換。通過交叉操作來使遺傳算法的搜索能力得以迅速提升[3]。

GCOA算法中，交叉是提取上一步選擇方式中得出的優良染色體的部分區段，隨機放至新產生的染色體中。這樣新產生的染色體就部分繼承了優良染色體的優秀基因，而新染色體的其余區段可以隨機產生，這樣就保證了算法的全局尋優能力。GCOA算法的選擇與交叉是有別于傳統遺傳算法的，這是獲得最優解的基礎。

1.4 變異規則

對于群體中的每個個體，以某一概率將某一個或數個染色體上的基因進行改變，從而得到不同的個體。這種改變雖然變化不大，但卻從一定程度上保障了檢索的全局性，避免陷入局部最優而無法跳出。由于編碼一般使用兩種方法，即二進制法或實數法，所以變異的方式也存在二進制變異和實數變異兩種模式。另外，變異的概率不能過大，否則會影響尋優的效率。因此，變異操作的過程是：先以一定的概率確定某個個體是否需要進行變異，如果需要，則隨機選擇個體需要變異的位置進行變異操作。

2 GCOA算法解決TSP問題

TSP問題（Travelling Salesman Problem）即旅行商問題，是數學中有名的尋求最優解問題[4]。假設有一個商人，要將自己的貨物在[n]個城市進行售賣。這個商人就要選擇一條能夠依次走過所有城市的路徑，每個城市都只能被走過一次，最后回到出發城市。而這條路徑選擇的最終目標就是要在所有可能的路徑中尋求最短的一條。所以，TSP問題就是尋找最短路徑的問題。

這類最短路徑問題實際上可以歸結為圖論問題，即“已給一個[n]個點的完全圖，每條邊都有一個長度，求總長度最短的經過每個頂點正好一次的封閉回路”。很多學者都發現，這個問題不管難度級別是否一致，但只要能夠找到一個有效的算法，所有此類問題就都可以使用這個算法進行求解。

但遺憾的是，到目前為止，還沒有對這類問題找到一個有效算法。大部分學者認為這類問題使用精確求解的方式不太現實，應將精力放在尋求近似最優解上。目前，在解決此類問題時普遍采用的遺傳算法、蟻群算法、模擬退火算法等智能化算法都在一定程度上將算法的運行時間與算法的結論優化性進行妥協，力求在有限的時間內找到一個近似最優的結論，從而解決實際問題。

在本文，研究者分別使用普通遺傳算法與GCOA算法對TSP問題進行求解，并從時間開銷、結論優化兩方面對這兩種算法進行對比。

2.1 問題描述

將前面旅行商的問題具體化，假設商人所要走過的城市是全國的31個省會，行走的方式與前面所提出的方案相同，即每個城市只能走過一次，且最后須回到出發城市。要求最終選擇的路徑是所有可行路徑之中的最短路徑。

假設31個省會城市的位置坐標是[1 304，2 312;3 639，1 315;4 177，2 244;3 712，1 399;3 488，1 535;3 326，1 556;3 238，1 229;4 196，1 044;4 312，790;4 386，570;3 007，1 970;2 562，1 756;2 788，1 491;2 381，1 676;1 332，695;3 715，1 678;3 918，2 179;4 061，2 370;3 780，2 212;3 676，2 578;4 029，2 838;4 263，2 931;3 429，1 908;3 507，2 376;3 394，2 643;3 439，3 201;2 935，3 240;3 140，3 550;2 545，2 357;2 778，2 826;2 370，2 975]

2.2 兩種算法的解決結果

在使用遺傳算法求解時，編碼方式采用實數編碼，即產生一組1到31隨機排列的組合為一個染色體。在MATLAB中使用randperm（31）即可產生一組染色體。計算這組染色體中依次所經過的距離作為適應度，且適應度函數值越小越優秀。采用輪盤賭注法進行染色體選擇，交叉時將兩個染色體中連續的4個基因組進行交叉，變異時采用0.1的概率改變染色體的一個基因。仿真結果如圖1和圖2所示。

使用GCOA算法進行求解時，編碼方式同普通遺傳算法一樣。在進行選擇處理時，對所有染色體求解適應度，并且兩兩對比留取數據更小的作為下一代染色體。在進行交叉操作時，從遺傳的優良子代中隨機選取連續的4位作為交叉基因組。將這組基因序列復制給新的子代，新子代中的其他位置隨機產生基因，但要避免產生重復數據。變異時采用0.1的概率改變染色體的一個基因。仿真結果如圖3和圖4所示。

通過對比仿真結果可以看出，GCOA算法無論從計算速度還是從結果的優化性上，都遠遠超過了傳統的遺傳算法。因此，GCOA算法對遺傳算法的改良是具有革命性的。

3 GCOA算法求解帶時間窗的車輛路徑規劃問題

車輛路徑問題（Vehicle Routing Problem，VRP）的一般定義是，組織合適的行車方案，讓眾多貨車將貨物從裝貨點運送至各個卸貨點。在滿足車輛容量、卸貨點貨物需求量、卸貨時間要求、行駛里程約束等的條件下，達到一定條件（如總里程最短、總費用最少、總耗時量最小、使用的車輛數最少）的最優化。VRP對應了很多實際問題，包括貨物配送、郵件投遞、鐵路航空調度等。

時間窗是指一個時間段[ETi，LTi]，是由客戶卸貨點要求的最早到達時間[ETi]和最晚到達時間[LTi]確定的一個服務時間區間。其是在傳統VRP問題的基礎上給每個卸貨點客戶加上服務所允許的時間窗（Time Windows）約束，就擴展成了VRPTW。本文采用更接近現實的軟時間窗約束進行考慮。軟時間窗約束是指如果在[ETi]之前到達則需要進行等待并懲罰，如果在[LTi]之后到達也需要進行懲罰。具體的懲罰函數如下：

接下來解決一個具體的VRPTW問題：現有一配送中心需要向8個客戶點運送貨物，第[i]個客戶點的貨物需求量是[qi]，并且每個客戶對于到貨時間也有一定的需求，分別是[ETi，LTi]，其具體的數值如表1所示。為了使問題相對簡單，假設配送中心只具有一種容量的貨車，其容量是8 t。現要求合理安排從配送中心出發，經由各客戶點后最終返回配送中心的車輛行駛路線，最終使得總運行費用最少。

在這里，假設車輛的行駛時間和距離成正比，每輛車的平均行駛速度為50 km/h。車場各任務點的距離如表2所示。

在進行問題求解時，使用GCOA算法。依然使用實數編碼，選擇、交叉、變異的規則依據GCOA的處理辦法。需要說明的是，在產生各染色體子代的同時，需要另開辟一個數組用以存儲間隔位置。例如：2 3 5|4 6|1 7 8表示的是有三條子路徑，分別是：配送中心—客戶2—客戶3—客戶5—配送中心;配送中心—子客戶4—子客戶6—配送中心;配送中心—子客戶1—子客戶7—子客戶8—配送中心。每條子路徑中間的“|”表示路徑的隔斷，另產生的數組以[3，5]的形式存儲隔斷的位置。這種方法比傳統的在隔斷處用0表示更容易進行程序處理。適應度函數由符合條件的路徑值+懲罰值構成，且數據越小，適應度越好。使用算法求解后得出結論：3 5 2|6 4|8 1 7。各路徑的距離分別是：240、265、405 km。取得了最優的結果。

4 結語

本文首先介紹了GCOA算法，說明了此算法是對傳統遺傳算法的突破性改良;然后，將傳統遺傳算法及GCOA算法分別應用于TSP問題的求解，得出GCOA算法在收斂速度及結果優化兩方面的有效性;最后將GCOA算法應用于求解VRPTW問題上，得出了最優化結論。

參考文獻：

[1]王曉麗，賈東明.GCOA算法：一種新的智能優化算法[J].價值工程，2017（8）：170-171.

[2]謝秉磊，李軍，郭耀煌.有時間窗的非滿載車輛調度問題的遺傳算法[J].系統工程學報，2000（3）：290-294.

[3]NAZIF H，LEE L S.Optimized crossover genetic algorithm for vehicle routing problem with time windows[J]. American Journal of Applied Sciences，2010（1）：95-101.

[4]Ben-Tal A，Nemirovski A. Robust solutions of linear programming problems contaminated with uncertain data[J].Mathematical Programming，2000（3）：411-424.