陳佳惠， 侯 寧，2，李曉璐，張 彭，朱廣宇

(1.北京交通大學(xué) 綜合交通運輸大數(shù)據(jù)應(yīng)用技術(shù)交通運輸行業(yè)重點實驗室，北京 100044；2.中國重型汽車集團(tuán)有限公司，山東 濟(jì)南 250101；3.交通運輸部規(guī)劃研究院信息所，北京 100028)

近年來，共享單車作為一種新型自行車租賃形式走進(jìn)了大眾視線[1]，給市民出行帶來了極大便利。共享單車在一定投放量的情況下，一些投放點出現(xiàn)供需時空失衡現(xiàn)象，無法滿足市民的出行需求，因此，單車的投放機構(gòu)需要對共享單車進(jìn)行調(diào)度，平衡供需關(guān)系。目前在車輛調(diào)度過程中，出現(xiàn)調(diào)度運輸車輛的分配與使用不協(xié)調(diào)問題，一些地區(qū)的調(diào)度車任務(wù)重、甚至調(diào)度車數(shù)量不足，而其他一些地區(qū)調(diào)度車工作任務(wù)較輕、甚至閑置。同時，調(diào)度人員未能按照規(guī)定數(shù)量，只憑借主觀意愿隨意投放，并且在調(diào)度路徑方面，調(diào)度人員只考慮自身喜好，不考慮調(diào)度是否合理，忽視調(diào)度過程中的道路交通環(huán)境，導(dǎo)致不能及時滿足各個共享單車投放點的供需要求，需要多次調(diào)度，不僅增加了運輸距離，還造成了過多的調(diào)度成本浪費。共享單車企業(yè)制定的調(diào)度規(guī)則也存在不合理問題，沒有考慮各個投放點在單車使用平峰期間內(nèi)的供需要求，一般只考慮將調(diào)度任務(wù)放在夜間或者早晚高峰期間進(jìn)行。在車輛調(diào)度過程中，出現(xiàn)的這些調(diào)度問題不僅極大地使共享單車的使用效率降低，而且也導(dǎo)致了用戶的體驗感降低。因此，如何實現(xiàn)共享單車在城市中的合理有效調(diào)度是目前亟需解決的問題。

目前，針對公共自行車調(diào)度方面的研究較多，如文獻(xiàn)[2-11]，根據(jù)公共自行車的調(diào)度研究，進(jìn)一步發(fā)展出對于共享單車的調(diào)度研究。于德新[12]等針對共享單車運營過程中的周轉(zhuǎn)率低及成本過高等問題，提出建立目標(biāo)為成本最小和投放率最高的調(diào)度模型，實驗結(jié)果表明模型有效。蔣塬銳[13]等針對共享單車供需失衡、共享率低等問題，提出目標(biāo)為最小成本的共享單車靜態(tài)調(diào)度模型，并使用單親遺傳算法求解。趙曼[14]對共享單車網(wǎng)絡(luò)，采用社會網(wǎng)絡(luò)分析法，提出了特征量和凝聚子群，得到了共享單車的局部最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)，并基于此提出調(diào)度路徑最優(yōu)方案。周傳鈺[15]結(jié)合共享單車的特點，考慮了軌道交通站點接駁區(qū)域的單車投放規(guī)模，提出調(diào)度最優(yōu)模型。盧琰[16]結(jié)合不同時段共享單車的分布特點，構(gòu)建混合軸輻式共享單車網(wǎng)絡(luò)結(jié)構(gòu)，提出有調(diào)度任務(wù)時間范圍和無調(diào)度任務(wù)時間范圍的調(diào)度優(yōu)化模型，并使用遺傳算法對模型驗證進(jìn)行求解?？嘴o[17]從共享單車的時間出行特性、空間出行特性、外部因素和用戶出行特征對共享單車的出行特性和影響因素進(jìn)行分析，考慮到目標(biāo)最短調(diào)度路徑和最高客戶滿意度進(jìn)行優(yōu)化，提出平峰期和高峰期調(diào)度路徑優(yōu)化模型。李三超[18]分析共享單車的交通特性及調(diào)度特征，構(gòu)建目標(biāo)為調(diào)度運輸車輛數(shù)和調(diào)度成本的半開放式多車場、含時間窗的車輛調(diào)度模型，提出使用禁忌搜索算法求解驗證模型。REISS和BOGENBERGER[19]分析共享單車的GPS數(shù)據(jù)，考慮多種影響因素表示出共享單車使用者的出行規(guī)律，提出需求模型，最后提出車輛調(diào)度模型，并通過案例驗證，證明調(diào)度方法的可行性。Leonardo Caggiani等[20]通過時空聚類的方法對共享單車使用規(guī)律進(jìn)行分析，并提出共享單車的需求預(yù)測模型，奠定了車輛調(diào)度優(yōu)化基礎(chǔ)。Aritra Pal和Yu Zhang[21]分析共享單車與傳統(tǒng)有樁公共自行車的特點，提出了不考慮時間窗的同一車輛多次訪問同一節(jié)點的共享單車車場靜態(tài)調(diào)度模型，模型求解采用混合變鄰域和大鄰域搜索算法，案例表明提出的調(diào)度方法有效。Leonardo Caggiani[22]等根據(jù)單車的需求進(jìn)行預(yù)測，并考慮共享單車投放點時空分布不均問題，提出目標(biāo)為最小運營成本和最高客戶滿意度的共享單車動態(tài)調(diào)度模型。

