A reduced integer programming model for the ferry scheduling problem
- PDF / 500,016 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 1 Downloads / 244 Views
A reduced integer programming model for the ferry scheduling problem Daniel Karapetyan · Abraham P. Punnen
Published online: 30 November 2012 © Springer-Verlag Berlin Heidelberg 2012
Abstract 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.
1 Introduction Given a set of ports, a set of ferries, and a planning horizon, the ferry scheduling problem (FSP) seeks a routing and scheduling scheme for the ferries so that the travel demand emanating at the ports during the planning horizon is satisfied while the operations cost and passenger dissatisfaction are minimized. Ferry companies are often confronted with the problem of revising the ferry schedules due to a variety of reasons. These include changing demographics within the service area, changes in fleet characteristics, changes in port configuration, altered service level restrictions, responses to customer feedback, and changes in government regulations. Developing an ‘optimal’ schedule is crucial in achieving operational efficiency and cost savings. This research work was supported by BC Ferries and MITACS. D. Karapetyan () · A.P. Punnen Department of Mathematics, Simon Fraser University Surrey, Central City, 250-13450 102nd AV, Surrey, British Columbia, V3T 0A3, Canada e-mail: [email protected] A.P. Punnen e-mail: [email protected]
152
D. Karapetyan, A.P. Punnen
Even for a problem instance that appears to be of a small size (e.g., 4 ferries and 7 ports with a 20 hour planning horizon), the FSP is still complex and requires systematic scientific approaches to construct useful schedules, attain insights into true operational bottlenecks, and to develop proper management strategies. Optimization problems similar to the FSP have been studied extensively in the operations research literature in the context of airline scheduling (Gopalan and Talluri 1998), public transport scheduling (Ceder 2003) and scheduling problems in maritime transportation (Christiansen et al. 2004, 2007). Such problems can be formulated as integer programming problems. However, solving the resulting integer programming models to optimality is prohibitively hard most of the time due to the very large size of the models. Heuristic solution procedures are often employed to obtain practical solutions for such problems. Despite the similarity with the airline or public transport scheduling problem, special treatme
Data Loading...
