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

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

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

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

1 問題描述

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

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

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

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

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

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

2.1 符號說明

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

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

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

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

2.3 模型求解

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

3 算例

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

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

留史鎮(zhèn)面積59.62 km2，人口5.36 萬人。管轄西王村、朱佐、中白樓、南白樓、北白樓、繆家營、杜家莊、大王村、李家佐、代家莊、曹佐、臧家營、東侯佐、劉家營、西侯佐15 個行政村，為了簡便15 個行政村分別用數(shù)字1～15 表示，客運中心用0 表示。劃分時間段t，考慮出行客流高峰時期，選取早上7:00～8:00 和下午13:00～14:00 兩個客流高峰時段，每10 min 劃分一個時間段;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)天各個村莊在每個時間段的客運需求量git見表2。

表2 各個村莊在每個時間段的客運需求量(單位:人次)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，第一個時間段客流量為4，累積到第二個時間段客流量為11，低于車輛載客量的一半，暫不發(fā)車，客流量累積到第三個時間段。在第三個時間段客流量為31，發(fā)出一輛車。第四個時間段客流量為32，發(fā)出一輛車。第五個時間段客流量為7，客流量較小暫不發(fā)車，客流量累積到第六個時間段。第六個時間段客流量為31，發(fā)出一輛車。在下午13:00～14:00，第一個時間段客流量為58，發(fā)出兩輛車。第二個時間段客流量為31，發(fā)出一輛車。第三個時間段客流量為23，發(fā)出一輛車。第四個時間段客流量為28，發(fā)出一輛車。第五個時間段客流量為13，低于車輛載客量的一半，暫不發(fā)車，客流量累積到第六個時間段。第六個時間段客流量為60，發(fā)出兩輛車。

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

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

4 結(jié)語

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

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

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

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

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

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

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

［7］胡明偉，唐浩.動態(tài)車輛路徑問題的多目標(biāo)優(yōu)化模型與算法［J］.深圳大學(xué)學(xué)報:理工版，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)村客運客流特征及班線組織方式分析［C］//交通與物流:第六屆交通運輸領(lǐng)域國際學(xué)術(shù)會議論文集，大連:大連理工大學(xué)出版社，2006.