郭俊一，吳麗娜，張雪飛

（1.廣州華商學(xué)院 管理學(xué)院，廣東 廣州 511300；2.廣州商學(xué)院 管理學(xué)院，廣東 廣州 510700）

0 引言

隨著高校擴(kuò)招政策的實(shí)施，人地矛盾日益突出。為緩解人地矛盾，高校校區(qū)也逐漸擴(kuò)大。校區(qū)面積大幅度增加的同時(shí)，學(xué)校師生的出行成了一個(gè)難題。較之路網(wǎng)密度、形態(tài)等傳統(tǒng)指標(biāo)，校園內(nèi)重要公共設(shè)施的優(yōu)化布局更加重要。此時(shí)，校園巴士應(yīng)運(yùn)發(fā)展起來，國(guó)內(nèi)高校大部分都有了校園巴士的身影。校內(nèi)師生對(duì)校園巴士的需求增多，但校園巴士數(shù)量供應(yīng)有限，需要合理安排運(yùn)行時(shí)長(zhǎng)與路線才能夠滿足眾多師生的生活需求。對(duì)校園巴士的路徑進(jìn)行優(yōu)化不僅可以減少資源的占用和浪費(fèi)，還保證了校園師生的安全，為創(chuàng)建節(jié)約型校園作出貢獻(xiàn)。薛瑞和陳世發(fā)采用Dijkstra算法為基礎(chǔ)，采用地理信息系統(tǒng)（GIS）空間網(wǎng)絡(luò)分析方法，規(guī)劃了校園巴士各乘車站點(diǎn)間最優(yōu)路徑的整體規(guī)劃方案。Lekin軟件作為教學(xué)的學(xué)術(shù)軟件，可以很好地解決車間調(diào)度問題。AZEMI，等使用Lekin和遺傳算法進(jìn)行企業(yè)流程優(yōu)化和調(diào)度。Balog，等采用Lekin軟件對(duì)工程部件實(shí)際制造過程的時(shí)間進(jìn)行結(jié)構(gòu)優(yōu)化，并取得了良好的效果。綜上所述，Lekin軟件可以很好地適用并解決校園巴士的路徑規(guī)劃問題。

本文以廣州華商學(xué)院為例，研究校園巴士的運(yùn)輸路徑優(yōu)化問題。廣州華商學(xué)院占地面積1 000畝，在校師生近40 000人，學(xué)校整體呈東西走向，從西區(qū)最邊的華商街到東區(qū)最邊的崇德樓步行至少需要15-25min，該路程還包括了上坡下坡等耗費(fèi)體力的路段，有時(shí)還會(huì)因?yàn)槿肆髁刻螅诵械?校道不夠?qū)挸ǘ霈F(xiàn)行路緩慢甚至堵塞的情況，因此師生們對(duì)交通工具有極大的需求。校園巴士制造成本較低，結(jié)構(gòu)簡(jiǎn)單，操作方便，承載量合理，桌位間隔空間恰到好處，在校園內(nèi)按時(shí)間點(diǎn)來運(yùn)行方便又便宜，安全且平穩(wěn)。根據(jù)調(diào)研發(fā)現(xiàn)廣州華商學(xué)院校內(nèi)設(shè)有多個(gè)校園巴士站點(diǎn)，但每一站點(diǎn)上下車用時(shí)并不相同，站點(diǎn)與站點(diǎn)之間也有不止一條路線。在上課和下課高峰時(shí)段，校園巴士供不應(yīng)求。與此同時(shí)，上下課期間校園內(nèi)道路擁擠，如何規(guī)劃校園巴士的路線，緩解校園巴士的運(yùn)輸壓力，成為當(dāng)前急需解決的難題。

1 方法介紹

1.1 Lekin軟件介紹

Lekin調(diào)度系統(tǒng)是紐約大學(xué)開發(fā)的用于教學(xué)的學(xué)術(shù)系統(tǒng)。該系統(tǒng)包含了8種優(yōu)先規(guī)則算法和4種啟發(fā)式算法，可以解決6種類型的車間調(diào)度問題。它允許用戶鏈接并測(cè)試自己的啟發(fā)式算法，并且和嵌入系統(tǒng)的算法進(jìn)行性能比較。該軟件是作為一種教育工具而創(chuàng)建的，其主要目的是向?qū)W生介紹日程安排理論及其應(yīng)用。軟件內(nèi)包含6 種工作環(huán)境，分別是：Single Maching（單機(jī)調(diào)度）、Flow Shop（流程型工廠）、Job Shop（作業(yè)車間調(diào)度）、Paralle Machines（并行機(jī)調(diào)度）、Flexible Shop（柔性流水車間調(diào)度）和Flexible Job Shop（柔性作業(yè)車間調(diào)度）。該軟件還包含8種優(yōu)先規(guī)則算法，分別是：ATCS（近似估計(jì)的延誤時(shí)間下考慮成本與整備時(shí)間算法）、EDD（最早工期優(yōu)先規(guī)則）、MS（最小寬裕時(shí)間規(guī)則）、FCFS（先到先服務(wù)優(yōu)先規(guī)則）、LPT（最長(zhǎng)加工時(shí)間優(yōu)先規(guī)則）、SPT（最短加工時(shí)間優(yōu)先規(guī)則）、WSPT（加權(quán)最短加工時(shí)間優(yōu)先規(guī)則）、CR（距到期日所剩時(shí)間/處理時(shí)間所得比率最小優(yōu)先規(guī)則)以及4種啟發(fā)式算法。

