基于泊松過程的校車優(yōu)化調(diào)度問題研究

鄭秋群，王 琪，王楚菡，桂預(yù)風(fēng)

(武漢理工大學(xué) 理學(xué)院，湖北 武漢 430070)

基于泊松過程的校車優(yōu)化調(diào)度問題研究

鄭秋群，王 琪，王楚菡，桂預(yù)風(fēng)

(武漢理工大學(xué) 理學(xué)院，湖北 武漢 430070)

針對傳統(tǒng)校車調(diào)度方案中管理不靈活的缺點(diǎn)，提出一種基于動(dòng)態(tài)調(diào)度原理和分段齊次泊松過程的雙目標(biāo)優(yōu)化模型。首先利用泊松分布對發(fā)車時(shí)間間隔進(jìn)行非等時(shí)優(yōu)化，得到發(fā)車間隔序列，再據(jù)此計(jì)算出一天內(nèi)的發(fā)車時(shí)刻，最后進(jìn)行泊松隨機(jī)數(shù)編程模擬不同時(shí)刻的乘車人數(shù)，得到調(diào)度方案。以武漢理工大學(xué)為例進(jìn)行模型檢驗(yàn)，所得結(jié)果表明該方案易于管理、靈活方便。

校車問題；雙目標(biāo)規(guī)劃；車輛調(diào)度；分段齊次泊松過程

0 引言

車輛調(diào)度問題[1](VRP)是組合優(yōu)化領(lǐng)域研究的熱點(diǎn)和難題，科學(xué)有效的調(diào)度能夠讓車輛正確運(yùn)轉(zhuǎn)，提高物流工作效率，保障企業(yè)機(jī)構(gòu)運(yùn)營效益。VRP問題一般可分為靜態(tài)VRP問題(SVRP)和動(dòng)態(tài)VRP問題(DVRP)，在實(shí)際應(yīng)用過程中，由于交通擁堵情況、天氣狀況、安全事故等諸多因素的影響，傳統(tǒng)SVRP問題的理論和方法已經(jīng)不再適用，這使得對DVRP問題的研究更為迫切。目前，國內(nèi)外對VRP問題的大部分研究還是建立在SVRP問題上，而DVRP問題更接近實(shí)際生活，解決DVRP問題的主要方法有啟發(fā)式算法等，以及與其研究思想相近的方法，現(xiàn)已成為解決實(shí)際生活中車輛調(diào)度問題的發(fā)展熱點(diǎn)。

隨著社會(huì)經(jīng)濟(jì)的發(fā)展和交通的日益發(fā)達(dá)，許多高校為了滿足自身需求購置校車，校車成為高校大學(xué)生在不同校區(qū)之間便捷通行的主要交通工具，高效的車輛管理和科學(xué)的安排調(diào)度不僅可以滿足學(xué)生日常的交通出行，而且降低了校車運(yùn)營成本，提高了校車服務(wù)質(zhì)量。武漢理工大學(xué)自建校以來，由于學(xué)校合并，各校區(qū)分布較為分散，對大部分在校學(xué)生而言，課程安排和行車路線及時(shí)刻表等的變化，使得學(xué)生們一般選擇乘坐校車往返于不同校區(qū)，如何對校車進(jìn)行合理的調(diào)度成為長期困擾高校學(xué)生的最主要問題。本文以武漢理工大學(xué)為例，對校車進(jìn)行動(dòng)態(tài)VRP調(diào)度研究，從而實(shí)現(xiàn)校車調(diào)度問題的優(yōu)化。

1 基本假設(shè)及符號(hào)說明

1.1 基本假設(shè)

1.2 符號(hào)說明

符號(hào)說明如表1所示。

表1 符號(hào)說明

注：此表中未出現(xiàn)的符號(hào)說明均以出處為準(zhǔn)

2 模型建立與求解

針對當(dāng)前武漢理工大學(xué)校內(nèi)校車的服務(wù)現(xiàn)狀，結(jié)合調(diào)查結(jié)果進(jìn)行分析，目前主要存在的問題是：①高峰期校車數(shù)量與規(guī)格與學(xué)生需求不均衡；②非高峰期校車發(fā)車時(shí)間安排不合理，導(dǎo)致等待時(shí)間過長。這兩個(gè)問題嚴(yán)重影響到校內(nèi)師生的出行質(zhì)量，為了更好地解決存在的問題，本文擬從動(dòng)態(tài)調(diào)度的角度出發(fā)，以學(xué)生滿意度最大和校車公司的利益最大為目標(biāo)，建立雙目標(biāo)規(guī)劃模型[5]。

2.1 原始數(shù)據(jù)處理分析

