數(shù)模論文-公交車(chē)調(diào)度問(wèn)題的研究-工程數(shù)學(xué)學(xué)報(bào)

第4頁(yè)（共7頁(yè)）公交車(chē)調(diào)度問(wèn)題的研究（國(guó)防科技大學(xué)，長(zhǎng)沙410073）編者按：該論文建立了兩個(gè)多目標(biāo)規(guī)劃模型，尤其是選擇運(yùn)力與運(yùn)量的平衡作為目標(biāo)函數(shù)有新意。尋找最小車(chē)輛數(shù)的方法正確。單車(chē)場(chǎng)模型作為雙車(chē)場(chǎng)模型的補(bǔ)充，雖然簡(jiǎn)單，也有自身特點(diǎn)。運(yùn)行發(fā)車(chē)時(shí)刻表切實(shí)可行，接近最優(yōu)解。摘要:本題為帶軟時(shí)間窗的單線(xiàn)路單車(chē)型的公交調(diào)度問(wèn)題，針對(duì)其多目標(biāo)、多變量的動(dòng)態(tài)特點(diǎn)，我們?yōu)闈M(mǎn)足不同的實(shí)際需求建立兩個(gè)多目標(biāo)規(guī)劃模型：雙車(chē)場(chǎng)模型和單車(chē)場(chǎng)模型。雙車(chē)場(chǎng)模型的主要目標(biāo)是使運(yùn)客能力與運(yùn)輸需求（實(shí)際客運(yùn)量）達(dá)到最優(yōu)匹配，單車(chē)場(chǎng)模型的主要目標(biāo)是使乘客的平均不方便程度和公交公司的成本達(dá)最小，其目的都是為了兼顧乘客與公司雙方的利益。兩個(gè)模型的主體都是采用時(shí)間步長(zhǎng)法，模擬實(shí)際的運(yùn)營(yíng)過(guò)程，從而得出符合實(shí)際要求的調(diào)度方案：靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度方案。關(guān)鍵字：公交車(chē)調(diào)度；軟時(shí)間窗；滿(mǎn)載率；時(shí)間步長(zhǎng)法一、問(wèn)題分析我們分析該問(wèn)題為一帶軟時(shí)間窗的單車(chē)型運(yùn)輸問(wèn)題。由已知條件無(wú)法確定是單車(chē)場(chǎng)問(wèn)題還是多車(chē)場(chǎng)問(wèn)題，故我們分別建立兩個(gè)模型：雙車(chē)場(chǎng)模型和單車(chē)場(chǎng)模型。其中，雙車(chē)場(chǎng)模型認(rèn)為車(chē)站A13和車(chē)站A0分別有車(chē)場(chǎng)A和B存車(chē)，即均可作為始發(fā)站和終點(diǎn)站，上行和下行路線(xiàn)獨(dú)立運(yùn)行；單車(chē)場(chǎng)模型認(rèn)為A0同時(shí)為上行終點(diǎn)和下行起點(diǎn)，它有轉(zhuǎn)運(yùn)能力但沒(méi)有存車(chē)能力，這樣實(shí)際上可將單車(chē)場(chǎng)方式理解為環(huán)線(xiàn)行駛。二、模型假設(shè)（略）三、模型的建立與求解㈠雙車(chē)場(chǎng)模型⒈模塊一：發(fā)車(chē)時(shí)刻表的確定依據(jù)前面的分析，兼顧乘客與公交公司雙方的利益，分別對(duì)單程的上行路線(xiàn)和下行路線(xiàn)建立如下的多目標(biāo)規(guī)劃模型：目標(biāo)函數(shù)Ⅰ供求的最優(yōu)匹配min∑(Qi×βi-Vi)2Ⅱ各時(shí)段的發(fā)車(chē)車(chē)次均最小min{Ni}約束條件①各時(shí)段的平均滿(mǎn)載率限制0.5≤βi≤1.2②供求匹配比限制α≤k符號(hào)說(shuō)明：Ni第i時(shí)段發(fā)車(chē)次數(shù)βi第i時(shí)段的平均滿(mǎn)載率βi=Ri/(c×Ni)Ri為第i時(shí)段的總上車(chē)人數(shù),c=100人/車(chē)次α供求匹配比α=(∑Vi)/(∑Qi)k控制參數(shù)Qi第i時(shí)段運(yùn)客能力（人×公里）Qi=第i時(shí)段發(fā)車(chē)次數(shù)Ni×每輛車(chē)標(biāo)準(zhǔn)載客量c×單程(上行或下行)總運(yùn)行距離L其中，上行時(shí)，L=14.58公里;下行時(shí)，L=14.61公里Vi第i時(shí)段的需要運(yùn)客量（人×公里）Vi=j∈(13,12…,1,0),上行方向；j∈(0，2，3，…13),下行方向。其中，xji為第i時(shí)段內(nèi)Aj站的上車(chē)人數(shù)；yji為第i時(shí)段內(nèi)Aj站的下車(chē)人數(shù)Lj為Aj站距該單程方向上終點(diǎn)站的距離。即認(rèn)為上車(chē)乘客的運(yùn)載距離為正，下車(chē)乘客的運(yùn)載距離為負(fù)。1.2目標(biāo)函數(shù)說(shuō)明：目標(biāo)函數(shù)Ⅰ使第i時(shí)段的運(yùn)客能力Qi與運(yùn)輸需求（實(shí)際客運(yùn)量）Vi達(dá)到最優(yōu)匹配,βi反映滿(mǎn)載率高低的影響。目標(biāo)函數(shù)Ⅱ使高峰期所發(fā)車(chē)次，即單位時(shí)段所發(fā)的最大車(chē)次，在滿(mǎn)足約束條件下盡可能少，以使總共需要的車(chē)輛數(shù)較少。1.3約束條件說(shuō)明：條件①是限制滿(mǎn)載率滿(mǎn)足運(yùn)營(yíng)調(diào)度要求，是考慮了乘客的利益。條件②是限制供求匹配比α小于常數(shù)k。我們根據(jù)參數(shù)k的變動(dòng)量分別進(jìn)行模擬，從而篩選最恰當(dāng)?shù)膋值。注：為使始發(fā)站車(chē)場(chǎng)的每天起始時(shí)刻的車(chē)輛數(shù)保持不變，需使總發(fā)車(chē)次數(shù)與總收車(chē)次數(shù)相等，即必須使單程車(chē)次總數(shù)達(dá)到匹配（N1=N2），而N1不能減少（受滿(mǎn)載率限制），因此我們?cè)谇蠼庀滦蟹较虻腘i時(shí)增加約束∑Ni2=N1.在增添約束條件∑Ni2=N1之后，用二次規(guī)劃求得各時(shí)段發(fā)車(chē)次數(shù)Ni1和Ni2.⒉模塊二運(yùn)營(yíng)過(guò)程的模擬在這部分，我們采用時(shí)間步長(zhǎng)法，根據(jù)假設(shè)一個(gè)時(shí)段內(nèi)發(fā)車(chē)間隔時(shí)間ti相等，則ti可由Ni確定，從而得到發(fā)車(chē)時(shí)刻表。按此發(fā)車(chē)時(shí)刻表模擬實(shí)際運(yùn)行過(guò)程，目標(biāo)是確定滿(mǎn)足時(shí)刻表的最小車(chē)輛數(shù)n，統(tǒng)計(jì)各項(xiàng)運(yùn)營(yíng)指標(biāo)，搜索最優(yōu)調(diào)度方案。2.1模擬子程序一：確定最小車(chē)輛數(shù)目n根據(jù)“按流發(fā)車(chē)”和“先進(jìn)先出”的原則，對(duì)起點(diǎn)站，在發(fā)車(chē)時(shí)刻應(yīng)至少有一輛車(chē)可以發(fā)出（處于等待發(fā)車(chē)狀態(tài)）。若有多輛車(chē)，則先進(jìn)站者先發(fā)車(chē)，其余車(chē)輛“排隊(duì)”等候；若無(wú)車(chē)可發(fā)，則出現(xiàn)“間斷”。完整的運(yùn)營(yíng)過(guò)程應(yīng)保證車(chē)輛嚴(yán)格按時(shí)刻表發(fā)車(chē)，不發(fā)生間斷。設(shè)A13站和A0站分別有車(chē)場(chǎng)A和B,從車(chē)場(chǎng)中不斷有車(chē)發(fā)出，同時(shí)接受車(chē)進(jìn)場(chǎng)，則車(chē)場(chǎng)中的車(chē)的數(shù)目是隨時(shí)間變化的狀態(tài)量。用Na和Nb來(lái)描述車(chē)場(chǎng)A和車(chē)場(chǎng)B中要滿(mǎn)足車(chē)流不間斷所需的最小數(shù)目，分別搜索其在運(yùn)行過(guò)程中的最大值，則所需最小車(chē)量數(shù)目n=Na+Nb。模擬子程序二：統(tǒng)計(jì)各項(xiàng)運(yùn)營(yíng)指標(biāo)確定各項(xiàng)運(yùn)營(yíng)指標(biāo)，采用模擬統(tǒng)計(jì)的計(jì)算方法，對(duì)不同的運(yùn)營(yíng)指標(biāo)進(jìn)行定量計(jì)算，主要功能是通過(guò)定量分析運(yùn)營(yíng)指標(biāo)來(lái)檢驗(yàn)方案的可行性，以確定方案調(diào)整。注：由于車(chē)次與發(fā)車(chē)時(shí)刻一一對(duì)應(yīng)，而車(chē)輛的隊(duì)列順序是不發(fā)生改變，因而對(duì)所需車(chē)輛進(jìn)行統(tǒng)一編號(hào)，則對(duì)每一車(chē)次，與其對(duì)應(yīng)的車(chē)輛編號(hào)是確定的，故我們直接對(duì)第k次車(chē)進(jìn)行考察。1i為非早高峰期時(shí)。ti∈{1,2,3…}注:1.目標(biāo)函數(shù)說(shuō)明：目標(biāo)函數(shù)Ⅰ使總車(chē)輛數(shù)目最小，即使公司的投資成本達(dá)到最小。目標(biāo)函數(shù)Ⅱ使總車(chē)次數(shù)最小，即使公司的運(yùn)營(yíng)成本達(dá)到最小。目標(biāo)函數(shù)Ⅲ是使所有顧客的平均不方便程度達(dá)到最小。2.約束③主要是考慮到可操作性,發(fā)車(chē)間隔劃分到秒一級(jí)，公交司機(jī)是沒(méi)法把握的,故最小只能劃分到分一級(jí),那么發(fā)車(chē)間隔就應(yīng)是1分的整數(shù)倍2.模型的求解本模型是多目標(biāo)、多約束的優(yōu)化模型，很難求出全局最優(yōu)解，所以我們先將多目標(biāo)規(guī)化簡(jiǎn)，再仿真模擬運(yùn)營(yíng)過(guò)程求解。轉(zhuǎn)化為單目標(biāo)的求解思路如下：給出初始發(fā)車(chē)時(shí)刻表給出初始發(fā)車(chē)時(shí)刻表→模擬客運(yùn)數(shù)據(jù)→運(yùn)營(yíng)→統(tǒng)計(jì)指標(biāo)→結(jié)論←人工分析客流分布（平均分布）→數(shù)據(jù)2.1模型化簡(jiǎn)化簡(jiǎn)多目標(biāo)問(wèn)題，我們可以有三個(gè)出發(fā)點(diǎn)：①分析各目標(biāo)之間相關(guān)聯(lián)的數(shù)學(xué)關(guān)系，減少目標(biāo)函數(shù)數(shù)目或約束條件數(shù)目。②依限定條件，針對(duì)具體數(shù)據(jù)挖掘隱含信息以降低求解難度。③分析各目標(biāo)權(quán)重，去掉影響很小的目標(biāo)函數(shù)，從而達(dá)到簡(jiǎn)化目的。分析目標(biāo)Ⅱ與Ⅲ存在數(shù)學(xué)關(guān)聯(lián)，發(fā)現(xiàn)總車(chē)次越多，乘客不方便程度越小。因此y2與y3不能同時(shí)取最小值。我們認(rèn)為Ⅲ為主要目標(biāo)，故主要考慮目標(biāo)函數(shù)Ⅲ。從具體數(shù)據(jù)可知，在上行方向7:00~8:00,A13站上車(chē)人數(shù)達(dá)3626人，平均每分鐘到達(dá)60人，A12站上車(chē)634人而下車(chē)僅205人，為客流量最大的時(shí)段，發(fā)車(chē)間隔時(shí)間至少需要2分鐘。由平均速度20公里/小時(shí)及環(huán)行距離，可得到此時(shí)至少需45輛車(chē)。.由以上分析將原模型簡(jiǎn)化為：目標(biāo)函數(shù)：y1=miny2=minMs.t.同上運(yùn)營(yíng)過(guò)程模擬⑴初始時(shí)刻表的產(chǎn)生方法原則上初始時(shí)刻表可以隨機(jī)產(chǎn)生，然后模擬判斷搜索出較優(yōu)解，但這樣搜索量太大，且很難保證有一個(gè)收斂結(jié)果。因此我們采用人機(jī)交互的方式，首先分析數(shù)據(jù)得出比較合理的發(fā)車(chē)時(shí)間間隔的近似值，再在其附近搜索，產(chǎn)生初始時(shí)刻表。表四為初始發(fā)車(chē)時(shí)間間隔表四：初始發(fā)車(chē)時(shí)刻表時(shí)段5~66~77~88~99~1010~1111~1212~1313~14ti1032388888時(shí)段14~1515~1616~1717~1818~1919~2020~2121~2222~23ti8832310101010⑵模擬運(yùn)營(yíng)過(guò)程，統(tǒng)計(jì)各指標(biāo)由于模擬運(yùn)營(yíng)過(guò)程與雙車(chē)場(chǎng)模型大同小異，故我們?cè)诖瞬辉僭斒觥＝Y(jié)果及統(tǒng)計(jì)分析對(duì)仿真產(chǎn)生的多組發(fā)車(chē)時(shí)刻表進(jìn)行模擬獲得最小的Y=5.6分,我們把這一組解做為我們的局部最優(yōu)解,其結(jié)果(其中統(tǒng)計(jì)指標(biāo)用來(lái)描述我們以怎樣的程度照顧雙方利益)如下:⑴總車(chē)數(shù)理想處理平均速度得總車(chē)數(shù)為45輛，加2輛應(yīng)急，為47輛；考慮高峰期車(chē)速小于20km/h，高峰期人流量大，是造成高峰期速度稍低于20公里/小時(shí)的主因，那么通過(guò)人流量數(shù)據(jù)和20公里/小時(shí)就可大致推算7：00-8：00速度約為18公里/小時(shí)。這樣高峰期的最小總車(chē)數(shù)45修正為50輛，加2輛應(yīng)急最終為52輛。⑵全天總車(chē)次M=253×2=506次⑶發(fā)車(chē)時(shí)刻表見(jiàn)表五（用各時(shí)段發(fā)車(chē)間隔時(shí)間簡(jiǎn)述）表五：?jiǎn)诬?chē)場(chǎng)各時(shí)段的發(fā)車(chē)間隔時(shí)段5~66~77~88~99~1010~1111~1212~1313~14ti1022246668時(shí)段14~1515~1616~1717~1818~1919~2020~2121~2222~23ti863237101010注：5：00-6：00只是一種統(tǒng)計(jì)劃分，首發(fā)車(chē)可以在5：00之前，也可在5：00之后。當(dāng)然當(dāng)不知道其它原則時(shí)可以假設(shè)首發(fā)車(chē)為5：00發(fā)。對(duì)單車(chē)場(chǎng)下行線(xiàn)始發(fā)為5：45與數(shù)據(jù)相吻合。5：00-6：00上行線(xiàn)共855人上車(chē)；下行線(xiàn)共50人。其可能原因之一就是上行在5：00-6：00都有車(chē)可統(tǒng)計(jì)；而下行只在5：45-6：00中有車(chē)可統(tǒng)計(jì)統(tǒng)計(jì)指標(biāo)：⑴乘客平均候車(chē)時(shí)間y3=5.6分⑵平均滿(mǎn)載率β0=66.4%結(jié)論分析：由上面兩個(gè)圖表可見(jiàn)我們的調(diào)度方案基本上能滿(mǎn)足乘客候車(chē)時(shí)間的限制，高峰期乘客在5分鐘內(nèi)等到車(chē)的概率為92.9%,非高峰期乘客在10分鐘內(nèi)等到車(chē)的概率為89.7%.調(diào)度方案：（見(jiàn)表六）表六：?jiǎn)诬?chē)場(chǎng)動(dòng)態(tài)調(diào)度方案時(shí)段5~66~77~88~99~1010~1111~1212~1313~14所需車(chē)輛數(shù)104652462416161614時(shí)段14~1515~1616~1717~1818~1919~2020~2121~2222~23所需車(chē)輛數(shù)14163046301410108五、模型的進(jìn)一步討論1.關(guān)于采集運(yùn)營(yíng)數(shù)據(jù)的討論由于我們假設(shè)乘客到站服從均勻分布，而實(shí)際中乘客到站時(shí)間不可能都服從均勻分布。特別是在高峰期的情況下，乘客到站時(shí)間的不均勻分布就會(huì)使模型結(jié)論誤差較大。我們建議以下幾種改進(jìn)采集方式的方法：⑴采取不等的統(tǒng)計(jì)人數(shù)的間隔時(shí)間在高峰期的情況下，為削弱乘客到站時(shí)間的不均勻分布帶來(lái)的影響，可適當(dāng)減小統(tǒng)計(jì)的間隔時(shí)間但統(tǒng)計(jì)時(shí)間加密應(yīng)有一定限度。對(duì)客流量很小的時(shí)段，我們可適當(dāng)增大統(tǒng)計(jì)的間隔時(shí)間，不必要每小時(shí)都統(tǒng)計(jì)一次。⑵增加能反應(yīng)有關(guān)滯留人數(shù)的統(tǒng)計(jì)數(shù)據(jù)。⑶按相等到站人數(shù)來(lái)區(qū)分時(shí)間段的統(tǒng)計(jì)方法是統(tǒng)計(jì)達(dá)到一定到站人數(shù)時(shí)的時(shí)間點(diǎn)，即可由此判斷乘客到站的大概分布情況，有利于按其分布的疏密進(jìn)行車(chē)輛調(diào)度，以更好的滿(mǎn)足乘客的需要。其缺點(diǎn)是不易確定相等人數(shù)間隔的大小，可操作性不高；其優(yōu)點(diǎn)是能較為準(zhǔn)確地反映客流量的變化情況。2.對(duì)調(diào)度方案的進(jìn)一步討論我們依據(jù)假設(shè)：各時(shí)段內(nèi)乘客到站時(shí)間服從均勻分布，從而認(rèn)為各時(shí)段內(nèi)的發(fā)車(chē)時(shí)間間隔相等。我們?cè)谀Ｐ偷母倪M(jìn)中，可考慮對(duì)不等的發(fā)車(chē)時(shí)間間隔進(jìn)行模擬，并與等間距的結(jié)果進(jìn)行比較。3.單車(chē)場(chǎng)調(diào)度方案與雙車(chē)場(chǎng)調(diào)度方案的選用由結(jié)果分析可知單車(chē)場(chǎng)調(diào)度方案減少了公司的前期投資成本；雙車(chē)場(chǎng)調(diào)度方案的運(yùn)營(yíng)成本小，更好的兼顧到乘客與公司雙方的利益。我們建議，在有雙車(chē)場(chǎng)的條件下選取雙車(chē)場(chǎng)調(diào)度方案更好。當(dāng)需進(jìn)行路線(xiàn)規(guī)劃，需要選取單車(chē)場(chǎng)或雙車(chē)場(chǎng)時(shí)，建議根據(jù)實(shí)際所需成本來(lái)選取方案。六、模型的評(píng)價(jià)本文的優(yōu)點(diǎn)如下：模型的主體是采用時(shí)間步長(zhǎng)法，模擬生成的發(fā)車(chē)時(shí)刻表的實(shí)際運(yùn)行過(guò)程，準(zhǔn)確性高，容量大，邏輯性嚴(yán)格，計(jì)算速度快，具有較強(qiáng)的說(shuō)服力和適應(yīng)能力。定義了能定量衡量我們的調(diào)度方案對(duì)乘客和公交公司雙方利益滿(mǎn)足程度的統(tǒng)計(jì)指標(biāo)。在求最少車(chē)輛數(shù)時(shí)，將兩個(gè)車(chē)場(chǎng)看作兩個(gè)發(fā)射源，通過(guò)對(duì)兩個(gè)車(chē)場(chǎng)的存車(chē)狀態(tài)的實(shí)時(shí)模擬，形成不間斷的運(yùn)營(yíng)過(guò)程，從而求得所需車(chē)輛數(shù)目。本文的缺點(diǎn)是：對(duì)于運(yùn)營(yíng)數(shù)據(jù)的采集方式，只給出了一些原則和想法，沒(méi)有經(jīng)過(guò)仿真驗(yàn)證。對(duì)于乘客到站的分布，直接假設(shè)為均勻分布，沒(méi)有對(duì)其他分布的情況再作討論。參考文獻(xiàn)：[1]：錢(qián)湔.運(yùn)籌學(xué)[M].北京：科學(xué)出版社，2000[2]：肖雁，符卓，李育安.帶軟時(shí)間窗口的車(chē)輛路徑問(wèn)題及其應(yīng)用前景探討[J].中國(guó)運(yùn)籌學(xué)會(huì)第六屆學(xué)術(shù)交流會(huì)論文集，下卷，634－638STUDYONTHESCHEDULINGPROBLEMDONGQiang，LIUChao-hui，MAYiInstructor：WUMeng-da（NationalUniversityofDefenceTechnology,ChangSha410073）Abstract：Asit’savehicle-schedulingproblemwithsofttimewindows,weestablishedtwomultipleobjectiveprogrammingmodelstosatisfydifferentpracticalconditions:double-parking-lotmodelandsingle-parking-lotmodel.Themainobjectiveoftheformerwastomatchthecapacityofpassengersholdingwiththerealdemand,whiletheobjectiveofthelatterwastominimizetheaveragei