□李宏光 陳燕生

[北京化工大學 北京 100029]

考慮站點配置的企業(yè)通勤班車綜合路徑規(guī)劃方法

□李宏光 陳燕生

[北京化工大學 北京 100029]

針對傳統(tǒng)方法中將班車站點選擇與路徑規(guī)劃分別進行處理而不能考慮兩者間關(guān)聯(lián)的問題，給出了一種考慮站點配置的綜合路徑規(guī)劃方法。首先基于信息熵的FCM半監(jiān)督聚類算法，對企業(yè)通勤班車站點配置問題進行求解，確定出基于員工居住信息的合理站點配置方案；在此基礎(chǔ)上，基于蟻群算法的對路徑優(yōu)化問題進行求解。實驗結(jié)果表明，綜合路徑規(guī)劃方法可以為優(yōu)化企業(yè)班車站點配置及路徑規(guī)劃策略提供參考。

站點配置；模糊聚類；路徑規(guī)化；蟻群算法

引言

企業(yè)通勤班車站點配置及路徑規(guī)劃屬于一類車輛路徑問題(Vehicle Routing Problem, VRP)。通勤班車是企業(yè)為方便員工上下班而安排的有固定線路并定時行駛的服務(wù)車輛。通勤車站點配置策略是影響企業(yè)員工乘車便利程度、車輛運營效率和調(diào)度計劃安排的重要因素。由于通勤班車工作時間處在上下班的高峰期，合理的安排通勤班車的站點及路線，可以降低企業(yè)職工路途時間，間接地提高職工的工作效率。

VRP受到研究關(guān)注不僅僅是因為它是一類典型較難的組合優(yōu)化問題，而主要是因為其具有廣泛的應(yīng)用背景和可觀的經(jīng)濟效益。國外學者Dantzing和Ramser[1]于1959年最早提出該問題。Balinski等人于1962年提出集分割，考慮可行解集合并在此基礎(chǔ)上進行建立了最簡單的VRP 優(yōu)化模型[2]。此后，Eilon等人[3]將動態(tài)規(guī)劃法引入VRP；Jerby Shai等人優(yōu)化設(shè)計了列車循環(huán)路線[4]；Gendreau等人應(yīng)用禁忌搜索算法解決VRP問題[5]。韓艷等人構(gòu)建了最大出行需求及線路總體通行時間最短的雙重尋優(yōu)目標，并運用啟發(fā)式算法進行求解[6]。張麗萍等人運用改進遺傳算法解決VRP問題[7]。然而，目前大多數(shù)處理VRP方法中將站點配置問題與路徑規(guī)劃問題分別進行處理，實際上兩者之間存在緊密聯(lián)系。

本文綜合考慮了企業(yè)員工居住地信息和班次安排對通勤車站點配置方案的影響以及站點配置方案對路徑優(yōu)化選擇的影響，建立站點配置及路徑優(yōu)化的綜合模型并基于蟻群算法與旅行商算法進行求解。實例研究表明本文研究可為改善企業(yè)班車站點選擇及路徑規(guī)劃策略提供參考。

一、綜合路徑規(guī)劃研究

（一）綜合路徑規(guī)劃模型

針對單車場、單車型、非滿載、純載客的通勤車路徑優(yōu)化問題，路徑規(guī)劃的目標是在安排企業(yè)通勤車數(shù)量的基礎(chǔ)上使得總運行路程最小。這里，對問題做如下說明：（1）設(shè)定企業(yè)所在地為通勤車起始點；（2） 通勤車將員工從企業(yè)送到各個站點，完成任務(wù)后所有車輛返回企業(yè)以便于統(tǒng)一管理。所使用通勤車型號一致，即所有通勤車行駛速度相等，通勤車搭載員工數(shù)不能超過最大載客量；（3） 站點固定，且每個站點的員工乘車數(shù)已知，但所設(shè)站點數(shù)目應(yīng)使得員工出行成本最小。

基于聚類方法選擇出使員工出行成本最小的站點配置方案，并在此基礎(chǔ)上進行路徑規(guī)劃。通勤車路徑優(yōu)化模型需要滿足如下約束：（1） 每條通勤車路徑上各站點總?cè)藬?shù)不超過通勤車的最大承載能力；（2） 每個站點都得到車輛接送服務(wù)；（3） 每條通勤車路徑上的站點數(shù)不超過總站點數(shù)；（4） 員工只能選擇一輛通勤車進行搭乘。

S-總站點數(shù)目；

U-所需通勤車數(shù)目；

Wi-每個站點員工數(shù)目；

Iki-在i站點乘車員工k與i站點之間的距離；

mu-每輛通勤車載客量；

dij-站點i與j之間距離；

nu-第u輛通勤車經(jīng)過的站點數(shù)目(nu表示未用第u量車)；

Ru-表示第u條路徑的通勤車站點集合；

這樣，企業(yè)通勤車綜合路徑優(yōu)化問題描述如下：u

