改進的差分進化算法解決混凝土攪拌站選址問題

文/歐運娟

1 引言

作為一個建設型大國，中國對混凝土的需求與日俱增，現有的攪拌站已不足以支撐建筑的需要。例如2017年南寧市中心城區的預拌混凝土需求達到1400萬立方米/年，要求攪拌站的總供應能力至少達到1960萬立方米/年，而目前已有站點的總供應能力約為1380萬立方米/年，存在很大的供應缺口。因此需要增加站點數量，并希望這些新增站點位于合理的位置，才能滿足城市建設需要。

傳統的選址問題涉及到的供應模式為“一對多”分配，屬于整數規劃問題。國內外許多學者對其進行研究并建立了一系列的模型和算法。與傳統選址問題不同的是，攪拌站問題屬于“多對多”分配模型。該問題的難點為站點向組團的分配量，即一個站點分配給一個組團的比例可以為0到1之間的任何實數，另一個難點是候選點的選擇。當候選點數量眾多時我們無法窮盡所有方案。常見的智能算法有蟻群算法、粒子群算法、遺傳算法、差分進化算法等。DE算法作為一種新近提出的優化算法，引起國內外學者的廣泛關注。但經典的DE算法對復雜優化問題容易出現早熟收斂。本文改進了經典的差分進化算法，增加了局部搜索，使其適用于攪拌站選址模型。

2 問題的描述與建模

2.1 問題分析

以2017年南寧市中心城區的攪拌站選址為例，研究如何選擇新增站點，并盡量縮短混凝土的運輸里其選址問題具有一些特殊性，主要體現在以下幾個方面：

（1）雙重規劃目標。攪拌站選址的規劃目標有兩個：一是最小化混凝土的加權運輸總里程（立方米·公里）；二是最小化新增站點數量。第一個目標可以縮短貨物運輸里程，從而減輕城市道路交通壓力，減少車輛污染物排放。第二個目標不僅可以減少攪拌站對城市景觀的影響，還有助于防范區域內攪拌站分布過于密集而出現惡性競爭。

（2）運輸距離限制。由于預拌混凝土的使用具有很強的時效性，無法運送到較遠的地方銷售，因此在建模時應設定運輸距離的上限。

（3）供應能力限制。單個混凝土攪拌站的規模不宜太大，實否則會造成規模不經濟，大量車輛進出還會造成城市局部路段交通堵塞。

（4）新增站點數量是不確定的。在最大供應距離受限制的情況下，新增站點的數量取決于供需缺口的大小及候選站點、原站點和建設組團的空間分布有關。

（5）組團與攪拌站屬于“多對多”的關系。即一個組團可以接受多個攪拌站的服務，一個攪拌站也可以供應多個組團。

2.2 符號說明

本文研究定義的集合、參數和決策變量說明如下：

2.2.1 集合

2.2.2 參數

demk為建設組團k的所需要的供應能力；dik為侯選站點ij與建設組團k的距離；djk為已有站點j與建設組團k的距離；td為混凝土運輸距離的上限，td=25公里；newsi為候選站點i的供應能力，所有候選站點供應能力為50萬立方米/年；oldsj表示原有站點j的供應能力，原有站點大部分的供應能力最大為170萬立方米/年，供應能力最小的僅為32萬立方米/年。

2.2.3 決策變量

2.3 建立模型

建立攪拌站選址的混合整數規劃模型如下：

式（1）和（2）是目標函數，在滿足需求的條件下，使貨物運輸總里程最小，同時要求新增站點數量盡量少。式（3）～（7）是約束條件，式（3）表示每個建設組團所需的供應能力都能得到滿足，式（4）和（5）站點供應能力約束，式（6）為已有攪拌站均必須參與供應，式（7）表示運輸距離不能砂于25公里。

2.4 經典DE算法

DE算法包括初始化、變異、交叉和選擇四個步驟，其設優化問題為：

2.4.1 初始化

設種群規模為NP，問題維度為D。則第i個個體可以通過以下公式產生：

2.4.2 變異

對種群中的每個向量xi（目標向量），DE算法產生一個擾動向量vi。常用的變異公式如下：

2.4.3 交叉

其中，對于每個試驗向量，均產生一個范圍為[1,NP]的隨機整數jrand，從而保證了在每一次迭代ui至少從vi獲取了一個元素。

2.4.4 選擇

DE的選擇算子采用了優勝劣汰的策略。計算試驗算子ui的目標函數值并與目標向量xi的目標函數值進行比較，并選擇目標函數值小的個體進入下一代。選擇操作如公式（16）所示。

3 改進的DE算法

