Bus Scheduling Model¶

Definition¶

The bus scheduling model chooses nonnegative integer counts $x_i$ of buses starting in each of six consecutive four-hour intervals. Each bus operates for two intervals. With requirements $d=(4,8,10,7,12,4)$ $(4, 8, 10, 7, 12, 4)$ , the cyclic model is

\begin{gathered} \min\sum_{i=1}^6x_i,\\ x_{i-1}+x_i\ge d_i\ (i=1,\ldots,6),\\ x_i\in\mathbb{Z}_{\ge0}, \end{gathered}

where $x_0=x_6$ $x_{6}$ .

Interpretation¶

The model finds the smallest fleet of buses that meets the requirement in every four-hour interval when each bus works two consecutive intervals. The variables count shift starts, while each coverage constraint counts all buses operating in an interval.

Bars for the demand for buses in six four-hour intervals of the day, with segments showing shifts of two consecutive intervals, including one that wraps around midnight.

The bars show the requirements $d_1,\ldots,d_6$ and the arrows show shifts. The $x_1$ buses run from 0 to 8 h and serve intervals 1 and 2, and the $x_4$ buses serve intervals 4 and 5. The $x_6$ buses start at 20 h, serve interval 6 and then, after midnight, interval 1 of the next day. Interval 1 is therefore covered by $x_6+x_1$ $x_{1}$ , which is why the model sets $x_0=x_6$ $x_{6}$ .

Each variable appears in exactly two constraints, those of its starting interval and the next one. Adding all six constraints gives $\displaystyle 2\sum_ix_i\ge45$ $45$ , so at least 23 buses are needed. This bound is not attained: enumerating the integer solutions gives a minimum of 26, so the optimal plan covers some intervals with more buses than they require.

Linear program formulation turns shift counts into decision variables and requirements into linear inequalities. Because every variable counts buses, the model is a pure integer program. The ambulance location model has the same coverage structure with yes-or-no variables.

A common slip is to write $x_i\ge d_i$ $d_{i}$ , reading $x_i$ as the number of buses on duty in interval $i$ . That ignores the buses that started one interval earlier and asks for more buses than necessary.

Key Results¶

Eight-hour operation covers exactly two consecutive four-hour intervals.
Coverage may exceed the minimum demand.
The repeating daily interpretation is the assumption used to formulate the midnight boundary.

Examples¶

The midnight-to-4 AM constraint is $x_6+x_1\ge4$ $4$ .
The 4 PM-to-8 PM requirement gives $x_4+x_5\ge12$ $12$ .

Prerequisites¶

Ambulance Location Model

Sources¶

OR Modelling · Week 2

Keywords: Shift scheduling Symbols: element of, integers, sum

Last updated: 20 October 2026 03:02