考慮共享單車再平衡的配送中心選址研究

吳家霞 （貴州大學(xué) 管理學(xué)院，貴州 貴陽550025）

0 引 言

近年來，中國經(jīng)濟(jì)的迅速增長迫切需要一種交通方式來緩解由于汽車數(shù)量增長帶來的交通壓力，共享交通應(yīng)運而生。共享單車在一定程度上起到了保護(hù)環(huán)境、節(jié)約資源的作用，減少了因為發(fā)展帶來的城市交通壓力。共享單車布局規(guī)劃研究主要解決的問題是基于需求分析得到的候選點基礎(chǔ)上，確定在哪些候選點建立設(shè)施。選址問題是一個長期戰(zhàn)略性決策，在對共享單車選址問題進(jìn)行研究時，主要由最優(yōu)化方法和仿真[1]的方法得到選址方案。最優(yōu)化方法包括單目標(biāo)規(guī)劃和雙目標(biāo)規(guī)劃兩種。單目標(biāo)規(guī)劃由最大需求覆蓋[2-3]、總成本最小[4]、最小運輸成本[2]等為目標(biāo)建立模型；雙目標(biāo)規(guī)劃則由以最大化收益—最小化旅行時間[5]、最小化成本—最大化安全[6]等為目標(biāo)建立模型。本文基于物流中心三層選址—路徑問題（LRP） 建立模型，在滿足車載限制、最大行駛距離限制以及車輛數(shù)量平衡等條件下，建立以包括設(shè)施建立費用和運輸費用的總費用最小的優(yōu)化模型，LRP 問題屬于NP-hard 問題，故而選擇遺傳算法對其求解，并通過案例證明算法的正確性和有效性。

1 模型建立

1.1 問題描述

本研究主要研究問題描述如下：某共享單車公司在某區(qū)域內(nèi)已經(jīng)建立好N個共享單車停放點，且各停放點地理位置已知，該公司內(nèi)現(xiàn)有輛送貨車，貨車按照其載重和耗油量分為三種不同的類型，分別是大型貨車（K1）、中型貨車（K2）、小型貨車（K3），其中K=K1∪K2∪K3，三種車型的載重分別是Q1、Q2、Q3，固定運輸成本分別是g1、g2、g3?，F(xiàn)該公司通過其他途徑在該區(qū)域內(nèi)選擇個點作為共享單車配送中心候選點，則該共享單車所有點的集合S=N∪R，并且該系統(tǒng)中任意兩點之間的運輸成本為cij，同時該系統(tǒng)中共享單車停放點的需求di為隨機(jī)變量且服從正態(tài)分布，其中：di＞0 表示單車需從停放點取出放置到送貨車中，di＜0 表示單車需從送貨車中拿入停放點。在配送中心候選點中選出部分點建立配送中心，其建立配送中心的固定成本為fi，從已經(jīng)建立的配送中心出發(fā)，選擇所需配送服務(wù)的停放點以及配送路徑，最后回到配送中心，形成閉環(huán)環(huán)路，在此過程中要求車輛在運輸過程中不會超過其最大載重Qkt以及最大行駛距離D。此次研究基于上述已知條件和流程，選擇位置最優(yōu)的配送中心和再平衡車輛路徑實現(xiàn)總成本（包括建設(shè)成本和運輸成本） 最低的目標(biāo)。

1.2 變量設(shè)置

參數(shù)：

R為配送中心候選點的集合；

N為各停放點的集合；

S=R∪N為所有點的集合；

K為所有車輛的集合；

mk為車型為k的可用車輛的集合；

cij為i，j兩點之間對應(yīng)的運輸成本；

fi為各配送中心建立的固定成本；

di為停放點i的需求，其中n-1 的停放點需求獨立同分布，第n個停放點的需求不獨立同分布，其中d1+d2+…+dn=0；

