基于GCOA算法的帶時(shí)間窗車輛路徑規(guī)劃問題研究

張杰飛 王曉麗

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

關(guān)鍵詞：GCOA;時(shí)間窗;車輛路徑規(guī)劃

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）創(chuàng)建的遺傳算法是根據(jù)自然界的生物進(jìn)化原理所構(gòu)建出的基因搜索算法。該方法根據(jù)自然界生物進(jìn)化過程中“優(yōu)勝劣汰，適者生存”的規(guī)律，利用某種編碼技術(shù)作用于稱為染色體的數(shù)字串，進(jìn)而進(jìn)行進(jìn)化尋優(yōu)[1]。具體來說，對(duì)于所要解決的最優(yōu)解問題，要先將其解空間編碼成可以用電腦進(jìn)行計(jì)算的染色體，然后利用遺傳算法的選擇、交叉、變異等規(guī)則進(jìn)行一代一代的求解，直到最終找到最優(yōu)解。

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

1.1 編碼

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

1.2 選擇方式

遺傳算法的具體操作包括優(yōu)選適應(yīng)性強(qiáng)的個(gè)體的“選擇”、個(gè)體間交換基因產(chǎn)生新個(gè)體的“交叉”、個(gè)體基因突變而產(chǎn)生新個(gè)體的“變異”[2]。

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

1.3 交叉邏輯

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

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

1.4 變異規(guī)則

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

2 GCOA算法解決TSP問題

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

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

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

在本文，研究者分別使用普通遺傳算法與GCOA算法對(duì)TSP問題進(jìn)行求解，并從時(shí)間開銷、結(jié)論優(yōu)化兩方面對(duì)這兩種算法進(jìn)行對(duì)比。

2.1 問題描述

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

假設(shè)31個(gè)省會(huì)城市的位置坐標(biāo)是[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 兩種算法的解決結(jié)果

在使用遺傳算法求解時(shí)，編碼方式采用實(shí)數(shù)編碼，即產(chǎn)生一組1到31隨機(jī)排列的組合為一個(gè)染色體。在MATLAB中使用randperm（31）即可產(chǎn)生一組染色體。計(jì)算這組染色體中依次所經(jīng)過的距離作為適應(yīng)度，且適應(yīng)度函數(shù)值越小越優(yōu)秀。采用輪盤賭注法進(jìn)行染色體選擇，交叉時(shí)將兩個(gè)染色體中連續(xù)的4個(gè)基因組進(jìn)行交叉，變異時(shí)采用0.1的概率改變?nèi)旧w的一個(gè)基因。仿真結(jié)果如圖1和圖2所示。

使用GCOA算法進(jìn)行求解時(shí)，編碼方式同普通遺傳算法一樣。在進(jìn)行選擇處理時(shí)，對(duì)所有染色體求解適應(yīng)度，并且兩兩對(duì)比留取數(shù)據(jù)更小的作為下一代染色體。在進(jìn)行交叉操作時(shí)，從遺傳的優(yōu)良子代中隨機(jī)選取連續(xù)的4位作為交叉基因組。將這組基因序列復(fù)制給新的子代，新子代中的其他位置隨機(jī)產(chǎn)生基因，但要避免產(chǎn)生重復(fù)數(shù)據(jù)。變異時(shí)采用0.1的概率改變?nèi)旧w的一個(gè)基因。仿真結(jié)果如圖3和圖4所示。

通過對(duì)比仿真結(jié)果可以看出，GCOA算法無論從計(jì)算速度還是從結(jié)果的優(yōu)化性上，都遠(yuǎn)遠(yuǎn)超過了傳統(tǒng)的遺傳算法。因此，GCOA算法對(duì)遺傳算法的改良是具有革命性的。

3 GCOA算法求解帶時(shí)間窗的車輛路徑規(guī)劃問題

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

時(shí)間窗是指一個(gè)時(shí)間段[ETi，LTi]，是由客戶卸貨點(diǎn)要求的最早到達(dá)時(shí)間[ETi]和最晚到達(dá)時(shí)間[LTi]確定的一個(gè)服務(wù)時(shí)間區(qū)間。其是在傳統(tǒng)VRP問題的基礎(chǔ)上給每個(gè)卸貨點(diǎn)客戶加上服務(wù)所允許的時(shí)間窗（Time Windows）約束，就擴(kuò)展成了VRPTW。本文采用更接近現(xiàn)實(shí)的軟時(shí)間窗約束進(jìn)行考慮。軟時(shí)間窗約束是指如果在[ETi]之前到達(dá)則需要進(jìn)行等待并懲罰，如果在[LTi]之后到達(dá)也需要進(jìn)行懲罰。具體的懲罰函數(shù)如下：

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

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

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

4 結(jié)語

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

參考文獻(xiàn)：

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

[2]謝秉磊，李軍，郭耀煌.有時(shí)間窗的非滿載車輛調(diào)度問題的遺傳算法[J].系統(tǒng)工程學(xué)報(bào)，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.