其中：式(1)、(2)為優(yōu)化目標，即通勤車行駛總路程最短和員工出行成本最小；式(3)、(4)、(5)為約束條件，分別表示每條路線上各站點總?cè)藬?shù)不超過通勤車最大承載能力、每個站點都得到車輛接送服務(wù)、以及每條路徑上的站點數(shù)不超過總站點數(shù)；式(6)表示每條路線的站點組成；式(7)表示每個員工僅能乘坐一輛通勤車；式(8)表示站點i到j(luò)間由車輛u經(jīng)過時，

（二）基于FCM聚類的站點配置

企業(yè)通勤車站點配置是后勤保障系統(tǒng)的重要基礎(chǔ)設(shè)施和不可缺少的重要環(huán)節(jié)。站點配置首先需要滿足員工從居住位置到乘車站點的成本最小。另外，考慮到不同的通勤車站點配置方案會直接影響路徑規(guī)劃的結(jié)果，而站點配置需要考慮其合理性。為此，本文將站點配置作為綜合路徑規(guī)劃問題的約束和前提，提出基于FCM的聚類算法對員工居住位置坐標值進行聚類，從而求解站點配置問題。

模糊C-均值聚類算法(Fuzzy C-Means,即FCM)[8～9]是一種聚類效率較好且廣泛應(yīng)用的聚類算法。傳統(tǒng)FCM是基于模糊隸屬度函數(shù)確定聚類程度的一種聚類算法，把n個d維樣本分為c類，聚類中心可表示為，其中vi表示類i的類中心。標準FCM聚類算法的數(shù)學模型可簡單表述為：

其中，uij表示樣本xj屬于類i的程度；U表示uij構(gòu)成的c×N隸屬度矩陣；V為vi構(gòu)成的c×n類中心矩陣；表示一個加權(quán)模糊指數(shù)，反映控制隸屬度在各類間重合歸屬的程度；表示樣本點xj到類中心vi的歐氏距離。

考慮到經(jīng)典FCM聚類算法的局限性，即在每次聚類過程中數(shù)據(jù)均勻收縮，在標準FCM數(shù)學模型的約束條件中增加信息熵約束，彌補模糊聚類存在數(shù)據(jù)收縮問題的不足，從而提高聚類性能[10]。約束條件中引入信息熵的FCM聚類算法數(shù)學模型可表示為：

上述優(yōu)化模型等價于

（三）綜合路徑規(guī)劃算法

蟻群算法(Ant Colony Optimization，即ACO)是由意大利學者Maniezzo等人[11]在1996 年率先提出的一種以自然界蟻群覓食行為啟發(fā)產(chǎn)生的仿生優(yōu)化算法，屬于隨機搜索算法的一種。本文針對需要解決的企業(yè)通勤班車綜合路徑規(guī)劃問題，對蟻群算法的參數(shù)設(shè)置、轉(zhuǎn)移概率計算以及信息素更新等方面做了相應(yīng)的變化，并用于求解通勤班車路線優(yōu)化問題。

實際中的VRP問題相對于TSP問題有更多的約束條件。因此，在計算轉(zhuǎn)移概率時考慮約束條件的信息，使其更具實際意義。通過考慮通勤車路徑優(yōu)化模型的約束條件，概率轉(zhuǎn)移公式為:

這樣，改進后的概率轉(zhuǎn)移計算公式考慮了實際約束條件，并結(jié)合隨機性選擇策略，從而提高了算法的全局搜索能力，避免產(chǎn)生局部最優(yōu)解。

另外，蟻群算法中當每一只螞蟻結(jié)束循環(huán)后，為防止路徑上信息素累積量過多導致啟發(fā)信息被殘留信息淹沒，需要及時更新對路徑上的殘留信息素，更新公式為：

其中：p表示信息素揮發(fā)系數(shù)，相應(yīng)的1-p表示信息素殘留系數(shù)，且表示第k只螞蟻在路徑i-j上分泌的信息素量；表示所有螞蟻在路徑i-j上分泌的信息素總量；Q表示各路徑上信息素大??； LK表示第k只螞蟻在當次循環(huán)中的走過的總路程。

值得注意的是，蟻群算法中的各個參數(shù)值的合理設(shè)置可使優(yōu)化結(jié)果更有效。α值過大，算法收斂過快，容易陷入局部優(yōu)化；β值越大，位置近的站點被選概率大，也不利于全局優(yōu)化；越小表示路徑上的信息素越不易揮發(fā)，殘留信息過多，使結(jié)果陷入局部最優(yōu)；p越大，殘留信息的作用被淹沒。本文對參數(shù)設(shè)置進行動態(tài)調(diào)整，初始設(shè)置值較小，擴大算法搜索范圍，隨著算法迭代到一定次數(shù)后增大參數(shù)值，逐步優(yōu)化出最優(yōu)路徑。本文將站點配置問題作為綜合路徑規(guī)劃問題的約束，整個綜合路徑規(guī)劃問題包括以下步驟：

1.初始化聚類及蟻群算法的各參數(shù)值；