從上述研究成果可以看出，共享單車的調(diào)度問題可理解為調(diào)度路徑的優(yōu)化問題，目前在進(jìn)行共享單車調(diào)度路徑的優(yōu)化設(shè)計前，首先考慮共享單車的時空分布特征及調(diào)度特征等因素，再進(jìn)行分析。但在調(diào)度路徑的優(yōu)化設(shè)計過程中，目標(biāo)大部分過于單一，有些只考慮成本，有的只考慮顧客滿意度，甚至一些調(diào)度只從一個車場出發(fā)，調(diào)度結(jié)束后必須返回原車場，因此，單一的目標(biāo)很難滿足現(xiàn)實需要。同時，在考慮多目標(biāo)的情況下也未考慮時間窗問題。所以本文在分析完共享單車調(diào)度問題及調(diào)度影響因素后，以最少的調(diào)度車輛、最小的運輸成本和最高的調(diào)度任務(wù)完成度為目標(biāo)，建立基于高峰時段的半開放多車場含時間窗的動態(tài)調(diào)度路徑優(yōu)化模型，并設(shè)計禁忌搜索算法求解模型。

1 共享單車調(diào)度路徑優(yōu)化模型

1.1 多車場車輛調(diào)度路徑優(yōu)化建模分析

由于居民出行的波動性，造成各個投放點共享單車時空分布出現(xiàn)不均衡，這就需要從調(diào)度車場派出調(diào)度車輛，并根據(jù)各投放點需求將各投放點的車輛合理分配，使各投放點供求均衡。在對共享單車進(jìn)行調(diào)度運輸時，可將調(diào)度問題看成車輛的調(diào)度路徑優(yōu)化問題，即按照投放點所需車輛的多少，合理安排調(diào)度路徑，并及時分配共享單車車輛。

隨著當(dāng)前各交通運輸企業(yè)對經(jīng)濟(jì)成本管理越來越嚴(yán)格，對物流與運輸也十分關(guān)注，因此，研究滿足實際需要的車輛調(diào)度路徑問題十分必要。本文結(jié)合實際動作模式：

1)一般的交通運輸公司都擁有多個調(diào)度車場，為節(jié)約成本，當(dāng)調(diào)度車輛服務(wù)完最后一個投放點后，無需再回到最初的調(diào)度場，可選擇?？吭陔x其最近的一個調(diào)度車場；

2)當(dāng)有長途運輸需要時，考慮成本，無需使調(diào)度車輛再回到最初的調(diào)度場，可選擇停靠在運輸?shù)氐恼{(diào)度車場；

3)若各個交通運輸企業(yè)聯(lián)合進(jìn)行調(diào)度，考慮經(jīng)濟(jì)成本，可進(jìn)行調(diào)度車場資源共享，即從本公司出發(fā)的調(diào)度車輛在完成調(diào)度任務(wù)后，選擇?？吭谄渌嚯x其最近的調(diào)度車場。

