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

□李宏光 陳燕生

[北京化工大學(xué) 北京 100029]

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

□李宏光 陳燕生

[北京化工大學(xué) 北京 100029]

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

站點(diǎn)配置；模糊聚類(lèi)；路徑規(guī)化；蟻群算法

引言

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

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

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

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

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

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

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

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

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

Wi-每個(gè)站點(diǎn)員工數(shù)目；

Iki-在i站點(diǎn)乘車(chē)員工k與i站點(diǎn)之間的距離；

mu-每輛通勤車(chē)載客量；

dij-站點(diǎn)i與j之間距離；

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

Ru-表示第u條路徑的通勤車(chē)站點(diǎn)集合；

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

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

（二）基于FCM聚類(lèi)的站點(diǎn)配置

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7.將按式(13)更新為

10.根據(jù)聚類(lèi)結(jié)果確定站點(diǎn)位置；

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

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

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

二、實(shí)例研究

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

表1　17個(gè)站點(diǎn)的坐標(biāo)值

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

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

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

圖3　改進(jìn)蟻群算法收斂過(guò)程

三、結(jié)論

論文從不同的通勤車(chē)站點(diǎn)配置方案會(huì)直接影響路徑規(guī)劃結(jié)果的角度，將通勤班車(chē)站點(diǎn)配置作為其路徑規(guī)劃問(wèn)題的約束和前提，提出一種綜合站點(diǎn)配置的企業(yè)通勤班車(chē)路徑規(guī)劃方法，并基于FCM聚類(lèi)及蟻群算法對(duì)綜合路徑規(guī)劃問(wèn)題進(jìn)行求解。實(shí)驗(yàn)結(jié)果表明本文提出的整合優(yōu)化模型可為改善企業(yè)通勤班車(chē)站點(diǎn)選擇及路徑規(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)宏志, 趙紅征. 通勤班車(chē)出行線路優(yōu)化研究[J]. 武漢理工大學(xué)學(xué)報(bào): 交通科學(xué)與工程版, 2011, 35(2): 379-382.

[7] 張麗萍, 柴躍廷. 車(chē)輛路徑問(wèn)題的改進(jìn)遺傳算法[J].系統(tǒng)工程理論與實(shí)踐, 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] 郭新辰, 樊秀玲, 郗仙田, 韓嘯. 改進(jìn)的FCM半監(jiān)督聚類(lèi)算法[J]. 吉林大學(xué)學(xué)報(bào): 理學(xué)版, 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- ）男，北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院教授、博士生導(dǎo)師；陳燕生（1983- ）男，北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院碩士研究生.