預約抽籤式之鐵路訂票尋優演算法

Heuristics for Railway Booking System based on a Reservation-Sortition Scheme

白子玄(Tzu-Hsuan Pai)

指導教授 ： 邱裕鈞

國立交通大學/管理學院/管理學院運輸物流學程/碩士(2016年)

摘要

花東地區對外公共交通主要依靠軌道運輸，茲因台鐵引進新自強號無站位型列車加入營運，及東部觀光成長遊客暴增，進出花東地區的公共運輸供給量遠不及需求量的成長，導致行旅需求者對於台鐵火車訂票系統的諸多抱怨，本研究的目的在於提出與現行即時訂票先到先決方式決定售票結果不一樣的訂票作業流程與售票結果分配邏輯，在事先收集旅客訂票需求架構下，於某個時間點以抽籤方式來決定售票分配結果，以此新流程為前提條件下，提出相對應的抽籤演算法來實作訂票系統的售票結果，並提出路線分段轉換座位、群組訂票座位拆分、未中籤遞延轉下班次訂單等功能，提高售票結果的媒合成功率，讓此列車的座位利用率可以達到最高。
本研究根據台鐵於官網上所能取得的資料，如2014年各車站的假日進出人數、起迄與中停車站的等級、列車行駛區域別、起迄距離長短等，作為數據產生的基本參數，使用蒙地卡羅模擬法以靜態離散隨機方式產生驗證演算法的需求數據，透過模擬特殊假日訂票模式的簡例設計，對於本研究所提出的優先次序演算法與距離次序演算法，根據多次需求數據產生與訂票抽籤媒合結果的資料，來做運算效率與座位利用率的驗證。

關鍵字

群組訂票 ； 原料裁切問題 ； 蒙地卡羅法 ； 啟發式演算法

並列摘要

East region of Formosa mainly depends on railway outbound to another area. Because of these two reasons, the Taiwan Railways Administration (TRA) operating the new Tze-Chiang Limited Express(Puyuma and Taroko) with non-standing seats in the most recent year and the number of tourists has been increasing rapidly and booming, the growth of the amount in public transportation supply are far less than the demand quantity. Its cause the passenger complains about the service satisfaction of the booking system. This study aims to offer another mechanism to replace the current FIFO (First-in First-out) booking and dispatching rule. This architecture collects all order requirement before drawing of lots to sale tickets at the sometime point. Under the process of the reservation sortition scheme, the study will propose optimized algorithms to implement ticket assigned procedure in my simulated booking system. And proposed three new creative functions, divide route into several unsold segment and combine it with entire journey, split group booking tickets by non-adjacent seat, deferred the order of non-success buying ticket into next train, to increase ticket sales results matchmaking success rate, so the utilization of the train seats can reach highest.
According to statistical information from TRA website, the parameters as the traveling data generated by passenger’s entry and exit at each station on holiday, the ranking level of stopping station, the area passed by train, the distance of the OD station. My study using Monte Carlo simulation theory to generate demand data by static discrete and random approach to validation the possibility and effectiveness of proposed algorithms. With constructing holiday booking patterns as a simple simulation model to verify and analysis the priority and distance algorithms if it could make expected result in operational efficiency and utilization of the seats.

並列關鍵字

Group seat reservation problem ； Cutting stock problem ； MonteCarlo method ； Heuristics algorithm

參考文獻

7. 馮正民、邱裕鈞(2004)，「研究分析方法」，建都文化事業股份有限公司。

5. 吳煜盛(2007)，大眾運輸交通工具之訂位系統觸控式螢幕使用者介面設計，大同大學工業設計學系碩士論文。

12. 蘇瑩瑩(2014) ，隨機團體需求之訂位限制，成功大學交通管理科學研究所碩士論文。

10. 楊仕欣(2009)，鐵路列車多停站網路超額訂位之座位配置模式，成功大學交通管理科學研究所碩士論文。

9. 蔡宜道(2005)，隨機需求之鐵路座位配置問題，成功大學交通管理科學研究所碩士論文。