Consider Example 18.3 again. In that example, all passengers go to the final destination. But, in general, bus schedules should also accommodate passengers who board the bus at station i and depart at station k (k > i). Traditionally, such schedules (e.g., for trains or for connecting flights) involve just one timing decision per station: that is, the scheduled arrival time is also the scheduled departure time. A service gap sufficient to allow passengers to disembark and embark (and to service the equipment, if necessary) may also be specified.

a. Show that service gaps can be considered part of the next leg travel time without affecting the optimal solution.

b. Explain why, if we wish to provide a high service level to disembarking passengers, we must pay by often delaying the vehicle in the station.

c. Suppose that we specify a departure time and an arrival time separately. By way of notation, let rk denote the scheduled departure time from station k and let dk denote the due date at that station. Also, let Tk = (Ck − dk )+, where Ck is the arrival time at station k. For convenience, assume that the bus departs from station 0 at time 0 (so r0 = d0 = 0). Any departure delays from that station can be considered part of the travel time of the first segment. Construct a model for this purpose where release dates and due dates are decisions.

d. Show that your model is convex. (Hint: Demonstrate convexity by recasting the model as an LP for any given stored sample.)