根據(jù)以上3種運作模式，本文提出基于半開放式多車場的共享單車調(diào)度路徑優(yōu)化模型，即考慮的車輛調(diào)度路徑問題為基于半開放多車場。該問題是指在調(diào)度運輸過程中，多個場地的具有一定裝載能力的運輸車輛，為使各地投放點供求均衡，運輸車輛結(jié)合實際調(diào)度路徑情況，合理選擇路徑進(jìn)行調(diào)度運輸，當(dāng)車輛調(diào)度運輸任務(wù)完成后，在合適的就近調(diào)度車場停放，若再有運輸任務(wù)，再重新出發(fā)，不需要再回到出發(fā)時的車場。與車輛路徑問題(VRP)相比，其有更多的約束條件，如投放點的運輸需求只能由其中一輛運輸車輛完成，同一個投放點的共享單車由一輛車運輸完成，一輛車也只能運輸一個投放點的共享單車；運輸車輛的額定載運量不低于投放點的需求量；車輛的最大運輸距離大于運輸路線長度。半開放式多車場車輛路徑如圖1所示。

圖1 半開放式多車場車輛路徑

1.2 共享單車車輛調(diào)度路徑優(yōu)化模型

結(jié)合半開放多車場車輛調(diào)度路徑問題的特點，考慮道路路網(wǎng)結(jié)構(gòu)、共享單車投放點的分布及運輸車輛的數(shù)量等情況，設(shè)置目標(biāo)函數(shù)和約束條件對整個問題進(jìn)行建模。為使模型更符合實際情況，假設(shè)道路交通條件不變，在半開放、多車場情況下，結(jié)合一些特定的約束條件，設(shè)定目標(biāo)為最少的調(diào)度車輛數(shù)、最低的調(diào)度成本，構(gòu)建共享單車調(diào)度路徑優(yōu)化模型。

模型中最主要的優(yōu)化目標(biāo)指標(biāo)為車輛數(shù)最小，次要的優(yōu)化目標(biāo)為調(diào)度成本最低，可表示為調(diào)度過程中運輸成本最低和調(diào)度任務(wù)完成度最高。因此，構(gòu)建的共享單車調(diào)度路徑優(yōu)化模型函數(shù)可設(shè)置為調(diào)度車輛數(shù)函數(shù)，以及調(diào)度成本函數(shù)。由于兩個目標(biāo)函數(shù)衡量標(biāo)準(zhǔn)不一致，目標(biāo)函數(shù)存在相互矛盾，為此綜合考慮，將最小調(diào)度車輛數(shù)目標(biāo)指標(biāo)轉(zhuǎn)化為調(diào)度車輛固定成本，可表示為

MinZ0=c0K.

(1)

在調(diào)度成本函數(shù)中，主要考慮最低的運輸成本及調(diào)度任務(wù)完成度最高。

1.2.1 最低運輸成本

在調(diào)度路徑優(yōu)化問題里，設(shè){1，2，…，n}為N個調(diào)度車場編號，{n+1，n+2，…，n+m}為M個投放點編號，其中

i，j∈N∪M,k∈{1,2,3，…,K}.

投放點與投放點之間的距離為

(2)

因此，共享單車在調(diào)度過程中，一個調(diào)度運輸車輛的運輸成本和車輛的運輸距離乘積為調(diào)度運輸所造成的成本，可表示為

(3)

1.2.2 最低時間懲罰費用(時間窗偏離最小，調(diào)度任務(wù)完成度最高)

調(diào)度任務(wù)時間窗(完成調(diào)度任務(wù)中必須滿足的規(guī)定時間范圍)一般設(shè)置為[lti,hti],為調(diào)度車輛完成投放點i的投放任務(wù)所需滿足的任務(wù)時間范圍，為使調(diào)度任務(wù)完成度最高，需要在時間窗內(nèi)完成，最高的完成度值為1。但考慮到會受多種因素影響，調(diào)度車輛很難達(dá)到最高的完成度，所以需要考慮調(diào)度任務(wù)可能會在一定時間范圍內(nèi)有所延遲，但也會導(dǎo)致調(diào)度任務(wù)的完成度有所降低。假設(shè)[ati，bti]為調(diào)度任務(wù)完成的時間范圍，若在時段 [ati,lti]或 [hti,bti]內(nèi)調(diào)度車輛完成調(diào)度任務(wù)，則調(diào)度任務(wù)完成度會降低，完成度值為0～1之間。

