Problem A:

Bus scheduling problem

With the rapid development of society in Xuzhou city, the public transport system plays an increasingly significant role in everyday life. How to arrange the bus travel plan reasonably has become an important problem under the condition of limited bus resources. The explanations and assumptions for bus arrangement problem are shown as below.

(1) Shift: The bus departures from origin node to destination node. (one shift)

(2) There are two kinds of buses: single-driver bus (one driver) and double-driver bus (two drivers). The single-driver bus and double-driver bus can both be used for bus scheduling unless there are some special constraints.

(3) Single-driver bus: Only one driver will drive the bus. These buses will be required to service about 2-3 shifts in morning peak hours and 2-3 shifts in evening peak hours. However, the single-driver bus can not service more than 5 shifts in the whole day.

(4) Double-driver bus: There are two drivers who will drive the bus. These buses need to arrange one driver in the morning and another one in the afternoon. The working time during the morning and the afternoon need to be assigned as evenly as possible, and the working time for each driver can not exceed 8 hours. Every double-driver bus should be used no more than 10 shifts in one day.

(5) The single-trip time of one shift includes the passengers boarding time and alighting time at each stops.

(6) We assume that each bus can operate one day without refueling.

(7) The departure time of the last bus can be adjusted 2 minutes (±2 minutes) on the basis of the original departure time scheduling requirement.

(8) This problem only considers a loop bus line. That is to say, a shift means the bus starts from A stop (the origin node) and then go back to A stop (destination node).

(9) The minimum stop time is defined as the shortest dwelling time at the destination node before the next shift. In question 1-3, we assume that the bus does not need to stay at the destination node and it can continue to service the next shift (the minimum stop time is zero).

Question 1. We consider the No. 2 bus in Xuzhou city. The departure station and terminal station of the No.2 bus are the same (Xuzhou railway station). The detail information of No.2 bus is shown in Table 1. Please formulate the corresponding mathematical model and calculate the least number of buses in the morning peak hours (6:00-8:00). The numbers of single-driver bus and double-driver bus are also need to given in the result.

Question 2. Please formulate a mathematical model and design the relevant solution algorithm to calculate the minimum number of buses in the whole day on the basis of Question 1 (The numbers of single-driver bus and double-driver bus are also needed in the result). Then, the bus schedule needs to be provided with the format of Table 2.

Question 3. Under the constraint of the single-driver bus is required for no less 3 buses, please formulate a mathematical model and design the relevant solution algorithm to calculate the minimum number of buses in the whole day on the basis of Question 2 (The numbers of single-driver bus and double-driver bus are also needed in the result). Then, the bus schedule needs to be provided with the format of Table 2.

Question 4. Apart from the above requirements, we also need to consider the following constraints in the process of bus scheduling:

(a) The driver of single-diver bus does not need to arrange to have meals. On the contrary, all the drivers of double-driver bus are need to arrange to have meals (breakfast and dinner) and the meal time is 20 minutes for each meal. The breakfast time is 8:00-10:00 and the dinner time is 18:00-20:00.

(b) The number of double-driver bus is 19.

(c) The second bus driver will drive the double-driver bus when the first driver finish the work of 5 shifts. And the double-driver bus needs to stop at the terminal station for at least 20 minutes for the two drivers exchange (including the shortest stop time).

Please formulate a mathematical model and design the relevant algorithm solution to calculate the minimum number of buses in the whole day on the basis of Table 3 (The numbers of single-driver bus and double-driver bus are also needed in the result). Then, the bus schedule needs to be provided with the format of Table 2.

Appendix

Table 1 The detail information of No.2 bus in Xuzhou city

Table 2 The schedule of No.2 bus in Xuzhou city

Note：The number of rows can be increased or decreased if necessary (except the first row and the last row) and the number of columns can not be changed.

Table 3 The adjusted detail information of No.2 bus in Xuzhou city