The campus shuttle bus begins running at 7:00 P.M. and continues until 2 A.M. Several drivers will be used, but only one should be on duty at any time. If a shift starts at or before 9:00 P.M., a regular driver can be obtained for a 4-hour shift at cost $50. Otherwise, part-time drivers will be used. Several would work 3-hour shifts at $40 and the rest are limited to 2-hour shifts at $30. A shortest path problem can be used to determine a minimum total cost nightly driver shift schedule.
(a) Draw the figure appropriate to illustrate this problem as a shortest path. Make sure the cost for each arc is identified.
(b) Write the constraint for the source node.
(c) Write the constraint for the sink node.
(d) Write the constraint for the node that is closest to the middle (pick the node one to the left if there is no middle node).