考慮故障車(chē)回收的共享單車(chē)靜態(tài)重平衡問(wèn)題

丁飛陽(yáng)，張 思

（上海大學(xué) 管理學(xué)院，上海 200444）

0 引言

共享單車(chē)給人民帶來(lái)便利的同時(shí)，其快速發(fā)展也帶來(lái)了一系列問(wèn)題。在一些城市，共享單車(chē)被隨處停放，導(dǎo)致有些區(qū)域形成交通擁堵，有些區(qū)域又一車(chē)難求，造成了供需不平衡的局面。此外，由于共享單車(chē)長(zhǎng)時(shí)間接受風(fēng)吹日曬，其故障率也遠(yuǎn)遠(yuǎn)高于普通自行車(chē)，影響用戶體驗(yàn)。

共享單車(chē)系統(tǒng)的平穩(wěn)運(yùn)行通常需要滿足用戶波動(dòng)出行需求的能力。為了保證系統(tǒng)可靠性和提高用戶的滿意度，運(yùn)營(yíng)商需要對(duì)共享單車(chē)系統(tǒng)進(jìn)行重平衡。重平衡問(wèn)題旨在研究如何調(diào)度各個(gè)站點(diǎn)間不平衡的共享單車(chē)數(shù)量，以更好地滿足客戶需求。其調(diào)度通常有兩種策略，一是客戶激勵(lì)：運(yùn)營(yíng)商根據(jù)系統(tǒng)的當(dāng)前和預(yù)測(cè)狀態(tài)，計(jì)算出停放共享單車(chē)在各個(gè)站點(diǎn)的獎(jiǎng)勵(lì)，并提供給顧客，具體可參考文獻(xiàn)[1]、[2]。二是運(yùn)營(yíng)商利用卡車(chē)將自行車(chē)從過(guò)剩（供應(yīng)）站運(yùn)到不足（需求）站，以實(shí)現(xiàn)理想的平衡?；谶\(yùn)營(yíng)商的重新平衡有兩種類(lèi)型：靜態(tài)重平衡和動(dòng)態(tài)重平衡。

靜態(tài)重平衡側(cè)重于在夜間進(jìn)行平衡過(guò)程，此時(shí)用戶使用和道路擁堵情況可以忽略不計(jì)，主要包含靜態(tài)完全重平衡問(wèn)題（SCRP）和靜態(tài)部分重平衡問(wèn)題（SPRP）。對(duì)于SCRP，Dell'Amico，等[3]首次完整定義了共享單車(chē)靜態(tài)重平衡問(wèn)題；為了求解該問(wèn)題，F(xiàn)orma，等[4]提出了一種三步啟發(fā)式算法。Erdogan，等[5]提出了帶需求區(qū)間的共享單車(chē)重平衡，將其視為1-PDTSP的變種。劉喜梅，等[6]和呂暢，等[7]分別用改進(jìn)啟發(fā)式算法進(jìn)行求解。Pal和Zhang[8]提出了一種混合嵌套的大鄰域搜索與可變鄰域下降算法，在大規(guī)模問(wèn)題上表現(xiàn)高效。秦冰芳[9]以最小化總成本和車(chē)輛工作時(shí)間為目標(biāo)建立了分批配送車(chē)輛路徑模型。陳植元，等[10]根據(jù)共享單車(chē)的時(shí)空分布將具有相似時(shí)空屬性的站點(diǎn)進(jìn)行聚類(lèi)，將問(wèn)題轉(zhuǎn)化為帶時(shí)間窗和容量約束的VRP問(wèn)題。對(duì)于SPRP，Ravia，等[11]首次提出了多調(diào)度車(chē)輛問(wèn)題。Ho和Szeto[12]提出一種迭代的禁忌搜索算法來(lái)求解。Li，等[13]考慮了多種單車(chē)類(lèi)型的重平衡問(wèn)題。Mohammadi，等[14]設(shè)計(jì)了一個(gè)基于旅行商的多目標(biāo)、多商品、多時(shí)期的數(shù)學(xué)模型，對(duì)其小規(guī)模問(wèn)題進(jìn)行精確求解。Szeto和Shui[15]引入了總需求不滿意（TDD）的概念，目標(biāo)函數(shù)首先最小化系統(tǒng)總需求不滿度的正偏差，然后使車(chē)輛的總服務(wù)時(shí)間最小。于德新，等[16]以最小化總成本和最大化投放率（投放與需求的比值）為目標(biāo),其創(chuàng)新點(diǎn)在于采用TOPSIS法在遺傳算法求解出的有效路線中選擇最優(yōu)路線。汪慎文，等[17]設(shè)計(jì)了一種離散差分進(jìn)化算法來(lái)求解該問(wèn)題。許媛媛[18]構(gòu)建了多目標(biāo)混合整數(shù)規(guī)劃模型，采用混合遺傳算法和變鄰域搜索算法的粒子群算法進(jìn)行求解。

