基于CPS架構的垃圾轉運車輛的優化調度系統

周克良，周 橋，胡梁眉

（江西理工大學 電氣工程與自動化學院，贛州 341000）

0 引言

CPS（Cyber-Physcial System：信息物理融合系統）是重要、較新的研究領域，是科技發展到一定階段的產物，順應信息技術發展趨勢[1]。基本理念是通過人機交互接口使網絡化空間以實時、可靠、安全的、遠程的協作方式對物理世界進行感知和控制[2]，為人類提供智能化服務，最終目標是實現整個系統的完全融合，從而建立可靠、可信、可控安全的系統網絡。

垃圾轉運可簡化為VRP（車輛路線）問題，最早由Dantzig和Ramser提出，經過研究發展，求解方法包括精確算法、啟發式算法。垃圾轉運涉及到垃圾收集點位置、垃圾量和車輛最大載重量、車輛最大行程等問題[3]。在垃圾轉運過程中，需要對涉及到的數據進行收集分析判斷。

垃圾轉運是垃圾處理中重要的一環，在垃圾轉運收集過程中，各個垃圾收集點的垃圾量動態變化[4]。將CPS結合在轉運車的調度中，物理層的實體通過對環境的感知, 對相應的信息進行處理[5]，即對垃圾收集點位置、垃圾量和車輛最大載重量、車輛最大行程等數據進行收集分析，對收集到的數據進行簡單處理，同時將信息通過網絡發送到信息層，信息層組件在獲取感知信息后，針對物理環境和網絡中用戶需求的改變，運用遺傳算法自動調整內部關聯與模型，然后得到最有效，最方便快捷的有效路徑，從而在垃圾轉運過程中減少資源的不必要的浪費。車輛在轉運過程中，我們可以在系統中監測任務的進度，如果物理環境發生擾動，CPS系統也可以實時的收集數據，對已定的任務進行調節。

1 CPS分析

1.1 CPS運行方式

CPS是一種典型的分布式控制系統。CPS系統中包含海量的受限單元，例如嵌入式控制單元、微型傳感單元等，由它們基本組成分布式控制網絡[6]。CPS系統需要龐大的計算能力，分布式技術能夠承擔龐大的計算任務，也可以減少網絡負載。

1.2 CPS的基本構架

CPS體系結構是CPS核心的技術，CPS結合計算和物理進程于一體，體現出一系列特定的系統特性。CPS基本架構如圖1所示，CPS是物理技術和信息技術的一體化，包括物理層，網絡層，協同優化層以及應用層[7]。

物理層指CPS中與現實環境緊密結合的感知測量設備、執行控制設備以及它們組成的具有特定功能或存在于特定區域的無線/有線網絡單元；網絡通信層負責將感知數據與控制要求的實時準確傳遞，為系統實時提供可靠服務；協同優化層負責對感知數據的分析與處理融合，其中，監控中心體現實時轉運狀態，決策控制中心包含一個由實際轉運線路映射的仿真模型，體現理想轉運狀態，將兩者對比，確定是否需要對原有轉運方案進行調整，并將該決策信息反饋給實際轉運設備；應用層支撐各類智能應用與資源和服務的協同優化。

圖1 CPS基本架構

2 問題描述及數學建模

2.1 問題描述

在一區域，有一垃圾處理中心，區域分布垃圾收集點，每日采集垃圾量數據，交通狀況實時采集并預測，車輛負責將垃圾轉運至垃圾處理中心進行預處理，車輛當日最大可運載路程由該車輛油量所定，采集數據，將數據分類上傳至CPS系統處理分析，得到將所有垃圾運轉到垃圾處理中心的最快速較短的距離，也就是最經濟的轉運路徑。

2.2 建立數學模型

在某一固定區域內有垃圾收集點N個，該區域內有M輛垃圾車負責轉運，都在垃圾處理中心等待調度，將垃圾轉運到中心進行處理。每輛車的最大載重量為C；每輛車最大行駛距離為lm（m=1，2，…，M）；假定第i個垃圾點產生的垃圾量為Gi噸（i=1，2，3，…，N）；各個垃圾收集點及處理中心任意兩點之間行車距離為lij。

假設車輛從垃圾處理中心出發，將垃圾轉運收集到處理站進行處理，第m輛收運次數為mf，里程為ml，第t運收路線為第mt條子路徑，包含nmt個垃圾收集點，pmt代表第mt條路徑中nmf個垃圾站點的集合，其中pmti（t=1，2，…，mt；i=1，2，…，nmt）代表第mt條子路徑的第i個垃圾站點，該垃圾車在該站收集的垃圾量為Gpmti，pmtj表示子路徑上最后一個垃圾收集站點，該垃圾收集點到垃圾壓縮站的距離為lptj。

以垃圾收運成本最低為模型，即最短路徑的模型，建立的模型如式(1)所示：

約束條件如式(2)所示：

如式(2)所示，在一條子路徑中，車輛運載的垃圾不能超過最大運載量；一輛轉運垃圾車轉運距離不能超過最大行車距離；垃圾轉運車要經過該區域內所有的有垃圾的垃圾收集點；垃圾轉運車收集到的垃圾量；一輛車的運輸次數不能超過設定值；子路徑中的垃圾收集點不能超過總的垃圾點個數。

3 求解算法設計

遺傳算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型[8]。

本節選用遺傳算法思想，設計基于經濟效益最高的垃圾轉運路線，具體包括：編碼與編碼設計、種群初始化、適應度函數以及遺傳操作[9]。遺傳算法流程圖如圖2所示。

圖2 遺傳算法基本流程圖

3.1 染色體的編碼與解碼

