An accelerated branch-and-price algorithm for multiple-runway aircraft sequencing problems

Document Type

Article

Publication Title

European Journal of Operational Research

Publication Date

1-1-2015

Abstract

This paper presents an effective branch-and-price (B&P) algorithm for multiple-runway aircraft sequencing problems. This approach improves the tractability of the problem by several orders of magnitude when compared with solving a classical 0-1 mixed-integer formulation over a set of computationally challenging instances. Central to the computational efficacy of the B&P algorithm is solving the column generation subproblem as an elementary shortest path problem with aircraft time-windows and non-triangular separation times using an enhanced dynamic programming procedure. We underscore in our computational study the algorithmic features that contribute, in our experience, to accelerating the proposed dynamic programming procedure and, hence, the overall B&P algorithm.

Volume

246

Issue

1

First Page

34

Last Page

43

DOI

10.1016/j.ejor.2015.04.019

ISSN

03772217

Link to Full Text

Share

 
COinS