A linear programming approximation for network capacity control problem with customer choice

摘要

By dividing customers into different segments according to origin-destination (O-D) pairs, we consider a network capacity control problem where each customer chooses the open product within the segment he belongs to. Starting with a Markov decision process (MDP) formulation, we approximate the value function with an affine function of the state vector and develop our model based on the O-D demands. The affine function approximation results in a linear program (LP). We give a column generation procedure for solving the dual problem of the LP and the control policies.