郗文彬 ，宋瑞* ，何必勝，劉星材

(1.北京交通大學(xué)城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100044;2.北京交通大學(xué)交通運(yùn)輸學(xué)院，北京 100044)

近年來，隨著我國(guó)城鎮(zhèn)化進(jìn)程的加快，鄉(xiāng)鎮(zhèn)之間、城鄉(xiāng)之間的聯(lián)系日益緊密，帶來了城鄉(xiāng)之間、鄉(xiāng)鎮(zhèn)之間客流量的增加，同時(shí)顯露了農(nóng)村(鄉(xiāng)鎮(zhèn))客運(yùn)的一些問題。雖然現(xiàn)在農(nóng)村的不少線路有了客運(yùn)班車，但線路分布不夠合理，有的線路客源少，車輛多;有的線路有一定的客流量，但配置不完善，居民出行有時(shí)無車可乘。由于現(xiàn)有的農(nóng)村客運(yùn)班車的營(yíng)運(yùn)路線、班次都是按平時(shí)的客流量進(jìn)行配置的，而農(nóng)村客流波動(dòng)較大，班次過密，將增加運(yùn)營(yíng)成本;但是一旦班次減少，到客流高峰時(shí)期，又會(huì)造成居民出行無車可乘。許多學(xué)者針對(duì)城鄉(xiāng)公交運(yùn)營(yíng)管理進(jìn)行了研究，文獻(xiàn)［1 -2］在對(duì)我國(guó)農(nóng)村客運(yùn)的發(fā)展現(xiàn)狀進(jìn)行分析的基礎(chǔ)上，提出繼續(xù)推進(jìn)農(nóng)村客運(yùn)班線公交化改造、調(diào)整班車的運(yùn)營(yíng)線路或新增客運(yùn)線路班次等發(fā)展對(duì)策;文獻(xiàn)［3］對(duì)城鄉(xiāng)公交線路特征進(jìn)行了分析，對(duì)比了與城市公交的不同，并介紹了其客流特征;文獻(xiàn)［4］提出利用農(nóng)村公交區(qū)域化的發(fā)展模式解決城鄉(xiāng)公交問題。城鄉(xiāng)公交不同于城市公交，城市公交客流需求比較穩(wěn)定，公交車輛行車路線固定;而城鄉(xiāng)公交客流波動(dòng)較大，人員比較分散，線路靈活。針對(duì)城鄉(xiāng)公交的特點(diǎn)，結(jié)合現(xiàn)在的農(nóng)村客運(yùn)班車營(yíng)運(yùn)適時(shí)信息查詢技術(shù)［5］，可以將動(dòng)態(tài)路徑公交服務(wù)應(yīng)用于城鄉(xiāng)公交系統(tǒng)中?？瓦\(yùn)中心根據(jù)出行居民發(fā)來的信息，安排發(fā)車數(shù)量及車輛的行駛路徑，并不斷調(diào)整行車路徑。

目前，動(dòng)態(tài)車輛路徑問題(DVRP)是車輛路徑問題研究的熱點(diǎn)，很多學(xué)者都對(duì)該問題進(jìn)行了模型和算法研究［6-7］。關(guān)于動(dòng)態(tài)車輛路徑在實(shí)際問題中的應(yīng)用也得到了學(xué)者們的關(guān)注，文獻(xiàn)［8］用動(dòng)態(tài)車輛路徑問題的思想處理物流配送問題;文獻(xiàn)［9］介紹了基于實(shí)時(shí)信息的動(dòng)態(tài)車輛路徑問題及應(yīng)用;文獻(xiàn)［10］介紹了動(dòng)態(tài)車輛路徑問題在產(chǎn)品速遞中的應(yīng)用。但是，目前的研究中將動(dòng)態(tài)車輛路徑問題應(yīng)用于公交調(diào)度的較少。本文將動(dòng)態(tài)路徑公交服務(wù)應(yīng)用于城鄉(xiāng)公交，在滿足客運(yùn)需求的前提下，找到公交運(yùn)行的實(shí)時(shí)最短路徑，合理安排發(fā)車車輛，以降低車輛運(yùn)營(yíng)成本。

1 問題描述