gk為車型為k k∈（K）的送貨車從配送中心出發(fā)再回到配送中心這一過程發(fā)生的固定費用；

Qkt為車型為k（k∈K）的第t（t∈mk）輛送貨車自身的最大載重量；

dij為共享單車系統(tǒng)內(nèi)點i到點j之間的距離；

D為每輛車的最大行駛距離。

決策變量：

yi為在配送中心候選點i建立設(shè)施yi=1，否則為0，其中i∈R；

xijkt為使用車型為k的第t輛送貨車從點i行駛到點j，則xijkt=1，否則為0，其中i∈S，j∈S，k∈K，t∈mk；

zij為在再平衡過程中，當(dāng)停放點j由配送中心i提供服務(wù)時，zij=1，否則為0，其中i∈R，j∈N；

為車型為k的第t（t∈mk）輛送貨車在離開點時的載貨量，其中，當(dāng)i為設(shè)施備選點時當(dāng)i為客戶點時，xijkt=1時，存在

1.3 選址路徑模型

根據(jù)上述問題，建立選址路徑模型如下：

在上述模型中，式（1） 表示目標(biāo)函數(shù)是總成本最小?？偝杀景ㄅ渌椭行牡慕ㄔO(shè)成本、再平衡過程的運輸成本以及車輛使用的固定成本；約束式（2） 保證每個停放點都有車輛提供服務(wù)；約束式（3） 每條路徑上的車輛在服務(wù)了任意一點后的車輛載重必須在車輛額定載重范圍內(nèi)；約束式（4） 對任一停放點，貨車進(jìn)入和出去車輛平衡；約束式（5） 表示每條路線只能從一個配送中心出發(fā)；約束式（6） 表示停放點只能由選中的配送中心提供服務(wù)；約束式（7） 是子路徑消除約束；約束式（8） 表示xijk與yi之間的邏輯關(guān)系；約束式（9） 表示每輛車在行駛過程中不應(yīng)該超過最大行駛距離；約束式（10） 至式（12） 則是變量約束。

2 模型有效性驗證

現(xiàn)有共享單車配送中心候選點1、2、3，以及5 個共享單車停放點4、5、6、7、8，則S= ｛1、2、3、4、5、6、7、8 ｝，各點之間的直線距離及各停放點的需求di如表1。

表1 各節(jié)點之間的直線距離以及停放點需求

現(xiàn)有兩種送貨車車型k1和k2，車型為k1的車輛載重為8 個單位，出行的固定成本為8 元，車型為k2的車輛載重為10 個單位，出行的固定成本為10 元，每輛車的最大行駛距離是20km。3 個共享單車配送中心候選點建立的固定成本相同，皆為f=300 元，車輛單位運輸成本為1.5 元/km，根據(jù)相關(guān)數(shù)據(jù)計算出共享單車系統(tǒng)內(nèi)所有點之間的運輸成本，并驗證模型的有效性，證明了該模型的可行域不是空集，即構(gòu)造一個可行解，證明該解滿足模型的約束條件，則證明該模型為有效。根據(jù)上述數(shù)據(jù)，構(gòu)造一個可行解如下：

（1） 在候選點1 處建立配送中心，2、3 處不建立配送中心，即y1=1，y2=0，y3=0；

（2） 由配送中心出發(fā)的車輛路徑為：k1: 1→6→7→1，k2：1→4→8→5→1。經(jīng)計算上述給出的選址—路徑方案是本文模型的一個可行解，故而本文模型有效。

3 遺傳算法

3.1 染色體編碼

在本次研究中，將采用特定的編碼方式，實現(xiàn)對車輛載重限制等約束條件的控制，每一條染色體將代表所研究問題的一組可行解。

