考慮需求可拆分的共享單車調(diào)度優(yōu)化研究

張建同 戴倩楠 丁燁

摘 要： ??研究考慮需求可拆分的共享單車調(diào)度優(yōu)化問(wèn)題為可拆分單商品取送貨TSP問(wèn)題，考慮一輛調(diào)度車，允許調(diào)度車多次訪問(wèn)各站點(diǎn)，每次滿足站點(diǎn)的部分需求，即允許對(duì)站點(diǎn)的需求進(jìn)行拆分。首先，考慮到調(diào)度車容量限制，統(tǒng)籌安排調(diào)度車行駛路徑和調(diào)度車在每個(gè)站點(diǎn)的取車量、送車量，使得企業(yè)的運(yùn)營(yíng)成本達(dá)到最優(yōu)。其次，提出了一種改進(jìn)的變鄰域搜索算法求解上述問(wèn)題，使算法在陷入局部最優(yōu)解時(shí)改變鄰域結(jié)構(gòu)，擴(kuò)大搜索范圍，以此提升算法跳出局部最優(yōu)解的能力，加快收斂速度。最后，用數(shù)值實(shí)驗(yàn)驗(yàn)證了算法的有效性。研究結(jié)論拓展了可拆分單商品取送貨問(wèn)題的相關(guān)理論，并為共享單車企業(yè)的實(shí)際運(yùn)營(yíng)提供決策支持。

關(guān)鍵詞： ?共享單車；路徑規(guī)劃；需求可拆分；改進(jìn)變鄰域算法

中圖分類號(hào)： ?F 572

文獻(xiàn)標(biāo)志碼： ??A

Optimization of Distribution of Ofo BikesConsidering Split-Demand

ZHANG Jiantong DAI Qiannan DING Ye

（School of Economics and Management， Tongji University， Shanghai 200092， China）

Abstract： ?This research studies the static bike rebalancing problem considering split-demand which can be viewed as split-demand one-commodity pickup and delivery traveling salesman problem， considering a shunting vehicle， where multiple visits are allowed to be performed at each node， i.e.， the demand for nodes is allowed to be split. The capacity limitation of the shunting vehicle is considered， and the driving path of the shunting vehicle and the amount of the vehicle fetching and delivering at each station are generally arranged， so as to make the operation cost of the enterprise optimal. Secondly， an improved variable neighborhood search algorithm is proposed to solve the problem above， when the algorithm falls into the local optimal solution， the neighborhood structure is changed and the search range is expanded， so as to improve the algorithms ability to jump out of the local optimal solution and speed up the convergence speed. Finally， numerical experiments verify the effectiveness of the algorithm. This research expands the relevant theories of split-demand one-commodity pickup and delivery traveling salesman problem， and provides decision support for the actual operation of bike-sharing companies.

Key words： ?free-floating sharing bike；vehicle routing problem；split-demand；improved variable neighborhood search algorithm

作為“共享經(jīng)濟(jì)”領(lǐng)域最熱的一類產(chǎn)品，共享單車的出現(xiàn)很好地解決了城市出行的“最后一公里”問(wèn)題。目前共享單車進(jìn)入穩(wěn)步發(fā)展階段，后續(xù)市場(chǎng)競(jìng)爭(zhēng)模式從增量競(jìng)爭(zhēng)轉(zhuǎn)向存量競(jìng)爭(zhēng)，從擴(kuò)張轉(zhuǎn)為精細(xì)化運(yùn)營(yíng)。當(dāng)前共享單車市場(chǎng)處于穩(wěn)定期，而隨著碳中和、健康出行等倡議以及用戶逐漸適應(yīng)市場(chǎng)，共享單車的用戶規(guī)模將有一個(gè)上升空間。與此同時(shí)單車供需不匹配的問(wèn)題也日益凸顯，企業(yè)在各大城市投放的共享單車量已超過(guò)理論上的需求量，然而調(diào)查顯示，共享單車的潮汐現(xiàn)象嚴(yán)重。在工作日早高峰時(shí)段，交通樞紐吸引了大量的車輛?？浚瑖?yán)重影響周圍的交通通行，這些單車在平峰時(shí)段處于暫時(shí)閑置狀態(tài)，并且造成了局部地區(qū)車輛不足的問(wèn)題；在晚高峰時(shí)段單車向各個(gè)居民區(qū)流動(dòng)，導(dǎo)致交通樞紐的共享單車供不應(yīng)求。該現(xiàn)象其實(shí)是供與求在時(shí)間、空間上不相匹配的問(wèn)題。這就要求共享單車企業(yè)進(jìn)行有效的調(diào)度操作。

