吳滿金 ，董紅召* ，劉冬旭 ，陳 寧

(1．浙江工業(yè)大學(xué)智能交通系統(tǒng)聯(lián)合研究所，浙江杭州310014;2．浙江科技學(xué)院機(jī)械與汽車工程學(xué)院，浙江杭州310023)

0 引 言

公共自行車作為“低碳排放”［1］的中短途綠色交通形式，在全世界越來(lái)越受到推崇［2-3］。隨著公共自行車系統(tǒng)(PBS)規(guī)模逐漸增大，租賃需求不平衡及部分自助服務(wù)點(diǎn)位置不合理等原因?qū)е铝俗孕熊嚒白膺€難”現(xiàn)象的產(chǎn)生，公共自行車調(diào)度問(wèn)題隨之而來(lái)。目前，調(diào)度模型方面的研究主要圍繞著不同目標(biāo)及約束條件而展開(kāi)。董紅召［4］、Ravi［5］等人以公共自行車用戶滿意度為優(yōu)化目標(biāo)建立了模型。Caggiania 等［6］建立了以車輛調(diào)度成本最低為優(yōu)化目標(biāo)的自行車動(dòng)態(tài)再分配仿真模型。Kloimullner 等［7］提出了使整體自行車調(diào)度數(shù)量最少的調(diào)度優(yōu)化模型。Pfrommer 等［8］通過(guò)對(duì)公共自行車服務(wù)點(diǎn)設(shè)定動(dòng)態(tài)變化的租車價(jià)格建立了再平衡調(diào)度模型。上述研究雖然在公共自行車調(diào)度方面取得了一定進(jìn)展，但考慮的約束條件較少，且都僅對(duì)單個(gè)優(yōu)化目標(biāo)進(jìn)行建模及求解，而實(shí)際調(diào)度過(guò)程中，往往涉及到用戶滿意度、企業(yè)調(diào)度成本等諸多影響因素。因此，為有效緩解公共自行車系統(tǒng)的“租還車難”問(wèn)題，平衡公共自行車在時(shí)間和空間上的分布，提高公共自行車的利用率，有必要對(duì)統(tǒng)籌用戶滿意度及企業(yè)調(diào)度成本的公共自行車調(diào)度問(wèn)題進(jìn)行研究。

本研究針對(duì)公共自行車系統(tǒng)自行車時(shí)空分布不均衡的問(wèn)題，對(duì)公共自行車調(diào)度過(guò)程中自助服務(wù)點(diǎn)調(diào)度優(yōu)先級(jí)、動(dòng)態(tài)需求特性、服務(wù)時(shí)間窗等進(jìn)行研究。

1 PBS 多目標(biāo)優(yōu)化調(diào)度模型的建立

1．1 服務(wù)點(diǎn)調(diào)度請(qǐng)求

目前，公共自行車系統(tǒng)“租還車難”的問(wèn)題比較凸顯，需調(diào)度的服務(wù)點(diǎn)較多，而調(diào)度的力量相對(duì)有限，僅能對(duì)一定數(shù)量的服務(wù)點(diǎn)進(jìn)行調(diào)度。因此，本研究根據(jù)公共自行車系統(tǒng)服務(wù)點(diǎn)車鎖比(服務(wù)點(diǎn)自行車數(shù)量與鎖樁數(shù)量的比值)，對(duì)服務(wù)點(diǎn)進(jìn)行調(diào)度優(yōu)先等級(jí)劃分，并設(shè)定調(diào)度請(qǐng)求判斷條件。

(1)一級(jí)服務(wù)窗口A+，即優(yōu)先進(jìn)行調(diào)度的服務(wù)點(diǎn)集合。本研究對(duì)車鎖比滿足α≤0．1 或α≥0．9 的服務(wù)點(diǎn)進(jìn)行優(yōu)先調(diào)度，并將其放入到服務(wù)窗口A+中。

(2)二級(jí)服務(wù)窗口A－，即準(zhǔn)備進(jìn)行調(diào)度的服務(wù)點(diǎn)集合。當(dāng)服務(wù)點(diǎn)車鎖比滿足α≤0．2 或α≥0．8 時(shí)，本研究將其放入服務(wù)窗口A－中，準(zhǔn)備接受調(diào)度車輛的調(diào)度。在保證能夠?qū)+窗口的服務(wù)點(diǎn)優(yōu)先調(diào)度的情況下，再對(duì)A－窗口的服務(wù)點(diǎn)進(jìn)行調(diào)度，同時(shí)，盡量不增加調(diào)度車輛的調(diào)度路徑。