在本文中，每一條染色體由三部分組成。第一個字串有n個基因位，由n個1 到k的隨機(jī)自然數(shù)組成，其中n是需要提供服務(wù)的停放點數(shù)量，k表示可供選擇的最大車輛數(shù)。第二個字串有n個基因位，是由1 到n的自然數(shù)隨機(jī)重排列生成，字串二和字串一是一一對應(yīng)關(guān)系，代表了每條路徑中車輛向停放點提供服務(wù)的先后順序。第三個字串有k個基因位，是由k個1 到r的隨機(jī)自然數(shù)組成，r表示配送中心候選點的數(shù)量，該字串與字串一、字串二相對應(yīng)，該字串控制了由字串一和字串二形成的車輛路徑屬于哪一個配送中心候選點，若配送中心候選點與形成的路徑相對應(yīng)，則意味著建立設(shè)施。由此可知，本文中染色體長度為n+n+k。

3.2 初始種群和適應(yīng)度函數(shù)

根據(jù)文章中提出的編碼方式，將染色體分為三個字串來分別生成：在本文中，一個染色體的總的長度為n+n+k，其中n為停放點的數(shù)量，k為所能提供最大的車輛數(shù)。一個染色體分為三個字串，第一個字串有n個基因位，其中每個基因位都由1 到k的自然數(shù)中隨機(jī)選取一個生成；第二個字串有n個基因位，這n個基因位都是由1 到n之間的自然數(shù)隨機(jī)全排列生成，該字串沒有重復(fù)的數(shù)值；第三個字串有k個基因位，其中每個基因位是由1 到r的自然數(shù)中隨機(jī)抽取一個一個生成。

在求解目標(biāo)函數(shù)的過程中，對于本文的模型，除了約束條件式（3） 之外的約束都通過編碼的方式解決，但約束式（3） 屬于車載容量約束，是必須滿足的，故而對該約束條件，將不滿足約束條件的那個染色體在計算其目標(biāo)值函數(shù)時加上一個極大值，用以減小其適應(yīng)度函數(shù)值。

由于本文中的目標(biāo)函數(shù)值是求最小值，故而將目標(biāo)函數(shù)值的倒數(shù)作為該染色體的適應(yīng)度函數(shù)。

3.3 選擇算子

本次研究一共采用了兩種選擇算子，輪盤法和精英法。在遺傳算法過程中，選擇部分主要是輪盤法，在每一個種群里，按照每一條染色體的適應(yīng)度函數(shù)來分配輪盤面積，每條染色體在整個輪盤所占面積的比率代表被選中的比率，然后隨機(jī)產(chǎn)生，根據(jù)其在輪盤上屬于哪一條染色體則將該區(qū)域?qū)?yīng)染色體復(fù)制給下一代，這樣產(chǎn)生的種群里，存在有適應(yīng)度較差的染色體，也存在相同的染色體。在交叉和變異過程皆采用了精英法，將通過交叉或者變異形成的種群和上一代種群放于同一個矩陣，對每條染色體的適應(yīng)度函數(shù)排序，將染色體適應(yīng)度較大的一半作為交叉或者變異的子代種群。

3.4 交叉算子

遺傳算法中的交叉過程是通過交叉概率進(jìn)行基因的重組，形成新個體。染色體的交叉是將兩條父代染色體，隨機(jī)生成一個或者多個交叉點，將兩條父代染色體基因互換，形成新的一對染色體。本文中為了不使染色體出現(xiàn)亂碼的情況，將每條染色體分為三個部分，第一個字串是第1 到第n位，使用單點交叉法進(jìn)行交叉；第二個字串是第n+1 位到第n+n位，由于是n個不能重復(fù)的實數(shù)，根據(jù)這個特點選則順序交叉法進(jìn)行交叉；第三個字串是第n+n+1 到第n+n+k位，使用單點交叉法進(jìn)行交叉。

3.5 變異算子