在共享單車調(diào)度的過(guò)程中，調(diào)度車從調(diào)度中心出發(fā)，逐個(gè)訪問(wèn)站點(diǎn)，并且根據(jù)站點(diǎn)的需求進(jìn)行取送貨操作，最后返回調(diào)度中心。由于在實(shí)際中會(huì)出現(xiàn)站點(diǎn)單車的需求量超過(guò)調(diào)度車最大承載量的情況，因此允許調(diào)度車多次訪問(wèn)站點(diǎn)滿足需求更符合實(shí)際。共享單車企業(yè)需統(tǒng)籌安排調(diào)度車的行駛路徑及其在每個(gè)站點(diǎn)取送的單車數(shù)量，以減少時(shí)間和路程的浪費(fèi)。

基于企業(yè)實(shí)際運(yùn)營(yíng)特征，以上調(diào)度問(wèn)題可定義為考慮需求可拆分的共享單車調(diào)度優(yōu)化問(wèn)題（Static Bike-sharing Rebalancing Problem Considering Split-demand， SBRPSD）。該問(wèn)題假設(shè)各站點(diǎn)的需求量，調(diào)度車在各站點(diǎn)間的行駛時(shí)間、服務(wù)時(shí)間確定并已知，考慮一輛調(diào)度車，允許調(diào)度車對(duì)每個(gè)站點(diǎn)進(jìn)行多次訪問(wèn)，即允許對(duì)各站點(diǎn)的需求進(jìn)行拆分，通過(guò)確定一條可行的調(diào)度車路徑和調(diào)度車在每個(gè)站點(diǎn)的取車量、送車量使得目標(biāo)函數(shù)達(dá)到最優(yōu)。SBRPSD松弛了單商品取送貨TSP問(wèn)題（One Commodity Pickup-and-Delivery TSP， 1-PDTSP）中各站點(diǎn)僅允許調(diào)度車訪問(wèn)一次的約束，使得每個(gè)站點(diǎn)的取車量、送車量在模型中也作為決策變量呈現(xiàn)。決策變量的增加意味著 SBRPSD 問(wèn)題的解空間比傳統(tǒng)的 VRP 問(wèn)題更大，因此比傳統(tǒng)的車輛路徑問(wèn)題（VRP）更為復(fù)雜，屬于NP-hard問(wèn)題。

共享單車興起于半世紀(jì)之前，近十年時(shí)間在世界范圍內(nèi)開始流行起來(lái)。起初的形式是有樁式共享單車（Station-Based Bike Sharing，SBBS）。Chemla等對(duì)有樁式共享單車調(diào)度問(wèn)題進(jìn)行了詳細(xì)的描述，初次建立數(shù)學(xué)模型，并用分支定界算法進(jìn)行求解，其中通過(guò)用禁忌搜索算法基于一定的規(guī)則得到上界，通過(guò)求解松弛問(wèn)題得到下界，并用隨機(jī)生成的算例驗(yàn)證了模型及算法的有效性。Raviv等首次提出需求部分滿足的概念，他們指出，在實(shí)際情況中由于調(diào)度時(shí)間的限制以及存在供不應(yīng)求的可能性，完全滿足需求很難實(shí)現(xiàn)，因此提出以最小化總懲罰成本和總調(diào)度成本的加權(quán)和為目標(biāo)函數(shù)的兩個(gè)數(shù)學(xué)模型，其中一個(gè)模型不允許各站點(diǎn)暫存自行車、被調(diào)度車多次訪問(wèn)，而另一個(gè)模型允許，并對(duì)兩個(gè)模型的求解結(jié)果進(jìn)行對(duì)比。DellAmico為該問(wèn)題建立了 4 個(gè)混合整數(shù)規(guī)劃模型，用分支定界算法分別對(duì)它們進(jìn)行求解，并對(duì)比結(jié)果。Erdogan通過(guò)將普通整數(shù)變量轉(zhuǎn)換為二元變量建立整數(shù)規(guī)劃模型，并通過(guò)計(jì)算實(shí)驗(yàn)發(fā)現(xiàn)站點(diǎn)可以暫存自行車的公共自行車調(diào)度問(wèn)題比不能暫存的更易求解。

