Assign-to-Seat : Dynamic Capacity Control for Selling Train Tickets

We consider a revenue management problem arising from the sales of high-speed train tickets in China. Compared to traditional network revenue management problems, the new feature of our problem is that each request, if accepted, needs to be instantly assigned to a unique seat throughout the whole journey, and later adjustment is not allowed. Therefore, when making decisions, the seller needs to track not only the total capacity available but also the status of each seat.We build a modified network revenue management model for this problem. We first study a static problem where all requests are given. Despite that the problem is NP-Hard in general, we identify conditions of the capacity matrix for polynomial-time solvability, based on which we propose a booking limit control policy which achieves asymptotic optimality. We then introduce a bid-price control policy based on a novel maximal sequence idea, which allows for non-linearity in bid-prices and thus results in a more accurate approximation of the value function than the traditional bid-price control policy. Finally, combining the dynamic view of the maximal sequence and the static solution of the primal problem, we propose a \textit{re-solving a dynamic primal} (RDP) policy which achieves uniformly bounded revenue loss under a mild assumption. Numerical experiments using both synthetic and real data show the advantage of our proposed policies in improving capacity allocation efficiency