Research Repository

A reduced integer programming model for the ferry scheduling problem

Karapetyan, Daniel and Punnen, Abraham P (2013) 'A reduced integer programming model for the ferry scheduling problem.' Public Transport, 4 (3). 151 - 163. ISSN 1613-7159

1205.3757v2.pdf - Accepted Version

Download (196kB) | Preview


We present an integer programming model for the ferry scheduling problem, improving existing models in various ways. In particular, our model has reduced size in terms of the number of variables and constraints compared to existing models by a factor of approximately O(n), with n being the number of ports. The model also handles efficiently load/unload time constraints, crew scheduling and passenger transfers. Experiments using real world data produced high quality solutions in 12 hours using CPLEX 12.4 with a performance guarantee of within 15 % of optimality, on average. This establishes that using a general purpose integer programming solver is a viable alternative in solving the ferry scheduling problem of moderate size.

Item Type: Article
Uncontrolled Keywords: Integer Programming; Planning Horizon; Travel Demand; Integer Programming Model; Crew Schedule
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 24 May 2018 11:52
Last Modified: 24 May 2018 12:15

Actions (login required)

View Item View Item