Institute of Transportation, MOTC

　　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.