對于VRP的問題，遺傳算法染色體編碼采用自然數編碼，用0代表垃圾處理中心，1,2，…，i，…，N-1，N代表N個垃圾收集站點。這種染色體結構可以通俗的理解為第一輛車送垃圾處理中心0出發，經過收集點1，2，…，n后回到處理中心0，形成子路徑1；第二輛車也從處理中心出發，經過子路徑1未訪問的收集點如i，…，M后回到處理中心，形成子路徑2，以此類推，直到所有的收集點全部被遍歷，形成M條子路徑，如0 8 10 12 11 0 4 6 7 9 0 5 2 1 0 3 0代表的轉運路徑為：

處理中心0→收集點8→收集點10→收集點12→收集點11→處理中心0；

處理中心0→收集點4→收集點6→收集點7→收集點9→處理中心0；

處理中心0→收集點5→收集點2→收集點1→處理中心0；

處理中心0→收集點3→處理中心0。

3.2 初始化種群

根據自然數染色體編碼方法，對于有N個垃圾收集點，M輛車的問題，在對種群中染色體進行初始化時，隨機的產生1到N之間的數來填充基因，保證它們不重復，隨機插入M+1個0代表處理中心，如此反復，直到初始種群規模為L。

3.3 適應度函數

遺傳算法中，個體適應度越大，表示個體的性能越好，因此需要將目標函數轉化為適應度函數[10]，如式(3)所示。

3.4 遺傳操作

本文遺傳算法采用最佳保留的輪盤賭復制法進行染色體的復制，采用最優保留順序交叉算子進行染色體的交叉，按照概率進行反轉變異[11]。

4 實例分析

4.1 問題描述

贛州章貢區市區有12個垃圾收集點，一個垃圾處理中心和一個車場，暫時位于同一位置，垃圾收集點編號為1～12，處理中心為0。實地測得各收集點和處理中心的位置，通過稱重技術獲得該區域的垃圾收集點垃圾量，GIS（地理信息）系統標記獲取經緯坐標后，簡化坐標，垃圾點基本數據如表1所示，采用百度地圖的開放平臺API獲取收集點之間當前時間段交通狀況下最段路徑如表2所示。市區垃圾收運車輛為中型貨車，車輛平均行駛速度為40km/h ，最大載重量為6t。

4.2 基于遺傳算法的問題求解

根據以上構建的數學模型，運用遺傳算法求解，在MATLAB R2014b上編程得到仿真結果如圖所示：

表1 垃圾收集點垃圾量、經緯坐標、簡化坐標

表2 任務點之間的距離

續（表2）

如圖3所示，總路徑通過遺傳算法迭代優化計算得到最短路徑為49.3（km）。

圖3 迭代過程

圖4 車輛優化路徑仿真圖

如圖4所示，★代表垃圾處理中心，其他收集點按坐標點標記，在MATLAB R2014b中編寫程序畫出任務分配路徑圖。

最優染色體編碼為0 1 11 7 9 0 3 2 0 6 5 4 0 12 10 8 0，編碼解碼表示為車輛的任務分配如表3所示。

表3 車輛最優收運路線

5 結束語

本文將發展迅速的CPS架構運用于垃圾轉運車的調度中，利用物理層采集的數據信息通過網絡數據庫和遺傳算法的計算處理，根據垃圾轉運外在和內在等主要元素，通過計算和優化使垃圾轉運的物理世界與信息世界深度融合，使實時、安全、高效、可靠的智能轉運環境能自主調節、自主運用和自主實現，驗證了將CPS與垃圾轉運是可行且可靠的，證明CPS系統在垃圾處理領域中具有發展前景，能有效提高垃圾轉運的經濟和時間效率。

[1]劉翔宇.電子信息技術發展現狀及發展趨勢[J].科技展望,2015,25(36):9-10.

[2]何明,梁文輝,陳國華,等.基于多視圖的信息物理融合系統體系結構研究[J].計算機工程與應用,2013,49(12):25-32.

【】【】

[3]劉長瑋.城市生活垃圾收運系統優化模型及其應用研究[D].重慶大學,2007.

[4]王勇.基于改進型蟻群算法的餐廚垃圾收運路線優化研究[D].重慶交通大學,2015.

[5]肖楓.大數據時代下CPS的制造系統調度優化[J].科學與信息化,2017,(4):36-38.

[6]韓杰,馬斌,黃寬,等.基于蟻群算法的分布式CPS系統任務調度設計[J].測控技術,2015,34(2):121-124.

[7]張明麗.基于CPS架構的垃圾站點無線遠程監控系統研究[D].江西理工大學,2015.

[8]金曉慧.基于流形距離和核函數的進化聚類算法研究及其應用[D].西安電子科技大學,2009.

[9]潘燁煬,郭潔,張林穎,等.基于自適應遺傳算法的優化布站方法研究[J].國外電子測量技術,2013,32(6):62-64.

[10]郭海雙,梁佳雯,張劭昀,等.MATLAB遺傳算法工具箱GADS優化及應用[J].電子設計工程,2015,23(10):27-29,32.

[11]朱志勇,刁洪祥.基于改進遺傳算法的車輛路徑問題研究[J].湘潭大學自然科學學報,2011,33(3).

[12]符俊波,馬慧民,張爽,等.有垃圾量變動的生活垃圾收運車輛調度干擾管理研究[J].上海理工大學學報,2017,39(4):368-375.

[13]Yun Wang;Dong Liu;Chen Sun , A Cyber Physical Model Based on a Hybrid System for Flexible Load Control in an Active Distribution Network[J]. Energies.2017(3):1-20.