由假設(shè)(2)可知，馬房山校區(qū)共有5個(gè)主要校車站點(diǎn)，但需乘坐校車的人數(shù)較多，流動(dòng)性較高的只有南湖、升升和東院3個(gè)站點(diǎn)。原始數(shù)據(jù)是以這3個(gè)站點(diǎn)為主按1min為一個(gè)基本時(shí)間單位進(jìn)行搜集，分析原始數(shù)據(jù)時(shí)出現(xiàn)時(shí)間密度太大，數(shù)據(jù)過于離散和間斷，為方便分析數(shù)據(jù)的規(guī)律性，并統(tǒng)計(jì)出高峰時(shí)段，將數(shù)據(jù)進(jìn)行處理，把7:00-18:00統(tǒng)計(jì)的數(shù)據(jù)以10min為一個(gè)基本時(shí)間單位進(jìn)行合并處理，合成66個(gè)時(shí)間段。由于各站點(diǎn)所在校區(qū)的功能屬性不同，高峰期時(shí)段也有所差異，比如南湖校區(qū)主要為教學(xué)區(qū)，通常乘坐校車的人數(shù)分布會(huì)在下課時(shí)段呈峰態(tài)，升升公寓為住宿區(qū)，乘坐校車的人數(shù)分布一般在臨近上課時(shí)段呈峰態(tài)。為了更直觀地分析乘車人數(shù)的變化規(guī)律，用MATLAB軟件畫出乘車人數(shù)隨時(shí)間段的變化折線圖。

2.1.1 南湖校區(qū)

南湖校區(qū)乘坐校車人數(shù)統(tǒng)計(jì)如圖1所示。

圖1 南湖校區(qū)乘坐校車人數(shù)統(tǒng)計(jì)

由圖1可看出，一天之內(nèi)南湖校區(qū)共有5個(gè)乘坐校車高峰期，所在時(shí)段序號(hào)分別為17、30、41、53、66，對應(yīng)的時(shí)間段為9:40-9:50、11:50-12:00、13:40-13:50、15:40-15:50、17:50-18:00，這些時(shí)段均為上下課時(shí)段，與南湖校區(qū)作為主要教學(xué)區(qū)的性質(zhì)相符。

2.1.2 升升公寓

升升公寓乘坐校車人數(shù)統(tǒng)計(jì)折線如圖2所示。

圖2 升升公寓乘坐校車人數(shù)統(tǒng)計(jì)折線

由圖2可看出，一天之內(nèi)升升公寓共有3個(gè)乘坐校車高峰期，所在時(shí)段序號(hào)分別為2～4、18、41，對應(yīng)的時(shí)間段為7:20-7:40、9:50-10:00、13:40-13:50。升升公寓是學(xué)生的居住區(qū)，每天需要乘坐校車的學(xué)生比例最大，高峰時(shí)段均為上課前20分鐘。

2.1.3 東院校區(qū)

東院校區(qū)乘坐校車人數(shù)統(tǒng)計(jì)折線如圖3所示。

圖3 東院校區(qū)乘坐校車人數(shù)統(tǒng)計(jì)折線

由圖3可看出，一天之內(nèi)東院共有4個(gè)乘坐校車高峰期，所在時(shí)段序號(hào)分別為27～30、40、53、64，對應(yīng)的時(shí)間段為11:30-12:00、13:30-13:40、15:50-16:00、5:30-5:40。高峰期分布無明顯規(guī)律。

2.2 車輛調(diào)度模型建立

由于校車的服務(wù)對象是學(xué)生，而學(xué)生的出行規(guī)律受一定的校內(nèi)課時(shí)安排限制，故學(xué)生到達(dá)站點(diǎn)的強(qiáng)度是隨時(shí)間變化的，是一個(gè)非齊次泊松過程[2]。非齊次泊松過程建模的研究難度較大，不易實(shí)施，本文擬將一天的時(shí)間離散化，分成不同的小時(shí)間段，在每個(gè)小時(shí)段內(nèi)學(xué)生到達(dá)乘車站點(diǎn)服從齊次泊松過程。為方便統(tǒng)計(jì)，以10min為一個(gè)基本時(shí)間單位，從7:00-18:00共有66個(gè)基本時(shí)間單位，T=66。結(jié)合現(xiàn)實(shí)中校車調(diào)度問題和泊松隨機(jī)過程理論[2]，有：

在一個(gè)發(fā)車時(shí)間間隔△Tijt內(nèi)，有k個(gè)學(xué)生到達(dá)i站點(diǎn)的概率為：

從學(xué)生滿意度最大化角度考慮，學(xué)生的滿意度主要受到等車時(shí)間的影響，等待時(shí)間越長，滿意度越低；從校車公司的利益角度分析，滿載率越高，即空車率越低，利益就越大[4]。因此最終的解決方法是設(shè)置一個(gè)合理的校車調(diào)度方案，求出使得這兩個(gè)目標(biāo)值達(dá)到最大的最優(yōu)解。

對S(t) 求期望，得到第t個(gè)時(shí)段從站點(diǎn)i到站點(diǎn)j學(xué)生等待時(shí)間總和的期望值為：

