基于NSGA-II的渣土車調(diào)度系統(tǒng)的研究與設(shè)計

母洪鋮，茍 剛，姚文欽，黃伶俐

(1.貴州大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，貴陽 550025; 2.花溪區(qū)人民檢察院,貴陽 550025)

0 引言

在實際生產(chǎn)中，一個渣土運輸子任務(wù)的渣土車調(diào)度方案是渣土車數(shù)量與運輸路徑笛卡爾積關(guān)系，運輸任務(wù)增加，調(diào)度方案呈指數(shù)級增長，在城市交通的限制下，渣土車由工地到消納場的路徑相對固定，對運輸成本影響較大的是不同渣土車到不同工地的空車調(diào)度距離。渣土車的位置隨時發(fā)生著變化，調(diào)度方案的規(guī)模龐大導(dǎo)致成本計算困難。元啟發(fā)式算法[1-3]在解決全局尋優(yōu)問題時，能基于問題的數(shù)學(xué)模型檢索出近似最優(yōu)解。經(jīng)典的尋優(yōu)算法有遺傳算法[4]、模擬退火算法[5-6]、蟻群算法[7]等。在渣土行業(yè)，工地的位置并不固定，有新的托運需求，則產(chǎn)生新的工地，調(diào)度的初始狀態(tài)就產(chǎn)生了改變。遺傳算法對初始種群具有依賴性[8]的特點符合渣土運輸?shù)倪@一特性。

遺傳算法模仿生物進(jìn)化和遺傳的特性，全局性地搜索解空間。其關(guān)鍵在于個體的編碼(可行解的表示方法)；遺傳過程中個體的選擇、交叉、變異；以及對個體進(jìn)行評價的適應(yīng)度函數(shù)，最終適應(yīng)度高的個體集合則是問題的較優(yōu)解。遺傳算法有多種編碼方[9]，常見的有二進(jìn)制編碼[10]、實數(shù)編碼[11]、矩陣編碼[12]等，研究使用無需反復(fù)編碼、解碼的實數(shù)編碼，并可直觀地對問題特征進(jìn)行描述，由于在工地中產(chǎn)生的渣土分較多種類，其運輸價格不同，矩陣編碼難以表示。遺傳算法于1975年提出，1992年由Holland J H[13]發(fā)表正式版本，該算法根據(jù)實際需求，已被大量研究者和探索者根據(jù)實際需求進(jìn)行了改進(jìn)[14-17]，滿足了不同的生產(chǎn)需求。非支配排序遺傳算法(NSGA)[18-19]在解決多目標(biāo)規(guī)劃問題上，有著良好的表現(xiàn)，帶精英策略的非支配排序算法(NSGA-II)[20-22]相較于前者有更低的計算復(fù)雜度，在遺傳過程中保證了種群的多樣性，同時精英策略的采用保證遺傳過程中最佳個體不會丟失。而第三代非支配排序遺傳算法(NSGA-III)[23]在解決高維優(yōu)化問題(優(yōu)化目標(biāo)大于3個)時有著更好的優(yōu)勢。

近年來，我國的建筑業(yè)施工面積保持著增長的姿態(tài)，渣土運輸業(yè)的發(fā)展缺乏信息化與智能化。工地產(chǎn)生的渣土，需要渣土運輸車來完成渣土由工地到消納場的轉(zhuǎn)移，現(xiàn)階段采用的方案是工地就近選擇運輸企業(yè)或車隊為單一承運方，由承運方對其管轄范圍內(nèi)的渣土運輸車輛進(jìn)行調(diào)度，完成渣土托運。該方案的優(yōu)點在于有流程簡單、責(zé)任人單一，而其缺點在于調(diào)度時有很大概率出現(xiàn)以下情況：承運方的部分渣土車較非承運方的渣土車更遠(yuǎn)，調(diào)度成本更高。研究根據(jù)實際調(diào)度需求，總結(jié)出以下3個優(yōu)化目標(biāo)：最小化調(diào)度車輛數(shù)，保證司機每日收入，相同任務(wù)量，出車越少，每個司機所得收入越高；最大化完成任務(wù)量，在任務(wù)量超出平臺總運力時，合理調(diào)度能完成更多的托運任務(wù)，加快建筑進(jìn)度；最大化總體收益，工地支出固定，渣土車的成本降低，則有更好的效益，同時，低成本調(diào)度意味著渣土車在城市中更少地作無效行駛?；贜SGA-II的渣土車調(diào)度系統(tǒng)，借北斗終端[24]實現(xiàn)渣土運輸?shù)倪h(yuǎn)程監(jiān)督[25]，算法對調(diào)度方案進(jìn)行了優(yōu)化，對渣土運輸業(yè)的信息化建設(shè)有著重要意義。

