網路分析法於航機座位分配問題之應用

NetworkApproach to Itinerary Seat Allocation Problems

本文探討在隨機需求之考量下，如何利用網路方法以求解主有關聯的旅程座位分配問題。由於座位分配問題的定式會隨著網路規模的增大而變得繁雜，且此等網路座位分配問題的最佳解要實用有效，有賴一有效率求解方法的存在，因此，本文提出以二個最佳分配問題來處理旅程座位分配的想法，即以兩個不同但主有關聯之網路來分別求解短旅程與長旅程之座位分配。又由於節線上的成本(收益)函數與其他節線流量(座位分配)有關，難以直接求解，因此，本研究特發展一反覆運算的程序以求解此等具相依性航空網路的座位分配問題，最後則以一簡例來示範其在座位庫存控制之應用。

This paper is concerned with employing the network approach to jointly solve the interdependent itinerary seat allocations (seat allocations in single fare class and mu1tiple itineraries) for a network when stochastic demand is taken into account. The seat allocation problem formulation becomes increasingly cumbersome as the size of network increases. Effective solution of the seat allocation problem in a network context depends on having an efficient method of solution. It has been shown that seat allocation problem can be formulated as two optimal distribution problems. Two separate but related networks are formulated to solve seat allocations for local itineraries and through itineraries, respectively Since the cost (revenue) functions in arcs are dependent on flows (seat allocations) in other arcs, an iterative approach is developed to solve the independent seat allocations for an airline network. A numerical example is iIlustrated to demonstrate the usage of network approach in the context of seat inventory contro1.