A reduced integer programming model for the ferry scheduling problem
by Daniel Karapetyan, Abraham P. Punnen
Abstract:
We present an integer programming model for the ferry scheduling problem, improving existing models in various ways. Our model has reduced size in terms of number of variable and constraints compared to existing models by a factor of approximately O(n), where n being the number of ports. The model also permits load/unload time and handle passenger transfer efficiently. Experiments using real world data produced high quality solutions in 12 hours using CPLEX 12.4 with a performance grantee 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.
Reference:
A reduced integer programming model for the ferry scheduling problem (Daniel Karapetyan, Abraham P. Punnen), Public Transport 4, 151–163, 2013.
Bibtex Entry:
@Article{Karapetyan2013c,
  Title                    = {A reduced integer programming model for the ferry scheduling problem},
  Author                   = {Karapetyan, Daniel and Punnen, Abraham P.},
  Journal                  = {Public Transport},
  Year                     = {2013},
  Pages                    = {151--163},
  Volume                   = {4},
  Abstract                 = {We present an integer programming model for the ferry scheduling problem, improving existing models in various ways. Our model has reduced size in terms of number of variable and constraints compared to existing models by a factor of approximately O(n), where n being the number of ports. The model also permits load/unload time and handle passenger transfer efficiently. Experiments using real world data produced high quality solutions in 12 hours using CPLEX 12.4 with a performance grantee 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.},
  Arxivid                  = {1205.3757},
  DOI                      = {10.1007/s12469-012-0058-0},
  Eprint                   = {1205.3757},
  ISSN                     = {1866749X}
}