A Novel Metaheuristic for the Office Bus Routing Problem

In recent years, the concept of carpooling, along with the use of public transport for office commute, has been increasing in popularity due to the environmental benefits. In this study, we define Office Bus Routing Problem (OBRP) as a variant of the School Bus Routing Problem (SBRP) in which we focus our solution approach on three steps: 1) Selection of bus stops to be visited, 2) Assignment of employees to the selected bus stops, 3) Determination of optimal routes. In addition to this, we consider the following constraints along with the constraints of SBRP: a maximum allowed time for each trip, minimum occupancy of a bus, and a maximum traveling distance for a bus per day. A Mixed Integer Programming (MIP) model is developed for the proposed formulation. An essential characteristic of the OBRP is the flexibility for the booking time given to office employees. Current booking systems in India require the employees to book a bus at least 9-12 hours before their planned office commute time. To get a solution in minimal computing time with dynamic allocation of employees on a real-time basis, we use a modified version of the GRASP method along with the VND metaheuristic developed in an earlier study of the SBRP. The results of this approach are tested on real datasets with different sizes taken by conducting a case study on Bengaluru city in India. Analysis shows that the developed metaheuristic can provide near-optimal solutions in less computational time compared to the original sequential method of using GRASP with VND algorithm.