Show simple item record

dc.contributor.authorLavoie, Sylvie
dc.contributor.authorMinoux, Michel
dc.contributor.authorOdier, Edouard
dc.date.accessioned2014-10-30T13:34:27Z
dc.date.available2014-10-30T13:34:27Z
dc.date.issued1988
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/14088
dc.language.isoenen
dc.subjectCombinatorial optimizationen
dc.subjectgeneralized linear programmingen
dc.subjectschedulingen
dc.subjectair transportationen
dc.subject.ddc003en
dc.titleA new approach for crew pairing problems by column generation with an application to air transportationen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe propose a new approach to crew-pairing problems arising in the context of airline companies. The problem is first formulated as a large scale set covering problem with many colums, each column representing a valid crew-pairing. We then suggest a solution procedure for the continuous relaxation of this large scale problem, based on generalized linear programming, in which the column generation subproblem is shown to be equivalent to a shortest path problem in an associated graph. Computational results obtained on a series of real problems (involving up to 329 flight segments) are reported, confirming both computational efficiency and practical applicability of the new approach. Indeed not only were the resulting solutions observed to be integral for most test problems, but average savings of about 4 to 5% over the best available hand-built solutions were shown to be obtained.en
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol35en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate1988
dc.relation.isversionofjnlpages45-58en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/0377-2217(88)90377-3en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record