我國(guó)很多城市的公交呈3 級(jí)結(jié)構(gòu)，分別為城區(qū)公交(服務(wù)城市內(nèi)部)、城鄉(xiāng)公交(服務(wù)城區(qū)與鄉(xiāng)鎮(zhèn)、鄉(xiāng)鎮(zhèn)內(nèi))和村鎮(zhèn)公交(鄉(xiāng)鎮(zhèn)與農(nóng)村、農(nóng)村內(nèi))。從廣義上講，城鄉(xiāng)公交包括城市與農(nóng)村地區(qū)的公共客運(yùn)交通。狹義上講，城鄉(xiāng)公交是指城區(qū)與鄉(xiāng)鎮(zhèn)或中心鎮(zhèn)與村之間的公共客運(yùn)系統(tǒng)。本文研究的城鄉(xiāng)公交指的是鄉(xiāng)鎮(zhèn)與村之間的公共客運(yùn)交通。城鄉(xiāng)公交線路客流具有以下特征:(1)時(shí)間分布特征。農(nóng)村客流的季節(jié)分布特征主要是節(jié)前進(jìn)城務(wù)工人員、學(xué)生回家，節(jié)后務(wù)工人員、學(xué)生回城。鄉(xiāng)村居民出行日分布特征是上午、中午、晚上形成高峰。(2)空間分布特征。不同農(nóng)村客運(yùn)線路的客流強(qiáng)度差別可能會(huì)很大，一條線路的不同區(qū)段或斷面流量也會(huì)有很大的差異性，這種特性構(gòu)成了客流的空間分布特征［11］。

針對(duì)農(nóng)村客運(yùn)存在的問題，綜合考慮城鄉(xiāng)居民出行特征，結(jié)合現(xiàn)在的農(nóng)村客運(yùn)班車營(yíng)運(yùn)適時(shí)信息查詢技術(shù)，將動(dòng)態(tài)車輛路徑問題引入城鄉(xiāng)公交研究中。將城鄉(xiāng)公交區(qū)域內(nèi)有客運(yùn)需求的村莊看成一系列需求點(diǎn)，客運(yùn)中心看成服務(wù)點(diǎn)，根據(jù)接收到的居民出行信息，確定合適的行車路徑安排公交車輛通過。同時(shí)，如果在整個(gè)客流運(yùn)送中適時(shí)動(dòng)態(tài)需求很頻繁，則計(jì)算很復(fù)雜，計(jì)算量很大。本文引入“時(shí)間段”［6］的概念，根據(jù)客流動(dòng)態(tài)需求的特點(diǎn)，按照一定規(guī)則，將整個(gè)公交運(yùn)營(yíng)時(shí)間分為若干個(gè)相等或不等的時(shí)間段來處理，在每一個(gè)時(shí)間段的結(jié)束時(shí)刻，實(shí)行動(dòng)態(tài)客流需求的插入。車輛發(fā)車前能獲得新的客流需求信息，在每一個(gè)時(shí)間段已發(fā)出的車輛不再調(diào)整運(yùn)行路線，將動(dòng)態(tài)車輛路徑問題轉(zhuǎn)化為一系列靜態(tài)問題，如圖1 所示。由于客運(yùn)中心的車輛數(shù)是有限的，每輛車的載客容量也有限制，所有車輛肯定是從客運(yùn)中心出發(fā)途經(jīng)各個(gè)村莊接送乘客后回到客運(yùn)中心，因此必須考慮這些約束條件的限制。公交運(yùn)營(yíng)公司在滿足客運(yùn)需求和為居民提供便利的公交服務(wù)的前提下，最關(guān)心的是運(yùn)營(yíng)成本最小化，所以我們要到達(dá)的目標(biāo)就是車輛的運(yùn)營(yíng)成本最小。

圖1 適時(shí)客流信息處理流程圖Fig.1 In-time processing flowchart of passenger flow information

2 優(yōu)化模型的建立及求解

本文研究的動(dòng)態(tài)路徑公交服務(wù)問題為:一個(gè)中心客運(yùn)站，擁有容量為Q 的車輛K 輛，負(fù)責(zé)對(duì)N 個(gè)村莊進(jìn)行旅客接送工作。其中村莊數(shù)為i(i=1，2，…，N)，劃分時(shí)間段t，在每個(gè)時(shí)間段發(fā)車前能獲得各個(gè)村莊的客運(yùn)需求信息，如果村莊i 有客運(yùn)需求則安排車輛途經(jīng)此村莊，反之則不途經(jīng)此村莊，據(jù)此調(diào)整車輛的行車路徑和發(fā)車數(shù)量。求在滿足客運(yùn)需求的前提下，在每個(gè)時(shí)間段t 使車輛的總運(yùn)營(yíng)成本最小。

模型存在以下幾個(gè)假設(shè):(1)只存在村莊到鄉(xiāng)鎮(zhèn)之間的客流，村莊與村莊之間的客流由于客流量較小，距離短不作考慮;(2)居民不是很關(guān)心出行時(shí)間，只要在此時(shí)間段上車就行;(3)在每個(gè)時(shí)間段若客流量較小(一般低于車輛載客量的一半)則暫不發(fā)車，并將當(dāng)前客流累積到下一個(gè)時(shí)間段，但每小時(shí)至少發(fā)一班車。

2.1 符號(hào)說明

