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

陶燁

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

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

中圖分類(lèi)號(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ò)分析空車(chē)調(diào)度和人員調(diào)度的聯(lián)合調(diào)度，總結(jié)出在聯(lián)合調(diào)度情況下，同樣數(shù)目的訂單，空車(chē)調(diào)度和人員調(diào)度的數(shù)量盡可能少，從而達(dá)到成本最低及高效的資源利用率[1]。

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

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

3.1 目標(biāo)1

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

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

s.t.

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

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

3.2 目標(biāo)2

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

引入邏輯變量

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

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

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

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

（8）

s.t.：

（9）

（10）

（11）

（12）

（13）

式（9）表示存在車(chē)輛調(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è)車(chē)輛數(shù)0≤k≤2，因此在自適應(yīng)遺傳算法中默認(rèn)調(diào)度1輛車(chē)，車(chē)場(chǎng)順序按照經(jīng)度的升序排列。矩陣中列為每個(gè)停車(chē)場(chǎng)，行為每個(gè)停車(chē)場(chǎng)對(duì)應(yīng)的時(shí)間對(duì)應(yīng)的調(diào)度方案。

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

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

5? 實(shí)例分析

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

6? 結(jié)論

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

參考文獻(xiàn)：

[1]唐婕，曹瑾鑫.共享汽車(chē)聯(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]劉彬彬.共享汽車(chē)租賃點(diǎn)運(yùn)營(yíng)特性分析與車(chē)輛調(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.