AbstractIn this paper, we study a public bus line operating between a terminal and a city center for which there exists a clear demand imbalance between the two directions during peak hours. Despite the demand imbalance, traditional public bus systems typically operate with a fixed‐route and fixed‐timetable scheme in both directions. To increase the efficiency of service during peak hours, in this paper, we propose an on‐demand operation that allows vehicles to take some shortcuts between the city center and the terminal, based on the passenger requests that are collected before the peak hours. We develop a variable neighborhood search (VNS) algorithm to optimize the operational decisions of this system. Based on the received requests, the VNS algorithm decides the following: (1) shortcut decisions: which shortcuts to take by each bus in each direction, (2) departure time decisions: when to depart from the city center and the terminal, and (3) passenger assignment decisions: which service serves each passenger. Experiments show that the total passenger travel time improves up to 45% on a real‐size line compared to its traditional fixed‐route operation. The performance of the system is also analyzed under different circumstances.