隨著時(shí)代的發(fā)展進(jìn)步，有樁式公共自行車演變成了無(wú)樁自由式共享單車（Free-Floating Bike Sharing，F(xiàn)FBS）。Pal等旨在高效地解決靜態(tài)再平衡問(wèn)題，提出了一種具有變鄰域下降算法的混合嵌套大鄰域搜索，在算例驗(yàn)證中，提出所用算法優(yōu)于禁忌搜索算法，并且能夠處理與 FFBS 和 SBBS 相關(guān)的規(guī)模不斷增加的靜態(tài)重新平衡問(wèn)題，同時(shí)在合理的 CPU 時(shí)間內(nèi)可獲得高質(zhì)量的解決方案。Schuijbroek基于先聚類后路徑規(guī)劃的思想，建立了基于聚類問(wèn)題的混合整數(shù)規(guī)劃模型，該模型將多調(diào)度車問(wèn)題為單調(diào)度車問(wèn)題進(jìn)行求解，并提出相應(yīng)的啟發(fā)式算法進(jìn)行求解。Hernandez-Perez描述了一種元啟發(fā)式算法，它用一組站點(diǎn)代表每個(gè)客戶，每個(gè)站點(diǎn)都與潛在訪問(wèn)相關(guān)聯(lián)，將每個(gè)客戶需求分解為與其站點(diǎn)相關(guān)的部分需求，并用變鄰域搜索解決單一商品取送貨旅行商問(wèn)題。Polat等提出了一個(gè)混合整數(shù)數(shù)學(xué)優(yōu)化模型和一個(gè)基于擾動(dòng)的鄰域搜索算法，并結(jié)合經(jīng)典的節(jié)約啟發(fā)式算法，計(jì)算結(jié)果表明，與文獻(xiàn)報(bào)道的方法相比，所提出的方法對(duì)一些著名的基準(zhǔn)問(wèn)題產(chǎn)生了更優(yōu)的解，對(duì)其余的測(cè)試問(wèn)題產(chǎn)生了相當(dāng)好的解。Cruz和Ho等都在算法上取得了突破。

綜上，共享單車調(diào)度優(yōu)化問(wèn)題的模型已有大量研究， 但是考慮需求可拆分的相關(guān)問(wèn)題研究較少。并且，改進(jìn)的變鄰域搜索算法在共享單車調(diào)度優(yōu)化問(wèn)題方面的應(yīng)用研究較少。因此，本研究考慮需求可拆分的共享單車調(diào)度優(yōu)化問(wèn)題，允許調(diào)度車在每個(gè)站點(diǎn)執(zhí)行多次訪問(wèn)，并設(shè)計(jì)一種改進(jìn)的變鄰域搜索算法，使算法在陷入局部最優(yōu)解時(shí)改變鄰域結(jié)構(gòu)，更換搜索范圍，以此提升算法跳出局部最優(yōu)解的能力，加快收斂速度，數(shù)值實(shí)驗(yàn)驗(yàn)證了算法的有效性。

1 模型建立

1.1 問(wèn)題定義

SBRPSD定義如下：考慮一組有限的節(jié)點(diǎn)，假設(shè)節(jié)點(diǎn)之間的距離（或成本）已知。若某節(jié)點(diǎn)單車過(guò)多需要調(diào)度車運(yùn)走，則該節(jié)點(diǎn)具有負(fù)需求，為取貨點(diǎn)；若某節(jié)點(diǎn)單車過(guò)少需要補(bǔ)充，則該節(jié)點(diǎn)具有正需求，為送貨點(diǎn)。假設(shè)有一輛有容量限制的車輛從調(diào)度中心出發(fā)分別訪問(wèn)各節(jié)點(diǎn)并根據(jù)節(jié)點(diǎn)需求取、送單車后再返回節(jié)點(diǎn)，各節(jié)點(diǎn)至少被訪問(wèn)一次，至多被訪問(wèn)兩次，選擇合適的路徑并滿足節(jié)點(diǎn)的需求。重置目標(biāo)可分為完全重置和部分重置，完全重置要求所有節(jié)點(diǎn)的單車存量對(duì)于需求量，考慮到完全重置的運(yùn)營(yíng)成本過(guò)高，因此目標(biāo)函數(shù)中除了考慮最小化行駛距離，同時(shí)要考慮最小化未滿足需求的懲罰成本。根據(jù)問(wèn)題定義，對(duì)模型進(jìn)行如下假設(shè)：

