雙目標(biāo)共享汽車調(diào)度優(yōu)化

陶燁

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

關(guān)鍵詞：共享汽車;python;設(shè)計(jì)自適應(yīng)遺傳算法;雙層規(guī)劃

中圖分類號(hào)：U491.1+7? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1674-957X（2021）15-0152-02

1? 調(diào)度問(wèn)題分析

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

2? 符號(hào)的說(shuō)明

3? 雙目標(biāo)規(guī)劃模型的建立

3.1 目標(biāo)1

設(shè)M為共享汽車租賃點(diǎn)總數(shù)。

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

s.t.

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

cij為i租賃點(diǎn)j時(shí)刻的停車數(shù)

3.2 目標(biāo)2

目標(biāo)2為車輛和人員的聯(lián)合調(diào)度，當(dāng)b地需要用車時(shí)，需要從a地調(diào)車，這是一次空車調(diào)度。當(dāng)完成一次空車調(diào)度后，工作人員需要去c地調(diào)車前往d地，這是一次人員調(diào)度。我們以此為基礎(chǔ)建立了以總成本最小的目標(biāo)函數(shù)[2]。

引入邏輯變量

目標(biāo)函數(shù)的確立

目標(biāo)函數(shù)為最小化系統(tǒng)成本，C為車輛調(diào)度成本，可表示為：

P為人員調(diào)度成本，可表示為：

式（4）表示系統(tǒng)的所有訂單需求都得到滿足，且只滿足一次;式（5）表示Xab的流量守恒;式（5）表示兩個(gè)訂單之間的差價(jià)時(shí)間應(yīng)大于車輛調(diào)度時(shí)間;式（6）表示對(duì)車輛總體尺寸的約束;等式（7）指示決策變量Xab是0-1變量。

（8）

s.t.：

（9）

（10）

（11）

（12）

（13）

式（9）表示存在車輛調(diào)度，當(dāng) Xab=1 而 T （ Za，Ob）=0時(shí)無(wú)需進(jìn)行人員調(diào)度， 為一個(gè)無(wú)窮大的數(shù);式（10）和式（11）表示只有 Xab、Xcd二者同時(shí)為 1 時(shí)，yab，cd的值才取1;式（12）表示人員調(diào)度時(shí)間滿足時(shí)間約束;式（13）為人員數(shù)目約束;式（13）表示決策變量 yab，cd，為 0-1 變量。

4? 自適應(yīng)遺傳算法設(shè)計(jì)

4.1 本文設(shè)計(jì)的編碼

如下：

假設(shè)車輛數(shù)0≤k≤2，因此在自適應(yīng)遺傳算法中默認(rèn)調(diào)度1輛車，車場(chǎng)順序按照經(jīng)度的升序排列。矩陣中列為每個(gè)停車場(chǎng)，行為每個(gè)停車場(chǎng)對(duì)應(yīng)的時(shí)間對(duì)應(yīng)的調(diào)度方案。

4.2 自適應(yīng)遺傳算法

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

5? 實(shí)例分析

共享汽車的固定成本100-200元/天，本文設(shè)定共享車的固定成本CV為150元/天。根據(jù)國(guó)家披露的數(shù)據(jù)，2018年全國(guó)城鎮(zhèn)非私營(yíng)單位就業(yè)人員年平均工資為82461元[5]，調(diào)度員平均工資CP設(shè)為220元/天。表2為優(yōu)化結(jié)果。

從表2可以看出，汽車共享的順序每天都在變化本文所采用的仿真模型和算法可以用來(lái)解決單個(gè)需求最優(yōu)解或近最優(yōu)解的求解時(shí)間是相對(duì)穩(wěn)定的。觀察結(jié)果表明，更多的站點(diǎn)和更多的訂單并不一定意味著更多的車輛和人員數(shù)量的絕對(duì)增長(zhǎng)。（表3）

6? 結(jié)論

本文通過(guò)處理數(shù)據(jù)，建立共享汽車調(diào)度優(yōu)化模型，綜合考慮訂單需求、車輛調(diào)度與人員調(diào)度三個(gè)方面，通過(guò)設(shè)計(jì)自適應(yīng)遺傳算法，得出總成本最低時(shí)所需車輛數(shù)和人員總數(shù)及聯(lián)合調(diào)度路徑。分析求解一個(gè)月的訂單數(shù)據(jù)，并通過(guò)具體的算例，進(jìn)一步驗(yàn)證了模型與算法的可行性及有 效性。同時(shí)，對(duì)比不同方案下所需的調(diào)度人員數(shù)與所需車輛數(shù)，驗(yàn)證了本文方案的優(yōu)越性。

參考文獻(xiàn)：

[1]唐婕，曹瑾鑫.共享汽車聯(lián)合調(diào)度優(yōu)化研究[J/OL].系統(tǒng)仿真學(xué)報(bào)：1-10[2021-05-25].https：//doi.org/10.16182/j.issn1004731x.joss.20-0236.

[2]劉彬彬.共享汽車租賃點(diǎn)運(yùn)營(yíng)特性分析與車輛調(diào)度研究[D].北京交通大學(xué)，2020.

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