通勤交通車路線問題模式與巨集啟發式解法

IP FORMULATION AND METAHEURISTICS FOR THE COMMUTER BUS ROUTING PROBLEM

對員工提供上下班通勤之交通車服務，在許多大型的公司企業，都是很普遍的現象。良好的通勤交通車路線規劃可替公司減少營運成本，亦可減短員工搭乘時間。員工通勤交通車路線問題（commuter bus routing problem, CBRP）屬學校交通車路線問題（school bus routing problem, SBRP）之延伸。相較於SBRP，CBRP需同時考慮多車種和多迄點的特性，亦歸屬於問題複雜度為NP-hard的開放式車輛路線問題（open vehicle outing problem, OVRP）型態。本文針對CBRP深入探討，首先以總營運成本最小為目標，對CBRP構建整數規劃（integer programming, IP）模式，並提出一套基於門檻接受法（threshold accepting, TA）的四階段巨集啟發式解法。本研究亦設計不同型態的中小型題庫28題，以驗證CBRP模式列式的正確性，並測試巨集啟發式解法之求解績效。結果發現，本研究之巨集啟發式解法，對題庫最佳解的誤差幾乎都在1%之內；個案應用結果方面，約可替個案公司減少年成本29%。

The Commuter Bus Routing Problem (CBRP) is a complicated problem faced by many big companies in their daily operations. A well-planned CBRP can reduce the operational cost, and the employee’s commuting time. The CBRP can be considered as an extension of the conventional School Bus Routing Problem (SBRP). However, the CBRP in general considers a more complicated OD pattern and vehicle fleet mix than the SBRP. In this paper, we proposed an IP formulation for CBRP, and validated our proposed model with a set of test instances. We also designed heuristic solution methods based on a four-stage approach: (1) the farthest neighbor-based method for the solution construction stage; (2) node exchange based on surplus capacity for the fleet improvement stage; (3) inter-route and intra-route exchange for the neighborhood search stage; (4) Threshold Accepting (TA) metaheuristics for the intensification and diversification search stage. Computational results of the proposed metaheuristics on test instances showed that the percentage deviation of the exact solution is within 1%. For real-world applications, our proposed metaheuristics can save up to 29% of the annual cost for the case company.