1 平臺架構(gòu)

1.1 總體架構(gòu)

平臺下渣土運輸車輛加裝北斗智能車載設(shè)備和傳感器，將反饋得到的實時數(shù)據(jù)上傳至管控平臺，從而實現(xiàn)對車輛位置、速度、運輸狀態(tài)的實時監(jiān)控，后臺對工地、消納場、司機進(jìn)行綜合管理。整體架構(gòu)如圖1所示。

圖1 系統(tǒng)架構(gòu)圖

平臺由5個層次和兩個體系組成：

用戶：總經(jīng)理、管理人員對系統(tǒng)整體有管理權(quán)限; 調(diào)度員對系統(tǒng)計算出的調(diào)度方案進(jìn)行最終決策; 車隊長，對司機進(jìn)行管理; 系統(tǒng)還包括司機、托運人等用戶，他們分別有著不同的權(quán)限。

表現(xiàn)層：系統(tǒng)的功能部分由地圖維護(hù)、車輛監(jiān)管、車輛調(diào)度等組成。工地將需要完成的渣土運輸任務(wù)發(fā)布在系統(tǒng)上，調(diào)度部分結(jié)合車的坐標(biāo)位置計算出調(diào)度方案。

業(yè)務(wù)層：針對北斗傳入數(shù)據(jù)的處理和清洗，通過北斗智能車載設(shè)備上傳的行駛?cè)罩緮?shù)據(jù)進(jìn)行解析，用以查看車輛當(dāng)前位置并加以利用。

數(shù)據(jù)層：包括司機、車輛、工地、消納場、用戶、業(yè)務(wù)等數(shù)據(jù)。

網(wǎng)絡(luò)層：使用以太網(wǎng)提供網(wǎng)絡(luò)服務(wù)。

兩個體系：運行維護(hù)體系和法律法規(guī)與標(biāo)準(zhǔn)化體系。連個體系分別保證系統(tǒng)的正常運行和合法合規(guī)。

工地是對產(chǎn)生渣土并需要運輸?shù)牡胤降慕y(tǒng)稱，其發(fā)布的托運請求信息應(yīng)包含位置信息、完成時間要求以及運輸方量、支付費用等。平臺根據(jù)車輛位置、運輸成本等數(shù)據(jù)，求解調(diào)度方案，最終得到若干個調(diào)度方案，不同方案的車輛數(shù)、收益以及完成工地任務(wù)數(shù)量均不相同，運力充足的情況工地發(fā)布的任務(wù)都能夠在規(guī)定時間內(nèi)完成，運力不足時，系統(tǒng)則對完成哪些工地任務(wù)進(jìn)行自動取舍。調(diào)度員只需要考慮司機收益、調(diào)度整體收益以及完成任務(wù)數(shù)的優(yōu)先級來確定最終調(diào)度方案，并將調(diào)度方案由系統(tǒng)一鍵轉(zhuǎn)發(fā)到對應(yīng)的渣土車司機手機。

系統(tǒng)根據(jù)實際需求完成對數(shù)據(jù)庫的設(shè)計，存儲用戶數(shù)據(jù)、工地和消納場定位數(shù)據(jù)以及運輸路線等數(shù)據(jù)。后臺服務(wù)使用ThinkPHP框架搭建，添加接收車輛定位數(shù)據(jù)的通訊擴(kuò)展，開發(fā)數(shù)據(jù)解析模塊將通訊報文中的有效信息存儲到數(shù)據(jù)庫中。引入高德地圖，對工地、消納場、渣土車等進(jìn)行可視化展示，系統(tǒng)內(nèi)置權(quán)限管理、日志查詢等功能。