(1)

同理得到第t個(gè)時(shí)間段從站點(diǎn)i到站點(diǎn)j的空座率為：

(2)

綜合式(1)和式(2)得到以學(xué)生滿意度和以校車公司利益為目標(biāo)的目標(biāo)函數(shù)如下：

2.3 模型求解

上文得到一個(gè)使學(xué)生滿意度和校車公司利益最優(yōu)的非線性雙目標(biāo)規(guī)劃模型，由于求解此模型比較復(fù)雜，故考慮轉(zhuǎn)換思路，即通過選擇合理的發(fā)車時(shí)間間隔△Tij，使得在△Tij時(shí)間段內(nèi)，乘坐校車的人數(shù)在[Q,αQ]之間的概率最大。其中，假設(shè)超載人數(shù)不能超過校車容量的一半，即α∈[1,1.5]。因此可將雙目標(biāo)規(guī)劃模型轉(zhuǎn)化為單目標(biāo)規(guī)劃如下：

(3)

以南湖校區(qū)為例，取α=1.5，假設(shè)高峰時(shí)段均發(fā)容量為60的車，非高峰時(shí)段均發(fā)容量為30的校車，得到南湖校區(qū)一天之內(nèi)的發(fā)車時(shí)間點(diǎn)如表2所示。

表2 南湖校區(qū)發(fā)車間隔

2.4 模型檢驗(yàn)

為檢驗(yàn)所建模型的有效程度，以南湖校區(qū)為例，進(jìn)行泊松隨機(jī)數(shù)編程模擬不同時(shí)刻的乘車人數(shù)，對其一天的發(fā)車情況進(jìn)行模擬，計(jì)算機(jī)模擬所需參數(shù)值以表2列出的為準(zhǔn)。

表3 南湖校區(qū)發(fā)車情況模擬結(jié)果

3 結(jié)語

如何安排和設(shè)置發(fā)車時(shí)間間隔從而使學(xué)生和校車公司的滿意度最大是車輛調(diào)度的目的。本文以武漢理工大學(xué)馬房山校區(qū)為例，利用搜集的原始數(shù)據(jù)，以學(xué)生的滿意度和校車公司的利益最優(yōu)為雙目標(biāo)，依據(jù)泊松分布建立相應(yīng)的校車優(yōu)化調(diào)度模型，得到不同時(shí)間段的發(fā)車時(shí)間間隔。最后以南湖校區(qū)為例，利用泊松隨機(jī)數(shù)編程模擬不同時(shí)刻的乘車人數(shù)，模擬出1 000天的發(fā)車情況，得到剩余等車人數(shù)的均值和標(biāo)準(zhǔn)差較小，模型比較合理，能夠?yàn)槲錆h理工大學(xué)校車調(diào)度問題提供較好的解決方案。但本文得到的計(jì)算結(jié)果是基于假設(shè)得到的，簡化了實(shí)際情況，比如在人流量極為龐大時(shí)，會(huì)出現(xiàn)校車的服務(wù)強(qiáng)度小于乘客到達(dá)速率的情況，乘客的等待時(shí)間就可能會(huì)大于一個(gè)發(fā)車間隔。如何把多種實(shí)際情況考慮到模型中并計(jì)算出結(jié)果將是下一步研究的重點(diǎn)。

[1] 劉云霞.動(dòng)態(tài)車輛調(diào)度問題分析及算法設(shè)計(jì)[D].成都：西南交通大學(xué)，2004.

[2] 陳家清,趙華玲.應(yīng)用隨機(jī)過程[M].武漢：武漢理工大學(xué)出版社，2014.

[3] 羅良浩,陳亮.論天津市公交校車的現(xiàn)狀及發(fā)展前景——車輛調(diào)度和網(wǎng)絡(luò)優(yōu)化[C].中國城市交通規(guī)劃2009年年會(huì)暨第23次學(xué)術(shù)研討會(huì)論文集,2009.

[4] 趙莎莎,熊偉,余萬玉,等.高校校車最優(yōu)調(diào)度與配置方案——以三峽大學(xué)為例[J].科技創(chuàng)新與應(yīng)用,2015(32):7-9.

[5] 楊梅,趙克全.基于多目標(biāo)規(guī)劃模型的校車最優(yōu)配置與調(diào)度方案[J].西南師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2014(6):50-54.

(責(zé)任編輯：孫 娟)

武漢理工大學(xué)自主創(chuàng)新研究基金項(xiàng)目(166814007)

桂預(yù)風(fēng)(1963-)，男，湖北黃梅人，博士，武漢理工大學(xué)理學(xué)院教授、碩士生導(dǎo)師，研究方向?yàn)榻y(tǒng)計(jì)建模。

10.11907/rjdk.171065

TP319

A

1672-7800(2017)003-0128-03