雙目標共享汽車調度優化

陶燁

摘要：本文針對汽車調度的問題，通過分析空車調度和人員調度的聯合調度，制定一個有利的調度方案，為了降低成本，總結出在聯合調度情況下，同樣數目的訂單，空車調度和人員調度的數量盡可能少，從而達到成本最低及高效的資源利用率;最后通過設計自適應遺傳算法編碼對雙層規劃模型進行求解，從而得到調度策略以及成本最低時所需的車輛和員工總數。

關鍵詞：共享汽車;python;設計自適應遺傳算法;雙層規劃

中圖分類號：U491.1+7? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1674-957X（2021）15-0152-02

1? 調度問題分析

為了制定一個有利的調度方案，本小組著重考慮調度的成本，通過分析空車調度和人員調度的聯合調度，總結出在聯合調度情況下，同樣數目的訂單，空車調度和人員調度的數量盡可能少，從而達到成本最低及高效的資源利用率[1]。

2? 符號的說明

3? 雙目標規劃模型的建立

3.1 目標1

設M為共享汽車租賃點總數。

Z=max （min （cij））（1）

s.t.

i∈（1，2，3，…M）? ? （2）

cij為i租賃點j時刻的停車數

3.2 目標2

目標2為車輛和人員的聯合調度，當b地需要用車時，需要從a地調車，這是一次空車調度。當完成一次空車調度后，工作人員需要去c地調車前往d地，這是一次人員調度。我們以此為基礎建立了以總成本最小的目標函數[2]。

引入邏輯變量

目標函數的確立

目標函數為最小化系統成本，C為車輛調度成本，可表示為：

P為人員調度成本，可表示為：

式（4）表示系統的所有訂單需求都得到滿足，且只滿足一次;式（5）表示Xab的流量守恒;式（5）表示兩個訂單之間的差價時間應大于車輛調度時間;式（6）表示對車輛總體尺寸的約束;等式（7）指示決策變量Xab是0-1變量。

（8）

s.t.：

（9）

（10）

（11）

（12）

（13）

式（9）表示存在車輛調度，當 Xab=1 而 T （ Za，Ob）=0時無需進行人員調度， 為一個無窮大的數;式（10）和式（11）表示只有 Xab、Xcd二者同時為 1 時，yab，cd的值才取1;式（12）表示人員調度時間滿足時間約束;式（13）為人員數目約束;式（13）表示決策變量 yab，cd，為 0-1 變量。

4? 自適應遺傳算法設計

4.1 本文設計的編碼

如下：

假設車輛數0≤k≤2，因此在自適應遺傳算法中默認調度1輛車，車場順序按照經度的升序排列。矩陣中列為每個停車場，行為每個停車場對應的時間對應的調度方案。

4.2 自適應遺傳算法

傳統的遺傳算法交叉率和變異率是不變的，這是不合理的。在迭代后期我們應該減小變異率和交叉率[3]。表達式如下：

5? 實例分析

共享汽車的固定成本100-200元/天，本文設定共享車的固定成本CV為150元/天。根據國家披露的數據，2018年全國城鎮非私營單位就業人員年平均工資為82461元[5]，調度員平均工資CP設為220元/天。表2為優化結果。

從表2可以看出，汽車共享的順序每天都在變化本文所采用的仿真模型和算法可以用來解決單個需求最優解或近最優解的求解時間是相對穩定的。觀察結果表明，更多的站點和更多的訂單并不一定意味著更多的車輛和人員數量的絕對增長。（表3）

6? 結論

本文通過處理數據，建立共享汽車調度優化模型，綜合考慮訂單需求、車輛調度與人員調度三個方面，通過設計自適應遺傳算法，得出總成本最低時所需車輛數和人員總數及聯合調度路徑。分析求解一個月的訂單數據，并通過具體的算例，進一步驗證了模型與算法的可行性及有 效性。同時，對比不同方案下所需的調度人員數與所需車輛數，驗證了本文方案的優越性。

參考文獻：

[1]唐婕，曹瑾鑫.共享汽車聯合調度優化研究[J/OL].系統仿真學報：1-10[2021-05-25].https：//doi.org/10.16182/j.issn1004731x.joss.20-0236.

[2]劉彬彬.共享汽車租賃點運營特性分析與車輛調度研究[D].北京交通大學，2020.

[3]陳斌，劉衛國.基于SAC模型的改進遺傳算法求解TSP問題[J/OL].計算機科學與探索：1-21[2021-05-25].http：//kns.cnki.net/kcms/detail/11.5602.TP.20210324.1113.008.html.