1.2 問題描述

本文考慮了單臺(tái)校園巴士或多臺(tái)校園巴士?jī)煞N情況下，校園巴士同時(shí)接送師生和接送效率最大化的校園巴士路徑問題。該問題具體描述如下：

（1）學(xué)校分布的每個(gè)站點(diǎn)都有師生上車或下車需求，并且滿足上車或下車需求必須在同一輛校園巴士，校園巴士在每個(gè)站點(diǎn)只允許?？?次；

（2）由于不同站點(diǎn)有不同數(shù)量的師生上下車，造成不同站點(diǎn)需要的?？繒r(shí)間也不相同；

（3）從華商街到各個(gè)站點(diǎn)的距離不同，校園巴士行車時(shí)間也不相同；

（4）校園巴士到各個(gè)站點(diǎn)的時(shí)間會(huì)有存在延遲的情況。

1.3 參數(shù)建立

廣州華商學(xué)院校園巴士停靠情況見表1，表中jobs 一列代表編號(hào)1-10個(gè)坐標(biāo)站點(diǎn)，通過調(diào)研得出各站點(diǎn)所在的校園巴士?？繒r(shí)間、校園巴士行駛時(shí)間、校園巴士預(yù)期到達(dá)時(shí)間。在進(jìn)行Lekin軟件求解時(shí)，會(huì)將表中參數(shù)代入，計(jì)算出不同數(shù)量校園巴士在不同法則下的最優(yōu)路徑。

在使用單輛校園巴士進(jìn)行路徑選擇時(shí)，在各個(gè)站點(diǎn)設(shè)立任務(wù)，并輸入相關(guān)參數(shù)，然后根據(jù)8 個(gè)算法查看每種方法下的路徑選擇，最后打開績(jī)效分析圖，各項(xiàng)數(shù)據(jù)較優(yōu)的路徑則為最佳路徑。校園巴士數(shù)量為2輛時(shí)，需要選擇Paralle Machines進(jìn)行路徑選擇。

2 成果與數(shù)據(jù)分析

以廣州華商學(xué)院崇德樓（東區(qū)）為始發(fā)點(diǎn)，華商街（西區(qū)）為終點(diǎn)的路線為例，在單車、雙車兩種情況下，對(duì)華商校園巴士的路徑選擇進(jìn)行優(yōu)化。

表1 廣州華商學(xué)院校園巴士停靠情況表（單位：min）

2.1 單車情況下的校園巴士路徑分析

由圖1 可知，在ATCS 法則下校園巴士的運(yùn)輸路徑為五飯-崇德樓-西九-東一-華商校門-明星-華職校門-三飯-速來寶-西十六。

圖1 ATCS法則下校園巴士的運(yùn)輸路徑

由圖2可知，在EDD法則下校園巴士的運(yùn)輸路徑為五飯-西九-明星-崇德樓-華商校門-東一-速來寶-華職校門-三飯-西十六。

圖2 EDD法則下校園巴士的運(yùn)輸路徑

由圖3可知，在MS法則下校園巴士的運(yùn)輸路徑為華商校門-速來寶-三飯-西十六-五飯-西九-華職校門-明星-東一-崇德樓。

圖3 MS法則下校園巴士的運(yùn)輸路徑

由圖4可知，在FCFS法則下校園巴士的運(yùn)輸路徑為西九-明星-華商校門-速來寶-華職校門-三飯-西十六-東一-崇德樓-五飯。

圖4 FCFS法則下校園巴士的運(yùn)輸路徑

從圖5中可知，在LPT法則下校園巴士的運(yùn)輸路徑為西十六-三飯-華職校門-速來寶-華商校門-東一-明星-崇德樓-西九-五飯。

圖5 LPT法則下校園巴士的運(yùn)輸路徑