(3)三級(jí)服務(wù)窗口B，即尚未有調(diào)度需求的服務(wù)點(diǎn)和已經(jīng)接受過(guò)調(diào)度的服務(wù)點(diǎn)集合，該集合中的服務(wù)點(diǎn)不接受調(diào)度請(qǐng)求。

實(shí)際運(yùn)用過(guò)程中，調(diào)度優(yōu)先級(jí)的劃分(車鎖比的設(shè)定)可根據(jù)實(shí)際情況而定。

1．2 服務(wù)點(diǎn)租賃需求量的確定

假設(shè)編號(hào)為i 的任意服務(wù)點(diǎn)可容納的公共自行車數(shù)量為Ei，在t 時(shí)刻自行車數(shù)量為qi(t)，車鎖比值為αi(t)，設(shè)定能正常提供服務(wù)的最小及最大車鎖比分別為αmin，αmax。當(dāng)αi(t)＜αmin時(shí)，服務(wù)點(diǎn)為調(diào)入需求量:

取其平均值:

同理，當(dāng)αi(t)＞αmax時(shí)，為調(diào)出需求量:

總結(jié)如下:

1．3 服務(wù)點(diǎn)調(diào)度時(shí)間窗的確定

服務(wù)點(diǎn)間的行駛時(shí)間是制定公共自行車調(diào)度計(jì)劃的重要依據(jù)。假設(shè)服務(wù)點(diǎn)i－1 到服務(wù)點(diǎn)i 的距離為Si，調(diào)度車平均行駛速度為vave，在服務(wù)點(diǎn)i－1 到i 之間的行駛時(shí)間為Si/vave，則從調(diào)度中心出發(fā)到第i 個(gè)服務(wù)點(diǎn)所需的總時(shí)間為。而在實(shí)際調(diào)度過(guò)程中，道路交通狀況的動(dòng)態(tài)變化導(dǎo)致調(diào)度車輛在服務(wù)點(diǎn)間的行駛時(shí)間也隨之動(dòng)態(tài)變化，因此:

式中:vh—調(diào)度車高峰時(shí)段平均行駛速度，va—平峰時(shí)段平均速度。

最終得到服務(wù)點(diǎn)調(diào)度時(shí)間窗約束條為:

1．4 動(dòng)態(tài)調(diào)度模型的建立

模型參數(shù)的含義如下:

Q 表示調(diào)度車的最大運(yùn)載量;

di(t)表示t 時(shí)刻，服務(wù)點(diǎn)i 需要運(yùn)進(jìn)或運(yùn)出的自行車數(shù)量;

Vi+1(t)表示t 時(shí)刻，對(duì)服務(wù)點(diǎn)i 完成調(diào)度后，調(diào)度車上的自行車數(shù)量;

c0表示使用每輛車的固定成本;

ε 表示車輛運(yùn)行單位距離所需的成本;

ρi表示服務(wù)點(diǎn)i 的權(quán)重值;

Wi表示服務(wù)點(diǎn)i 的鎖樁周轉(zhuǎn)率。

公共自行車系統(tǒng)需要統(tǒng)籌考慮用戶需求和調(diào)度成本，本研究建立了以用戶滿意度最大、調(diào)度成本最低為多優(yōu)化目標(biāo)的特征函數(shù)，具體如下:

綜合目標(biāo)函數(shù)為:

式(3)表示用戶滿意度，通過(guò)服務(wù)點(diǎn)周轉(zhuǎn)率體現(xiàn)。周轉(zhuǎn)率高則表明自行車的利用率高，說(shuō)明能更好地為用戶提供服務(wù)，使用戶對(duì)自行車系統(tǒng)的滿意度更高。其中:ρi—根據(jù)服務(wù)點(diǎn)類型取值，一般情況下中心服務(wù)點(diǎn)ρi取1．5，普通服務(wù)點(diǎn)ρi為1．0;n—調(diào)度計(jì)劃中，服務(wù)點(diǎn)接受調(diào)度的序號(hào)，即表示該服務(wù)點(diǎn)為第n 個(gè)接受調(diào)度的服務(wù)點(diǎn)?？梢钥闯鰧?duì)周轉(zhuǎn)率大，權(quán)重值高的服務(wù)點(diǎn)進(jìn)行優(yōu)先調(diào)度，調(diào)度計(jì)劃整體周轉(zhuǎn)率Z1就越高，即滿意度越高。式(4)表示車輛使用固定成本及行駛成本。式(5)表示多目標(biāo)綜合成本，λ 為變換因子［9］，λ=K0Knc0，其中:K0—常數(shù)，決定了對(duì)用戶滿意度的注重程度，根據(jù)經(jīng)驗(yàn)設(shè)定;Kn—受調(diào)度的服務(wù)點(diǎn)數(shù)量。

