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

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

有別於現行臺鐵先到先決訂票作業及售票分配邏輯，本文提出利用抽籤方式分配售票結果的訂票機制，並研擬三種抽籤演算法，包括長距離次序演算法、短距離次序演算法，以及優先次序演算法，進而搭配路線分段轉換座位、群組訂票座位拆分，以及未中籤遞延轉下一班次等優化功能，進一步提高售票的媒合成功率及座位利用率。在實例驗證方面，本文根據臺鐵官網取得的資料，作為訂票模擬需求之基本參數，利用蒙地卡羅模擬法以隨機方式產生需求資料，用以驗證本研究所提出的演算法。結果顯示，本研究所提出的抽籤方式訂票機制及其尋優演算法，不僅可避免民眾熬夜訂票的痛苦、降低訂票系統之短期間尖峰訂票負荷，更可提高列車座位利用率至92%以上。

Different from the current FIFO (First-in First-out) railway booking approach, this study proposes a novel reservation sortition scheme based on three ticket assignment optimization heuristics, including long-distance priority algorithm short-distance priority algorithm, and priority algorithm. Moreover, to further increase ticket matching and train seat utilization rates, three fine-tuning algorithms are incorporated, including dividing origin-destination segments into several unsold segments, splitting group booking tickets into non-adjacent seats, and deferring unsuccessful booking orders to next train. To validate the proposed heuristics, a Monte Carlo simulation booking system is designed based on the real ticket sales data obtained from Taiwan Railways Administration website. The results show the proposed scheme can relieve passengers' burden to stay up late for booking and the heavy reservation burden of the booking system and increase train seat utilization rate to 92% or more.