1.2 數(shù)據(jù)流程

平臺上的數(shù)據(jù)分為兩部分，一部分是用戶錄入，例如用戶個人信息、工地托運任務(wù); 另一部分為系統(tǒng)自動錄入，這部分?jǐn)?shù)據(jù)為渣土車的定位數(shù)據(jù)。經(jīng)過處理的數(shù)據(jù)根據(jù)業(yè)務(wù)需求存入MySQL數(shù)據(jù)中，并自動備份。系統(tǒng)數(shù)據(jù)流程如圖2所示。

圖2 數(shù)據(jù)流圖

2 系統(tǒng)實現(xiàn)

2.1 通訊框架

交通部門要求渣土車、旅游大客車等大型車輛，必須安裝北斗導(dǎo)航系統(tǒng)的車載終端[26-27]。系統(tǒng)沒有權(quán)限直接從終端獲取定位數(shù)據(jù)，終端通過用戶數(shù)據(jù)報協(xié)議(UDP,user datagram protocol)或傳輸控制協(xié)議(TCP,transmission control protocol)與車管平臺進(jìn)行信息通訊，當(dāng)通訊鏈路系統(tǒng)異常，車載終端采用短消息服務(wù)(SMS,short message service)方式通訊。系統(tǒng)則是通過與車管平臺建立socket通信獲取車輛定位數(shù)據(jù)。系統(tǒng)通訊流程圖如3所示。

圖3 通訊流程

2.2 平臺框架

渣土車調(diào)度系統(tǒng)的搭建基于PHP的開源框架THinkPHP3.2，該框架有較強的模塊化概念，方便開發(fā)的有序進(jìn)行。服務(wù)器使用的是開源的Apache，能對事務(wù)實現(xiàn)較好的處理。數(shù)據(jù)庫是MySQL的5.3版本，有較好的穩(wěn)定性。前端結(jié)合Bootstrap實現(xiàn)頁面展示，該前端框架對個組件進(jìn)行了封裝，具有統(tǒng)一的設(shè)計風(fēng)格，提高前端功能的開發(fā)效率。

2.3 功能實現(xiàn)

2.3.1 日常管理

日常管理模塊中包含工地、消納場、車輛等注冊功能以及收入支出管理功能等日常業(yè)務(wù)，實現(xiàn)渣土運輸?shù)娜粘Ｉa(chǎn)管理，其中運輸路線管理功能記錄不同車輛在各工地和消納場之間的運輸費用，為車輛調(diào)度成本預(yù)算提供數(shù)據(jù)支撐。各項管理數(shù)據(jù)在數(shù)據(jù)庫中分表存儲，通過控制器(Controller)查詢并格式化為Json格式數(shù)據(jù)，前端通過接口對所需數(shù)據(jù)進(jìn)行訪問。

2.3.2 車輛管理

車輛管理模塊包含車輛實時位置獲取、各渣土車的托運記錄管理以及歷史軌跡復(fù)現(xiàn)三大功能。

北斗終端按照J(rèn)T/T 808-2011《道路運輸車輛衛(wèi)星定位系統(tǒng) 終端通訊協(xié)議及數(shù)據(jù)格式》的規(guī)范，通過TCP或UDP實現(xiàn)與車聯(lián)網(wǎng)位置信息通訊，系統(tǒng)與車聯(lián)網(wǎng)采用雙鏈路通訊方式，通過車聯(lián)網(wǎng)所提供的對外接口，搭建socket服務(wù)，獲得渣土車的定位數(shù)據(jù)包，服務(wù)器對數(shù)據(jù)包進(jìn)行解析并存入數(shù)據(jù)庫中，并將渣土車定位點通過地圖API進(jìn)行繪制。系統(tǒng)與車聯(lián)網(wǎng)的通訊模塊制定了重連策略，若長時間內(nèi)未收到定位數(shù)據(jù)包，則根據(jù)最近丟失時間，主動向上級發(fā)出數(shù)據(jù)包請求，以保證定位的有效性。