在共享單車使用的高峰期，為同時符合及時調(diào)度和低成本調(diào)度，需要考慮多目標(biāo)問題，但兩者衡量標(biāo)準(zhǔn)不一致，為解決該問題，使用調(diào)度任務(wù)時間窗懲罰函數(shù)代替及時調(diào)度。即使用不滿足調(diào)度任務(wù)時間窗而產(chǎn)生懲罰費用的最低值代替調(diào)度任務(wù)完成度最高值，調(diào)度任務(wù)完成度函數(shù)可轉(zhuǎn)化為調(diào)度任務(wù)時間窗懲罰函數(shù)p(ti)。當(dāng)調(diào)度車輛在調(diào)度任務(wù)完成度最高的時間范圍[lti,hti]內(nèi)完成投放點i的調(diào)度，懲罰值表示為0；當(dāng)調(diào)度車輛在時間范圍 [ati,lti]或時間范圍 [hti,bti]內(nèi)完成投放點i的調(diào)度時，會產(chǎn)生對應(yīng)的調(diào)度任務(wù)時間范圍懲罰費用；當(dāng)調(diào)度車輛越早于時間ati或越晚于時間bti完成投放點i的調(diào)度，產(chǎn)生的調(diào)度任務(wù)時間窗懲罰值會越大，調(diào)度任務(wù)時間窗懲罰費用會越高。懲罰費用函數(shù)為

(4)

假設(shè)共享單車投放點i的容量為Ci，t時刻投放點i的車輛數(shù)為q(ti)，t時刻投放點的共享單車停放率為

(5)

(6)

由于兩個目標(biāo)函數(shù)優(yōu)先級不同，所以為兩種指標(biāo)賦予不同的權(quán)重值。整個共享單車高峰期調(diào)度系統(tǒng)目標(biāo)函數(shù)為調(diào)度過程中固定的車輛成本、運輸成本和時間懲罰費用之和最小

(7)

式中：dij為投放點之間的距離；K為運輸車輛數(shù)；c0為單個調(diào)度車輛的固定使用成本；c1為單個調(diào)度車輛的運行使用成本；c2為等待時間需要的成本；g1為早于ETi到達(dá)投放點的懲罰系數(shù)；g2為晚于LTi到達(dá)投放點的懲罰系數(shù)； [ati,bti]為可接受服務(wù)時間窗；ω1,ω2為權(quán)重值。

在調(diào)度過程中需要滿足的約束條件有：

4)各個需要進(jìn)行投放的地點，只由一輛調(diào)度車輛進(jìn)行調(diào)度服務(wù)；

其中Q為調(diào)度運輸車輛規(guī)定的額定載運量，L為調(diào)度運輸車輛規(guī)定的額定行駛距離。

2 共享單車調(diào)度路徑優(yōu)化模型求解算法

車輛調(diào)度路徑問題與NP-hard問題類似，故求解算法使用精確算法與啟發(fā)式算法[23]可以解決車輛調(diào)度問題。在面對一般的小規(guī)模網(wǎng)絡(luò)問題時，精確算法在全局范圍內(nèi)可以達(dá)到最優(yōu)解，但如果求解規(guī)模變大，求解將很難完成。本文采用啟發(fā)式算法對模型求解，通過對比各類啟發(fā)式算法發(fā)現(xiàn)，禁忌搜索算法雖然對初始解要求較高，但相較其他算法可有效完成局部鄰域搜索，防止陷入局部最優(yōu)，且搜索速度較快。

2.1 共享單車調(diào)度路徑相關(guān)問題處理