1）調(diào)度中心只有一個(gè)，調(diào)度中心、節(jié)點(diǎn)的坐標(biāo)位置和需求已知且固定，不考慮運(yùn)輸中交通狀況的影響。

2）每個(gè)節(jié)點(diǎn)至少訪問(wèn)一次，至多訪問(wèn)兩次。

3）調(diào)度車服務(wù)時(shí)的載重不可超過(guò)其最大承載量。

4）調(diào)度車從調(diào)度中心出發(fā)并最終返回調(diào)度中心，且服務(wù)開始前和結(jié)束后調(diào)度車的載重均為0。

1.2 數(shù)學(xué)模型

定義G=（V，A）為一個(gè)完全圖。V={0}∪（VC）表示網(wǎng)絡(luò)節(jié)點(diǎn)集合，其中0表示調(diào)度中心；VC=∪i∈I Vi表示調(diào)度車對(duì)各站點(diǎn)的訪問(wèn)節(jié)點(diǎn)，I={1，…，n}表示站點(diǎn)集合，Vi={i1，i2 }，i∈I表示調(diào)度車對(duì)站點(diǎn)i的第一次訪問(wèn)和第二次訪問(wèn)；A={（v，w）│v∈V，w∈V，v≠w}表示網(wǎng)絡(luò)中的弧集；對(duì)于SV，δ+（S）={（v，w）│v∈S，wS}，δ-（S）={（v，w）│vS，w∈S}。

模型變量及參數(shù)的含義為：

Ca：給定弧a=（v，w），調(diào)度車從節(jié)點(diǎn)v到節(jié)點(diǎn)w的路徑成本。

φ：節(jié)點(diǎn)需求未滿足的懲罰成本。

pi：調(diào)度開始前節(jié)點(diǎn)i的單車數(shù)量。

p′i：調(diào)度結(jié)束后節(jié)點(diǎn)i期望的單車數(shù)量。

di：di=p′i-pi，表示節(jié)點(diǎn)i的需求，di>0表示節(jié)點(diǎn)i需要運(yùn)來(lái)di輛單車（對(duì)應(yīng)于送貨點(diǎn)），di<0表示節(jié)點(diǎn)i運(yùn)走di輛單車（對(duì)應(yīng)于取貨點(diǎn)），假設(shè)∑i∈Idi =0。

Q：調(diào)度車的最大承載量。

決策變量為：

xa：0-1變量，若調(diào)度車經(jīng)過(guò)弧a時(shí)為1，否則為0。

yv：0-1變量，當(dāng)路徑訪問(wèn)節(jié)點(diǎn)v時(shí)為1，否則為0。

fa：非負(fù)變量，調(diào)度車經(jīng)過(guò)弧a時(shí)的載重。

gv：整數(shù)變量，調(diào)度車在節(jié)點(diǎn)v取貨量（gv<0）或送貨量（gv>0）。VP={v|gv<0}表示取貨點(diǎn)集合，VD={v|gv>0}表示送貨點(diǎn)集合。

SD1PDTSP的數(shù)學(xué)模型可以表示為：

min∑ ?α∈A ca xa+φ∑ ?i∈I |di-gi1-gi2| （1）

s.t.

yi1=1，i∈I （2）

y0=1 （3）

∑a∈δ+（v）xa=∑a∈δ- （v）xa=yv， v∈V （4）

∑a∈δ+ （S）xa≥yv+yw-1， SV，v∈S， w∈V＼S （5）

∑a∈δ-（v）fa-∑a∈δ+（v）fa=gv， v∈V （6）

0≤fa≤Qxa， a∈A （7）

pi+gi1≥0， v∈V （8）

pi+gi1+gi2≥0， v∈V （9）

yv，xa∈{0，1}， v∈V，a∈A （10）

