基于客運需求的城鄉(xiāng)公交動態(tài)路徑問題研究

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

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

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

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

1 問題描述

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

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

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

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

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

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

2.1 符號說明

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

2.2 約束條件和目標函數

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

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

2.3 模型求解

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

3 算例

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

3.1 算例數據

留史鎮(zhèn)面積59.62 km2，人口5.36 萬人。管轄西王村、朱佐、中白樓、南白樓、北白樓、繆家營、杜家莊、大王村、李家佐、代家莊、曹佐、臧家營、東侯佐、劉家營、西侯佐15 個行政村，為了簡便15 個行政村分別用數字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)

當天各個村莊在每個時間段的客運需求量git見表2。

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

3.2 算例求解及結果分析

用lingo12.0 求解，最終求解結果見表3。

表3 算例求解結果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ā)出兩輛車。

客運中心在每個時間段內根據適時信息客流量的大小決定是否發(fā)車，若客流量較小，一般低于車輛載客量的一半則暫不發(fā)車，但是每小時最少發(fā)一班車。實現(xiàn)了根據客流的波動安排發(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)化后的目標值80.07，優(yōu)化前后的線路如圖2 所示。

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

4 結語

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

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

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

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

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

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

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

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