通勤交通車路線問題之研究

Abstract

近年來許多公司體認到通勤交通車之服務是一項不可或缺之員工福利，而交通車路線規劃為最重要之關鍵。通勤交通車路線問題屬於車輛路線問題之特殊型態，且類似於傳統之校車路線問題，但是大多校車路線問題之研究只考量單一迄點及單一車種之特性。本研究考量多對多起迄點與多車種之特性，探討通勤交通車路線設計問題，以數學規劃建構通勤交通車路線模式，並發展一啟發式解法構建通勤交通車路線，以有效率地求解大規模之實務問題。 本研究依據通勤交通車之特性，以總營運成本最小為規劃目標，利用整數規劃(IP)構建通勤交通車路線模式，並設計完全性路網走廊型(CC)、完全性路網非走廊型(CR) 、非完全性路網走廊型(IC) 、非完全性路網非走廊型(IR)四種路網型態之小型測試例題，以ILOG OPL Development Studio 4.2軟體於Windows XP 作業系統、Pentium Ⅳ 2.8GHz CPU 及1GHz RAM之個人電腦求取最佳解(exact solution)來驗證IP模式之正確性。在啟發式解法方面，本研究利用C++程式語言構建通勤交通車路線起始解模組與路線改善模組，其中起始解以搜尋種子點及最近鄰點法構建，路線改善則考量路線之剩餘車容量與剩餘時間，進行路線間之節點移轉。為了評估啟發式解法之成效，本研究亦以啟發式解法求解四種路網型態之小型測試例題，將啟發式解法之結果與IP模式之最佳解進行比較與分析。分析結果顯示，利用啟發式解法求解小型例題皆可求解出最佳解，且執行時間皆在1秒內，求解效果良好。 在實務應用方面，本研究以新竹科學園區內某一公司之實際個案資料為例，挑選其中14條路線作為研究範圍。個案考慮三種車型，14條路線總長度共524.4公里，服務人數有244人，年成本約500萬元。依本研究構建之IP模式，個案問題有變數38,296,776個，限制式2,247,204個，無法求得最佳解，故以本研究啟發式解法求解。求解結果顯示，求解時間約1.5秒，路線數減少2條，路線總長度減少約113公里，每年節省成本約103萬元(佔原成本20 %)。 後續研究方面，建議可考慮以服務品質為目標，如所有搭乘員工總搭乘時間最小化，亦可考量多重目標，將營運成本與服務品質同時考量。

Commuter Bus Routing Problem (CBRP) is defined as a multi-workplace and multi-vehicle routing problem commonly faced by many companies for their employee’s daily commuting. CBRP can be considered as a variant of Vehicle Routing Problem (VRP), but traditional solution methods of VRP are not applicable to solve CBRP. School Bus Routing Problem (SBRP) is similar to CBRP, but most of the research on SBRP only considered single-school and single-vehicle. In this study, we presented an integer programming (IP) formulation for CBRP, and developed heuristic methods for solving large scare CBRP. We first formulated an IP model with the objective of minimizing total operating cost, and then generated a bank of 24 small example problems for testing and validation of our IP model. We also developed heuristic methods to solve the CBRP. The heuristic methods consist of two phases. In route construction phase, we first selected seed nodes and applied nearest neighbor procedures. In route improvement phase, we considered surplus vehicle capacity and surplus route time to improve the incumbent solution. Comparing the results of IP model and the heuristic methods, we found that our heuristic methods can solve all the 24 small example problems correctly in about 0.3 seconds. In this study, we also tested a real-world problem of a company in Hsinchu Science Park. There were 14 routes providing commuting services to 244 employees in the case problem, and the annual operating cost was about 5 million. The case problem would have 38,296,776 variables and 2,247,204 constraints in the IP model, and is difficult to obtain the exact solution. We applied our heuristic methods to successfully solve the case problem in 1.5 seconds, and the results could save about 20% total operating cost. In this study, we only considered the objective of minimizing total operating cost. For service consideration, further research may consider the objective of minimizing total travel time or multiple objectives.