人工智慧方法應用於校車路徑規劃問題

Optimization Analysis for the School Bus Routing Problem by Using the Artificial Intelligence Approach

廖雅陵(Ya-Ling Liao)

指導教授 ： 劉正達

國立虎尾科技大學/管理學院/經營管理研究所/碩士(2015年)

摘要

隨著時代變遷，提供校車接送成為私校必備的附加服務之一，但是搭車的學生通常來自四面八方，以往採用人工方式規劃校車路線並不符合經濟效益。近年來由於全球定位系統(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.

並列關鍵字

School bus routing problem ； Encoding scheme ； PSO ； GA

參考文獻

[55] 李維平、張加憲，2011，“改良粒子群演算法求解旅行銷售員問題”，先進工程學刊， 6卷，1期，頁21~30。

[42] 林豐澤，2005，“演化式計算下篇：基因演算法以及三種應用實例”，智慧科技與應用統計學報 ，3卷，1期，頁29~56。

[59] 劉正達，2011，“人工智慧方法應用於聖火傳遞路徑最佳化”，大專體育學刊，13卷，4期，頁368~378。

[12] 韓復華，呂泓儒，朱佑旌，2011，“以改良型回溯門檻接受法求解回程取貨車輛路線問題之研究”，運輸計劃季刊，40卷，2期，頁213~232。

[29] 韓復華，朱政威，2010，“通勤交通車路線問題模式與巨集啟發式解法”，運輸計畫季刊，39卷，2期，頁133~164。