其中：式（1）是本文的目標(biāo)函數(shù)，它由調(diào)度工作的固定成本、運(yùn)輸成本以及懲罰成本組成；式（2）（3）確保每個(gè)節(jié)點(diǎn)均被調(diào)度車訪問(wèn)；式（4）表示車輛流平衡約束；式（5）確保路徑連通；式（6）表示調(diào)度車在節(jié)點(diǎn)v取走（或投放）的數(shù)量等于調(diào)度車離開節(jié)點(diǎn)v后的載重減去調(diào)度車到達(dá)節(jié)點(diǎn)v前的載重；式（7）確保了調(diào)度車裝載量非負(fù)且小于調(diào)度車最大承載量；式（8）、（9）確保各節(jié)點(diǎn)的單車存儲(chǔ)量大等于0，并且確保各節(jié)點(diǎn)的第一次訪問(wèn)先于第二次訪問(wèn)。

2 算法

2.1 算法原理和實(shí)現(xiàn)步驟

變鄰域搜索算法（VNS）的基本思想是通過(guò)局部搜索算法求得局部最優(yōu)解，利用不同的動(dòng)作構(gòu)成的鄰域結(jié)構(gòu)進(jìn)行交替搜索，在集中性和疏散性之間達(dá)到很好的平衡。它能夠在當(dāng)前鄰域中找到最優(yōu)解，又能跳出當(dāng)前鄰域?qū)ふ腋玫慕?，然而變鄰域搜索算法存在收斂速度慢的?wèn)題，解的質(zhì)量依賴合適的鄰域結(jié)構(gòu)集合。

為提升算法擾動(dòng)性，本文提出改進(jìn)變鄰域搜索算法（IVNS），在傳統(tǒng)鄰域結(jié)構(gòu)的基礎(chǔ)上，結(jié)合局部搜索和擾動(dòng)機(jī)制，并且引入模擬退火算法的解接受準(zhǔn)則， 以一定概率接受較差的解。算法的具體流程見圖1。首先隨機(jī)生成一個(gè)初始解。接下來(lái)，連續(xù)應(yīng)用局部搜索、擾動(dòng)機(jī)制，直到滿足停止標(biāo)準(zhǔn)。也就是說(shuō)，當(dāng)前解在某個(gè)鄰域結(jié)構(gòu)中無(wú)法找到更好的解時(shí)以一定的概率激活擾動(dòng)機(jī)制，從而跳出局部最優(yōu)。

2.2 拆分節(jié)點(diǎn)需求（SplitVertex）

本文引入了一個(gè)名為SplitVertex的過(guò)程，對(duì)需求未完全滿足的節(jié)點(diǎn)進(jìn)行額外訪問(wèn)。具體來(lái)說(shuō)分別選擇了取貨和送貨情況下最不平衡的節(jié)點(diǎn)i和j，并且有兩種添加方式：（i）在節(jié)點(diǎn)j之后添加弧（j，i） 和（i，j）；（ii）在節(jié)點(diǎn)i之后添加?。╥，j）和（j，i）。

圖2通過(guò)例子祥細(xì)地描述了該過(guò)程，其中17號(hào)節(jié)點(diǎn)和9號(hào)節(jié)點(diǎn)是最不平衡的。17號(hào)節(jié)點(diǎn)初始有20輛單車，需要取走10輛，即一個(gè)取貨點(diǎn)，而9號(hào)節(jié)點(diǎn)初始沒(méi)有車，需要送來(lái)10輛，即一個(gè)送貨點(diǎn)。圖2（a）給出了一個(gè)可行的解決方案，然而節(jié)點(diǎn)的需求沒(méi)有得到滿足，因?yàn)?7號(hào)節(jié)點(diǎn)只取走了4輛自行車，9號(hào)節(jié)點(diǎn)送來(lái)了4輛自行車。圖2（b）顯示了一種改進(jìn)的解決方案，添加弧（9，17）和（17，9）后可以觀察到，第二次訪問(wèn)是對(duì)第一次訪問(wèn)的補(bǔ)充，滿足了兩個(gè)節(jié)點(diǎn)的需求：車輛在9號(hào)節(jié)點(diǎn)送來(lái)1輛，其余7輛在17號(hào)節(jié)點(diǎn)取走，現(xiàn)已平衡，最后通過(guò)送來(lái)6輛自行車滿足9號(hào)節(jié)點(diǎn)的需求。

