基于蟻群優(yōu)化算法的S大學(xué)校內(nèi)校車路線優(yōu)化研究目錄TOC\o"1-3"\h\u36631前言 1219561.1研究背景以意義 166391.1.1研究背景 1284141.1.2研究意義 2306071.2國內(nèi)外相關(guān)文獻(xiàn)綜述 3167182研究方法 424722.1研究思路 441052.2研究內(nèi)容及工具 5117902.2.1目前學(xué)生出行情況調(diào)查 546592.2.2校車站點設(shè)計 5302272.2.3校車路線設(shè)計 6309063校車站點設(shè)計 721483.1基礎(chǔ)數(shù)據(jù)收集 7274493.2校車站點設(shè)計 9171964校車路線設(shè)計 14225744.1相關(guān)理論概述 14102484.2蟻群優(yōu)化算法及其實現(xiàn) 15104405結(jié)論 19222645.1相關(guān)理論概述 1925365附錄 201前言研究背景以意義1.1.1研究背景以S大學(xué)為例，根據(jù)百度百科的數(shù)據(jù)，從2021年4月開始，S大學(xué)官方網(wǎng)站顯示，校園占地面積243萬平方米，校園建筑面積104多萬平方米，S大學(xué)現(xiàn)有兩個主校區(qū)，西校區(qū)（主校區(qū)）和東校區(qū)，以西校區(qū)為例，西校區(qū)主要分為南苑和北苑，南苑主要是宿舍，北苑有教學(xué)、宿舍等。此外，學(xué)生上課的地方往往遠(yuǎn)離宿舍樓。學(xué)生們通常把大部分時間花在上課的通勤上。而現(xiàn)在，校車的運行情況也不是很好，目前校園主要是供學(xué)生購買電動車、自行車和各種自行車共用，主管部門還沒有制定明確的校車出行規(guī)則，以保證學(xué)生出行的安全。此外，自行車共享是混合的，稅收也不統(tǒng)一。學(xué)校在這方面沒有統(tǒng)一的管理，學(xué)生每天上下班的時間比較多，大部分學(xué)生沒有自己的交通工具，因此，建立一個健康的校車管理體系不僅僅是暨南大學(xué)，暨南大學(xué)過去也實施過校車管理計劃，但不會長久存在。現(xiàn)在破車還停在圖書館下面，每次去圖書館都能看到。具體如圖1.1所示，當(dāng)時校車覆蓋面積只能滿足少數(shù)學(xué)生的需求；因此，有必要對新型校車的操作系統(tǒng)進(jìn)行優(yōu)化。圖1.1原校車目前狀況1.1.2研究意義如今，校園內(nèi)主要的交通工具是電動車、自行車、共享單車和教師注冊的私家車，一般來說，大多數(shù)大學(xué)生應(yīng)該比較清楚[1]。學(xué)生在學(xué)校的日常出行需求相對較高，但由于實行無車管制制度，學(xué)校共享自行車的壟斷相對不完全，學(xué)校在這方面為學(xué)生提供的服務(wù)水平降低。經(jīng)過一定的檢查，學(xué)校的非機(jī)動車輛數(shù)量也比過去減少了，學(xué)生的交通工具選擇也和往常不一樣了，大學(xué)生的選擇余地仍然很小，這給大學(xué)生的求學(xué)之路造成了很大的障礙和問題。校車的管理是影響校車運行安全的重要因素[2]。加強(qiáng)對校車的重視，促進(jìn)校車的管理；此外，綜合管理處應(yīng)對校車主體進(jìn)行管理，落實管理責(zé)任[3]，校車運營的實施有利于滿足學(xué)生出行需求，并且是一個提高后勤服務(wù)水平的系統(tǒng)，使學(xué)生和教職工的出行更加快捷方便，校車系統(tǒng)既能滿足學(xué)生和教職工的出行需求，又起到了比較強(qiáng)的帶動作用。適當(dāng)?shù)囊?guī)劃可以使校車成為學(xué)校自身獨特的文化特色和效益所在，從而提高學(xué)生的素質(zhì)，從而保證高等教育優(yōu)質(zhì)活動的開展。本研究在前人理論的基礎(chǔ)上，對暨南大學(xué)校車的運行路線和規(guī)劃進(jìn)行了優(yōu)化研究，而且學(xué)生宿舍和教育大樓的碩士點之間或者教學(xué)樓和教學(xué)樓之間的距離往往很大，校車開了一段時間，但場地太小，現(xiàn)在停了?？梢詾樾＼囘\營提供更好的理論指導(dǎo)。另外，校車管理問題的解決將直接影響學(xué)生和教職工群體在校園自學(xué)或上課的體驗。綜上所述，本研究可為解決校車及校車線路管理問題提供一定的理論指導(dǎo)。1.2國內(nèi)外相關(guān)文獻(xiàn)綜述上世紀(jì)五六十年代，dancing和Ramser首次用學(xué)術(shù)術(shù)語提出了車輛定位問題，后來，越來越多的學(xué)者開始研究這類相關(guān)問題，60年代末，克拉克和賴特首先改進(jìn)了dancing和ramser提出的數(shù)學(xué)模型，這就是臭名昭著的歐亞貪婪算法的起源。由于有一定數(shù)量的客戶，具體的配送中心要根據(jù)客戶對商品的不同需求量提供相應(yīng)的商品，并由一個或多個團(tuán)隊負(fù)責(zé)不同客戶的商品配送和相應(yīng)路線的選擇。其目的是在滿足顧客需求的同時，也要在特定的約束條件下，實現(xiàn)這些優(yōu)化目標(biāo)，如成本最小、距離最短、時間消耗最小等。圖1.2車輛路徑問題圖示校車路徑問題（SBRP）則是在滿足各種已有的約束條件下安排校車運營路線的最優(yōu)化問題，是校車運營管理環(huán)節(jié)中的關(guān)鍵環(huán)節(jié)。SBRP屬于車輛路徑問題（VRP）的一個重要應(yīng)用分支，自1969年由Newton和Thomas提出后，學(xué)者們持續(xù)不斷地探索相關(guān)的數(shù)學(xué)模型及求解算法。而校車路徑問題對應(yīng)于不同的情況也有不同的分類。校車一般指的是接送中小學(xué)上下學(xué)的指定車輛。但是對于高校而言，校車問題主要可以分為兩種：一種是校外校車，負(fù)責(zé)不同校區(qū)之間教職工的輸送的工作；另一種是校內(nèi)校車，校內(nèi)校車是滿足學(xué)生及教職工在校園內(nèi)出行需要必備的交通工具。本研究主要以校內(nèi)校車的站點及路線設(shè)計為主要的研究對象。在當(dāng)今關(guān)于校車定位問題的主要研究目標(biāo)中，校車管理成本往往是國內(nèi)外學(xué)生所考慮的唯一或主要的優(yōu)化目標(biāo)，而與成本密切相關(guān)的變量包括校車數(shù)量，總里程（時間）等變量，劉查[4]等人的研究結(jié)果表明，如果校車的數(shù)量和日耗油量等相關(guān)成本能夠在一定程度上降低，這將是降低運營成本的主要途徑。國內(nèi)外學(xué)者以運營成本為優(yōu)化目標(biāo)進(jìn)行了具體的研究，Martinez[5]提出了一種分支算法和一種捆綁算法來解決里斯本學(xué)校公交車上的問題，Arias-Rojas[6]等人采用蟻群優(yōu)化算法來解決優(yōu)化校車的總工作時間，Rieraledesmas[7]等人以校車總里程為優(yōu)化目標(biāo)，他們建立了設(shè)計模型，并用精確的算法進(jìn)行求解，張淼[8]創(chuàng)建了一個規(guī)劃問題的移動模型來訓(xùn)練校車，并用遺傳算法來優(yōu)化校車路徑的總長度他們考慮了車輛數(shù)量和運營總里程，并使用啟發(fā)式算法來解決相關(guān)問題。劉青松[10]等人采用模擬反饋算法對運營總里程進(jìn)行優(yōu)化，上述文獻(xiàn)是基于考慮運力約束，沒有考慮服務(wù)質(zhì)量等其他問題。此外，在校車定位問題次級方案下，尋找校車站的選擇是非常重要和必要的。它主要用于確定校車站的位置和分配學(xué)生到站，校車站的分布直接決定了學(xué)生步行到車站的距離；作為學(xué)校路線規(guī)劃問題的一部分，校車站問題很少單獨討論，對校車站選址的研究大多集中在最大人口覆蓋率或最小運營成本上；校車站的軌道往往遵循學(xué)生最短的總距離，效益最小的站數(shù)覆蓋所有學(xué)生，針對這一問題，國內(nèi)外學(xué)者在這方面做了大量的研究。國外一些學(xué)者提出了公交站點優(yōu)化的數(shù)學(xué)模型，使總出行時間最小化；國外也有一些學(xué)者將現(xiàn)有的公交站點作為潛在的公交站點，自行選擇將學(xué)生直接分配到公交站點；在搜索相關(guān)研究方法方面，任立[11]采用基于時空聚類的遺傳算法對客戶點進(jìn)行分組，并將其分配到不同的分布區(qū)域；張富[9]等人提出了以至少包含所有數(shù)據(jù)點的圓心攝取法作為校準(zhǔn)點，但大多數(shù)方法除了從現(xiàn)有公交站點選擇外，很少考慮公共汽車站應(yīng)位于道路網(wǎng)絡(luò)上的問題。目前國內(nèi)外對校車路線問題及相關(guān)問題的研究，在查閱了大量國內(nèi)外相關(guān)文獻(xiàn)后，本研究擬利用spss26軟件包中的系統(tǒng)聚類或K均值聚類算法等工具和MATLAB中的蟻群優(yōu)化算法的方法，對該問題的選址和路線設(shè)計進(jìn)行詳細(xì)的研究，以指導(dǎo)校車，最后設(shè)計一條新的公交線路。2研究方法2.1研究思路本研究以優(yōu)化設(shè)計S大學(xué)校園內(nèi)的校內(nèi)校車路線為主要的研究目標(biāo)。初期，采用騰訊問卷網(wǎng)上調(diào)查的方式收集學(xué)生們當(dāng)今出行的主要方式以及學(xué)生們對于校車的需求程度。此外，我們還收集了學(xué)生們?nèi)粘５幕顒勇肪€以及活動區(qū)域，為下一步校車站點選擇問題做好數(shù)據(jù)方面的準(zhǔn)備。接下來的任務(wù)主要是確定校車站點。因為在校園內(nèi)，宿舍樓、教學(xué)樓等區(qū)域往往并不是隨機(jī)分布的，而是有聚集的。所以一個教學(xué)樓設(shè)置一個站點顯然是有浪費的。而且校車短時間內(nèi)多次?？匡@然在經(jīng)濟(jì)上也是不可合理的，是不環(huán)保的。為了解決這個問題，擬選用spss26軟件包內(nèi)自帶的系統(tǒng)聚類或者K均值聚類等工具，對所有點進(jìn)行聚類分析，再結(jié)合校園內(nèi)日常主要干道的人流量等具體情況，最終確定校車運行所能夠?？康母鱾€站點。最后，就是本研究的主體部分對校車路線進(jìn)行規(guī)劃設(shè)計。在查閱了很多前人的研究后，最后確定以蟻群優(yōu)化算法為主要工具，對校車路徑問題進(jìn)行研究并最終制定出合理的符合實際情況的校車運營路線以及相應(yīng)的調(diào)度規(guī)劃。2.2研究內(nèi)容及工具本研究圍繞校內(nèi)校車的路徑優(yōu)化問題為主要目標(biāo)，分層次分階段的對各個步驟進(jìn)行科學(xué)的研究，主要有以下幾點內(nèi)容，包括對當(dāng)下校內(nèi)校內(nèi)的大學(xué)生出行情況、日出行平均次數(shù)、對校車的需求程度等的的調(diào)查，校內(nèi)校車站點的選擇以校內(nèi)校車路線的制定。下面對這幾方面的內(nèi)容以及主要的研究工具分別進(jìn)行詳細(xì)的說明。2.2.1目前學(xué)生出行情況調(diào)查要設(shè)計出新的校車運行路線，最重要的不是算法或者說設(shè)計工具的選擇，而是對當(dāng)下校園內(nèi)學(xué)生出行情況的調(diào)查以及學(xué)生群體對于校車的需求程度。為此，根據(jù)目前的實際情況，采取問卷調(diào)查收集信息是最為方便也是最為可靠的方法。在工具的選擇上，采用了騰訊問卷網(wǎng)上調(diào)查的方式。首先調(diào)查了學(xué)生們的基本人口學(xué)變量，比如說性別，年級等。其次，調(diào)查了同學(xué)們現(xiàn)在主要的活動區(qū)域以及經(jīng)常去的教學(xué)樓等情況，以及日出行次數(shù)還有目的地等，收集這部分的信息主要是為了下一步校內(nèi)車站點的采集提供詳細(xì)的數(shù)據(jù)基礎(chǔ)；還有的就是同學(xué)們對于校內(nèi)校車的需求度，這直接關(guān)系到了本篇論文的研究價值；最后就是學(xué)生們的日常出行時間等信息，這些信息為接下來校車的運行時間提供一定的參考價值。2.2.2校車站點設(shè)計在校車路徑問題（SBRP）的相關(guān)聯(lián)的子問題下面，站點選擇問題的研究也是非常重要的而且必須是要被考慮的。一個好的站點選擇既能避免不必要的浪費更能夠節(jié)省學(xué)生們的時間。校車站點布局問題是一種服務(wù)于學(xué)生及老師群體的一種設(shè)施選址問題，在本研究中主要是服務(wù)于大學(xué)內(nèi)的學(xué)生以及老師們，其中大學(xué)生是服務(wù)對象的主體。站點的選擇主要用于確定校車車站的位置，并將學(xué)生分配到站點上。校車站點的分布直接決定了學(xué)生到車站的步行距離；而作為校車路徑規(guī)劃問題中的一部分，校車站點布局問題很少被研究學(xué)者們單獨拿出來討論。大多數(shù)設(shè)施選址研究均以最大化的人的口覆蓋面積或者是最小化的運行成本為主要的優(yōu)化目標(biāo)；而校車站點布局往往追求學(xué)生總的步行距離最短獲益最少的站點數(shù)覆蓋所有的學(xué)生。校車站點設(shè)置的太少，沒有辦法去滿足學(xué)生們的需要，而設(shè)置的太多則有可能會造成浪費，也不夠環(huán)保，對于校車運行成本也會造成一定的壓力。在站點選擇的問題中，大部分學(xué)者都會采用聚類的算法，把相近或者相似的的點歸為一個點，這樣就能大大的減少浪費。聚類算法在有的研究學(xué)者的論文中也把它稱作“群分析”，聚類算法是研究樣品或者指標(biāo)的一種數(shù)學(xué)上的統(tǒng)計分析方法，同時它也是數(shù)據(jù)挖掘領(lǐng)域內(nèi)的一個重要算法。聚類分析是由若干個互不相同的模式組合而成的。通常來說，模式是一個可以度量的量，或者可以說是在多維空間中的一個點就是一個模式。聚類分析的基礎(chǔ)就是由相似性而來的，在一個聚類中的模式之間比不在同一聚類中的模式之間具有更多的相似性。常見的聚類算法主要有劃分法、基于密度的方法、基于網(wǎng)格的方法、層次法以及基于模型的方法。實際的研究中，學(xué)者們通常用K-means聚類算法、K-means++聚類算法、系統(tǒng)聚類算法等。在本研究中，由于聚類的是二維平面內(nèi)的各個不相同的點，所以采用聚類算法或者K均值聚類算法往往會有較好的聚類效果。2.2.3校車路線設(shè)計在確定學(xué)校站點后，下一步就是規(guī)劃校園校車路線，在當(dāng)前優(yōu)化學(xué)校路徑的目標(biāo)下，成本往往是優(yōu)化的唯一目標(biāo)或主要目標(biāo)，與成本密切相關(guān)的目標(biāo)包括校車數(shù)量、總里程（時間）等，國內(nèi)外學(xué)者對成本優(yōu)化進(jìn)行了相關(guān)研究。一些學(xué)者提出了解決葡萄牙里斯本市校車問題的連接分支和算法；有學(xué)者計劃利用蟻群優(yōu)化算法對校車的總工作時間進(jìn)行優(yōu)化；有學(xué)者將校車總里程作為優(yōu)化路線設(shè)計的目標(biāo)，建立相應(yīng)的設(shè)計模型，并用精確算法進(jìn)行求解，在現(xiàn)有的優(yōu)化算法系統(tǒng)中，有兩種常見的系統(tǒng)：一種是精確的算法，可以得到比較精確的結(jié)果；另一種是啟發(fā)式算法。這類算法不需要對最優(yōu)目標(biāo)解進(jìn)行優(yōu)化，只需要找到一個滿意的解，常用的啟發(fā)式算法模擬了重組、蟻群優(yōu)化、模糊全局評價等，采用蟻群優(yōu)化算法設(shè)計校園路由問題，蟻群算法是一種啟發(fā)式算法，實踐證明，蟻群算法在求解TSP問題時具有良好的性能。