參數(shù)和變量的一般定義:O 表示中心客運(yùn)站，N 表示服務(wù)的村莊點(diǎn)的數(shù)目，K 表示中心客運(yùn)站的車輛總數(shù)，Kt表示在t 時(shí)間段客運(yùn)中心剩余車輛數(shù)，rt表示在t 時(shí)間段回到客運(yùn)中心的車輛數(shù)，Q 表示車輛的最大載客容量，t 表示時(shí)間段，git表示村莊點(diǎn)i 在t 時(shí)間段的客運(yùn)需求量，qtik表示第k 輛車在時(shí)間段t 在村莊i 的載運(yùn)客流量，c 表示單公里油耗成本，lij表示村莊i 到村莊j 之間的距離，v 表示車速，sij表示從村莊i 到村莊j 之間的運(yùn)營(yíng)成本，

2.2 約束條件和目標(biāo)函數(shù)

綜合考慮車輛數(shù)限制，車輛載客容量限制，車輛由客運(yùn)中心出發(fā)、再回到客運(yùn)中心的約束，以總運(yùn)營(yíng)成本最小為目標(biāo)函數(shù)的動(dòng)態(tài)車輛路徑問題優(yōu)化模型如下:

其中，式(4)表示在任意t 時(shí)間段所有接送旅客的車輛數(shù)目不能超過客運(yùn)中心剩余車輛數(shù);式(5)表示在任意t 時(shí)間段更新客運(yùn)中心車輛數(shù);式(6)～(7)表示保證車輛都是從客運(yùn)中心出發(fā)，再回到客運(yùn)中心;式(8)表示網(wǎng)絡(luò)流平衡約束;式(9)表示每個(gè)有客運(yùn)需求的村莊乘客被接送;式(10)表示每輛車在t 時(shí)間段的所有載客量不能超過車輛的最大載客容量;式(11)表示決策變量。

2.3 模型求解

上述模型為0-1 整數(shù)規(guī)劃模型，且模型針對(duì)的是城鄉(xiāng)公交。由于將問題分解為每個(gè)時(shí)間段，因此解空間相對(duì)較小，商業(yè)數(shù)學(xué)優(yōu)化軟件就可以滿足求解需求，不必設(shè)計(jì)算法，因此，本文采用Lingo12.0 優(yōu)化軟件進(jìn)行求解。而且在滿足所有約束的條件下，在任意時(shí)間段總能找到途經(jīng)各個(gè)需求村莊的最佳行駛路徑并確定發(fā)車數(shù)量，所以一定存在最優(yōu)解。

3 算例

選擇留史鎮(zhèn)城鄉(xiāng)公交作為實(shí)例研究，驗(yàn)證本文設(shè)計(jì)模型的有效性。

3.1 算例數(shù)據(jù)

留史鎮(zhèn)面積59.62 km2，人口5.36 萬人。管轄西王村、朱佐、中白樓、南白樓、北白樓、繆家營(yíng)、杜家莊、大王村、李家佐、代家莊、曹佐、臧家營(yíng)、東侯佐、劉家營(yíng)、西侯佐15 個(gè)行政村，為了簡(jiǎn)便15 個(gè)行政村分別用數(shù)字1～15 表示，客運(yùn)中心用0 表示。劃分時(shí)間段t，考慮出行客流高峰時(shí)期，選取早上7:00～8:00 和下午13:00～14:00 兩個(gè)客流高峰時(shí)段，每10 min 劃分一個(gè)時(shí)間段;N 為15;K 為10;Q 為32;c 為2.355 元/km。村莊i到村莊j 之間的距離(km)lij見表1。

表1 村莊到村莊之間的距離(單位:km)Table 1 The distance between villages i and j (Unit:km)

當(dāng)天各個(gè)村莊在每個(gè)時(shí)間段的客運(yùn)需求量git見表2。

表2 各個(gè)村莊在每個(gè)時(shí)間段的客運(yùn)需求量(單位:人次)Table 2 Passenger transport demand of all villages at every time section

3.2 算例求解及結(jié)果分析

用lingo12.0 求解，最終求解結(jié)果見表3。

表3 算例求解結(jié)果Table 3 Solution result of a computation case

在上午7:00～8:00，第一個(gè)時(shí)間段客流量為4，累積到第二個(gè)時(shí)間段客流量為11，低于車輛載客量的一半，暫不發(fā)車，客流量累積到第三個(gè)時(shí)間段。在第三個(gè)時(shí)間段客流量為31，發(fā)出一輛車。第四個(gè)時(shí)間段客流量為32，發(fā)出一輛車。第五個(gè)時(shí)間段客流量為7，客流量較小暫不發(fā)車，客流量累積到第六個(gè)時(shí)間段。第六個(gè)時(shí)間段客流量為31，發(fā)出一輛車。在下午13:00～14:00，第一個(gè)時(shí)間段客流量為58，發(fā)出兩輛車。第二個(gè)時(shí)間段客流量為31，發(fā)出一輛車。第三個(gè)時(shí)間段客流量為23，發(fā)出一輛車。第四個(gè)時(shí)間段客流量為28，發(fā)出一輛車。第五個(gè)時(shí)間段客流量為13，低于車輛載客量的一半，暫不發(fā)車，客流量累積到第六個(gè)時(shí)間段。第六個(gè)時(shí)間段客流量為60，發(fā)出兩輛車。