遺傳算法中的變異過程的目的是為了防止求解過程陷入局部最優(yōu)，故而設(shè)置變異概率，隨機(jī)生成的概率值低于變異概率，就可以通過變異尋找新的搜尋區(qū)。同樣，根據(jù)本文染色體的特點將染色體分為三個字串，由于本文的染色體基因位的數(shù)皆是大于零的自然數(shù)，且第二字串不能出現(xiàn)重復(fù)數(shù)值，故而三個字串皆用倒置的方法對其進(jìn)行變異，過程如下：程序隨機(jī)生成兩個小于每一個字串長度的自然數(shù)，即對應(yīng)基因位置，然后將兩個位置之間的數(shù)值進(jìn)行倒置，形成新的染色體，這個過程的變異概率需要多次的實驗確定。

3.6 結(jié)束條件

遺傳算法的求解過程是從初始種群出發(fā)，在可行域內(nèi)一步一步搜索更好的解的過程，在程序語言中則是通過迭代來完成尋優(yōu)過程。迭代過程結(jié)束一般可以通過設(shè)置迭代次數(shù)、迭代時間或者適應(yīng)度函數(shù)值或者目標(biāo)函數(shù)值無法進(jìn)行下一次迭代這三種情況，本文研究選擇迭代T次，結(jié)束迭代過程，然后取出最優(yōu)目標(biāo)函數(shù)值和最優(yōu)染色體。

4 算例計算

（1） 基礎(chǔ)數(shù)據(jù)

某共享單車企業(yè)現(xiàn)已建共享單車停放點20 個（編碼1-20） 以及調(diào)查得出配送中心候選點3 個（編碼21-23），建立設(shè)施的固定費用分別為127、158、142，根據(jù)武漢市公布的共享單車出行報告，90%的騎行都在15km/h，83%的騎行都在20 分鐘以內(nèi)，故而共享單車兩個點之間的距離取1～5 公里之間的隨機(jī)值，兩個點之間的運輸費用取2 元/km。公司現(xiàn)有5 輛同車型的送貨車，每輛車最大載重150 輛該公司的單車，單輛車出行一次的固定費用為50 元，每輛車的最大行駛距離為20km。

（2） 模型求解

本次研究模型求解是使用Matlab 語言對遺傳算法進(jìn)行編碼，各參數(shù)設(shè)置如下：交叉概率為0.8，變異概率設(shè)置為0.005，極大值M設(shè)置為100 000，染色體種群設(shè)置為300，染色體長度為45，迭代次數(shù)為1 000 次。最終計算出目標(biāo)函數(shù)值為419.71 元。相對應(yīng)的選址—路徑方案為：在設(shè)施點21 處建立設(shè)施；車輛1 的行駛路徑為：21-16-12-5-7-10-4-15-6-21；車輛2 的行駛路徑為：21-1-8-20-17-19-14-21；車輛3 的行駛路徑為：21-13-2-11-18-3-21；車輛4 的行駛路徑為：21-9-21。目標(biāo)函數(shù)值與迭代次數(shù)的關(guān)系如圖1 所示。

圖1 目標(biāo)函數(shù)值與迭代次數(shù)的關(guān)系

5 結(jié) 論

本文提出將共享單車再平衡過程納入考慮，建立共享單車配送中心選址模型。模型中將車輛載重、車輛最大行駛距離以及車輛數(shù)量平衡等作為約束條件，以總成本最小建立模型。然后采用遺傳算法對模型進(jìn)行求解，根據(jù)模型的特點選擇相適應(yīng)的編碼方式、交叉算子以及變異算子。當(dāng)前無論國內(nèi)外研究，共享單車系統(tǒng)選址的研究大都做的是停放點選址或者停放點選址+再平衡。受物流中心選址中三層LRP 問題啟發(fā)，配送中心是停放點的上一層級，研究配送中心選址可以為以后研究配送中心選址+停放點選址+再平衡研究提供理論基礎(chǔ)。同時，當(dāng)前共享單車配送中心的選址研究缺乏研究成果，更需要深入研究，加深理論基礎(chǔ)。