5.初始化員工位置矩陣C；

7.將按式(13)更新為

10.根據(jù)聚類結(jié)果確定站點位置；

11.根據(jù)式(15)(16)選擇下一站點j；

14.根據(jù)式(17),(18),(19)更新每條路徑上的信息素；

16.輸出綜合路徑優(yōu)化結(jié)果。

二、實例研究

在已知所有員工居住地點坐標的情況下，采用Matlab實現(xiàn)基于信息熵的FCM半監(jiān)督聚類算法，確定出所有員工出行成本和（距離）最小的站點布局方案，如圖1所示，最優(yōu)站點配置數(shù)目為17，各站點坐標如表1所示。

表1　17個站點的坐標值

另外，考慮到通勤班車路線的規(guī)劃對員工上下班時間以及企業(yè)班車調(diào)度成本有著至關(guān)重要的影響，因此本文在考慮站點配置的約束情況下，對通勤班車路徑優(yōu)化模型進行求解。設(shè)企業(yè)所在地為始發(fā)站，記為站點0；通勤車最大載客量為60人；企業(yè)共有30輛通勤車；各站點員工數(shù)目分別為9、11、6、14、12、9、12、7、15、13、7、12、4、11、8、14、13；站點i與j之間距離可通過公式（20）進行計算：

圖2　通勤班車最優(yōu)運行路線圖

算法的收斂過程如圖3所示，可以看出具有很好的收斂性。

圖3　改進蟻群算法收斂過程

三、結(jié)論

論文從不同的通勤車站點配置方案會直接影響路徑規(guī)劃結(jié)果的角度，將通勤班車站點配置作為其路徑規(guī)劃問題的約束和前提，提出一種綜合站點配置的企業(yè)通勤班車路徑規(guī)劃方法，并基于FCM聚類及蟻群算法對綜合路徑規(guī)劃問題進行求解。實驗結(jié)果表明本文提出的整合優(yōu)化模型可為改善企業(yè)通勤班車站點選擇及路徑規(guī)劃策略提供參考。

[1] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1):80-91.

[2] BALINSKI M L, QUANDT R E. On an integer program for a delivery problem [J]. Operations Research, 1962, 12(2): 300-304.

[3] EILON S, WATSON-GANDY C D T, CHRISTOFIDES N. Distribution management[M]. London: Griffin, 1971.

[4] JERBY S, CEDER A. Optimal routing design for shuttle bus service[J]. Transportation Research Record: Journal of the Transportation Research Board, 2006, 1971(1): 14-22.

[5] GENDREAU M, HERTZ A, LAPORTE G. A tabu search heuristic for the vehicle routing problem[J]. Management Science, 1994, 40(10): 1276-1290.

[6] 韓艷, 關(guān)宏志, 趙紅征. 通勤班車出行線路優(yōu)化研究[J]. 武漢理工大學學報: 交通科學與工程版, 2011, 35(2): 379-382.

[7] 張麗萍, 柴躍廷. 車輛路徑問題的改進遺傳算法[J].系統(tǒng)工程理論與實踐, 2002, 22(8): 79-84.

[8] CHEN M S, WANG S W. Fuzzy clustering analysis for optimizing fuzzy membership functions[J]. Fuzzy Sets and Systems, 1999, 103(2): 239-254.

[9] BEZDEK J C, HATHAWAY R J, SABIN M J, et al. Convergence theory for fuzzyC-means: Counterexamples and repairs[J]. Systems, Man and Cybernetics, IEEE Transactions on, 1987, 17(5):873-877.

[10] 郭新辰, 樊秀玲, 郗仙田, 韓嘯. 改進的FCM半監(jiān)督聚類算法[J]. 吉林大學學報: 理學版, 2014, 52(06): 1293-1296.

[11] MANIEZZO V, DORIGO M, COLORNI A. The ant system: Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems Man and Cybernetics, 1996 (Part B): 29-41.

編輯 何 婧

Study on Enterprise Shuttle Bus Location and Route Optimization： An Integrated Approach

LI Hong-guang CHEN Yan-sheng
(Beijing University of Chemical Technology Beijing 100029 China)

Enterprise’s shuttle bus location and route optimization problems play an important role in increasing the logistics management efficiency and operation expenditure control. Traditional researches optimize location and route separately, thus causing danger to ignore the close connection between them. In this paper, we propose an information entropy-based improved fuzzy c-means semi-supervised clustering algorithm for bus location optimization and experiments are conducted to evaluate the reliability and effectiveness of it. Thereafter, a shuttle bus route selection model is introduced and an enhanced ant colony optimization (ACO) algorithm is designed to obtain the optimal results.

location selection; fuzzy c-means; vehicle routing problem; ant colony optimization

U491.2

A [DOI]10.14071/j.1008-8105(2016)04-0068-06

2015 - 04 - 12

李宏光（1963- ）男，北京化工大學信息科學與技術(shù)學院教授、博士生導師；陳燕生（1983- ）男，北京化工大學信息科學與技術(shù)學院碩士研究生.