由于本文是研究半開放式多車場車輛調(diào)度問題，所以考慮將各個調(diào)度車場看做整體去優(yōu)化，多個調(diào)度任務(wù)使用一條路徑表示。本文采用整體法，設(shè)定虛擬車場，將所有車場和投放點當(dāng)成一個整體來求解調(diào)度路徑優(yōu)化問題；并將調(diào)度路徑問題轉(zhuǎn)化為多目標(biāo)規(guī)劃問題進(jìn)行求解[24]。所有投放點和實際調(diào)度車場均由虛擬車場服務(wù)，虛擬車場為調(diào)度任務(wù)的開始點，從開始點出發(fā)，到達(dá)實際調(diào)度車場后，再出發(fā)到各個投放點完成調(diào)度任務(wù)，從虛擬車場到實際車場的過程中都為0消耗。

2.2 禁忌搜索算法設(shè)計

本文采用禁忌搜索算法，對前一章節(jié)構(gòu)建的共享單車調(diào)度路徑優(yōu)化模型進(jìn)行求解。禁忌搜索算法中當(dāng)前的最優(yōu)解為一個隨機給定的初始解，全局最優(yōu)解為一個給定的狀態(tài)。算法開始的候選解為從初始解的一個鄰域中選定的若干解；然后需要用設(shè)置的適配值函數(shù)評價這些候選解，評價出最優(yōu)的候選解。判定最優(yōu)候選解當(dāng)前的狀態(tài)是否滿足全局最優(yōu)要求：若滿足，則作為新的全局最優(yōu)解并將狀態(tài)更新，并在禁忌表中記錄該候選解的信息；若不滿足，則將該最優(yōu)候選解的信息記錄到禁忌表和非禁忌表中。經(jīng)多次迭代得到最終的全局最優(yōu)解及其對應(yīng)的狀態(tài)。

本文主要從編碼初始解設(shè)計、鄰域結(jié)構(gòu)設(shè)計、適配值函數(shù)設(shè)計等闡述禁忌算法的運算流程。

2.2.1 構(gòu)成要素編碼

共享單車調(diào)度車場有N個，投放點M個，則編碼a1～an表示實際調(diào)度車場，編碼an+1～an+m表示投放點，虛擬車場可表示為a0。由a0，a1～an和an+1～an+m一起排列構(gòu)成解的編碼。

2.2.2 初始解設(shè)計

禁忌搜索算法是一個局部搜索過程，一般從一個初始解開始，初始解的設(shè)計會影響結(jié)果，因此要設(shè)計初始解。

1)對共享單車投放點進(jìn)行的編碼：隨機生成區(qū)間為an+1～an+m、長度為1～m內(nèi)的互相獨立不重復(fù)編碼；

2)對實際調(diào)度車場進(jìn)行的編碼：對a1～an中的n個編碼構(gòu)造一個集合；

3)合并1)和2)的編碼：①將編碼a0插入，將從2)的編碼里隨機挑選的編碼，放到1)的編碼首位；②從該編碼開始逐步搜索，如果不滿足適配值函數(shù)的評價，則記錄并跳出搜索；③上述跳出搜索位置填入從2)的編碼中再次隨機挑選的一個編碼，并在后面插入編碼a0；④再重復(fù)插入一次上述跳出搜索位置的編碼，按照步驟②重復(fù)上述搜索，如果不滿足適配值函數(shù)的評價，則重復(fù)①步驟，直到搜索完所有1)的編碼。

2.2.3 鄰域結(jié)構(gòu)設(shè)計

為滿足目標(biāo)函數(shù)，禁忌搜索算法的能力需要進(jìn)一步增強。通過參考相關(guān)文獻(xiàn)，本文使用了四種鄰域結(jié)構(gòu)[25]，從不同路徑中或本路徑中隨機挑選出兩個點，進(jìn)行鄰域結(jié)構(gòu)設(shè)計。

1)重新指派：取出在路徑中挑選出來的一個頂點，在第二個頂點之前插入之前取出的頂點；

2)頂點交換：將所挑選的兩個頂點位置進(jìn)行互換；

3)2—opt：如果在同一個調(diào)度路徑里抽取了兩個頂點，則把兩個頂點之間的所有點進(jìn)行逆轉(zhuǎn)排序；