客運(yùn)中心在每個(gè)時(shí)間段內(nèi)根據(jù)適時(shí)信息客流量的大小決定是否發(fā)車，若客流量較小，一般低于車輛載客量的一半則暫不發(fā)車，但是每小時(shí)最少發(fā)一班車。實(shí)現(xiàn)了根據(jù)客流的波動(dòng)安排發(fā)車，同時(shí)由于得到每個(gè)村莊的適時(shí)客流需求信息，總能找到適時(shí)最短路徑。如在上午7:00～8:00 第三個(gè)時(shí)間段原來的行車路線為0 -1 -8-14 -6 -12 -5 -3 -4 -9 -2 -10 -11 -15 -13 -0運(yùn)營(yíng)成本為85.25，大于優(yōu)化后的目標(biāo)值80.07，優(yōu)化前后的線路如圖2 所示。

圖2 第三個(gè)時(shí)間段優(yōu)化前后對(duì)比分析Fig.2 Comparison analysis of pre-optimization and prooptimization at the third time section

4 結(jié)語

本文將動(dòng)態(tài)路徑公交服務(wù)應(yīng)用于鄉(xiāng)鎮(zhèn)與村之間的城鄉(xiāng)公交，構(gòu)建了城鄉(xiāng)公交動(dòng)態(tài)路徑優(yōu)化模型，并以留史鎮(zhèn)為實(shí)例驗(yàn)證模型的有效性。驗(yàn)證結(jié)果表明，這種動(dòng)態(tài)路徑城鄉(xiāng)公交能在滿足客運(yùn)需求的前提下，為居民提供便利的公交服務(wù)。結(jié)合適時(shí)信息查詢技術(shù)，在每個(gè)時(shí)間段根據(jù)適時(shí)信息客流量的大小安排發(fā)車，并為車輛安排成本最小路徑運(yùn)行，可以降低公共交通部門的運(yùn)營(yíng)成本。

［1］閆淑華.農(nóng)村客運(yùn)現(xiàn)狀與發(fā)展探討［J］.中國(guó)城市經(jīng)濟(jì)，2011(18):320 -323.

［2］翁志新.新時(shí)期農(nóng)村道路客運(yùn)發(fā)展的現(xiàn)狀與對(duì)策［J］.交通世界(運(yùn)輸.車輛)，2011(6):184 -186.

［3］周業(yè)利，李鵬飛，楊超.城鄉(xiāng)公交線路特征及其客流特征分析［J］.交通標(biāo)準(zhǔn)化，2011(21):59 -63.

［4］沈吟東.農(nóng)村客運(yùn)改革:公交化及區(qū)域模式［J］.中國(guó)軟科學(xué)，2009(S1):40 -46.

［5］鄭長(zhǎng)安，張起森，黎茂盛.農(nóng)村客運(yùn)班車運(yùn)營(yíng)適時(shí)信息手機(jī)查詢技術(shù)及其應(yīng)用［J］.湖南交通科技，2011，37(4):180 -182.

［6］錢艷婷，王鵬濤，魏國(guó)利.動(dòng)態(tài)車輛路徑問題的算法研究［J］.天津理工大學(xué)學(xué)報(bào)，2010，26(6):72 -74.

［7］胡明偉，唐浩.動(dòng)態(tài)車輛路徑問題的多目標(biāo)優(yōu)化模型與算法［J］.深圳大學(xué)學(xué)報(bào):理工版，2010，24(2):230 -234.

［8］WEN M，CORDEAUB J F，LAPORTE G，et al.The dynamic multi-period vehicle routing problem［J］.Computers ＆ Operations Research，2010，37(9):1615 -1623.

［9］LIAO T Y，HU T Y.An object-oriented evaluation framework for dynamic vehicle routing problems under real-time information［J］.Expert Systems with Applications，2011，38(10):12548 -12558.

［10］FERRUCCI F，BOCK S，GENDREAU M.A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goods［J］.European Journal of Operational Research，2013，225(1):130 -141.

［11］王建軍，過秀成，吳能萍，等.農(nóng)村客運(yùn)客流特征及班線組織方式分析［C］//交通與物流:第六屆交通運(yùn)輸領(lǐng)域國(guó)際學(xué)術(shù)會(huì)議論文集，大連:大連理工大學(xué)出版社，2006.