動(dòng)態(tài)重平衡則與白天操作的平衡有關(guān)，此時(shí)系統(tǒng)處于高使用率，車(chē)站的需求會(huì)在重平衡期間發(fā)生變化。Kloimullner，等[19]將每個(gè)累積的需求函數(shù)分割成弱單調(diào)片段，用四種啟發(fā)式方法對(duì)實(shí)例進(jìn)行了測(cè)試。馮麟博[20]提出了一種BP神經(jīng)網(wǎng)絡(luò)算法對(duì)共享單車(chē)需求進(jìn)行預(yù)測(cè)，引入虛擬調(diào)度中心的概念，從而將動(dòng)態(tài)問(wèn)題轉(zhuǎn)化為靜態(tài)問(wèn)題。張徐[21]提出了改進(jìn)的隨機(jī)森林預(yù)測(cè)方法對(duì)需求進(jìn)行預(yù)測(cè)，之后利用K-means對(duì)區(qū)域進(jìn)行劃分，將問(wèn)題從全局最優(yōu)轉(zhuǎn)化為局部最優(yōu)，采用改進(jìn)蟻群算法求解。但是人們出行充滿不確定性，因此多數(shù)動(dòng)態(tài)問(wèn)題轉(zhuǎn)化為靜態(tài)問(wèn)題時(shí)對(duì)需求的預(yù)測(cè)也會(huì)存在一定偏差。此外在需求高位波動(dòng)的白天，運(yùn)營(yíng)商調(diào)度成本更高的同時(shí)還易受到交通擁堵等外界影響。因此本文選擇靜態(tài)重平衡為研究對(duì)象。

以上研究只考慮到了對(duì)好車(chē)的重平衡，未考慮到對(duì)故障車(chē)的回收。近年來(lái)，逐步有學(xué)者開(kāi)始考慮到故障車(chē)的回收。徐國(guó)勛，等[22]在調(diào)度中考慮了損壞自行車(chē)的回收，設(shè)計(jì)了混合禁忌搜索算法求解。Wang 和Szeto[23-24]首次提出了考慮CO2排放的帶故障車(chē)回收的重平衡問(wèn)題，采用增強(qiáng)型人工蜂群算法求解該綠色BRP問(wèn)題。Du，等[25]研究了多中心、多車(chē)型、允許多次訪問(wèn)的帶故障車(chē)回收的重平衡問(wèn)題，其結(jié)果量化了帶故障車(chē)回收的綜合重平衡相比于單獨(dú)重平衡的好處。王涵霄，等[26]首次提出了小故障單車(chē)當(dāng)場(chǎng)維修、大故障單車(chē)回收、好單車(chē)調(diào)度的概念，其采用蟻群算法來(lái)求解。

現(xiàn)階段的研究多為考慮故障車(chē)回收的靜態(tài)完全重平衡問(wèn)題，由多車(chē)輛進(jìn)行工作，這勢(shì)必會(huì)增加車(chē)輛運(yùn)行的固定成本。本文的研究考慮故障車(chē)回收的共享單車(chē)靜態(tài)部分重平衡問(wèn)題，由單車(chē)輛進(jìn)行多車(chē)次工作，將全部故障單車(chē)進(jìn)行回收，下一次作業(yè)車(chē)輛上的初始單車(chē)數(shù)受到上一次作業(yè)最終狀態(tài)的影響。為此，提出了一種改進(jìn)遺傳算法，引入了精英個(gè)體爬山、自適應(yīng)交叉、變異等操作來(lái)求解該問(wèn)題。