上述混合整數規劃模型雖然屬于條件中位問題，常見的解決離散優化問題的啟發式算法有遺傳算法、蜂群算法、差分進化算法和蟻群算法等,本文算法在DE算法的基礎上增加了局部搜索。

本文算法流程如下：

Step1：初始化種群規模NP，交叉率CR，收縮因子F。并初始化種群中所有個體；

Step2：計算每個個體的適應值，采用目標函數值作為適應值，計算f(xi)；

Step3：若當前最優解的適應值min(f(xi))低于xbest的適應值f(xbest)，則按當前最優解更新xbest；

Step4：按照公式（12）（15）（16）進行一次迭代；

Step5：如果滿足規則，則執行局部搜索操作；

Step6：求出歷史最優解xhbest；

Step7：如果算法達到最大評估次數，則退出；否則返回Step2。

3.1 編碼

本文算法采用一個矩陣chr=（N+2）×M表示一個個體，其中M為最大站點數，N為組團數。增加的2行用來記錄站點位置及剩余量。數組中前M行中的每個元素代表該列所在站點對該行所在組團的供應量，第M+1行的每個元素代表該列所在站點的位置，第M+2行的每個元素代表該列所在站點可供分配量。

3.2 種群初始化

種群中每個個體為問題的一個解，因此個體所包含的站點須滿足所有約束條件。同時，為產生多樣性的解，在選取站點時采用隨機選取的方法。其步驟如下：

Step1：為每個個體chri隨機選取M個站點，若chri包含所有原有站點，并且站點的總供應量大于總需求量，則進行Step2，否則返回Step1。

Step2：檢查所有組團的分配量。若有組團的需求得不到滿足，則隨機選取一個未滿足需求的組團，將站點分配給該組團。否則分配結束。

3.3 適應度函數：

此模型有兩個優化目標，即最小化路徑與其供應量的乘積的和（公式（1）），同時最小化新增站點的數量（公式（2））。因為新增站點數量規模不大，本文的算法將新增站點數量作為問題的輸入。本文算法優化公式（1）。同時，我們將公式（1）作為算法的適應度函數。

表1：參數設置

表2：算法性能對比

3.4 交叉

本文算法按照公式（12）進行交叉操作。子代產生過程的具體步驟如下：

Step1：隨機產生交叉點a、b并按照公式（12）進行交叉，產生子代；

Step1：檢查子代中重復的站點并進行替換；

Step1：檢查交叉后產生的子代是否能滿足需求，如果子代的供應量大于總需求量，則調整分配方案使每個組團的需求得到滿足，否則不進行交叉操作。調整操作如下：

（1）遍歷所有組團，如果該組團的供應量大于需求量，則將供應該組團的所有站點中路徑最長的站點進行重新分配，直到該組團的供應量等于需求量。

（2）遍歷所有組團，如果該組團的供應量小于需求量，則將需要從新分配的所有站點中路徑最短的站點分配給該組團，直到該組團需求量得到滿足。

3.5 局部搜索

針對攪拌站問題的特殊性，本文設計了兩種變異方案。

（1）用未包含在個體中的候選站點隨機替換包含在個體中的候選站點，為保證經過變異后的個體仍為模型的解，需要檢查替換的站點是否滿足組團的需求。如果不滿足，則不進行變異。

（2）隨機改變站點中的兩條分配路徑并調整方案，其步驟如下（假設li,n為站點i到組團n的路徑）：

Step1：隨機選取兩條路徑li,n、lj,m，假設路徑li,n的供應量小于lj,m；

Step1：用路徑li,m替換li.n，令兩條路徑的供應量相等；

Step1：增加一條路徑lj,n，在只改變站點j供應量的條件下使所有組團的需求得到滿足。

4 實驗

以2017年南寧市中心城區的攪拌站選址為例進行模擬實驗。實驗數據包括8個組團，23個已有組團以及20個候選組團。參數設置如表1所示。

把基于DE算法的混合算法應用于南寧市城區混凝土攪拌站的選址問題，由于DE算法帶有隨機性，因此不能保證每次結果的一致性，但從結果看，該算法基本能控制在2.90e+5（米·萬立方米/年）以內，顯示了算法良好的穩定性。

表2給出了本文算法與GA算法、文化基因算法的性能對比，實驗環境為獨立運行30次。從表2可以看出，本文算法無論是最好結果或平均結果都要優于經典的GA和文化基因算法。

5 結論與展望

本文對混凝土攪拌站的選址問題嘗試以新的思路來研究，在傳統的差分進化算法基礎上增加了局部搜索，提出了一種改進的差分進化算法。實驗結果表明，該算法能穩定、有效地解決混凝土攪拌站的選址問題。

注[1]為了保障需求，供應能力與需求量的比例按1.4計算，則1400×1.4=1960萬立方米/年。