由圖6可知，在SPT法則下校園巴士的運(yùn)輸路徑為西九-五飯-明星-崇德樓-東一-華商校門-速來寶-華職校門-三飯-西十六。

圖6 SPT法則下校園巴士的運(yùn)輸路徑

由圖7可知，在WSPT法則下校園巴士的運(yùn)輸路徑為崇德樓-五飯-西九-東一-華商校門-明星-華職校門-三飯-速來寶-西十六。

圖7 WSPT法則下校園巴士的運(yùn)輸路徑

由圖8可知，在CR法則下校園巴士的運(yùn)輸路徑為五飯-西九-明星-崇德樓-東一-華商校門-速來寶-華職校門-三飯-西十六。

圖8 CR法則下校園巴士的運(yùn)輸路徑

表2 八種法則下校園巴士運(yùn)輸路徑的績(jī)效指標(biāo)

從績(jī)效分析表可得，最大延誤時(shí)間（T）指標(biāo)中八種法則的排序是ATCS,CR,EDD,SPT,WSPT＜MS＜FCFS,LPT。因此最佳方案選擇為ATCS、CR、EDD、SPT、WSPT法則下的調(diào)度結(jié)果，單個(gè)校園巴士情況下最大延誤時(shí)間為54min?？傔\(yùn)輸站點(diǎn)延誤數(shù)（∑U）指標(biāo)中八大法則的排序是FCFS,SPT,WSPT＜ATCS,CR,EDD,LPT,MS，最大總派送地點(diǎn)延誤數(shù)為9個(gè)。運(yùn)輸總時(shí)間（∑C）指標(biāo)中八大法則的排序是CR,SPT＜EDD＜ATCS＜WSPT＜FCFS＜MS＜LPT，最 大 運(yùn) 輸 總 時(shí) 間 為250min。總延誤時(shí)間（∑T）指標(biāo)中八大法則的排序是CR,SPT＜EDD＜ATCS＜WSPT＜FCFS＜MS＜LPT，最大總延誤時(shí)間為185min?？偧訖?quán)運(yùn)輸時(shí)間（∑WC）指標(biāo)中八大法則的排序是WSPT＜ATCS＜CR＜SPT＜EDD＜FCFS＜MS＜LPT，其 中 最 小 的 總 加 權(quán) 運(yùn) 輸 時(shí) 間 是445min?？偧訖?quán)延誤時(shí)間（∑WT）指標(biāo)中八大法則的排序是ATCS＜WSPT＜CR＜SPT＜FCFS＜MS＜LPT，其中最小的總加權(quán)延誤時(shí)間為309min。

根據(jù)績(jī)效分析表，選出各指標(biāo)中數(shù)據(jù)最小的三項(xiàng)，繪制頻數(shù)分布圖，如圖9所示。

圖9 單車情況下八大法則的分布圖

由圖9可知，CR和SPT輛法則是出現(xiàn)次數(shù)最多的兩個(gè)法則。在該法則下，績(jī)效指標(biāo)最小的個(gè)數(shù)都是5。

圖10 單車情況下各八大法則雷達(dá)圖

由雷達(dá)圖（如圖10所示）可知，八種派工法則中，派工法則SPT的單車路徑可以實(shí)現(xiàn)最優(yōu)。

2.2 雙車情況下的校園巴士路徑分析

在ATCS法則下兩輛校園巴士的運(yùn)輸路徑分別為五飯-西九-華商校門-華職校門-速來寶；崇德樓-東一-明星-三飯-西十六。具體如圖11所示。

圖11 ATCS法則下兩輛校園巴士的運(yùn)輸路徑

在EDD法則下兩輛校園巴士的運(yùn)輸路徑分別為五飯-明星-華商校門-華職校門-西十六；西九-崇德樓-東一-速來寶-三飯。具體如圖12所示。

圖12 EDD法則下兩輛校園巴士的運(yùn)輸路徑

在MS法則下兩輛校園巴士的運(yùn)輸路徑分別是華商校門-三飯-五飯-西九-明星-東一-崇德樓；速來寶-西十六-華職校門。具體如圖13所示。

圖13 MS法則下兩輛校園巴士的運(yùn)輸路徑

在FCFS法則下兩輛校園巴士的運(yùn)輸路徑分別是西九-華商校門-華職校門-西十六；明星-速來寶-三飯-東一-崇德樓-五飯。具體如圖14所示。

圖14 FCFS法則下兩輛校園巴士的運(yùn)輸路徑

在LPT 法則下兩輛校園巴士的運(yùn)輸路徑分別是西十六-速來寶-華商校門-崇德樓-五飯；三飯-華職校門-東一-明星-西九。具體如圖15所示。