1 模型建立

在共享單車(chē)系統(tǒng)中一個(gè)調(diào)度中心通常服務(wù)多個(gè)站點(diǎn)，多車(chē)次具有相同容量的調(diào)度車(chē)從調(diào)度中心出發(fā)，在供應(yīng)站提取正常的單車(chē)，并將它們送到需求站。同時(shí)每個(gè)站點(diǎn)的故障單車(chē)會(huì)被裝載到調(diào)度車(chē)上。當(dāng)調(diào)度車(chē)的容量已滿或調(diào)度車(chē)的容量不足以服務(wù)下個(gè)站點(diǎn)時(shí)，返回調(diào)度中心進(jìn)行卸貨。直到所有站點(diǎn)均被服務(wù)一次后任務(wù)結(jié)束。一個(gè)典型示例如圖1所示，包含一個(gè)調(diào)度中心和七個(gè)站點(diǎn)，車(chē)輛的容量為10。調(diào)度車(chē)返回調(diào)度中心，所有故障單車(chē)均被卸下，再次出發(fā)時(shí)允許調(diào)度車(chē)上存在不超過(guò)確定數(shù)量的好單車(chē)。

圖1 共享單車(chē)調(diào)度和回收故障車(chē)輛示意圖

本模型提出如下假設(shè)：

（1）站點(diǎn)調(diào)度與回收故障車(chē)工作發(fā)生于深夜，此時(shí)不考慮站點(diǎn)單車(chē)數(shù)量的變動(dòng)，為靜態(tài)重平衡；

（2）只存在一個(gè)調(diào)度中心，調(diào)度車(chē)輛從該處出發(fā)，最后需返回該處；

（3）每個(gè)站點(diǎn)好車(chē)和壞車(chē)的數(shù)量已知；

（4）調(diào)度車(chē)輛的行駛成本只與距離成線性相關(guān)，不考慮其他因素；

（5）調(diào)度車(chē)第一次從調(diào)度中心出發(fā)時(shí)為空車(chē)，第二次及之后從調(diào)度中心出發(fā)時(shí)允許調(diào)度車(chē)上存在不多于一定數(shù)量的好單車(chē)；

（6）站點(diǎn)所存在的多余好車(chē)、壞車(chē)需全部被回收，但允許站點(diǎn)的好車(chē)需求數(shù)不被滿足。

在有向圖G=(V,A)上，其中V= {0,1,2,...,n} 表示所有節(jié)點(diǎn)的集合，0表示調(diào)度中心，0,1,2,...,n表示調(diào)度點(diǎn)，A表示弧的集合，A={(i,j):i,j ∈V,i ≠j} 。表示調(diào)度點(diǎn)的集合。

變量符號(hào)及其含義見(jiàn)表1。

表1 變量符號(hào)及含義

模型建立如下：

目標(biāo)函數(shù)（1）表示最小化總成本，包括調(diào)度車(chē)輛的行駛成本，偏離好車(chē)需求期望的懲罰成本。約束條件（2）表示各個(gè)調(diào)度點(diǎn)的好車(chē)轉(zhuǎn)移方程，好車(chē)有裝有卸。約束條件（3）表示各個(gè)調(diào)度點(diǎn)的好車(chē)需先滿足自身期望后，多余的好車(chē)才可裝到調(diào)度車(chē)上。約束條件（4）表示各個(gè)調(diào)度點(diǎn)裝到調(diào)度車(chē)上的壞車(chē)數(shù)需等于該站點(diǎn)初始?jí)能?chē)數(shù)。約束條件（5）（6）表示服務(wù)點(diǎn)i 前后，調(diào)度車(chē)上所擁有的好車(chē)數(shù)和壞車(chē)數(shù)較剛到達(dá)站點(diǎn)i時(shí)的數(shù)量變化情況，其數(shù)值等于在站點(diǎn)i的裝卸量。約束條件（7）表示調(diào)度車(chē)到達(dá)與離開(kāi)的是同一個(gè)站點(diǎn)，確保流守恒。約束條件（8）（9）表示調(diào)度車(chē)從調(diào)度中心出發(fā)時(shí)，第一次為空車(chē)，第二次車(chē)上允許存在一定數(shù)量好車(chē)。約束條件（10）表示車(chē)輛的容量約束。約束條件（11）表示每個(gè)站點(diǎn)只能被一輛調(diào)度車(chē)輛服務(wù)一次。約束條件（12）（13）表示每輛調(diào)度車(chē)均從調(diào)度中心出發(fā)，工作完后都返回調(diào)度中心。約束條件（14）（15）表示調(diào)度車(chē)在站點(diǎn)i所卸載的好車(chē)數(shù)要滿足該站點(diǎn)的需求和調(diào)度車(chē)容量的較小值。約束條件（16）表示消除子回路，避免不經(jīng)過(guò)調(diào)度中心的回路出現(xiàn)。約束條件（17）-（21）分別定義了變量的定義域。

