[發(fā)明專利]一種基于多類型自行車裝卸的公共租賃自行車調(diào)度方法

在審

• 申請?zhí)枺?/td>: 201711128839.3
• 申請日: 2017-11-14
• 公開（公告）號: CN107832957A
• 公開（公告）日: 2018-03-23
• 發(fā)明（設(shè)計）人: 魏明;孫榮;魯鳳;王晗;許致火;劉志東
• 申請（專利權(quán)）人: 南通大學(xué)
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q30/06
• 代理公司: 南京瑞弘專利商標(biāo)事務(wù)所(普通合伙)32249
• 代理人: 顧森燕

技術(shù)領(lǐng)域：

本發(fā)明涉及交通出行領(lǐng)域，尤其涉及一種基于多類型自行車裝卸的公共租賃自行車調(diào)度方法。

背景技術(shù)：

公共租賃自行車作為一種新型的交通方式，兼有公共交通和慢行交通的特點，越來越受到人們的青睞。由于城市的功能布局、經(jīng)濟發(fā)展差異，這引起租賃網(wǎng)絡(luò)上的公共自行車供需關(guān)系時空分布不平衡，需要將部分租賃點的多余自行車合理地提前調(diào)配至缺少自行車的租賃點，如何合理安排卡車訪問租賃點的順序并確定其裝卸量至關(guān)重要。

公共租賃自行車調(diào)度(Rental Bicycle Dispatching Problem，簡稱RBDP)是車輛路徑問題(Vehicle Routing Problem，簡稱VRP)的一種拓展形式，兩者區(qū)別在于：1)租賃點的缺少或多余自行車數(shù)量部分決定了它們在卡車路徑的順序；2)同時確定確定卡車在租賃點的裝卸數(shù)量，尤其是考慮缺少自行車的各個租賃點的服務(wù)水平。因此，RBDP比VRP復(fù)雜的多，近年來吸引了國內(nèi)外學(xué)者的廣泛關(guān)注。目前，國內(nèi)外學(xué)者從運籌與優(yōu)化角度研究了眾多RBDP的拓展模型，主要分為先裝后卸(卡車訪問供應(yīng)點裝完自行車后，才訪問需求點卸載自行車)、同時裝卸(卡車同時訪問供應(yīng)或需求點，但是滿足需求點的自行車需求)兩種研究思路，前者比后者調(diào)度效率低，但是操作相對容易。

有上可知，現(xiàn)有SBRP較少同時涉及多車型、多調(diào)度中心對公共租賃自行車調(diào)度線路的影響，尤其是每個租賃點的不同車型同時缺少或多余引起卡車既裝又卸，這比傳統(tǒng)VRP復(fù)雜的多，已有SBRP和VRP均不能適用。多車型的RBDP一般在旅游景區(qū)比較常見，居民可以在某租賃點借還單、雙和多人自行車。

發(fā)明內(nèi)容：

為了解決上述問題，本發(fā)明提供了一種能夠?qū)崿F(xiàn)兼顧配送里程最少和乘客滿意度最大的調(diào)度目標(biāo)，針對某種車型自行車，將部分租賃點的多余車輛運輸至缺少車輛的租賃點的技術(shù)方案：

一種基于多類型自行車裝卸的公共租賃自行車調(diào)度方法，主要包括構(gòu)建多類型自行車裝卸的公共租賃自行車調(diào)度優(yōu)化模型，以及求解公共租賃自行車調(diào)度優(yōu)化模型的基于遺傳算法的兩階段算法，其中構(gòu)建多類型車輛裝卸的公共租賃自行車調(diào)度優(yōu)化模型包括核心輸入數(shù)據(jù)準(zhǔn)備及其符號變量、核心輸出數(shù)據(jù)及其決策變量、目標(biāo)函數(shù)和約束條件，基于遺傳算法的兩階段算法，包括第一階段利用GA搜索可行卡車訪問租賃點的順序，第二階段利用啟發(fā)式算法計算卡車在各個租賃點的裝卸方案。

作為優(yōu)選，構(gòu)建多類型自行車裝卸的公共租賃自行車調(diào)度優(yōu)化模型的核心輸入數(shù)據(jù)準(zhǔn)備及其符號變量，是每個租賃點的一或多種車型的供需數(shù)量，以及最少滿足需求點的缺少自行車數(shù)比例，包括：

(1)某個區(qū)域的租賃點和調(diào)度中心集合記為N和O；所有租賃點的停放自行車類型集合記為M；卡車集合記為K，其最大容量和最大里程為C和D；

(2)租賃點關(guān)于自行車類型(自行車類型m的所占存儲空間記為r_m)的自行車需求量，若則多余；否則缺少；

(3)公共自行車租賃點(調(diào)度中心)i和j之間距離，記為d_ij。

作為優(yōu)選，構(gòu)建多類型自行車裝卸的公共租賃自行車調(diào)度優(yōu)化模型的核心輸出決策變量及其符號變量，是卡車訪問租賃點的順序，以及卡車在每個租賃點的不同自行車類型裝卸數(shù)量，包括：確定車輛k依次訪問租賃點i和j的次序，即車輛k訪問租賃點i時自行車類型m的裝卸數(shù)量，即車輛k是否防問租賃點i，即輔助變量，即U_ik。

作為進(jìn)一步優(yōu)選，構(gòu)建多類型自行車裝卸的公共租賃自行車調(diào)度優(yōu)化模型的目標(biāo)函數(shù)，是在確保每個租賃點在不同車型需求最低服務(wù)水平情況下，兼顧各個租賃點的滿意度最大和總配送里程最少為目標(biāo)，其中以各個租賃點的滿意度最大和總配送里程最少為目標(biāo)，即

γ為最少滿足需求點的缺少自行車數(shù)比例，即服務(wù)水平；c₀和c₁為里程費用和滿意度費用，由于目標(biāo)函數(shù)蘊含針對某種車型自行車，若供大于需，則滿意度為1，此時所有需求點被滿足；否則，所有供應(yīng)點在調(diào)度后自行車存量為0，通過該優(yōu)化調(diào)度目標(biāo)，在現(xiàn)有租賃點的供需情況下，盡可能確保自行車系統(tǒng)的服務(wù)水平。