約束條件為:s．t．

式(6)表示調(diào)度完服務(wù)點(diǎn)i 后，調(diào)度車上的自行車數(shù)量;式(7)表示調(diào)度車在任何時(shí)刻都不超過(guò)最大運(yùn)載量;式(8)表示各服務(wù)點(diǎn)調(diào)入與調(diào)出總量不超過(guò)車輛的最大運(yùn)載量;式(9)表示單個(gè)服務(wù)點(diǎn)需求量均不超過(guò)車輛的最大運(yùn)載量。式(10)為車輛服務(wù)時(shí)間的約束條件。

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

智能優(yōu)化算法主要包括禁忌搜索算法［10］、遺傳算法［11］、蟻群算法［12］及模擬退火算法［13］等，以上算法單獨(dú)使用時(shí)，都存在一定的局限性，大多數(shù)學(xué)者采用混合智能算法［14-16］以彌補(bǔ)算法本身的缺陷。禁忌搜索算法能夠跳出局部最優(yōu)，爬山性能較好，但鄰域構(gòu)造簡(jiǎn)單，一定程度上削弱了算法的搜索能力。相反，遺傳算法雖然有著易早熟的缺點(diǎn)，但算子選擇、交叉、變異能夠產(chǎn)生新的種群，可有效增加鄰域的多樣性，兩者有著較好的互補(bǔ)性?？紤]公共自行車調(diào)度的各種約束，本研究采用禁忌搜索算法與遺傳算法相結(jié)合的混合算法求解公共自行車調(diào)度模型，得到調(diào)度車輛最優(yōu)的行駛路線，滿足其社會(huì)效益及經(jīng)濟(jì)效益的需求，具體流程如圖1 所示。

圖1 混合算法流程圖

2．1 調(diào)度初始路線獲取與適應(yīng)度函數(shù)

本研究對(duì)公共自行車初始調(diào)度路線采用雙層編碼方式。第一層序列代表調(diào)度車經(jīng)過(guò)的n 個(gè)服務(wù)點(diǎn)的一種調(diào)度路徑;根據(jù)調(diào)度車輛的容量約束條件，將調(diào)度路徑分割成多條有效的子路徑，這些子路徑直接構(gòu)成第二層序列。本研究選取公共自行車調(diào)度模型中的綜合目標(biāo)函數(shù)式(5)為混合算法的適應(yīng)度函數(shù)。

2．2 變鄰域生成

(1)算子選擇。本研究采用精英保留策略與輪盤賭相結(jié)合的方法進(jìn)行算子選擇。選取群體中10%的優(yōu)秀個(gè)體保留至下一代，該部分優(yōu)秀個(gè)體不參與交叉變異。剩余90%的個(gè)體采用輪盤賭選擇方法進(jìn)入下一代參與交叉和變異的操作。

(2)交叉算子。交叉算子可有效避免某些算子存在的“早熟收斂”，在算法中起著關(guān)鍵作用。采用雙交叉點(diǎn)隨機(jī)組合的方法，算子交叉示意圖如圖2 所示。

圖2 算子交叉示意圖

(3)算子變異。算子變異改變的是某一路徑上某個(gè)服務(wù)點(diǎn)的順序，這里采用2-Opt 算法進(jìn)行算子變異操作。對(duì)某一條調(diào)度路線任選兩個(gè)不相鄰的路段進(jìn)行交換，如果交換后的目標(biāo)值有所提高，并且滿足容量約束，則更新該路線，否則保持原路線不變。

2．3 禁忌表與藐視準(zhǔn)則

禁忌表用于存放禁忌對(duì)象，表示在搜索過(guò)程中被禁忌的操作，即產(chǎn)生的新解若為禁忌對(duì)象，則不能替換當(dāng)前解，以避免陷入局部最優(yōu)。藐視準(zhǔn)則是為了避免遺失優(yōu)良解，而讓部分禁忌對(duì)象可以被重新選擇，即候選解集中的某個(gè)解優(yōu)于歷史最優(yōu)解時(shí)，不考慮該解是否屬于禁忌對(duì)象，直接替換當(dāng)前解。