2 算法設(shè)計(jì)

遺傳算法最早由美國(guó)John Holland 教授于1975年提出,其靈感來(lái)自于自然進(jìn)化的規(guī)律。在遺傳算法中，每個(gè)染色體需要定義一個(gè)適應(yīng)度函數(shù)來(lái)進(jìn)行評(píng)價(jià)，使適應(yīng)度值好的染色體有更多的繁殖機(jī)會(huì)，從而形成下一代新種群。對(duì)這個(gè)新種群進(jìn)行下一輪進(jìn)化，如此往復(fù)直到找到滿意解。

在求解一些較為復(fù)雜的優(yōu)化問(wèn)題時(shí)，遺傳算法的計(jì)算效率高，全局搜索性強(qiáng)，能在較短時(shí)間內(nèi)求出問(wèn)題的滿意解，因此本問(wèn)題采用遺傳算法進(jìn)行求解。但經(jīng)典遺傳算法局部搜索性能較差，容易過(guò)早收斂而陷入局部最優(yōu)，因此本文在遺傳算法中引入了精英個(gè)體爬山操作、自適應(yīng)交叉和變異操作，從而提高了其魯棒性。

2.1 初始解的生成

本文采用自然數(shù)編碼方式，每一條染色體由自然數(shù)0至N（待服務(wù)站點(diǎn)數(shù)目）所組成，代表調(diào)度車(chē)輛的行駛路徑。其中0代表調(diào)度中心，其余自然數(shù)代表每個(gè)待服務(wù)的站點(diǎn)。

如其中一條染色體為：0—3—7—5—0—2—4—6—0—1—8—0 表示共出動(dòng)了三個(gè)車(chē)次，包含三條路徑。路徑1：0—3—7—5—0 路徑2：0—2—4—6—0 路徑3：0—1—8—0。

2.2 適應(yīng)度函數(shù)

上述編碼方式不能保證解碼的染色體使用不超過(guò)規(guī)定的車(chē)次數(shù)，所以提出懲罰函數(shù)來(lái)解決這一問(wèn)題。配送方案總成本的計(jì)算公式如下：

式中，X(i)為目標(biāo)函數(shù)（1）的總成本，w(i)為使用超過(guò)規(guī)定數(shù)目車(chē)次的懲罰成本。γ為違反車(chē)次數(shù)量約束的懲罰因子，di為第i條染色體使用的車(chē)次數(shù)，ni為規(guī)定的最大車(chē)次數(shù)。

2.3 選擇與爬山操作

本文采用二元錦標(biāo)賽與精英個(gè)體爬山操作相結(jié)合，具體如圖2所示。為了避免過(guò)早陷入局部最優(yōu)，本文對(duì)選擇操作后的染色體進(jìn)行去重操作，并與父代染色體相結(jié)合形成新種群。對(duì)該代染色體中適應(yīng)度函數(shù)最高的精英個(gè)體進(jìn)行爬山，采用2-opt領(lǐng)域搜索法，隨機(jī)交換染色體中兩個(gè)位置的基因，計(jì)算其適應(yīng)度，若適應(yīng)度提高，則互換基因后的個(gè)體替代原來(lái)的個(gè)體保存到下一代，跳出循環(huán)。若適應(yīng)度未增加，則最優(yōu)染色體不變。重復(fù)以上步驟，直到達(dá)到指定次數(shù)為止。

圖2 選擇操作流程圖