2.3 鄰域結(jié)構(gòu)集合和擾動(dòng)機(jī)制設(shè)計(jì)

2.3.1 鄰域結(jié)構(gòu)集合設(shè)計(jì)

在局部搜索過(guò)程中，初始解和擾動(dòng)解可以通過(guò)基于變鄰域下降（VND）的過(guò)程得到改進(jìn)。VND系統(tǒng)地檢查不同類型的鄰域，如果鄰域產(chǎn)生一個(gè)更好的解，那么更新當(dāng)前解并且從第一個(gè)鄰域開始繼續(xù)搜索，否則將在下一個(gè)鄰域進(jìn)行搜索，當(dāng)所有鄰域都無(wú)法完善當(dāng)前解時(shí)，該過(guò)程結(jié)束。

本文共設(shè)計(jì)5個(gè)鄰域結(jié)構(gòu)，具體如下：（1）Swap，交換兩個(gè)節(jié)點(diǎn)的序列；（2）Reinsertion，移除一個(gè)節(jié)點(diǎn)，將其重新插入序列的其他位置；（3）Or_opt2，移除兩個(gè)連續(xù)的節(jié)點(diǎn)，將其重新插入序列的其他位置；（4）Suppression，移除節(jié)點(diǎn)的第二次訪問(wèn)；（5）SplitVertex，拆分節(jié)點(diǎn)需求。表1詳細(xì)地展示了初始解為0-8-7-1-5-3-4-2-6-2-9-0時(shí)每個(gè)鄰域結(jié)構(gòu)的過(guò)程，為便于說(shuō)明，省略了取送貨操作值以及車輛負(fù)載。例如，初始解在Suppression鄰域結(jié)構(gòu)中移除節(jié)點(diǎn)2的第二次訪問(wèn)，得到了新的解0-8-7-1-5-3-4-2-6-9-0。

表1詳細(xì)地展示了鄰域結(jié)構(gòu)的組成過(guò)程，其中初始解為0-8-7-1-5-3-4-2-6-2-9-0。

2.3.2 擾動(dòng)機(jī)制設(shè)計(jì)

每當(dāng)算法進(jìn)入擾動(dòng)機(jī)制時(shí)，隨機(jī)選擇以下兩種機(jī)制：（1）Or_opt3——移除三個(gè)連續(xù)的節(jié)點(diǎn)，將其重新插入序列的其他位置；（2）Suppression——移除節(jié)點(diǎn)的第二次訪問(wèn)。

2.4 解接受規(guī)則

為進(jìn)一步平衡算法的收斂速度與擾動(dòng)性，引入模擬退火算法的解接受準(zhǔn)則，以一定概率接受較差的解，在某個(gè)鄰域結(jié)構(gòu)中無(wú)法找到更好的解時(shí)以一定的概率激活擾動(dòng)機(jī)制，從而跳出局部最優(yōu)，擾動(dòng)機(jī)制激活的頻率隨著迭代次數(shù)的增加而降低。假定當(dāng)前解xc經(jīng)過(guò)VND得到x1，當(dāng)f（x1）>f（xc）時(shí)，以一定概率接受x1。初始狀態(tài)為T0，冷卻系數(shù)為θ，溫度更新為T=T0，其中0<θ<1，θ越接近0溫度下降越快，反之越慢。

2.5 算法終止準(zhǔn)則

由于變鄰域搜索算法與其他現(xiàn)代優(yōu)化算法一樣，并不能保證找到問(wèn)題的全局最優(yōu)解，所以需要另外給出終止條件來(lái)停止搜索。常用的終止準(zhǔn)則有設(shè)置最大迭代次數(shù)、設(shè)置終止溫度Tf、設(shè)置當(dāng)前最優(yōu)解保持不變的最大迭代次數(shù)等。本文采用的方法是設(shè)置當(dāng)前最優(yōu)解保持不變的最大迭代次數(shù)，即如果當(dāng)前的最優(yōu)解在迭代了設(shè)定值次數(shù)后還沒(méi)有找到更好的解，那么認(rèn)為算法收斂，并終止算法。

3 數(shù)值實(shí)驗(yàn)仿真

