Fixed-line buses are known to be very efficient in highly populated areas, but they become under-utilized when the demand decreases. In consequence, researchers study alternative f lexible solutions called on-demand or demand-responsive bus systems [1]. By flexible, we mean that the bus routes might change from one day to another in order to satisfy the existing demand. We find in [2] one of several existing real-life ODBRP-SA applications. Additionally, in [1] some more already running systems can be found. In this work, we propose two algorithms to optimize bus routes in an on-demand public bus system that runs during nighttime (i.e., low demand) in an area with a high concentration of bus stops. Even though on-demand mobility for public bus systems has been covered in the literature [1], only a few articles propose assigning passengers’ origins and destinations to bus stops or meeting points to reduce transportation costs [3, 4] and pollution.