2.4 遺傳自適應(yīng)操作

為保證算法的高效性，設(shè)置交叉概率為：

式中，fi表示待交叉的兩個(gè)染色體中適應(yīng)度的較大值，fave表示該代種群適應(yīng)度的平均值，fmax表示該代種群中適應(yīng)度函數(shù)的最大值，Pc1表示較小的交叉概率，Pc2 表示較大的交叉概率。改進(jìn)的交叉操作如下所示。

設(shè)置變異概率為：

式中，fi表示待變異的兩個(gè)染色體中適應(yīng)度的較大值，fave表示該代種群適應(yīng)度的平均值，Pm1 表示較小的變異概率，Pm2 表示較大的變異概率。其中變異操作采用兩互換方法。

改進(jìn)遺傳算法運(yùn)行流程如圖3所示。

圖3 算法流程圖

3 算例分析

現(xiàn)有一調(diào)度中心和若干個(gè)待服務(wù)的站點(diǎn)（小規(guī)模算例R1001-R1010 表示有10 個(gè)算例，每個(gè)算例有10 個(gè)待服務(wù)的站點(diǎn)，中規(guī)模算例R2001-R2010 表示有10 個(gè)算例，每個(gè)算例有20 個(gè)待服務(wù)的站點(diǎn)，大規(guī)模算例R4001-R4010 表示有10 個(gè)算例，每個(gè)算例有40 個(gè)待服務(wù)的站點(diǎn)），其中調(diào)度車(chē)輛的容量為40，好單車(chē)不足的懲罰成本為2，車(chē)輛行駛單位距離成本為1.5，使用過(guò)多調(diào)度車(chē)時(shí)的懲罰成本為10。每個(gè)案例的好單車(chē)需求期望均設(shè)置為15，未經(jīng)服務(wù)前的好單車(chē)數(shù)設(shè)置為0到30的隨機(jī)數(shù)，壞單車(chē)數(shù)設(shè)置為0到10的隨機(jī)數(shù)。

3.1 參數(shù)設(shè)計(jì)

采用中規(guī)模R2001 算例來(lái)進(jìn)行參數(shù)設(shè)置。首先設(shè) 定NIND=200，Pc1=0.4，Pc2=0.8，Pm1=0.1，Pm2=0.3，MAXGEN=2 000。

之后依次優(yōu)化NIND、Pc1、Pc2、Pm1、Pm2。例如，當(dāng)其他參數(shù)固定時(shí)，NIND需要設(shè)置80-440來(lái)比較優(yōu)化效果，每個(gè)不同的NIND數(shù)都需進(jìn)行五次運(yùn)行來(lái)確定目標(biāo)函數(shù)的平均值，如果優(yōu)化效果最好時(shí)NIND 為200，固定此參數(shù)繼續(xù)優(yōu)化其他參數(shù)。優(yōu)化結(jié)果如圖4所示。最后優(yōu)化后的參數(shù)為NIND=400，Pc1=0.3，Pc2=0.75，Pm1=0.125，Pm2=0.3，MAXGEN=2 000。

圖4 遺傳算子參數(shù)設(shè)計(jì)

3.2 算例分析

遺傳算法相關(guān)參數(shù)見(jiàn)表2，其中小規(guī)模中可使用的車(chē)次設(shè)置為2次。

表2 遺傳算法參數(shù)設(shè)置

采用改進(jìn)遺傳算法對(duì)小規(guī)模算例進(jìn)行求解，并用gurobi求解相同問(wèn)題，從而進(jìn)行比較分析。具體求解結(jié)果見(jiàn)表3。由于在小規(guī)模案例中，遺傳算法在同一實(shí)例中經(jīng)過(guò)迭代所找出的近似最優(yōu)解都相同，因此并不需計(jì)算其平均目標(biāo)函數(shù)值。

表3 小規(guī)模算例求解結(jié)果分析（算例R1001-算例R1010）

從表3可以看出，在小規(guī)模問(wèn)題中精確算法與改進(jìn)遺傳算法相比，其目標(biāo)函數(shù)值在大部分算例中都相同，在小部分算例中有微小的差異，可驗(yàn)證所提出遺傳算法的有效性。