圖15 LPT法則下兩輛校園巴士的運(yùn)輸路徑

在SPT 法則下兩輛校園巴士的運(yùn)輸路徑分別是西九-明星-東一-速來寶-三飯；五飯-崇德樓-華商校門-華職校門-西十六。具體如圖16所示。

在WSPT法則下兩輛校園巴士的運(yùn)輸路徑分別是崇德樓-東一-明星-華職校門-速來寶；五飯-西九-華

圖16 SPT法則下兩輛校園巴士的運(yùn)輸路徑

商校門-三飯-西十六。具體如圖17所示。

圖17 WSPT法則下兩輛校園巴士的運(yùn)輸路徑

在CR法則下兩輛校園巴士的運(yùn)輸路徑分別是五飯-西九-明星-崇德樓-速來寶-三飯；華商校門-東一-華職校門-西十六。具體如圖18所示。

圖18 CR法則下兩輛校園巴士的運(yùn)輸路徑

績(jī)效分析表（Log book）是經(jīng)過八個(gè)方案選擇調(diào)度后所得出的調(diào)度目標(biāo)的結(jié)果。對(duì)比各個(gè)法則的績(jī)效指標(biāo)，擁有最小值較多項(xiàng)者，則為最優(yōu)路徑選擇結(jié)果。

表3 八種法則下兩輛校園巴士運(yùn)輸路徑的績(jī)效指標(biāo)表

由表3 可得，C指標(biāo)中八種法則的排序是FCFS，LPT＜MS＜CR,EDD,SPT＜ATCS,WSPT,因此最佳方案選擇為FCFS,LPT 法則下的調(diào)度結(jié)果，雙車下最長(zhǎng)運(yùn)輸時(shí)間為34min。T指標(biāo)中八種法則的排序是CR,EDD,SPT＜ATCS,WSPT＜MS＜FCFS,LPT。因此最佳方案選擇為CR,EDD,SPT法則下的調(diào)度結(jié)果，雙車下最長(zhǎng)延誤時(shí)間為23min。∑U指標(biāo)中八大法則的排序是FCFS＜ATCS,EDD,SPT,WSPT＜CR,LPT,MS,因此總運(yùn)輸?shù)攸c(diǎn)延誤數(shù)為8個(gè)。∑C指標(biāo)中八大法則的排序 是EDD,SPT＜CR＜WSPT,ATCS＜FCFS＜MS＜LPT，運(yùn)輸總時(shí)間為143min?！芓指標(biāo)中八大法則的排序是SPT,EDD＜CR＜ATCS,WSPT＜FCFS＜MS＜LPT，總 延 誤時(shí)間為78min。∑WC指標(biāo)中八大法則的排序是ATCS,WSPT＜EDD,SPT＜CR＜FCFS＜MS＜LPT,其中總加權(quán)運(yùn)輸時(shí)間是262min?！芖T指標(biāo)中八大法則的排序 是ATCS,WSPT＜SPT,EDD＜CR＜FCFS＜MS＜LPT，其中總加權(quán)延誤時(shí)間為130min。

由圖19可知，EDD和SPT是出現(xiàn)次數(shù)最多的兩個(gè)法則。在該法則下，績(jī)效指標(biāo)最小的個(gè)數(shù)都是6。結(jié)合雷達(dá)圖（如圖20所示）可知，在雙車情況下，派工法則EDD為最優(yōu)派工法則。

圖19 雙車情況下八大法則的分布圖

圖20 雙車情況下各八大法則雷達(dá)圖

3 結(jié)語

隨著高校擴(kuò)招以及高校校園擴(kuò)建，方便出行成為廣大師生關(guān)注的關(guān)鍵問題。

本文通過調(diào)研對(duì)校園內(nèi)師生的交通現(xiàn)狀進(jìn)行深入了解，在此基礎(chǔ)上，確定了廣州華商學(xué)院校內(nèi)巴士的設(shè)計(jì)原則，結(jié)合上述Lekin實(shí)驗(yàn)分析，把實(shí)際問題轉(zhuǎn)變?yōu)閿?shù)學(xué)模型來求解最優(yōu)路徑，最后對(duì)調(diào)研數(shù)據(jù)進(jìn)行歸納與整理，設(shè)計(jì)了符合廣州華商學(xué)院實(shí)際情況的校園巴士站點(diǎn)和路線。在單車情況下，西九-五飯-明星-崇德樓-東一-華商校門-速來寶-華職校門-三飯-西十六的路徑為最優(yōu)；在雙車情況下，兩輛校園巴士的運(yùn)輸路徑分別是五飯-明星-華商校門-華職校門-西十六；西九-崇德樓-東一-速來寶-三飯為最優(yōu)。