渣土車托運記錄管理是對調(diào)度任務(wù)完成情況的核驗，系統(tǒng)對渣土車分別在工地、消納場的停滯時間和工地到消納場的行駛距離進(jìn)行記錄，并通過預(yù)設(shè)數(shù)據(jù)的正常和非正常值范圍，對比實際記錄數(shù)據(jù)，對此趟運輸記錄的“待處理”狀態(tài)進(jìn)行修改，不同值范圍代表不同狀態(tài)，狀態(tài)“采用”表示該趟運輸有效且以此計算司機薪酬，否則由記錄員查看歷史軌跡并對該條記錄進(jìn)行“采用”或“刪除”操作。

系統(tǒng)通過渣土車ID和時間區(qū)間，后臺查詢時間段內(nèi)對應(yīng)渣土車的位置點信息，前端得到位置點的結(jié)果集在地圖上進(jìn)行繪制，并按時間的先后順序進(jìn)行連線，得到渣土車在地圖上的行駛軌跡，管理員可通過軌跡查詢直觀地看到渣土車在各時間段的行駛情況。

2.3.3 調(diào)度模塊

工地通過管理員在系統(tǒng)添加托運請求，系統(tǒng)將任務(wù)托運方量按規(guī)定方案換算為趟數(shù)，并將工地總支出以運輸產(chǎn)值單價在列表中展示。系統(tǒng)記錄了工地和消納場的位置、渣土車可運行路線以及渣土車的調(diào)度成本等數(shù)據(jù)，調(diào)度時使用最近時間段渣土車的位置信息，通過遺傳算法對調(diào)度方案進(jìn)行計算，得到最終調(diào)度方案，在詳情頁展示，并由調(diào)度員確認(rèn)發(fā)布調(diào)度訊息，調(diào)度實現(xiàn)如圖4、圖5所示。

圖4 渣土調(diào)度方案選擇與發(fā)布

圖5 調(diào)度詳情

3 車輛調(diào)度方案設(shè)計

3.1 問題定義

研究問題的具體描述如下：在渣土車集合N中選出部分渣土車，按照不同的順序完成工地的任務(wù)集合T使得用車數(shù)最少、時間最短或者成本最小，這個渣土車的調(diào)度序列則是問題的解。系統(tǒng)當(dāng)前已注冊渣土車集合q={q1,q2,q3,...,qj}，j為平臺注冊渣土總數(shù)，工地集合M={M1,M2,M3,...,Mm}，m為平臺注冊工地總數(shù)，消納場集合N={N1，N2，N3，...，Nn}，工地與消納場之間的距離集合為D={D(1,1)，D(1,2)，...，D(m,n)}，由于渣土車運輸路線相對單一的特殊性，該系統(tǒng)中將工地到消納場之間的路徑存儲為確定值，且集合D的元素可為空(工地和消納場不是一一對應(yīng)，存在渣土車無法從某些工地到達(dá)某些消納場)，其路徑距離通過工地ID與消納場ID成對查詢，各工地運輸任務(wù)的趟數(shù)集合T={T1，T2，...，Tm}。

3.2 編碼

對問題的解決方案進(jìn)行編碼是遺傳算法的重要初始步驟，也是問題解的表示方式，為了更直觀地表示工地及任務(wù)量，同時也為避免二進(jìn)制編碼的漢明懸崖問題[9]，此處采用實數(shù)編碼，種群的個體就是問題的解。每個解序列的長度為n×5+3，n為平臺車輛數(shù)，5表示一輛車一天運輸趟數(shù)不超過5次，3是評價函數(shù)的個數(shù)，分別對應(yīng)3個優(yōu)化目標(biāo)。例如序列(5,0,3,5,0,3,0,3,0,0,f1,f2,f3)中有2個5，表示5號工地的渣土需要2次運輸能夠完成，3個3表示3號工地的渣土需要3次能夠運輸完成。在序列中截取長度為5的序列組(5,0,3,5,0)，第一次截取表示編號為1的渣土車當(dāng)前的調(diào)度任務(wù)，序列含義為1號渣土車首先完成5號工地的一次托運，0表示沒有調(diào)度任務(wù)安排，然后完成3號工地的一次托運，最后完成5號工地的一次托運，第二次截取的序列組則是2號渣土車的調(diào)度次序，每次截取長度為5的序列組，以此類推，序列后的f1，f2，f3表示3個優(yōu)化目標(biāo)的評價函數(shù)值，也稱適應(yīng)度函數(shù)值，分別代表該個體在不同優(yōu)化目標(biāo)上的適應(yīng)度大小，通過前n×5個調(diào)度序列計算得到。

