《共享單車站點調(diào)度模型和算法分析綜述》2700字

共享單車站點調(diào)度模型和算法分析綜述1.1問題描述共享單車調(diào)度問題不同于傳統(tǒng)的車輛路徑問題，其無序性和靈活性對調(diào)度系統(tǒng)的效率要求更高。需要滿足各站點某一時段的單車需求，使站點之間達(dá)到供需平衡的狀態(tài)，降低企業(yè)的調(diào)度成本，提升用戶的滿意度。共享單車的調(diào)度問題包括站點需求預(yù)測和站點間的調(diào)度優(yōu)化兩個子問題，第三章已經(jīng)對站點的需求進(jìn)行了預(yù)測分析，為單車調(diào)度做了準(zhǔn)備工作。本章將在第三章的基礎(chǔ)上建立站點調(diào)度優(yōu)化模型。描述為：在未來某時間段采用單一車輛進(jìn)行車輛調(diào)度，并且根據(jù)各個站點的需求量和實際單車量的數(shù)量差進(jìn)行調(diào)度任務(wù)，首先從配送中心出發(fā)，配送車輛的最大容量固定不變，但各個共享單車站點的需求量會隨著時間段，氣候等因素實時發(fā)生變化，要求在不重復(fù)訪問各個站點且滿足各個站點的單車需求的前提下，制定出最短調(diào)度路線。1.2共享單車調(diào)度模型1.2.1基本假設(shè)共享單車調(diào)度模型有如下假設(shè)：站點：每個站點都有調(diào)入調(diào)出需求，且站點需求在調(diào)度期間穩(wěn)定不變，各個站點具體的需求量由第四章的預(yù)測模型給出，各個站點的調(diào)度量之和不能大于調(diào)度車輛的最大容量，最佳調(diào)度路線必須要滿足各個站點的需求量，每個站點在調(diào)度路線中不能重復(fù)，即站點不能重復(fù)訪問,配送車輛的最大容量Maxbike為100，站點的訪問狀態(tài)用一個數(shù)組表示，如果站點已經(jīng)被訪問了 就用0表示，若沒有被訪問，用1表示。共享單車：調(diào)度區(qū)域內(nèi)的單車類型唯一，且總數(shù)量不變，站點區(qū)域內(nèi)不存在壞損車輛；每一輛單車只能在結(jié)束服務(wù)前只能被一個用戶使用調(diào)度區(qū)域：調(diào)度車輛的行駛路線的出發(fā)地為調(diào)度中心，目的地必須也是調(diào)度中心，即調(diào)度路線必須為一個閉合環(huán)線時間間隔：以小時為單位，一個調(diào)度周期為一個小時，選取早高峰和晚高峰的時間段執(zhí)行調(diào)度任務(wù)1.2.2變量及參數(shù)說明本文在對共享單車調(diào)度問題分析的基礎(chǔ)上，建立以調(diào)度路線最短為目標(biāo)的調(diào)度模型，對模型所用的變量及參數(shù)做如下說明：符號參數(shù)：表4-1參數(shù)符號及意義參數(shù)符號參數(shù)含義站點i到站點j的距離配送中心到站點i的距離站點j返回到配送中心的距離Maxbike調(diào)度貨車最大負(fù)載量決策變量：表4-2決策變量及意義決策變量變量含義站點i的需求量，若大于0，則表示站點i的單車供大于求，應(yīng)執(zhí)行調(diào)出操作，否則站點i供不應(yīng)求，應(yīng)執(zhí)行調(diào)入操作若等于1，表示調(diào)度貨車訪問了從站點i到站點j之間的路線，否則，則表示沒有訪問過集合變量：S:調(diào)度站點集合，S={0,1,2,...,m},其中m為50;C：站點的實時需求量，.1.2.3模型構(gòu)建根據(jù)上一節(jié)的參數(shù)定義和模型的假設(shè)，建立以最短調(diào)度路線為目標(biāo)的調(diào)度模型，如公式4-1所示：其中模型滿足以下約束條件：由上可知，式4-2表示在同一條配送路線上，各個站點調(diào)度共享單車數(shù)量不能超過調(diào)度貨車的最大容量，式4-3和式4-4表示在調(diào)度共享單車的路線中，各站點要求只能出現(xiàn)一次。1.3求解共享單車調(diào)度模型的蟻群算法1.3.1求解算法概述共享單車調(diào)度問題實際是車輛路徑問題的一個分支，屬于NP-hard問題，即問題的輸入數(shù)據(jù)越大，求解難度越大。目前，求解此類問題的主要方法包括精確算法和啟發(fā)式算法。精確算法適用于求解問題規(guī)模數(shù)據(jù)較小的車輛調(diào)度問題，而啟發(fā)式算法在求解大規(guī)模問題時具有極大的優(yōu)勢。啟發(fā)式算法分為傳統(tǒng)啟發(fā)式算法和現(xiàn)代啟發(fā)式算法，傳統(tǒng)的啟發(fā)式算法主要通過領(lǐng)域搜索的方式，不斷優(yōu)化初始解到當(dāng)前解的過程，得到滿足約束條件的新解，雖能在短時間求解問題，但是容易陷入局部最優(yōu)，現(xiàn)代啟發(fā)式算法結(jié)合了人工智能的方法，適合求解大規(guī)模問題，故本文采用蟻群算法求解上述站點調(diào)度模型，得到最優(yōu)調(diào)度路徑。1.3.2蟻群算法的原理及流程蟻群算法(antcolonyoptimization,ACO)，又稱螞蟻算法，是一種在圖中尋找優(yōu)化路徑的算法。螞蟻在運動過程中，會留下信息素，并且隨著螞蟻增加移動距離，信息素濃度會慢慢減少，所以距離最短時，信息素的濃度也是最濃的，而且螞蟻也會根據(jù)信息素的濃度去尋找方向，信息素濃度越大，該條路徑被選擇的概率也就越大。螞蟻的運動過程可以歸納為：當(dāng)附近沒有信息素時，螞蟻的運動具有不確定性，有一定的概率會選擇其他路徑。當(dāng)附近有信息素的時候，螞蟻會根據(jù)信息素的濃度選擇運動方向。找食物時，螞蟻會留下與出發(fā)點有關(guān)的信息素，返回出發(fā)點時，螞蟻會留下關(guān)于食物的信息素，隨著螞蟻移動距離的增加，信息素會逐漸變淡，隨著時間的推移，信息素會逐漸揮發(fā)。首先需要對算法中涉及到的參數(shù)進(jìn)行初始化操作，然后隨機投放螞蟻，當(dāng)螞蟻將所有站點遍歷完后再對路徑中的信息素濃度進(jìn)行更新，判斷是否已經(jīng)達(dá)到條件終止，如果達(dá)到了終止條件就可以得出最優(yōu)解。本文中的共享單車調(diào)度問題的難點在于如何選擇下一個站點以及如何更新信息素。解決方案為采用輪盤的方式選擇下一個站點，信息素的更新采用蟻周模型，在蟻周模型中，第k只螞蟻在站點i和站點j之間的路徑上釋放的信息素濃度可以表示為：1.3.3蟻群算法的設(shè)計思路根據(jù)上述算法的基本思想，本文采用基于蟻群的啟發(fā)式算法解決共享單車的調(diào)度問題。蟻群算法的參數(shù)：包括ALPHA(信息啟發(fā)因子)，ALPHA值越大，螞蟻重復(fù)選擇路徑的可能性就越大，相反蟻群搜索范圍就會越小，容易陷入局部最優(yōu)。BETA值(期望啟發(fā)式因子)越大，蟻群大概練會選擇局部較短的路徑，算法的收斂速度會加快，RHO(信息揮發(fā)因子)為信息素的初始濃度，可以表示為調(diào)度貨車的最大容量、蟻群的數(shù)量等。獲取禁忌列表：在訪問各個站點時，需要考慮站點調(diào)度單車數(shù)量的正負(fù)值。如果為正，需要保證配送車上已有的單車數(shù)量與需要調(diào)度的單車數(shù)量之和不超過調(diào)度車的最大容量，若為負(fù)，需要保證配送車上已有的單車數(shù)量與該配送單車數(shù)量之和不小于0，該站點才可以加入配送路線中。輪盤賭選擇站點：以輪盤賭方法進(jìn)行站點的選擇，螞蟻選擇站點的概率與信息素濃度和站點之間的距離有關(guān)，與信息素濃度成正比，與距離成反比，即：式(4-6)中，表示為選擇概率，為信息啟發(fā)式因子，為期望啟發(fā)式因子，為信息素濃度，為站點i到站點j的距離。獲悉每個站點被選擇的概率之后，求所有概率的總和，最后得到選擇到達(dá)各個站點真正的概率，選擇用輪盤的方法獲得每個站點的概率值，來防止每次只選擇最大概率的站點，輪次相減到各個站點的概率值，當(dāng)概率值為負(fù)數(shù)之后，得到下一個站點的序號，所有站點都是同樣的操作，直到遍歷完所有的站點。信息素衰減：蟻群算法一般將信息素濃度設(shè)置為一個較小的數(shù)，在完成一次遍歷之后，信息素需要更新，信息素主要有兩方面的影響因素：螞蟻在路徑中留下的信息素和信息素的減少，因此，信息素濃度可以為：隨著站點之間的信息素不斷的減少，對螞蟻的選擇會有一定程度的影響，故在不斷迭代的過程