3.1 測(cè)試環(huán)境

本文算法測(cè)試采用C++編碼通過(guò)Visual Studio Code實(shí)現(xiàn)，在主頻3.2Ghz、內(nèi)存8G的計(jì)算機(jī)上進(jìn)行。

3.2 測(cè)試算例

為測(cè)試算法的有效性，本文結(jié)合共享單車實(shí)際運(yùn)營(yíng)情況， 采用以下方法生成算例。節(jié)點(diǎn)坐標(biāo)在［-100，100］范圍內(nèi)隨機(jī)生成，調(diào)度車容量為20，節(jié)點(diǎn)需求為［-35，35］范圍內(nèi)的整數(shù)，并且所有節(jié)點(diǎn)的需求之和為0。對(duì)于節(jié)點(diǎn)規(guī)模，考慮三類：小規(guī)模的節(jié)點(diǎn)數(shù)為30，中等規(guī)模的節(jié)點(diǎn)數(shù)為50，大規(guī)模的節(jié)點(diǎn)數(shù)為100。每個(gè)規(guī)模各有10個(gè)算例，命名為A～J。

3.3 參數(shù)設(shè)定及參數(shù)尋優(yōu)

改進(jìn)變鄰域算法的初始狀態(tài)T0取值范圍可參照模擬退火算法，一般取1000、2000、3000、4000等，溫度更新函數(shù)中的冷卻系數(shù)θ一般取0. 9、0. 95、0. 98等，當(dāng)前最優(yōu)解保持不變的最大迭代次數(shù)iter根據(jù)問(wèn)題類型的不同可取200至2000不等。

為了更合理地設(shè)置算法的參數(shù)，本文通過(guò)對(duì)節(jié)點(diǎn)規(guī)模為30的十個(gè)算例的計(jì)算進(jìn)行參數(shù)尋優(yōu)。首先，令iter=500，冷卻系數(shù)θ= 0. 95，取T0為1000、2000、3000、4000，計(jì)算結(jié)果如表2所示，當(dāng)T0=3000時(shí)，算法求得的最優(yōu)值最小且運(yùn)行時(shí)間較短，所以取T0=3000。其次，令T0=3000，iter=500，取θ為0.9、0. 95、0.98，計(jì)算結(jié)果如表3所示，當(dāng)θ=0.95時(shí)，算法求得的最優(yōu)值最小，因此取θ=0.95。最后，在以上參數(shù)給定的基礎(chǔ)上，取iter為500、1000、1500，計(jì)算結(jié)果如表4所示，當(dāng)iter=1500時(shí)所得最優(yōu)值最小，因此取iter=1500。

3.4 算法有效性檢驗(yàn)

為驗(yàn)證改進(jìn)變鄰域算法的有效性，本文將IVNS算法與傳統(tǒng)VNS算法進(jìn)行對(duì)比實(shí)驗(yàn)。其中，VNS的擾動(dòng)機(jī)制與IVNS相同，VNS 算法的局部搜索過(guò)程對(duì)擾動(dòng)機(jī)制中產(chǎn)生的當(dāng)前解分別進(jìn)行局部搜索，采用Swap算子或Or-opt2算子，其余參數(shù)設(shè)置相同。

本文運(yùn)用IVNS和VNS分別對(duì)上述30個(gè)算例進(jìn)行求解，兩種算法對(duì)每個(gè)算例進(jìn)行10輪求解，結(jié)果如表5、表6所示。其中，表5展示了兩種算法對(duì)30個(gè)算例的求解結(jié)果最優(yōu)值及其對(duì)應(yīng) CPU 時(shí)間，表6展示了兩種算法對(duì)30個(gè)算例求解結(jié)果的平均值及標(biāo)準(zhǔn)差。

通過(guò)表5求解結(jié)果比較可知，IVSN算法求得的最優(yōu)值優(yōu)于VNS算法，IVNS求解中型算例速度很快，但當(dāng)算例規(guī)模擴(kuò)大到100時(shí)求解時(shí)間急劇增加，可見算法擾動(dòng)性的增加一方面能提高解的質(zhì)量但同時(shí)也花費(fèi)了更久的CPU時(shí)間，但仍在可接受的范圍內(nèi)，可見IVSN算法可以在合理的時(shí)間內(nèi)求得高質(zhì)量的解。此外，通過(guò)表5求解結(jié)果比較可知，IVNS算法的平均值和標(biāo)準(zhǔn)差都更優(yōu)，說(shuō)明使用IVNS能夠更穩(wěn)定地獲得更優(yōu)的解。