3.3 初始化種群

種群是遺傳算法中個體的集合，這些個體在渣土車調(diào)度應(yīng)用中表示的是調(diào)度方案，種群就是不同調(diào)度方案的集合，其數(shù)學(xué)表示是一個矩陣。在本系統(tǒng)中，種群的生成可分為以下幾個步驟：

1)初始化足夠長度且元素為‘0’的一維數(shù)組，其長度等于系統(tǒng)現(xiàn)有車輛數(shù)與每輛車每天最多可運趟數(shù)的乘積加3；

2)隨機選擇一個編號為a的工地，且該工地是第一次被選擇，其任務(wù)量為n趟，判斷一維數(shù)組中除保存適應(yīng)度值的末尾3位，剩下的‘0’的個數(shù)是否大于n，若是，則隨機修改末尾三位前的‘0’為a，否則，標(biāo)記a工地為非第一次選擇，選擇下一個工地繼續(xù)以上操作；

3)重復(fù)步驟2)，當(dāng)一維數(shù)組中的元素全不為‘0’或工地全被標(biāo)記為非第一次選擇時，停止循環(huán)，得到一個個體的編碼序列；

4)重復(fù)以上3個步驟，得到一個新的個體，即一個新的數(shù)組，將這個數(shù)組與前面得到的數(shù)組合并，得到一個列數(shù)不變，行數(shù)加一的矩陣。種群的大小就是以上4個步驟的重復(fù)次數(shù)，最終得到初始化矩陣，在該矩陣后面增加三列，每一列分別代表3個目標(biāo)的適應(yīng)度函數(shù)值。

3.4 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)的作用是對個體的適應(yīng)度進(jìn)行計算，適應(yīng)度是評價個體好與壞的重要指標(biāo)，也是調(diào)度序列好與壞的直接表示。研究針對調(diào)度的3個優(yōu)化目標(biāo)：

1)最小化車輛數(shù)，通過編碼序列可知車輛的調(diào)度情況，對某一編碼序列進(jìn)行長度為5的截取分片，得到若干定長編碼序列和一個長度為3的序列，各長度為5的序列分別對應(yīng)渣土車的調(diào)度情況，分片序列全為0，則對應(yīng)渣土車沒有被調(diào)度；若不全為0，則對車輛使用數(shù)統(tǒng)計時加1。由此可得到如下車輛使用數(shù)的表示

(1)

式中，di表示第i輛渣土車的調(diào)度序列，NULL表示調(diào)度序列全為0，即序列所對應(yīng)車輛未被調(diào)度。

2)最大化任務(wù)完成數(shù)，任務(wù)數(shù)表示所有渣土車的托運總趟數(shù)，在編碼序列中，除序列后三位，序列中不為0的則表示有一趟運輸任務(wù)。遍歷編碼序列的前5n位，編碼不為0時，則任務(wù)總數(shù)加1，托運總趟數(shù)的表示如下：

(2)

式中，ti表示編碼序列中第i位的值，若為0則沒有托運任務(wù)，相反托運總趟數(shù)加1。