4)“尾巴”交換：如果在不同的調(diào)度路徑里抽取了兩個頂點，則把抽取的兩個頂點(兩個頂點必須是投放點)后面的值進(jìn)行互換。

2.2.4 適配值函數(shù)設(shè)計

適配值函數(shù)通過評價當(dāng)前算法的搜索狀態(tài)，來判斷是否打破禁忌準(zhǔn)則，更新當(dāng)前狀態(tài)。本文將前面所述的目標(biāo)函數(shù)設(shè)定為適配值函數(shù)。

根據(jù)本文提出的兩個目標(biāo)函數(shù)，即最少的調(diào)度運輸車輛數(shù)和最低的車輛調(diào)度運輸成本(包括調(diào)度過程中運輸成本和未按調(diào)度任務(wù)時間范圍要求而產(chǎn)生的懲罰費用)，具有較高優(yōu)先權(quán)的目標(biāo)是最少的車輛數(shù)目，所以一般多是運輸車輛數(shù)少的解，但這樣會造成車輛運輸成本增加。為獲得更多可行解，可接受不可行解，所以，在目標(biāo)函數(shù)里加入約束條件，如超過車輛額定運載量和超過最大運輸距離時，會產(chǎn)生相應(yīng)的懲罰值，構(gòu)造的適配值函數(shù)為

(8)

式中：Z(k)為車輛k的調(diào)度成本；EV(k)為車輛超過調(diào)度車輛k額定載運量的數(shù)量，當(dāng)某個解為可行解時，EV(k)值等于0；EL(k)為車輛運輸超過調(diào)度車輛k額定運輸里程的路程，當(dāng)某個解為可行解時，EL(k)值等于0；p為懲罰函數(shù)。

在禁忌對象設(shè)置中，本文把每一次迭代過程中的最優(yōu)解作為禁忌對象放在禁忌表中。

2.3 禁忌搜索算法流程

根據(jù)上述編碼初始解設(shè)計、鄰域結(jié)構(gòu)設(shè)計等，禁忌搜索算法流程為：

1)設(shè)置初始解xNow，設(shè)置禁忌表H=?;

2)達(dá)到終止規(guī)則要求時，則停止，否則構(gòu)造滿足適配值函數(shù)要求的候選集Can_N(xNow)，且候選集在xNow的鄰域中選出;

3)若有滿足特赦規(guī)則的候選解，則釋放該解,否則,一個評價最優(yōu)解xNow在Can_N(xNow)中選出，令xNow=xbest，并在禁忌表H中進(jìn)行更新，重復(fù)步驟2)；

4)輸出計算結(jié)果，停止運算。

終止規(guī)則為：

1)目標(biāo)控制準(zhǔn)則：若最優(yōu)解在規(guī)定的步長內(nèi)一直保持一個恒定值，停止運算；

2)步長控制準(zhǔn)則：搜索到的最優(yōu)解需要在規(guī)定的步長范圍內(nèi)；

3)頻率控制準(zhǔn)則：若當(dāng)前解超過規(guī)定頻率給定值，停止運算。

特赦規(guī)則為：如果存在一個解優(yōu)于當(dāng)前狀態(tài)，則從禁忌表中特赦；若候選解全部被禁忌，則從禁忌表中特赦最優(yōu)禁忌候選解。

3 案例分析

2016年，共享單車開始進(jìn)入大眾視野，目前在北京市各處都分布有共享單車，本文研究的對象為北京市海淀區(qū)部分地區(qū)共享單車系統(tǒng)，通過分析摩拜共享單車的實際運營數(shù)據(jù)，來驗證本文提出的模型是否可行。北京市海淀區(qū)部分共享單車投放點分布如圖2所示。

圖2 北京市海淀區(qū)部分投放點分布

根據(jù)研究內(nèi)容，規(guī)定由調(diào)度中心統(tǒng)一調(diào)配投放點共享單車，首先編碼所有投放點及調(diào)度車場。1～3為實際調(diào)度車場，4～33為投放點，34為虛擬車場。