4 結(jié)語(yǔ)

本文對(duì)共享單車調(diào)度優(yōu)化問(wèn)題模型進(jìn)行擴(kuò)展，松弛了站點(diǎn)僅訪問(wèn)一次這一條件，允許拆分站點(diǎn)的需求使調(diào)度車能夠?qū)φ军c(diǎn)進(jìn)行兩次訪問(wèn)，令問(wèn)題更具實(shí)際意義，拓展了共享單車調(diào)度優(yōu)化問(wèn)題理論研究，并為共享單車企業(yè)管理運(yùn)營(yíng)提供決策支持。本文還設(shè)計(jì)一種改進(jìn)變鄰域算法，將模擬退火算法的解接受準(zhǔn)則引入其中，以增強(qiáng)算法擾動(dòng)性、擴(kuò)大搜索范圍跳出局部最優(yōu)解，并在后續(xù)的數(shù)值實(shí)驗(yàn)中驗(yàn)證了該算法的有效性和穩(wěn)定性。同時(shí)，本文研究的問(wèn)題及采用的方法還有待提升。一方面，該模型可擴(kuò)展到多輛車、時(shí)間窗限制等，也可考慮將其中的站點(diǎn)作為中轉(zhuǎn)站使其暫時(shí)超過(guò)或不滿足其需求；另一方面，改進(jìn)變鄰域搜索算法在本文中起到了良好的作用，但仍可以嘗試與其他方法如啟發(fā)式算法、機(jī)器學(xué)習(xí)等結(jié)合，以更好地求解該問(wèn)題。

參考文獻(xiàn)：

［1］ ?王涵霄.考慮維修的共享單車調(diào)度優(yōu)化研究［J］. 工業(yè)工程與管理， 2019，24（2）：31-37.

［2］ CHEMLA D. Bike sharing systems： solving the static rebalancing problem［J］. Discrete Optimization， 2013，10（2）： 120-146.

［3］ RAVIV T， TZUR M， FORMA 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.

［4］ DELL′AMICO M. The bike sharing rebalancing problem： mathematical formulations and benchmark instances［J］. Omega-International Journal of Management Science， 2014（45）： 7-19.

［5］ ERDOGAN G. An exact algorithm for the static rebalancing problem arising in bicycle sharing systems［J］. European Journal of Operational Research， 2015， 245（3）： 667-679.

［6］ PAL A， ZHANG Y. Free-floating bike sharing： solving real-life large-scale static rebalancing problems［J］. Transportation Research Part C-Emerging Technologies， 2017（80）： 92-116.

［7］ SCHUIJBROEK J. Inventory rebalancing and vehicle routing in bike sharing systems［J］. European Journal of Operational Research， 2017，257（3）： 992-1004.

［8］ HERNANDEZ-PEREZ H. ?Heuristic algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem［J］. Computers & Operations Research， 2018（97）： 1-17.

［9］ POLAT O. A perturbation based variable neighborhood search heuristic for solving the vehicle routing problem with simultaneous pickup and delivery with time limit［J］. European Journal of Operational Research， 2015，242（2）： 369-382.

［10］ CRUZ F. A heuristic algorithm for a single vehicle static bike sharing， rebalancing problem［J］. Computers & Operations Research， 2017（79）： 19-33.

［11］ HO S C， SZETO W Y. A hybrid large neighborhood search for the static multi-vehicle bike-repositioning problem［J］. Transportation Research Part B-Methodological， 2017（95）： 340-363.

［12］ 張建同，丁燁. 變鄰域模擬退火算法求解速度時(shí)變的VRPTW問(wèn)題［J］. 運(yùn)籌與管理，2019，28（11）：77-84.

［13］ 徐東洋，李昆鵬，鄭飄，等. 多車場(chǎng)多車型多品類供需未匹配與可任意拆分取送貨車輛路徑問(wèn)題優(yōu)化［J］. 管理學(xué)報(bào)，2020，17（7）：1086-1095.