基于客運需求的城鄉公交動態路徑問題研究

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

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

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

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

1 問題描述

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

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

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

2 優化模型的建立及求解

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

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

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 約束條件和目標函數

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

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

2.3 模型求解

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

3 算例

選擇留史鎮城鄉公交作為實例研究，驗證本文設計模型的有效性。

3.1 算例數據

留史鎮面積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，低于車輛載客量的一半，暫不發車，客流量累積到第三個時間段。在第三個時間段客流量為31，發出一輛車。第四個時間段客流量為32，發出一輛車。第五個時間段客流量為7，客流量較小暫不發車，客流量累積到第六個時間段。第六個時間段客流量為31，發出一輛車。在下午13:00～14:00，第一個時間段客流量為58，發出兩輛車。第二個時間段客流量為31，發出一輛車。第三個時間段客流量為23，發出一輛車。第四個時間段客流量為28，發出一輛車。第五個時間段客流量為13，低于車輛載客量的一半，暫不發車，客流量累積到第六個時間段。第六個時間段客流量為60，發出兩輛車。

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

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

4 結語

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

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

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

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

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

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

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

［7］胡明偉，唐浩.動態車輛路徑問題的多目標優化模型與算法［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.