Optimal Average Cost Policies for the Two-Terminal Shuttle

In this paper we consider a transportation system consisting of a carrier with capacity Q ≤ ∞, operating between two terminals. Passengers arrive at these terminals according to independent Poisson processes and are transported by the carrier from one terminal to the other terminal. Under a fairly general cost structure we show that the optimal operating policy which minimizes the expected average cost is a monotone decreasing function of the number of customers waiting at each terminal. Bounds are derived for the optimal average cost policy and a method to compute these optimal policies using linear programming is presented.