各投放點的調(diào)度需求量可結(jié)合利用Arcgis繪制熱力圖(見圖3，主要包括工作日、早高峰時段及居民出行的熱點區(qū)域)，分析共享單車空間出行規(guī)律、不同類型區(qū)域共享單車的借還量。

圖3 工作日07：00—09：00北京市居民騎行熱力

3.1 模型參數(shù)標(biāo)定

本文安排的調(diào)度車場N=3；單個調(diào)度車輛的恒定載車量Q=60；需要進(jìn)行調(diào)度的投放地點M=30，研究早高峰時段時間窗的調(diào)度問題，各投放點調(diào)度量和要求的時間窗信息如表1所示(本文只列舉10個投放點)。

表1 投放點調(diào)度量和時間窗要求

一般來說，調(diào)度車輛的固定使用成本涉及到油耗、車輛維護(hù)保養(yǎng)及人員成本等，故設(shè)本案例的調(diào)度車輛固定使用成本為c0=50元/輛，車輛的調(diào)度運輸成本c1=1元/km。同時，當(dāng)調(diào)度運輸車輛時未按調(diào)度任務(wù)時間窗要求進(jìn)行，產(chǎn)生的調(diào)度任務(wù)時間懲罰成本為c2=24元/h。

共享單車的調(diào)度除了考慮經(jīng)濟(jì)成本外，還需要保證調(diào)度任務(wù)的完成度，因此，需要在規(guī)定的調(diào)度任務(wù)時間范圍內(nèi)完成調(diào)度任務(wù)。懲罰系數(shù)可設(shè)置為g1=0.3，g2=0.7。

3.2 案例求解

利用上一節(jié)給出的案例數(shù)據(jù)，對30個投放點、3個調(diào)度車場使用MATLAB進(jìn)行調(diào)度模型編程設(shè)計求解，得到的最優(yōu)調(diào)度路徑方案如表2所示。得到的結(jié)果是使用車輛數(shù)最少為2輛，調(diào)度成本的最小值為兩條路徑調(diào)度成本之和，共計163.07元。得到的路徑軌跡如圖4所示，優(yōu)化迭代如圖5所示。

圖4 調(diào)度路徑軌跡

圖5 最優(yōu)值迭代過程

表2 最優(yōu)調(diào)度路徑方案

為進(jìn)一步研究模型效果，在規(guī)定的約束條件不變情況下，設(shè)定新目標(biāo)函數(shù)為調(diào)度完成度最高和運輸成本最低，即不考慮調(diào)度車輛數(shù)。然后使用與之前相同的數(shù)據(jù)開展下一步研究，得到的研究結(jié)果如表3所示。通過研究結(jié)果可看出本文提出的目標(biāo)具有更優(yōu)的調(diào)度路徑，可節(jié)約調(diào)度成本。

表3 研究結(jié)果

4 結(jié) 論

通過對共享單車調(diào)度問題進(jìn)行的相關(guān)研究，構(gòu)建了共享單車調(diào)度路徑的優(yōu)化模型，并利用禁忌搜索算法求解該模型，得出以下結(jié)論:

1)首先分析了目前共享單車需要調(diào)度的主要原因是共享單車時空分布不均，借鑒公共自行車車輛調(diào)度經(jīng)驗，構(gòu)建了帶時間窗的多車場共享單車調(diào)度路徑優(yōu)化模型，該模型的目標(biāo)函數(shù)為最少調(diào)度車輛數(shù)及最少和最低的調(diào)度成本，求解采用禁忌搜索算法。

2) 分析北京市海淀區(qū)投放點案例，求解驗證本文提出的調(diào)度模型和算法，最后的驗證結(jié)果表明本文提出的調(diào)度路徑優(yōu)化模型和禁忌搜索求解算法能夠提高調(diào)度系統(tǒng)的運輸效率，同時能夠節(jié)約調(diào)度運輸成本。

3)論文中仍存在一些不足，如調(diào)度模型中設(shè)置了過多的約束條件，導(dǎo)致模型求解較困難，同時沒有考慮道路交通條件、早晚高峰道路堵塞情況的運輸車輛發(fā)生故障概率等因素，即未能更加詳細(xì)考慮實際情況，有待進(jìn)一步研究。