為進(jìn)一步驗(yàn)證本文提出遺傳算法的優(yōu)勢(shì)，對(duì)中大規(guī)模算例進(jìn)行實(shí)驗(yàn)對(duì)比。其中遺傳算法對(duì)不同算例分別進(jìn)行10 次求解。其中中規(guī)模算例可使用的車(chē)次設(shè)置為3 次，MAXGEN 設(shè)置為2 000 次；大規(guī)模算例可使用的車(chē)次設(shè)置為5 次，MAXGEN 設(shè)置為5 000次。

從表4 可知，在中規(guī)模算例中，改進(jìn)遺傳算法所得的目標(biāo)函數(shù)值總成本比gurobi 求解結(jié)果高0.80%，但是算法計(jì)算速度在大多算例中遠(yuǎn)遠(yuǎn)快于gurobi 求解。從表5 可知，在大規(guī)模算例中，改進(jìn)的遺傳算法依舊能保持較好的魯棒性，且依舊能快速得出近似最優(yōu)值，但gurobi求解在規(guī)定的2小時(shí)內(nèi)已經(jīng)無(wú)法求出解?？梢?jiàn)隨著算例規(guī)模的進(jìn)一步增大，遺傳算法在速度方面的優(yōu)勢(shì)愈發(fā)體現(xiàn)出來(lái)，可用來(lái)求解大規(guī)模問(wèn)題。

表4 中規(guī)模算例求解結(jié)果分析（算例R2001-R2020）

表5 大規(guī)模算例求解結(jié)果分析算例（R4001-R4010）

3.3 敏感度分析

在對(duì)算例進(jìn)行求解時(shí)，調(diào)度車(chē)的車(chē)次限制（NV）、調(diào)度車(chē)的最大容量（Cap）以及第二次及之后從調(diào)度中心出發(fā)時(shí)允許初始的最大好車(chē)數(shù)（G_max）都會(huì)對(duì)結(jié)果有影響。為了探究以上三種因素的變化對(duì)總目標(biāo)函數(shù)的影響，本節(jié)在中規(guī)模算例（R2001-R2010）下對(duì)其進(jìn)行靈敏度分析。在敏感度分析時(shí)，初始NV=3，Cap=40，G_max=10。對(duì)不同因素進(jìn)行分析時(shí)，十個(gè)算例分別進(jìn)行五次求解且取其中的最小值記錄，將每個(gè)算例中所記錄的最小值取平均值，作為當(dāng)前的目標(biāo)函數(shù)平均值。

3.3.1 分析NV敏感度。從表6可知，隨著NV從1到5逐漸變大，目標(biāo)函數(shù)先降低后趨于平穩(wěn)態(tài)勢(shì)（如圖5（b）所示）。

表6 調(diào)度車(chē)次限制（NV）敏感度分析

圖5 目標(biāo)函數(shù)和求解時(shí)間隨著NV變化的敏感性分析

3.3.2 分析Cap敏感度。從表7可知，隨著車(chē)輛容量Cap的增加，目標(biāo)函數(shù)值下降，其下降斜率從大到小逐漸變小（如圖6（b）所示）。

表7 車(chē)輛容量（Cap）敏感度分析

圖6 目標(biāo)函數(shù)和求解時(shí)間隨著Cap變化的敏感性分析

分析原因?yàn)椋寒?dāng)Cap小于40時(shí)，其完成任務(wù)所需要使用的調(diào)度車(chē)次大于初始的NV（值為3），因此其不僅需要更多的調(diào)度車(chē)次增加了懲罰成本，還需要多次來(lái)回調(diào)度中心增加了額外的路徑成本。因此在Cap為20-40期間，目標(biāo)函數(shù)值下降幅度較大，其下降幅度先大后小。當(dāng)Cap大于40時(shí)，目標(biāo)函數(shù)幅度下降變緩，其減少的成本在于減少來(lái)回調(diào)度中心的額外路徑成本。隨著車(chē)輛容量Cap的增加，求解時(shí)間總體呈下降趨勢(shì)（如圖6（a）所示）。原因在于隨著Cap的增大，所需要使用的車(chē)次數(shù)減少，因此算法搜索時(shí)間變少。