3 實(shí)驗(yàn)與分析

3．1 實(shí)驗(yàn)方案與數(shù)據(jù)

本研究選取杭州市濱江某區(qū)域的公共自行車系統(tǒng)為調(diào)度研究對(duì)象，該區(qū)域內(nèi)共有一個(gè)調(diào)度中心M0 和62 個(gè)公共自行車系統(tǒng)服務(wù)點(diǎn)，選取9 個(gè)滿足一級(jí)服務(wù)窗條件的服務(wù)點(diǎn)作為實(shí)驗(yàn)對(duì)象，其中相關(guān)租賃需求數(shù)據(jù)如表1 所示。設(shè)定服務(wù)點(diǎn)需要運(yùn)出自行車時(shí)di(t)＞0，運(yùn)入自行車時(shí)di(t)＜0。實(shí)際每輛調(diào)度車最大可裝載自行車的數(shù)量為75 輛，行駛里程成本為2 元/km，調(diào)度車平均行駛速度為36 km/h，各服務(wù)點(diǎn)以及服務(wù)點(diǎn)與調(diào)度中心之間的距離如表2 所示。根據(jù)以往調(diào)度經(jīng)驗(yàn)設(shè)定調(diào)度人員上架或下架一輛自行車需20 s時(shí)間，則調(diào)度車在服務(wù)點(diǎn)的調(diào)度停留時(shí)長(zhǎng)為di(t)/3 min，轉(zhuǎn)化為行駛距離后為0．2di(t)km，調(diào)度一輪的固定成本c0為80 元，用戶滿意度變換因子為0．36 c0。

表1 服務(wù)點(diǎn)租賃需求信息數(shù)據(jù)表

3．2 結(jié)果分析

本研究根據(jù)表1，表2 所示實(shí)驗(yàn)數(shù)據(jù)，通過(guò)禁忌遺傳混合算法獲取公共自行車系統(tǒng)的調(diào)度計(jì)劃。在實(shí)驗(yàn)測(cè)試結(jié)果過(guò)程中，一共進(jìn)行了20 次的迭代次數(shù)為200的實(shí)驗(yàn)，得到了8 次表現(xiàn)相同的最優(yōu)調(diào)度方案，最優(yōu)解如表3 所示。

表2 各服務(wù)點(diǎn)以及服務(wù)點(diǎn)與調(diào)度中心之間的距離

表3 禁忌遺傳混合算法的最優(yōu)解

從表3 中可以得到，由混合算法優(yōu)化得到的調(diào)度路線總長(zhǎng)度僅為22．9 km，比經(jīng)驗(yàn)路線的路徑長(zhǎng)度減少了8．5 km，約占27．1%;同時(shí)優(yōu)化后的路線對(duì)重要服務(wù)點(diǎn)(6210，6205)進(jìn)行了優(yōu)先調(diào)度，盡可能的提高了用戶的滿意度。優(yōu)化路線的綜合調(diào)度成本為97 元(非實(shí)際成本僅作參考)，比經(jīng)驗(yàn)路線的綜合調(diào)度成本節(jié)約了28．5 元，約為優(yōu)化前的22．7%。對(duì)應(yīng)的路線如圖3 所示，虛線為調(diào)度車根據(jù)經(jīng)驗(yàn)路線進(jìn)行調(diào)度的實(shí)際行車軌跡，由車載GPS 定位系統(tǒng)得到;黑色路線為優(yōu)化后的調(diào)度路線。從圖3 中可看出，經(jīng)驗(yàn)調(diào)度時(shí)，調(diào)度車在部分服務(wù)點(diǎn)間的行駛路線非最短距離路線，而是進(jìn)行了不必要的繞行。而優(yōu)化后路線在合理安排服務(wù)點(diǎn)接受調(diào)度順序的同時(shí)，調(diào)度車在兩服務(wù)點(diǎn)間的行駛路線為最短距離路線，大大降低了調(diào)度成本。

圖3 調(diào)度車行駛路線圖

4 結(jié)束語(yǔ)