3)最大化收益，工地發(fā)布托運任務(wù)時對渣土車運輸一趟所支付的費用稱為運輸產(chǎn)值單價，承運方收入是固定的，當(dāng)成本降低，承運方的收益則對應(yīng)上升，同時為了方便后期實驗結(jié)果與實際生產(chǎn)記錄作對比，以收益最大化為優(yōu)化目標(biāo)。完成托運任務(wù)總收益為工地總產(chǎn)值與運輸成本的差值，承運方的成本由空車行駛成本和載重行駛成本兩部分組成，公式表示如下:

tij=t_cost(p_startij,p_endij)

mij=m_cost(p_endi(j-1)，p_startij)

(3)

式中，n為渣土車總數(shù)，4表示渣土車每日運輸趟數(shù)上限5次，將調(diào)度序列用一個n×5的A矩陣表示，即payij為工地Mi到消納場Nj的運輸產(chǎn)值單價，t_cost(p_startij,p_endij)表示渣土車完成任務(wù)A(i,j)的載重成本，m_cost(p_end(i-1)j-p_startij)為空車調(diào)度成本，若該趟空車調(diào)度是當(dāng)日第一次調(diào)度，則m_cost(p_endi(j-1)，p_startij)為渣土車定位到工地Mi的空車調(diào)度成本，否則為上一個調(diào)度消納場到工地Mi的空車調(diào)度成本。

由式(1)～(3)3個目標(biāo)函數(shù)可轉(zhuǎn)化為以下3個適應(yīng)度函數(shù)：

車輛數(shù)適應(yīng)度函數(shù)：

(4)

托運趟數(shù)適應(yīng)度函數(shù)：

(5)

收益適應(yīng)度函數(shù)：

(6)

式(6)中，payi為第i個工地的運輸產(chǎn)值單價。

3.5 選擇、交叉與變異

計算出種群每個個體的適應(yīng)度，可對比個體的優(yōu)劣。研究的選擇操作采用二錦標(biāo)賽選擇方法，即兩兩對比，選擇適應(yīng)度更好的個體，由于有一個個體有3個適應(yīng)度值，當(dāng)個體的適應(yīng)度不能滿足3個同時優(yōu)于另一個個體時(非支配排序)，對比個體的聚集距離(個體在直角坐標(biāo)系上的距離)，選擇聚集距離更大的個體，即更加離散的個體。完成選擇操作，得到初始種群一半個體數(shù)量的種群，將該種群繼續(xù)做交叉和變異操作。

交叉操作在遺傳算法中的作用是產(chǎn)生新的個體，為了保證調(diào)度序列的有效性，使用順序交叉，步驟如下：

1)選擇兩個個體作為父代1和父代2，在父代1中隨機選擇一段連續(xù)基因，如圖6所示。

圖6 父代被選中的基因段

圖7 子代與父代被選中基因段相同

3)在父代2中依次找出被選中的基因的位置，再將其與基因按順序放入子代1中，如圖8所示。

圖8 新的子代的產(chǎn)生

經(jīng)過以上3個步驟，得到子代1的調(diào)度序列為(9,6,9,5,7,0,2,7,5)，該交叉方法的兩個父代會產(chǎn)生兩個子代，子代2的產(chǎn)生與子代1的形成步驟相同。該方法生成的個體不需要做有效性檢測。

遺傳算法的選擇和交叉操作均基于初始種群，而初始種群并未列出所有可行調(diào)度序列，變異操作在遺傳算法中的作用是維持種群的多樣性，擴(kuò)大其索解范圍，防止陷入局部最優(yōu)解。變異方法采用兩點互換，隨機選中父代的兩個基因，交換兩個基因在序列中的位置得到變異后的子代。變異操作如圖9所示。

圖9 變異產(chǎn)生新的子代個體

3.6 個體選擇策略

在進(jìn)行二錦標(biāo)賽選擇時，留下的僅是兩個個體之間更好的個體，若兩個較優(yōu)個體對比時，相對較差但在群體中較優(yōu)的個體會被拋棄，這種選擇方式得到的種群只是相對較好，而有可能去除了優(yōu)質(zhì)個體。研究采用了精英保留策略，該策略將將父代種群和子代種群合并，合并后的種群進(jìn)行非支配排序[28]，產(chǎn)生若干個分類子集，根據(jù)等級由低到高選擇出與初始種群大小相同的種群，若存在臨界層分類子集，需要對該子集的個體進(jìn)行擁擠度計算，為了保證群體的分布性和多樣性，將聚集距離小的個體認(rèn)為更優(yōu)，優(yōu)先選擇，在臨界層分類子集選擇若干個個體，直到種群大小滿足初始要求。選擇流程如圖10所示。

