臺灣博碩士論文加值系統

本研究探討鐵路座位配置模式，並加入了列車之間需求不獨立性，即考量旅客在訂票被拒絕後並不一定會馬上選擇其他運具，而可能會改訂其他班車。另外，本研究亦考量了配置的公平性，避免在最大化營收的過程中將資源集中在部分的車站，而讓某些車站無法被分配到資源。為了解決這樣的多目標問題，本研究導入了啟發式演算法—NSGA-II來有效的求解。本研究也定義了「需求滿足率」此項指標來衡量分配之公平性。實證分析後，本研究發現考慮列車間需求不獨立性的確可以提高整體收益，但資源會集中於某些營收貢獻度高之O-D；因此同時納入公平性做考量後，可發現僅需減少有限的營收就可使分配的公平性大幅提升，營收貢獻度低的O-D也會被配置更多的座位。本研究之模式可提供鐵路公司因應地方政府單位要求增停或增加座位供給量，而衡量所需補貼之參考。

This study propose a railway seat allocation model which considers passengers may choose next train rather than choose another mode immediately after booking rejected. This model also considers fairness, which means avoiding to seats all allocated to specific ODs and causing some ODs cannot get any resource. In order to solve the multi-objective problem, this study introduces a genetic algorithm NSGA-II. This study also defines demand satisfaction ratio to measure fairness. After empirical study, we find that considering passengers’ dependent demand really improve expected total revenue, and seats are allocated more to high revenue-contributed ODs. Then, while we consider dependent demand and fairness simultaneously, fairness indeed can be improved by reducing limited revenue, and low revenue-contributed ODs can get more seats than before. This model can provide some information to Railway Company to calculate number of subsidy while local government asks for stopping or allocating more seats to their stations.

1.Introduction 1
1.1 Research Background and Motivation 1
1.2 Research Objectives 4
1.3 Research Scope and Subjects 5
1.4 Research Framework 5

2.Literature Review 7
2.1 Revenue Management 7
2.1.1 Seat Allocation 7
2.1.2 Seat Allocation with Dependent Demand 12
2.2 Fairness of Resource Allocation 15
2.3 Multi-objective Optimization 17
2.3.1 Approaches to Multi-objective Optimization 19
2.3.2 NSGA-II(Non-Dominated Sorting Genetic Algorithm II) 19
2.4 Monte Carlo Simulation Method 22
2.5 Summary 24

3. Mathematic Formulation 25
3.1 Problem Definition 25
3.2 Assumptions 26
3.3 Model Formulation 26

4. Solution Procedure 30
4.1 Procedure of NSGA-II 31
4.2 Procedure of Monte Carlo Simulation (MCS) 36

5. Empirical Result 40
5.1 Data Collection 40
5.2 Considering Dependent Demand between Consecutive Trains 42
5.3 Considering Fairness and Dependent Demand between Consecutive Trains 46

6. Conclusion and Discussion 58
6.1 Conclusion 59
6.2 Academic Contribution 60
6.3 Management Implication 62
6.4 Limitation and Future Research 63

References 64

