隨著時代變遷,提供校車接送成為私校必備的附加服務之一,但是搭車的學生通常來自四面八方,以往採用人工方式規劃校車路線並不符合經濟效益。近年來由於全球定位系統(Global Position System,GPS)快速發展以及網路資料庫(data base)的建置成功,兩節點間的最短路徑可以經由電子資料庫Google Map取得,該資料庫的功能可以規劃兩地之間的最佳路徑,使得運輸效率大幅提升。因此,本研究針對雲林縣正心中學101學年度下學期31條校車路線進行實務規劃,應用該電子資料庫,建置各搭載點之間的距離矩陣,並且發展一人工智慧方法,同時提出新的編碼技巧,以搜尋校車最佳化路徑。 另外為了提升演算品質及效率,本研究結合粒子群演算法(Particle Swarm Optimization, PSO)及遺傳演算法(Genetic Algorithms, GA)提出一種新的混種演算法(Hybrid Algorithm, HA),以適用於具高度複雜性的(School Bus Routing Problem, SBRP),並且考慮校車容量限制、每部校車起點不同及所有通勤學生皆被準時服務下,以總車輛數最少(亦即路線數最少)為目標規劃最佳化路徑,同時致力於找尋最短路徑。經演算分析,平均車速60Km/hr及每條路線旅行時間 45分鐘的限制條件下,使用29部車即可載運完所有的學生,一年總共減少兩條路線,預計節省的經費達百萬元,研究結果大幅提升草嶺通運公司學生專車的使用效率,除了節省營運成本外,亦可降低交通意外風險,提升企業競爭力,但本研究發現29部校車之總路徑較原始31部校車總路徑長,代表本研究提出的編碼技巧仍有改善的空間,故後續將試圖改變編碼方式以搜尋最短總路徑,使校車路徑規劃成果更符合經濟效益。
In this study, we investigate the school bus routing problem with the limitations of bus capacity and time windows. The objective is to minimize the number of school bus and the total distance. Based upon the bus stop coordinates obtained from global position system (GPS) and distances between stops obtained from Google map, an artificial intelligence approach is used to solve the school bus routing problem. The 31 school bus routes of Yun-Lin Scared Hearts High School in 2012 second term were used to implement the proposed approach. By reasonably combining particle swarm optimization (PSO) and genetic algorithms (GA), we develop a fast and easily implemented hybrid algorithm (HA) for solving the considered problem. In addition, a novel encoding scheme is proposed for solving the school bus routing problem. Computational results indicate that only 29 school buses can transport all students within 45 minutes if the average velocity is assumed as 60km per hour. This implies that the proposed HA can use the information of Google map to schedule the school bus routes effectively, and it can significantly reduce the management cost of school bus operator. The reduction of a single bus is worth 540,000 of operating costs for the bus company. Therefore, the proposed HA is an effective approach and it can save approximately NT$1.08 milliom of the management cost per year and improve the competitiveness for a school bus operator.