通過(guò)分析公共自行車系統(tǒng)調(diào)度問(wèn)題的特性，筆者建立了以調(diào)度成本最低與用戶滿意度最高為優(yōu)化目標(biāo)的公共自行車系統(tǒng)動(dòng)態(tài)調(diào)度模型，利用禁忌遺傳混合調(diào)度算法對(duì)公共自行車系統(tǒng)動(dòng)態(tài)調(diào)度模型進(jìn)行了求解，實(shí)驗(yàn)結(jié)果基本可行。

該算法在保證用戶滿意度基礎(chǔ)上，減少了調(diào)度車輛的行駛距離，解決了以往單目標(biāo)調(diào)度優(yōu)化而導(dǎo)致的系統(tǒng)整體優(yōu)化結(jié)果缺失的問(wèn)題，對(duì)公共自行車系統(tǒng)調(diào)度工作具有重要指導(dǎo)意義。此外，調(diào)度計(jì)劃的質(zhì)量在一定程度上還依賴于服務(wù)點(diǎn)潛在用戶需求量的精確估算，這需要更進(jìn)一步的探索。

［1］陳 飛，諸大建．城市低碳競(jìng)爭(zhēng)力理論與發(fā)展模式研究．城市規(guī)劃學(xué)刊［J］．2011(4):15-22．

［2］SHAHEEN S A，GUZMAN S，ZHANG H． Bikesharing in europe，the americas，and asia［J］． Transportation Research Record，2010(2143):159-167．

［3］FISHMAN E，WASHINGTON S，HAWORTH N，et al．Factors influencing bike share membership:an analysis of melbourne and brisbane［J］． Transportation Research Part A，2015(71):17-30．

［4］董紅召，趙敬洋．公共慢行系統(tǒng)的動(dòng)態(tài)調(diào)度建模與滾動(dòng)時(shí)域調(diào)度算法研究［J］．公路工程，2009，34(6):68-75．

［5］RAVIV T，TZUR M，F(xiàn)ORMA I A． Static repositioning in a bike-sharing system:models and solution approaches［J］．EURO Journal on Transportation and Logistics，2013，2(3):187-229．

［6］CAGGIANI L，OTTOMANELLI M． A dynamic simulation based model for optimal fleet repositioning in bike-sharing systems［J］． Procedia-Social and Behavioral Sciences，2013(87):203-210．

［7］KLOIMULLNER C，PAPAZEK P，HU B． Balancing bicycle sharing systems:an approach for the dynamic case［J］． Evolutionary Computation in Combinatorial Optimisation，2014(8600):73-84．

［8］PFROMMER J，WARRINGTON J，SCHILDBACH G，et al． Dynamic vehicle redistribution and online price incentives in shared mobility systems［J］． IEEE Transactions on Intelligent Transportation Systems，2014，15(4):1567-1578．

［9］賈永基，王長(zhǎng)軍．基于滿意優(yōu)化的多目標(biāo)車輛調(diào)度問(wèn)題模型與算法［J］．東華大學(xué)學(xué)報(bào)，2009，35(3):351-354．

［10］ALESSANDRO C，KNUST S，MEIER D，et al． Tabu search and lower bounds for a combined production-transportation Problem［J］． Computers and Operations Research，2013，40(3):886-900．

［11］MOCKOVA D，RYBICKOVA A． Application of genetic algorithms to vehicle routing problem［J］． Neural Network World，2014，24(1):57-78．

［12］胡天軍，程文科．帶回程取貨的逆向物流車輛路徑建模及其蟻群算法［J］． 交通運(yùn)輸系統(tǒng)工程與信息，2010，10(3):110-114．

［13］XIAO Y，ZHAO Q，KAKU I，et al． Variable neighbourhood simulated annealing algorithm for capacitated vehicle routing problems［J］． Engineering Optimization，2014，46(4):562-579．

［14］朱珈楠，陳 勇，魯建廈．多品種多工藝制造企業(yè)車間作業(yè)調(diào)度的ACA 建模［J］． 輕工機(jī)械，2013，31(3):99-103．

［15］余 麗，陸 鋒，楊 林．交通網(wǎng)絡(luò)旅行商路徑優(yōu)化的遺傳禁忌搜索算法［J］． 測(cè)繪學(xué)報(bào)，2014，43(11):1197-1203．

［16］GASPERO L D，RENDL A，URLI T． A Hybrid ACO+CP for balancing bicycle sharing systems［J］． Hybrid Metaheuristics，2013(7919):198-212．