圖10 算法流程圖

4 實驗結(jié)果與分析

4.1 實驗步驟和方法

在數(shù)據(jù)庫中通過SQL獲取到調(diào)度需求、車輛歷史定位以及調(diào)度成本等數(shù)據(jù)，并轉(zhuǎn)換為“xls”表文件，在Matlab中完成算法的仿真實驗，通過實驗結(jié)果對調(diào)度方案設(shè)計的有效性進(jìn)行驗證。將Matlab中的算法代碼移植到系統(tǒng)擴(kuò)展功能上，完成算法在系統(tǒng)中的實際應(yīng)用。

4.2 實驗結(jié)果

以2020年6月中某一日為例，完成仿真實驗得到的結(jié)果如圖11所示。

圖11 第一層非支配排序結(jié)果集

圖11中，f1，f2，f3分別對應(yīng)3個優(yōu)化目標(biāo)的適應(yīng)度函數(shù)值，每個點的所對應(yīng)的個體的編碼序列，即為渣土車的調(diào)度方案。為更加明顯地展示算法在實際系統(tǒng)應(yīng)用的有效性，實驗選擇2020年6月整月的歷史數(shù)據(jù)和計算結(jié)果進(jìn)行統(tǒng)計，并以平均量作對比。對比結(jié)果如表1所示。

表1 2020年06月不同調(diào)度方案結(jié)果

表中用車最少和完成任務(wù)量最多兩個調(diào)度方案均取得了較好的應(yīng)用效果。當(dāng)該月每天的調(diào)度以收益最大為目標(biāo)時，完成任務(wù)量減少了，原因是該月有一天的調(diào)度方案是少完成一個工地的托運任務(wù)，總收益更多；該方案用車數(shù)沒有得到有效減少，原因之一是平臺所有渣土車的運力超過工地對運力的需求，車輛相對工地較為集中，若以收益最大為目標(biāo)，系統(tǒng)會就近大量調(diào)度渣土車，降低返程托運的空車調(diào)度成本。

實驗證明，該算法能夠有效地完成渣土車調(diào)度方案的設(shè)計，并得到比以往人工調(diào)度更優(yōu)的結(jié)果。系統(tǒng)對渣土運輸業(yè)相關(guān)數(shù)據(jù)進(jìn)行了有效管理，方便管理員對歷史數(shù)據(jù)的復(fù)驗，隨著平臺規(guī)模的擴(kuò)大，其實用效果將更加明顯。

5 結(jié)束語

研究對渣土運輸車的調(diào)度過程進(jìn)行了建模，結(jié)合NSGA-II算法，設(shè)計并實現(xiàn)了渣土車調(diào)度系統(tǒng)，以貴陽市111輛渣土車、95個工地、235個消納場、461條路線等數(shù)據(jù)加以驗證，結(jié)果表明，該調(diào)度系統(tǒng)能夠在管理好渣土運輸市場各方數(shù)據(jù)的同時，能夠替代調(diào)度員對調(diào)度方案的設(shè)計工作，根據(jù)不同目標(biāo)需求對渣土車進(jìn)行調(diào)度。本系統(tǒng)存在的不足是，對時間約束的處理不是最優(yōu)，司機雖能完成調(diào)度任務(wù)，但對于距離較近的托運任務(wù)，司機完成系統(tǒng)調(diào)度任務(wù)后仍有較多可工作時間。后期優(yōu)化調(diào)度的時間約束，可提高系統(tǒng)的預(yù)算精準(zhǔn)度，調(diào)度方案也更接近最優(yōu)解。若擴(kuò)大系統(tǒng)的用戶量，在更多城市推廣，可有效提高渣土運輸業(yè)的效益。