3校車站點設(shè)計3.1基礎(chǔ)數(shù)據(jù)收集校車路徑問題的第一步就是調(diào)查情況，設(shè)計合理化的站點。為此，本研究通過騰訊問卷網(wǎng)上調(diào)查的方式，收集學(xué)生們的基本信息、出行方式、日出行次數(shù)、活動區(qū)域以及對于校內(nèi)校車的需求程度等信息。具體的問卷結(jié)構(gòu)以及各個部分相對應(yīng)的信息可以在附錄中進(jìn)行查看。下面對收集上的數(shù)據(jù)進(jìn)行簡要的分析，詳細(xì)情況見下表：表3.1性別分布表性別頻率百分比男生6050.8女生5849.2合計118100.0表3.2年級分布表年級頻率百分比大一1512.7大二2722.9大三2823.7大四4840.7合計118100.0如上表3.1、表3.2所示，本次問卷調(diào)查共收集了S大學(xué)大一至大四的118名學(xué)生的數(shù)據(jù)，其中男生占比50.8%，女生占比49.2%。在表3.2年級分布表中，大一學(xué)生占總?cè)藬?shù)的12.7%；大二學(xué)生占總?cè)藬?shù)的22.9%。大三學(xué)生占總?cè)藬?shù)的23.7%；大四學(xué)生占總?cè)藬?shù)的40.7%。這些數(shù)據(jù)基本上能反映出S大學(xué)校園內(nèi)整體大學(xué)生的情況了。接下來，對于學(xué)生出行的主要方式以及日出行情況和對校車的需求程度等信息也做了一定的收集，具體詳細(xì)信息見下表：表3.3出行方式出行方式頻率百分比騎車（自行車、電動車）4538.1走路7361.9合計118100.0表3.4日出行次數(shù)情況表日出行次數(shù)頻率百分比一次3529.7兩次或三次5647.5大于三次2722.5合計118100.0我們對學(xué)生的出行情況做了簡要的調(diào)查，結(jié)果見上表3.3、表3.4。結(jié)果顯示，在學(xué)生群體中，出行方式為走路的為全體學(xué)生的61.9%；而選擇騎自行車或者是選擇電動車的占全體學(xué)生總數(shù)的38.1%。也就是說，在校園內(nèi)有超過6成的大學(xué)生是走路的。接下來，我們有對學(xué)生的日出行次數(shù)情況做了統(tǒng)計，結(jié)果顯示日出行在兩次及兩次以上的學(xué)生占全體學(xué)生的70.3%。大約占了全體學(xué)生的7成；而每天的平均出行次數(shù)為一次的只占了全體學(xué)生總數(shù)的三成。結(jié)合這些數(shù)據(jù)來看，學(xué)生中的大部分在校園內(nèi)是沒有電動車的，有電動車的只占了一小部分，大多數(shù)學(xué)生還是選擇了走路上下課。而且，大部分學(xué)生的日出行平均次數(shù)為兩次及以上，說明了大家對于校車這種的需求還是有的，而且很大。表3.5管制校園內(nèi)個人交通工具意愿表是否希望管制頻率百分比希望管制8067.8不希望管制3832.2合計118100.0表3.6校內(nèi)校車需求表是否有需求頻率百分比不需要2319.5有點需要3428.8需要6151.7合計118100.0表3.7乘坐校車意愿表是否選擇乘坐頻率百分比是5546.6否3428.8不確定2924.6合計118100.0為了進(jìn)一步的驗證此結(jié)論，本研究接著調(diào)查了學(xué)生們對于現(xiàn)行的個人交通管制的看法以及對于校內(nèi)校車的一些看法。詳細(xì)結(jié)果見上表3.5、表3.6以及表3.7。根據(jù)表中的數(shù)據(jù)可以看出，在全體調(diào)查樣本中，有67.8%的學(xué)生支持管控學(xué)校內(nèi)的個人交通工具，接近了7成；與此同時，在這之中只有32.2%的人不希望管制校園內(nèi)的個人交通工具。這表明學(xué)生是希望管控這些個人的交通工具的，更希望有校車這種更安全的交通工具的出現(xiàn)。接下來，在校內(nèi)校車需求表中的數(shù)據(jù)與之前的推論是相吻合的。只有19.5%的學(xué)生不需要校內(nèi)小車的運營，占比不到兩成。超過8成的學(xué)生對于校內(nèi)校車是持肯定態(tài)度的。在隨后的乘坐校車意愿表中，只有24.6%的學(xué)生明確表示不會乘坐，大多數(shù)學(xué)生都表示會乘坐的。綜上所述，可以看出，校內(nèi)校車對于學(xué)生來說是有很大好處的，而且大多數(shù)學(xué)生都支持這樣的事情，這也從另外一方面說明了本研究是有意義的。圖3.1支付方式選擇關(guān)于校車運行后的支付方式，也做了一定的調(diào)查，調(diào)查結(jié)果顯示在118民學(xué)生中，有98名學(xué)生表示可以接受校園卡支付；有97名學(xué)生表示可以接受有微信支付寶這樣的付款方式；僅有13名學(xué)生選擇了現(xiàn)金支付。所以，結(jié)合同學(xué)們的意愿，計劃在校車運行后采用校園卡支付，同時也支持微信支付寶這樣的付款方式。至于收費標(biāo)準(zhǔn)，則沿襲原先的收費標(biāo)準(zhǔn)，上車一次一元，給學(xué)生以最大的優(yōu)惠3.2校車站點設(shè)計在基本情況調(diào)查完后，開始進(jìn)行校車站點選擇的工作。首先，依據(jù)百度地圖等網(wǎng)上數(shù)據(jù)以及校園內(nèi)的實際情況，初步選取了28個備選的站點。S大學(xué)全貌如圖3.2所示。28個備選的站點包括主要的教學(xué)樓，各個門口以及食堂，娛樂等地方。并對這28個地方進(jìn)行編碼并按照百度地圖以適當(dāng)?shù)谋壤嬎愠龈鱾€點的坐標(biāo)。具體結(jié)果見下表3.8：圖3.2S大學(xué)地圖表3.8備選站點信息編碼名稱X軸坐標(biāo)Y軸坐標(biāo)11教4322教4233教2844教21155教5266教7277教104810教255911教2461012教29811梅花館6312圖書館28713機(jī)械樓34614土木綜合實驗樓37615逸夫科學(xué)樓361016化學(xué)化工學(xué)院361117特教樓381118一食10819二食15420三食41221八食19422大禮堂（校醫(yī)院）5823足球場6824洗浴中心18425網(wǎng)球場261026東南門29427新西門11028天橋132同時，本研究也在問卷中收集了學(xué)生們平時去的教學(xué)樓以及除去教學(xué)樓以外學(xué)生們經(jīng)常去的地方的相關(guān)信息，具體詳細(xì)結(jié)果如下圖3.2、圖3.3所示：圖3.2教學(xué)樓信息圖3.3其他站點信息如上圖3.2、圖3.3所示，在學(xué)生們經(jīng)常去的教學(xué)樓中，圖書館、10教以及11教是人流量最大的，而在除教學(xué)樓以外的備選站點中，八食、東南門以及新西門是人流量最大的，這幾個備選站點應(yīng)該著重加以關(guān)注。在問卷調(diào)查完學(xué)生們的基本信息后，下一步就是正式的校車站點的選擇了。在本研究中，擬采用spss26軟件中的系統(tǒng)聚類以及K均值聚類對所有備選站點進(jìn)行聚類分析，詳細(xì)的分析結(jié)果見如下圖表：首先對28個坐標(biāo)進(jìn)行系統(tǒng)聚類分析，采用組間聯(lián)接的方法，區(qū)間采用平方歐式距離進(jìn)行計算，最后得出有關(guān)于28個坐標(biāo)的譜系圖，如圖3.4所示：圖3.4平均聯(lián)接譜系圖聚類結(jié)果如圖3.4所示，在進(jìn)行第一次聚類的時候把28個坐標(biāo)點分為7組；第二次把原先的7組進(jìn)一步聚類，分為了5組；第三次把原先的5組進(jìn)一步聚類，分為了3組；但因為這是校車站點的設(shè)計，在考慮實際情況后，發(fā)現(xiàn)采用系統(tǒng)聚類的方法并不合適，分的組太少，這樣學(xué)生步行到車站的距離就大大增加了。所以接著采用了spss中的K均值聚類算法進(jìn)行再一次的聚類分析。最終聚類中心以及每個中心所包含的備選站點見下表：表3.9最終聚類中心坐標(biāo)聚類中心X軸坐標(biāo)Y軸坐標(biāo)13711242329442105108673710482569143102981126101219413346143761568表3.10最終聚類中心包含備選站點聚類中心包括站點115；16；1721；2；532643；4；20；2751866；117788；9919；281010；1211251221；29131314141522；23如上表3.9、3.10的結(jié)果顯示，在經(jīng)過spss的K均值聚類分析后，把所有的28個坐標(biāo)點進(jìn)行聚類后只剩了15個坐標(biāo)點。再結(jié)合之前的系統(tǒng)聚類以及實際情況后，最終確定了校車運營站點的具體坐標(biāo)以及具體數(shù)量。圖3.5校車?？空军c圖如上圖3.5所示，圖中紅色五角星為最終確定的校車?？空军c。1號站點包括了逸夫科學(xué)樓、化學(xué)化工學(xué)院以及特教樓這三個備選站點；2號站點包括了1教、2教以及5教；3號站點主要是東南門；4號站點包括了3教、4教、新西門以及三食堂；5號站點主要是一食堂及其附近樓層；6號站點包括了梅花館以及6教；7號站點包括了7教以及附近的各個學(xué)院；8號站點包括了10教以及11教；9號站點包括了天橋以及二食堂；10號站點包括了圖書館以及12教；11號站點主要是網(wǎng)球場附近區(qū)域；12號站點主要是包括了洗浴中心、八食堂以及附近區(qū)域；13號站點主要是機(jī)械樓附近的區(qū)域；14號站點主要是土木工程綜合實驗樓以及附近區(qū)域；15號站點主要是大禮堂、校醫(yī)院以及足球場等附近區(qū)域。綜上所述，在分別用SPSS軟件中的系統(tǒng)聚類方法以及K-均值聚類方法進(jìn)行分析后，從最開始的28個坐標(biāo)點進(jìn)行一步步的聚類，最后得到了一共15個最終站點的坐標(biāo)。4校車路線設(shè)計4.1相關(guān)理論概述校車培訓(xùn)問題是在各種約束條件下組織校車管理路線的優(yōu)化問題，SBRP是車輛轉(zhuǎn)向問題（VRP）應(yīng)用的一個重要分支。自69年代牛頓和托馬斯提出校車規(guī)劃問題以來，學(xué)者們不斷探索其數(shù)學(xué)模型和算法，校車規(guī)劃問題的數(shù)學(xué)模型與車輛路徑規(guī)劃問題相似。優(yōu)化的目標(biāo)是使車輛數(shù)量、總運行時間、總行駛距離、成本、行駛距離、負(fù)荷平衡和滿意度最小化，SBRP研究涉及到數(shù)據(jù)準(zhǔn)備、選址、優(yōu)化設(shè)計、優(yōu)化設(shè)計、優(yōu)化設(shè)計等多個子問題，路線生成和車輛規(guī)劃。Desrosiers等人回顧了1981年以前的SBRP研究。Park和Kim根據(jù)問題a的特點對SBRP問題進(jìn)行了詳細(xì)分類，并對模型算法做了簡單的總結(jié)，其他研究也對SBRP問題做了簡要的回顧。在校車路徑問題的有關(guān)研究中，校車路線設(shè)計是最為關(guān)鍵的一點。校車路線設(shè)計的成功與否，直接關(guān)系到整個校車運營系統(tǒng)的最終質(zhì)量的好與壞。國內(nèi)外許多研究學(xué)者都對路線設(shè)計的方法進(jìn)行了細(xì)致的研究。一些學(xué)者提出了連接分支和算法來解決里斯本學(xué)校的公交車問題；有學(xué)者計劃利用蟻群優(yōu)化算法對校車的總工作時間進(jìn)行優(yōu)化；有學(xué)者將校車總里程作為優(yōu)化路線設(shè)計的目標(biāo)，建立相應(yīng)的設(shè)計模型，并用精確算法進(jìn)行求解，在現(xiàn)有的優(yōu)化算法系統(tǒng)中，有兩種常見的系統(tǒng)：一種是精確的算法，可以得到比較精確的結(jié)果；另一種是啟發(fā)式算法。這類算法不需要對最優(yōu)目標(biāo)解進(jìn)行優(yōu)化，只需要找到一個滿意的解，常用的啟發(fā)式算法模擬了重組、蟻群優(yōu)化、模糊全局評價等，采用蟻群優(yōu)化算法設(shè)計校園路由問題，蟻群算法是一種啟發(fā)式算法，實踐證明，蟻群算法在求解TSP問題時具有良好的性能。4.2蟻群優(yōu)化算法及其實現(xiàn)4.2.1蟻群優(yōu)化算法人類認(rèn)識事物的能力來源于與自然的相互作用，這一直是人類創(chuàng)造力的源泉，自然界中存在著許多適應(yīng)性優(yōu)化的現(xiàn)象，不斷地照亮著人們。自然界中的生物和生態(tài)系統(tǒng)可以利用自身的進(jìn)化，使許多高度復(fù)雜的優(yōu)化問題幾乎得到完美的解決，嘗試通過模擬自然生態(tài)系統(tǒng)來解決復(fù)雜的優(yōu)化問題，比如蟻群算法，遺傳算法，這些算法極大地豐富了現(xiàn)有的優(yōu)化技術(shù)，也為傳統(tǒng)優(yōu)化技術(shù)難以處理的組合優(yōu)化問題提供了實用的解決方案。長期以來，生物學(xué)家們發(fā)現(xiàn)，每一只螞蟻的智力都不高，似乎沒有集中的指揮，但它們可以齊心協(xié)力，集中精力，筑起堅固美麗的巢穴，繁衍后代，蟻群算法是模擬昆蟲王國中蟻群智能行為的一種仿生優(yōu)化算法。它具有魯棒性強(qiáng)、分布式計算機(jī)系統(tǒng)優(yōu)秀、易于與其他方法結(jié)合等優(yōu)點，雖然蟻群算法的剛性理論基礎(chǔ)尚未建立，國內(nèi)外的研究還處于實驗階段，蟻群算法的研究已經(jīng)從原來的旅行商問題（TSP）的獨特領(lǐng)域，從一維靜態(tài)優(yōu)化問題的求解，到多維組合優(yōu)化問題的求解，滲透到了許多應(yīng)用領(lǐng)域，離散領(lǐng)域的研究逐漸擴(kuò)展到連續(xù)領(lǐng)域的研究，使得這種新型仿生優(yōu)化算法顯示出強(qiáng)大的生命力和廣闊的發(fā)展前景。蟻群算法的靈感來自自然界中實際螞蟻的覓食行為。它的許多觀點都來源于真實螞蟻的群體，因此算法中定義的人工螞蟻與真實螞蟻有以下幾點共同點：1）群體中存在個體間相互通信的機(jī)制。人工螞蟻和真實螞蟻都有一種改變當(dāng)前環(huán)境的機(jī)制：真實螞蟻在其路徑上留下信息素，而人工螞蟻改變其路徑上存儲的數(shù)字信息，即算法中定義的信息量，記錄了螞蟻當(dāng)前和歷史解的表現(xiàn)狀態(tài)，可以被其他后續(xù)的人工螞蟻讀寫，蟻群的這種通信方式改變了當(dāng)前螞蟻路徑周圍的環(huán)境，通常，蟻群算法中存在一種揮發(fā)機(jī)制，隨著時間的推移，路徑上的信息量會發(fā)生變化，就像實際的信息揮發(fā)量一樣，揮發(fā)機(jī)制讓人工螞蟻和真實螞蟻逐漸忘記歷史留下的信息，這使得螞蟻在選擇路線時不局限于以往螞蟻的“經(jīng)驗”i、e.尋找從源節(jié)點（巢穴）到目的節(jié)點（食物源）的最短路徑，人工螞蟻和實際螞蟻不跳躍，可以在相鄰節(jié)點之間一步一步地移動，直到所有城市交叉，在多重檢測過程中尋找最短路徑，（3）隨機(jī)選擇策略利用當(dāng)前信息選擇路徑，人工螞蟻和實際螞蟻都采用概率選擇策略從一個節(jié)點移動到下一個節(jié)點。概率選擇策略只使用當(dāng)前信息來預(yù)測未來情況，而不使用未來信息，因此，實際的人工螞蟻和螞蟻所使用的選擇策略在時間和空間上都是局部的。在構(gòu)造蟻群算法的過程中，受蟻群真實行為的啟發(fā)，人工蟻群還具有一些真實蟻群所不具備的特性：（1）人工蟻群存在于離散空間中，它們的運動是從一種狀態(tài)到另一種狀態(tài)的過渡。（2）人工螞蟻有一種記憶過去行為的內(nèi)在狀態(tài)。（3）人工螞蟻存在于與時間無關(guān)的環(huán)境中。（4）人工螞蟻并非完全失明，也受到問題空間特征的啟發(fā)，例如，在一些問題中，人工螞蟻在產(chǎn)生解決方案后會改變信息量，但不管采用什么方法，為了提高算法的優(yōu)化效率，人工螞蟻可以提高一些性能，如預(yù)測未來、局部優(yōu)化、退避等。在許多具體的應(yīng)用中，人工螞蟻可以在局部優(yōu)化過程中進(jìn)行信息交換，一些人工螞蟻在改進(jìn)的蟻群算法中可以得到簡單的預(yù)測。圖3.5最終優(yōu)化路線及優(yōu)化最短距離圖3.6迭代次數(shù)5結(jié)論5.1相關(guān)理論概述本研究的主要內(nèi)容是校車站點的選擇和校車路線的制定，校車定位問題是一個在各種約束條件下組織校車路線的優(yōu)化問題，SBRP是車輛轉(zhuǎn)向問題（VRP）應(yīng)用的一個重要分支。自69年代牛頓和托馬斯提出校車規(guī)劃問題以來，學(xué)者們不斷探索其數(shù)學(xué)模型和算法，校車規(guī)劃問題的數(shù)學(xué)模型與車輛路徑規(guī)劃問題相似。優(yōu)化的目標(biāo)是使車輛數(shù)量、總運行時間、總行駛距離、成本、行駛距離、負(fù)荷平衡和滿意度最小化，SBRP研究涉及到數(shù)據(jù)準(zhǔn)備、選址、優(yōu)化設(shè)計、優(yōu)化設(shè)計、優(yōu)化設(shè)計等多個子問題，路線生成和車輛規(guī)劃。Desrosiers等人回顧了1981年以前的SBRP研究。Park和Kim根據(jù)問題a的特點對SBRP問題進(jìn)行了詳細(xì)分類，并對模型算法做了簡單的總結(jié)，其他研究也對SBRP問題做了簡要的回顧。附錄S大學(xué)西校區(qū)校內(nèi)校車規(guī)劃設(shè)計：為了改進(jìn)之前校車運營期間的種種不足，更好的服務(wù)于廣大同學(xué)。現(xiàn)懇請各位同學(xué)抽出寶貴時間，填一下這份關(guān)于校車運營問題的問卷，本問卷用于科學(xué)研究，不會泄露大家的隱私，請大家放心填寫。萬分感謝各位同學(xué)?。。?您的性別[單選題]男女2您的年級[單選題]大一大二大三大四其他3您平時在校園內(nèi)主要靠哪種方式去上課或自習(xí)[單選題](請選擇一種您最常出行的方式)騎車（自行車，電動車等）走路其他4您每天出行的平均次數(shù)大約為[單選題]一次兩次或三次大于三次5您是否希望控制學(xué)校內(nèi)的個人交通工具[單選題]是否6您對于校內(nèi)校車的需求程度[單選題]不需要有點需要需要7如果校車重新開通，您是否會選擇乘坐[單選題]是否不確定8如果校車重新開通，您希望校車的收費方式為[多選題](可多選)校園卡微信支付寶現(xiàn)金9如果校車重新開通，您希望校車的運營時間包括以下哪幾個時間段[多選題](可多選)7：30——8：309：30——10：3011：30——12：3013：30——14：3015：30——16：3017：30——18：3010您平常在哪里上課或自習(xí)[多選題](此題為多選題，請勾選出您平常去過的場所（次數(shù)無要求，去過一次也算）)1教2教梅花館3教4教5教第6實驗樓7教10教11教12教圖書館機(jī)械樓土木工程綜合實驗樓化學(xué)化工學(xué)院逸夫樓生物科學(xué)與技術(shù)學(xué)院特教樓+其他____11您平常去的除教學(xué)樓外的其他場所[多選題](此題為多選題，請勾選出您平常去過的場所（次數(shù)無要求，去過一次也算）)一食二食三食八食東南門西南門老西門新西門天橋大禮堂校醫(yī)院體育場網(wǎng)球場洗浴中心行政樓+其他____%%%%%%%%%%%%%%%%%%%%蟻群算法解決TSP問題%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%clearall;%清除所有變量closeall;%清圖clc;%清屏m=50;%螞蟻個數(shù)Alpha=1;%信息素重要程度參數(shù)Beta=5;%啟發(fā)式因子重要程度參數(shù)Rho=0.1;%信息素蒸發(fā)系數(shù)G_max=200;%最大迭代次數(shù)Q=100;%信息素增加強(qiáng)度系數(shù)C=[3711;42;294;210;108;73;...104;256;143;298;2610;194;...346;376;68];%31個省會城市坐標(biāo)%%%%%%%%%%%%%%%%%%%%%%%%第一步：變量初始化%%%%%%%%%%%%%%%%%%%%%%%%n=size(C,1);%n表示問題的規(guī)模（城市個數(shù)）D=zeros(n,n);%D表示兩個城市距離間隔矩陣fori=1:nforj=1:nifi~=jD(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;elseD(i,j)=eps;endD(j,i)=D(i,j);endendEta=1./D;%Eta為啟發(fā)因子，這里設(shè)為距離的倒數(shù)Tau=ones(n,n);%Tau為信息素矩陣Tabu=zeros(m,n);%存儲并記錄路徑的生成NC=1;%迭代計數(shù)器R_best=zeros(G_max,n);%各代最佳路線L_best=inf.*ones(G_max,1);%各代最佳路線的長度figure(1);%優(yōu)化解whileNC<=G_max%%%%%%%%%%%%%%%%%%第二步：將m只螞蟻放到n個城市上%%%%%%%%%%%%%%%%Randpos=[];fori=1:(ceil(m/n))Randpos=[Randpos,randperm(n)];endTabu(:,1)=(Randpos(1,1:m))';%%%%%第三步：m只螞蟻按概率函數(shù)選擇下一座城市，完成各自的周游%%%%%%forj=2:nfori=1:mvisited=Tabu(i,1:(j-1));%已訪問的城市J=zeros(1,(n-j+1));%待訪問的城市P=J;%待訪問城市的選擇概率分布Jc=1;fork=1:nifisempty(find(visited==k,1))J(Jc)=k;Jc=Jc+1;endend%%%%%%%%%%%%%%%%%%計算待選城市的概率分布%%%%%%%%%%%%%%%%fork=1:length(J)P(k)=(Tau(visited(end),J(k))^Alpha)...*(Eta(visited(end),J(k))^Beta);endP=P/(sum(P));%%%%%%%%%%%%%%%%按概率原則選取下一個城市%%%%%%%%%%%%%%%%Pcum=cumsum(P);Select=find(Pcum>=rand);to_visit=J(Select(1));