Adelman, D. (2007). Dynamic bid prices in revenue management. Operations Research, 55(4), 647-661.
Armony, M. (2005). Dynamic routing in large-scale service systems with heterogeneous servers. Queueing Systems, 51(3-4), 287-329.
Armony, M., ＆ Ward, A. R. (2010). Fair dynamic routing in large-scale heterogeneous-server systems. Operations Research, 58(3), 624-637.
Avi-Itzhak, B., Levy, H., ＆ Raz, D. (2004). Quantifying fairness in queueing systems: Principles and applications. Preprint.
Barz, C., ＆ Waldmann, K. H. (2007). Risk-sensitive capacity control in revenue management. Mathematical Methods of Operations Research, 65(3), 565-579.
Basu, M. (2008). Dynamic economic emission dispatch using nondominated sorting genetic algorithm-II. International Journal of Electrical Power ＆ Energy Systems, 30(2), 140-149.
Belobaba, P. (1987). Air travel demand and airline seat inventory management. Cambridge, MA: Flight Transportation Laboratory, Massachusetts Institute of Technology,[1987].
Belobaba, P. P. (1989). OR Practice—Application of a Probabilistic Decision Model to Airline Seat Inventory Control. Operations Research, 37(2), 183-197.
Ben-Akiva, M., ＆ Bierlaire, M. (2003). Discrete choice models with applications to departure time and route choice. Handbook of transportation science, 32.
Bertsimas, D., ＆ De Boer, S. (2005). Simulation-based booking limits for airline revenue management. Operations Research, 53(1), 90-106.
Bertsimas, D., ＆ Popescu, I. (2003). Revenue management in a dynamic network environment. Transportation science, 37(3), 257-277.
Bertsimas, D., ＆ Popescu, I. (2003). Revenue management in a dynamic network environment. Transportation science, 37(3), 257-277.
Bertsimas, D., ＆ Popescu, I. (2003). Revenue management in a dynamic network environment. Transportation science, 37(3), 257-277.
Box, G. E., ＆ Muller, M. E. (1958). A note on the generation of random normal deviates. The annals of mathematical statistics, 29(2), 610-611.
Boyd, E. A., ＆ Bilegan, I. C. (2003). Revenue management and e-commerce. Management Science, 49(10), 1363-1386.
Brooks, J. D., ＆ Mendonca, D. (2014, March). Equity-effectiveness tradeoff in the allocation of flows in closed queueing networks. In Systems Conference (SysCon), 2014 8th Annual IEEE (pp. 511-517). IEEE.
Brumelle, S. L., ＆ McGill, J. I. (1993). Airline seat allocation with multiple nested fare classes. Operations Research, 41(1), 127-137.
Brumelle, S. L., McGill, J. I., Oum, T. H., Sawaki, K., ＆ Tretheway, M. W. (1990). Allocation of airline seats between stochastically dependent demands. Transportation Science, 24(3), 183-192.
Chanta, S., Mayorga, M. E., ＆ McLay, L. A. (2014). Improving emergency service in rural areas: a bi-objective covering location model for EMS systems. Annals of Operations Research, 221(1), 133-159.
Chen, L., ＆ Homem-de-Mello, T. (2010). Mathematical programming models for revenue management under customer choice. European Journal of Operational Research, 203(2), 294-305.
Chen, L., ＆ Homem-de-Mello, T. (2010). Mathematical programming models for revenue management under customer choice. European Journal of Operational Research, 203(2), 294-305.
Cheng, Y. H., ＆ Liang, Z. X. (2014). A strategic planning model for the railway system accident rescue problem. Transportation research part E: logistics and transportation review, 69, 75-96.
Cléaz-Savoyen, R. L. (2005). Airline revenue management methods for less restricted fare structures (Doctoral dissertation, Massachusetts Institute of Technology).
Cooper, W. L. (2002). Asymptotic behavior of an allocation policy for revenue management. Operations Research, 50(4), 720-727.
Cooper, W. L., ＆ Gupta, D. (2006). Stochastic comparisons in airline revenue management. Manufacturing ＆ Service Operations Management, 8(3), 221-234
Cross, R. G., Higbie, J. A., ＆ Cross, Z. N. (2011). Milestones in the application of analytical pricing and revenue management. Journal of Revenue ＆ Pricing Management, 10(1), 8-18.
Cruse, T. A. (1997). Reliability-based mechanical design (Vol. 108). CRC Press.
Curry, R. E. (1990). Optimal airline seat allocation with fare classes nested by origins and destinations. transportation science, 24(3), 193-204.
de Boer, S. V., Freling, R., ＆ Piersma, N. (2002). Mathematical programming for network revenue management revisited. European Journal of Operational Research, 137(1), 72-92.
Deb, K. (2014). Multi-objective optimization. In Search methodologies (pp. 403-449). Springer US.
Deb, K., Pratap, A., Agarwal, S., ＆ Meyarivan, T. A. M. T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. Evolutionary Computation, IEEE Transactions on, 6(2), 182-197.
Delasay, M., Kolfal, B., ＆ Ingolfsson, A. (2012). Maximizing throughput in finite-source parallel queue systems. European Journal of Operational Research, 217(3), 554-559.
Felder, S., ＆ Brinkmann, H. (2002). Spatial allocation of emergency medical services: minimising the death rate or providing equal access?. Regional Science and Urban Economics, 32(1), 27-45.
Fonseca, C. M., ＆ Fleming, P. J. (1993, June). Genetic Algorithms for Multiobjective Optimization: FormulationDiscussion and Generalization. In ICGA (Vol. 93, pp. 416-423).
Gallego, G., Iyengar, G., Phillips, R., ＆ Dubey, A. (2004). Managing flexible products on a network.
Gallego, G., Ratliff, R., ＆ Shebalov, S. (2014). A general attraction model and sales-based linear program for network revenue management under customer choice. Operations Research, 63(1), 212-232.
García-Martínez, C., Cordón, O., ＆ Herrera, F. (2007). A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP. European Journal of Operational Research, 180(1), 116-148.
Gesetz zur Regionalisierung des öffentlichen Personennahverkehrs (1993) (Regionalization of the Public Transportation Law), Retrieved from http://www.gesetze-im-internet.de/regg/
Glover, F., Glover, R., Lorenzo, J., ＆ McMillan, C. (1982). The passenger-mix problem in the scheduled airlines. Interfaces, 12(3), 73-80.
Goldberg, D. E., ＆ Kuo, C. H. (1987). Genetic algorithms in pipeline optimization. Journal of Computing in Civil Engineering, 1(2), 128-141.
Goldberg, D. E., ＆ Richardson, J. (1987, July). Genetic algorithms with sharing for multimodal function optimization. In Genetic algorithms and their applications: Proceedings of the Second International Conference on Genetic Algorithms (pp. 41-49). Hillsdale, NJ: Lawrence Erlbaum.
Hetrakul, P., ＆ Cirillo, C. (2014). A latent class choice based model system for railway optimal pricing and seat allocation. Transportation Research Part E: Logistics and Transportation Review, 61, 68-83.
Kimes, S. E. (1989). Yield management: a tool for capacity-considered service firms. Journal of operations management, 8(4), 348-363.
Kimes, S. E. (1994). Perceived fairness of yield management. The Cornell Hotel and Restaurant Administration Quarterly, 35(1), 22-29.
Kimes, S. E. (2002). Perceived fairness of yield management. The Cornell Hotel and Restaurant Administration Quarterly, 43(1), 21-30.
Kimms, A., ＆ Müller-Bungart, M. (2007). Simulation of stochastic demand data streams for network revenue management problems. Or Spectrum, 29(1), 5-20.
Kroese, D. P., Brereton, T., Taimre, T., ＆ Botev, Z. I. (2014). Why the Monte Carlo method is so important today. Wiley Interdisciplinary Reviews: Computational Statistics, 6(6), 386-392.
Leclerc, P. D., McLay, L. A., ＆ Mayorga, M. E. (2012). Modeling equity for allocating public resources. In Community-based operations research (pp. 97-118). Springer New York.
Lee, T. C., ＆ Hersh, M. (1993). A model for dynamic airline seat inventory control with multiple seat bookings. Transportation Science, 27(3), 252-265.
Liao, X., Li, Q., Yang, X., Zhang, W., ＆ Li, W. (2008). Multiobjective optimization for crash safety design of vehicles using stepwise regression model. Structural and Multidisciplinary Optimization, 35(6), 561-569.
Littlewood, K. (1972). Forecasting and Control of Passenger Bookings, AGIFORS 12th Annual Symposium Proceedings. October, Nathanya, Israel, 193-204.
Liu, J. S. (2008). Monte Carlo strategies in scientific computing. Springer Science ＆ Business Media.
Madansky, A. (1960). Inequalities for stochastic linear programming problems. Management science, 6(2), 197-204.
Marcus, B., ＆ Anderson, C. K. (2008). Revenue management for low-cost providers. European Journal of Operational Research, 188(1), 258-272.
Marsh, M. T., ＆ Schilling, D. A. (1994). Equity measurement in facility location analysis: a review and framework. European Journal of Operational Research, 74(1), 1-17.
Mauri, A. G. (2007). Yield management and perceptions of fairness in the hotel business. International Review of Economics, 54(2), 284-293.
Mooney, C. Z. (1997). Monte carlo simulation (Vol. 116). Sage Publications.
Petrick, A., Steinhardt, C., Gönsch, J., ＆ Klein, R. (2012). Using flexible products to cope with demand uncertainty in revenue management. OR spectrum, 34(1), 215-242.
Rajagopalan, H. K., Saydam, C., Setzler, H., ＆ Sharer, E. (2012). Decision making for emergency medical services. In Community-Based Operations Research (pp. 275-296). Springer New York.
Robinson, L. W. (1995). Optimal and approximate control policies for airline booking with sequential nonmonotonic fare classes. Operations Research, 43(2), 252-263.
Saadatseresht, M., Mansourian, A., ＆ Taleai, M. (2009). Evacuation planning using multiobjective evolutionary optimization approach. European Journal of Operational Research, 198(1), 305-314.
Smith, B. C., Leimkuhler, J. F., ＆ Darrow, R. M. (1992). Yield management at American airlines. interfaces, 22(1), 8-31.
Srinivas, N., ＆ Deb, K. (1994). Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary computation, 2(3), 221-248.
Syvertsen, T. (1999). The many uses of the “public service concept. Nordicom Review, 20(1), 5-12.
Talluri, K. T., ＆ Van Ryzin, G. J. (2006). The theory and practice of revenue management (Vol. 68). Springer Science ＆ Business Media.
Talluri, K., ＆ Van Ryzin, G. (1999). A randomized linear programming method for computing network bid prices. Transportation Science, 33(2), 207-216.
Talluri, K., ＆ Van Ryzin, G. (2004). Revenue management under a general discrete choice model of consumer behavior. Management Science, 50(1), 15-33.
Tong, C., ＆ Topaloglu, H. (2013). On the approximate linear programming approach for network revenue management problems. INFORMS Journal on Computing, 26(1), 121-134.
Tzeng, G. H., Cheng, H. J., ＆ Huang, T. D. (2007). Multi-objective optimal planning for designing relief delivery systems. Transportation Research Part E: Logistics and Transportation Review, 43(6), 673-686.
Van Ryzin, G., ＆ McGill, J. (2000). Revenue management without forecasting or optimization: An adaptive algorithm for determining airline seat protection levels. Management Science, 46(6), 760-775.
Wang, J., ＆ Zhou, C. (2014, June). Research on ontology building and pricing of customized product. In Service Systems and Service Management (ICSSSM), 2014 11th International Conference on (pp. 1-5). IEEE.
Weatherford, L. R., ＆ Bodily, S. E. (1992). A taxonomy and research overview of perishable-asset revenue management: yield management, overbooking, and pricing. Operations Research, 40(5), 831-844.
Williamson, E. L. (1992). Airline network seat inventory control: Methodologies and revenue impacts. [Cambridge, Mass.: Massachusetts Institute of Technology, Dept. of Aeronautics ＆ Astronautics], Flight Transportation Laboratory,[1992].
Wirtz, J., ＆ Kimes, S. E. (2007). The moderating role of familiarity in fairness perceptions of revenue management pricing. Journal of Service Research, 9(3), 229-240.
Wirtz, J., Kimes, S. E., Theng, J. H. P., ＆ Patterson, P. (2003). Revenue management: resolving potential customer conflicts. Journal of Revenue and Pricing Management, 2(3), 216-226.
Wollmer, R. D. (1986). An airline reservation model for opening and closing fare classes. unpublished company report, Douglas Aircraft Company, McDonnell Douglas Corporation, Long Beach, CA.
Wollmer, R. D. (1992). An airline seat management model for a single leg route when lower fare classes book first. Operations Research, 40(1), 26-37.
Wu, W., Simpson, A. R., ＆ Maier, H. R. (2009). Accounting for greenhouse gas emissions in multiobjective genetic algorithm optimization of water distribution systems. Journal of water resources planning and management, 136(2), 146-155.
You, P. S. (2008). An efficient computational approach for railway booking problems. European Journal of Operational Research, 185(2), 811-824.
Zhang, D., ＆ Cooper, W. L. (2005). Revenue management for parallel flights with customer-choice behavior. Operations Research, 53(3), 415-431.
Zitzler, E., ＆ Thiele, L. (1999). Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. evolutionary computation, IEEE transactions on, 3(4), 257-271.
陳昭宏、張有恆，航空公司營收管理模式之研究---整合艙位配置與超額訂位之動態策略，成功大學交通管理科學系博士論文，1997。
蔡言宏、汪進財，航空公司超額訂位控制策略之研究，交通大學運輸與物流管理學系碩士論文，1998。
顏上堯、陳茂南，航空公司網路機位庫存管理，中央大學土木工程研究所博士論文，2000。