Route network improvement in air transportation schedule planning

Abstract

One of the routing and scheduling problems faced by an airline is to configure a route network. It seeks to answer the following two questions: First, should scheduled service be provided for a city pair market? Second, if market entry is warranted, should the city pair be served by a non-stop, multi-stop, or connect routing? A profit maximizing airline, in trying to answer these questions, has to abide by the route regulations imposed by the Civil Aeronautics Board. The airline has to take into account the inter carrier route competition. It has to recognize that its share of the passenger demand is a function of the level of service offered, and that passengers usually want to reach their destination in the most convenient routing for themselves. An optimization model is formulated for the route network configuration problem. Because of the huge combinatorial dimensionality inherent in the problem, a special solution method has to be devised. Only a handful of the most promising, feasible route candidates are identified at a time. An optimal choice is immediately made out of the few candidates. These route candidates are generated "as needed" by graph theoretic schemes, while route selection is performed by solving an integer program characterized by an ill-behaved objective function. At each generation/selection step, route network improvement is made by the optimal selection of the route candidate (i) to add to an existing network, (ii) to replace an unprofitable route, or simply (iii) to be deleted from the route network. The solution algorithm is based on the method of successive approximation in dynamic programming. Primal feasibility is maintained at all times. If the algorithm is stopped prematurely, due to limited computational resources, an improved (but not necessarily optimal) solution is always available. A 40-routine computer software package for the algorithm has been developed. It was successfully used to analyze a case study from American Airlines. Our limited computational experience showed that execution time is at least seven times faster than a comparable algorithm.