3.3.3 分析G_max敏感度。從表8可知，隨著車(chē)輛容量G_max的增加，目標(biāo)函數(shù)先下降后趨于平穩(wěn)，其下降幅度從大到?。ㄈ鐖D7（a）所示）。

表8 允許所帶的好車(chē)數(shù)（G_max）敏感度分析

圖7 目標(biāo)函數(shù)和求解時(shí)間隨著G_max變化的敏感性分析

分析原因?yàn)椋寒?dāng)調(diào)度車(chē)因容量限制返回調(diào)度中心，再次出發(fā)時(shí)調(diào)度車(chē)上的好車(chē)數(shù)會(huì)被初始化為G_max，若G_max過(guò)小，則會(huì)損失一些好車(chē)，從而造成好車(chē)不足懲罰成本的產(chǎn)生。隨著G_max從0逐步增大到15左右時(shí)，目標(biāo)函數(shù)都在下降，因?yàn)樵龃驡_max可以減少對(duì)路線規(guī)劃的限制從而搜索到目標(biāo)函數(shù)值更小的滿意解。隨著G_max的進(jìn)一步增加，由于其路徑滿意解中不存在需要G_max更大的路徑，因此其目標(biāo)函數(shù)值并沒(méi)有下降。隨著G_max的改變，求解時(shí)間總體呈上升趨勢(shì)（如圖7（b）所示），原因在于G_max的增大會(huì)在一定程度上增大搜索規(guī)模。

4 結(jié)語(yǔ)

本文考慮了共享單車(chē)的實(shí)際情況，包括好車(chē)的調(diào)度和壞車(chē)的回收，對(duì)于共享單車(chē)企業(yè)具有重要的現(xiàn)實(shí)意義。本文的主要工作如下：（1）在遺傳算法的基礎(chǔ)上，對(duì)其進(jìn)行了改進(jìn)，引入了爬山操作、自適應(yīng)交叉、變異等。（2）本文通過(guò)gurobi對(duì)模型進(jìn)行精確求解，并與啟發(fā)式算法求解結(jié)果進(jìn)行分析比較。通過(guò)小、中、大三個(gè)規(guī)模實(shí)驗(yàn)分析，證明本文所提出的改進(jìn)遺傳算法具有可行性和優(yōu)勢(shì)性。最后，本文對(duì)調(diào)度車(chē)的車(chē)次限制、最大容量以及第二次及之后從調(diào)度中心出發(fā)時(shí)允許初始的最大好車(chē)數(shù)進(jìn)行了敏感性分析，其結(jié)果總體呈下降趨勢(shì)，并得出了以下結(jié)論：（1）增加調(diào)度車(chē)的車(chē)次并不一定會(huì)降低成本，因?yàn)檐?chē)次過(guò)多時(shí)一些調(diào)度車(chē)并不一定會(huì)以最優(yōu)路線運(yùn)行；（2）增加調(diào)度車(chē)的最大容量，調(diào)度車(chē)的運(yùn)行成本降低，但降低幅度逐漸變小，因此需要結(jié)合調(diào)度車(chē)的固定成本來(lái)權(quán)衡合適的車(chē)輛容量；（3）增加第二次及之后從調(diào)度中心出發(fā)時(shí)允許初始的最大好車(chē)數(shù)，其運(yùn)行成本先降低后略微上升，因此需要選擇適當(dāng)?shù)某跏甲畲蠛密?chē)數(shù)來(lái)減少成本。

本文提出的共享單車(chē)平衡和回收已經(jīng)有了一定的成果，但還存在許多不足需要改善，在未來(lái)的研究中可以從以下幾個(gè)方面進(jìn)行改進(jìn)：（1）可引入客戶的滿意度以及調(diào)度車(chē)作業(yè)時(shí)的碳排放量為目標(biāo)函數(shù)，使其成為更復(fù)雜的多目標(biāo)函數(shù)問(wèn)題。（2）后續(xù)對(duì)模型假設(shè)復(fù)雜化，將其設(shè)置為每個(gè)站點(diǎn)可多次訪問(wèn)，共享單車(chē)所停位置為非固定式的散亂停放，以及好車(chē)壞車(chē)數(shù)量在調(diào)度工作途中會(huì)在較小幅度波動(dòng)的情況。