座位更換最小化之鐵路座位指派模式

RAILWAY SEAT ASSIGNMENT MODELING TOWARDS MINIMUM SEAT CHANGES

李東哲(Tung-Che Li) ； 邱裕鈞(Yu-Chiun Chiou) ； 王詮勳(Chuan-Hsun Wang)

《運輸計劃季刊》 50卷4期 (2021/12) Pp. 277-300

摘要

鐵路運輸如座位指派不當會使得列車座位未能有效利用，導致座位利用率、服務乘客總數，以及票箱收入之降低。因此，適度將預訂座位中途換座，或可提高座位利用率。基此，本研究以裝箱問題模式為基礎，依據歷史列車售票資料，建立靜態座位指派模式。本模式先將所有訂位需求，均切割成各站均換座之單一格位高度（即一筆訂票1站），而使座位利用率最高，再透過單一格位的重組（裝箱），來使座位分開及座位更換之總次數最小化。為驗證本模式之可應用性，本文以小規模的一個6個車站20個座位的列車做為簡例驗證。結果顯示，若容許中途換座，則座位利用率可由92%提升至98%、訂單接受率由85%提升至100%，且只有一筆2張座位之訂單必須中途換座，顯示本模式確具有可應用性。

關鍵字

鐵路運輸 ； 座位指派 ； 中途換座 ； 裝箱問題

並列摘要

Inappropriate railway seat assignment may decrease its load factor, number of passengers, and farebox revenue. Consequently, seat changes allowed in booking system may increase the load factor. To do so, based on bin-packing model and historical sales data, this study firstly breaks multi-stop seats into ＂unit seats＂ (a seat for a stop; i.e., a unit bin). All passengers have to change seat at every stop (for multi-stop ticket) so as to maximize the load factor. This study proposes a static seat assignment model by switching the assigned seats among passengers to minimize the total number of seat changes. To investigate the applicability of the proposed model, an exemplified case study with 6 train stations and 20 seats is conducted. The results show that the proposed model can increase the load factor from 92% (no seat change) to 98% (seat change allowed) and the booking acceptance rate from 85% (no seat change) to 100% (seat change allowed) at the expense of one booking order with two seats has to change their seats once. The applicability of the proposed model has been proved.

並列關鍵字

Rail transportation ； Seat assignment ； Seat change ； Bin packing

參考文獻

Clausen, T., Hjorth, A. N., Nielsen, M., & Pisinger, D. “The Off-line Group Seat Reservation Problem”, European Journal of Operational Research, Vol.207, No.3, 2010, pp.1244-1253.

Boyar, J., Krarup, S., & Nielsen, M. N. “Seat Reservation Allowing Seat Changes”, Electronic Notes in Theoretical Computer Science, Vol.50, No.1, 2001, pp.24-38.

王泓達，「台灣高鐵團體旅客車廂與座位配置之研究」，成功大學交通管理科學研究所碩士論文，民國 102 年。

Lodi, A., Martello, S., & Vigo, D. “Recent Advances on Two-dimensional Bin Packing Problems”, Discrete Applied Mathematics, Vol. 123, No. 1, 2002, pp.379-396.

Martello, S., & Vigo, D. “Exact Solution of the Two-Dimensional Finite Bin Packing Problem”, Management Science, Vol. 44, No. 3, 1998, pp.388-399.