{"entities":{"Q1098764":{"pageid":1109516,"ns":120,"title":"Item:Q1098764","lastrevid":42874176,"modified":"2025-07-15T14:56:24Z","type":"item","id":"Q1098764","labels":{"en":{"language":"en","value":"A new approach for crew pairing problems by column generation with an application to air transportation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4037583"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098764$876A55BE-B14E-40DD-9EA4-BC1B2FDD447B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"436e04806bbac33fdf105cf037a016e2d3a17f0d","datavalue":{"value":{"text":"A new approach for crew pairing problems by column generation with an application to air transportation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1098764$5CB519AA-2501-4B3A-B682-741345940242","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ace3baf84735e890f33935f089db76a58331d24f","datavalue":{"value":"0636.90041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098764$06C4D7F8-2D66-4C1A-A9F4-2BC526A85104","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0a6bb004efde57c672b630668a53dba7cb13b3e8","datavalue":{"value":"10.1016/0377-2217(88)90377-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098764$AFC562E5-A8D6-4FAB-9684-8A04448974E0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"757513b2a75acdc0fe542c94a49da792dd911d82","datavalue":{"value":{"entity-type":"item","numeric-id":1098762,"id":"Q1098762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098764$CDAEDA9F-4EC0-4DC8-8D56-5D9434E8B9D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8b2480f70a96a0e09506405db969492fd41acf1c","datavalue":{"value":{"entity-type":"item","numeric-id":325411,"id":"Q325411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098764$9E72110A-8593-4D25-932D-81A992DBA6EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5995d4b7722dffa213180e47300870950fb55a0a","datavalue":{"value":{"entity-type":"item","numeric-id":1098763,"id":"Q1098763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098764$24D725CA-3B4B-40D0-B623-092A4346E296","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098764$0ACEC55F-1954-4DE7-9157-2A2D84A6E6C7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1098764$FA465E13-7AE8-4AD0-9AC9-EA6C6DFCFED1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"55aa2c378db221e1d104b0219afa15fc0d3bfc11","datavalue":{"value":"We 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 columns, 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.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098764$168DC7BD-9893-44C6-BE94-A66F22A62865","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098764$D3DF52EB-EF7C-43E4-B299-32392B67E3E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"418d4d19aa7c87e33d52e580c9c108a1bc2de096","datavalue":{"value":"90C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098764$D064BBF0-10E2-42DC-B887-CC9DE8635295","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098764$32C6788F-1E2D-4DA4-A9DE-5755CE2F12C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e038e5e16128fe63d90643b4c4804d63f3db1339","datavalue":{"value":"90C06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098764$EA4DFDDB-9DE6-4877-AE8D-FA4701FE2204","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098764$4D7924B6-112F-4915-AF42-DF4853F117E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098764$5D25B887-BBEC-4B38-9143-5FD9BD5043AE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3278a991620911ce0bb027ad8b630e0d7c92dc8a","datavalue":{"value":"4037583","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098764$4B9313DE-508A-4ED1-B722-03774900A116","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f8011396c9a52a0d0f8a50e071328d8351da8ef7","datavalue":{"value":"crew-pairing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098764$CBD78D54-F6B7-4C02-93C7-A0B15495B774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7a4c14f81ee8ab60cee848f877389112e3c8aa7","datavalue":{"value":"large scale set covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098764$34F44F66-B1C6-4793-84FA-3F0AD561EFCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06a46b7e60ac80ffc118406f0df9e720d3f3b13f","datavalue":{"value":"continuous relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098764$AB089561-A83F-409E-BDE7-2C7B192807C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b91e334a5c601e41391afe683197a5bbc09ae9a","datavalue":{"value":"column generation subproblem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098764$B809F337-1B1F-47D0-8D16-0E7CABD2BB5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f85e9f2721221f48af2e899508349c71e3faa29f","datavalue":{"value":"shortest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098764$A0275138-7631-433F-8B5F-8B0D3F540F7F","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098764$0B0447C6-DD09-419A-9E9D-E3AC84359E13","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ee1511f9f01486fca9aef885e2680c21d0f228cd","datavalue":{"value":"https://doi.org/10.1016/0377-2217(88)90377-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1098764$F5FAE880-A1A6-422D-B0E4-A18CD12C20C4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7d8d6e3f7376b9d63cad2f8a85d7deef371fe009","datavalue":{"value":"W2077724649","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098764$3127097F-4DD4-4E1E-8129-39B473AC3E8B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b49831ffa1b847141ffe4d70b0a36ebaa8beccc","datavalue":{"value":{"entity-type":"item","numeric-id":3875704,"id":"Q3875704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098764$8569CED5-13A0-4A8E-83D3-35FB44048D0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4855508c035089f5a450bea34664199d6eca85fe","datavalue":{"value":{"entity-type":"item","numeric-id":3048579,"id":"Q3048579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098764$BEFC7ABC-8583-4389-8830-7A577345F929","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a43ca27cba6b8cbde68d00987a946f9cde333444","datavalue":{"value":{"entity-type":"item","numeric-id":3844775,"id":"Q3844775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098764$55CAF856-5BA6-43C2-A844-2FB6980ECF78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e6a4e3723e1ca96af481175af5a2af3721526ff","datavalue":{"value":{"entity-type":"item","numeric-id":3688124,"id":"Q3688124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098764$CA3D390E-4B98-4BFA-A5C0-300FEDCD17B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b989f45b85fa44137ad22092706b6102fd241bf","datavalue":{"value":{"entity-type":"item","numeric-id":78129,"id":"Q78129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098764$C48E246C-EA5A-4145-97C0-09A719B243B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3544ff5c3325f5ac1e5dcd2fd92020bf1b6189fb","datavalue":{"value":{"entity-type":"item","numeric-id":3292914,"id":"Q3292914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098764$67CBD9C0-2F44-4E57-AD1B-C416A869B6AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a215457c438695bb7fc4ab73c68b207d61ff499","datavalue":{"value":{"entity-type":"item","numeric-id":3275357,"id":"Q3275357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098764$9003EA6B-9D3B-4F02-9089-D7087E49B45B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"273e96f3fd191a1c748a335432845ba0076495c5","datavalue":{"value":{"entity-type":"item","numeric-id":3960718,"id":"Q3960718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098764$5F419477-00F8-4808-9FF4-0B25B673B8AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1fe81516bd3c75d8bc076e9e1356c960939cf0a","datavalue":{"value":{"entity-type":"item","numeric-id":4117605,"id":"Q4117605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098764$1B7CDFD5-5101-4024-9656-D1340159919B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ada25ef2c80f1a4481a522bbafc307210cf825c","datavalue":{"value":{"entity-type":"item","numeric-id":3337942,"id":"Q3337942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098764$48AF6120-C27E-4D00-BC80-65B597B9D3FA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9788f8d6b95d3740b077f4177d171764a1bcebf4","datavalue":{"value":{"entity-type":"item","numeric-id":5392088,"id":"Q5392088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c385e62986d853b2c03dacc9853c008a3ce9c800","datavalue":{"value":{"amount":"+0.93363565","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1098764$4BD1A318-7720-4BBF-A7CD-88392B573EFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24ec8d3830761c3dd34d50ab8916821d126dccf1","datavalue":{"value":{"entity-type":"item","numeric-id":3416571,"id":"Q3416571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4c4ca30243ef9c313732981a36d4348058a0913","datavalue":{"value":{"amount":"+0.93205893","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1098764$A0FC0645-C59E-4446-92DA-E37D65CB7A21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cc6960594f7d5f89fa640d74e7c0d7a778ae38d","datavalue":{"value":{"entity-type":"item","numeric-id":4723558,"id":"Q4723558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecb89c79041d09254f2db76725bd0daf3c8b6039","datavalue":{"value":{"amount":"+0.9299875","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1098764$09DFE283-D27A-497A-AE29-95ACBB049147","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30aaf34d20cd7a8c4129d6e5f94e9d9f9d957a8b","datavalue":{"value":{"entity-type":"item","numeric-id":4545676,"id":"Q4545676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2a53ec71c95bc4454d70094a030780dbc50d7f1","datavalue":{"value":{"amount":"+0.9269855","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1098764$9901A718-FB6D-483B-8778-BC3598A99859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e96c2a6d61c424d94f50962a0acf1a7f41d3b3a2","datavalue":{"value":{"entity-type":"item","numeric-id":5688724,"id":"Q5688724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"352eec82ab2cbb081b2f66f43abd1dcf4a07dff8","datavalue":{"value":{"amount":"+0.9252626","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1098764$84ABC7EB-D5BB-4AEA-8E7A-420056A690AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6116d7f8dac1e5d34b391479e0473f43b41dc767","datavalue":{"value":{"entity-type":"item","numeric-id":4666721,"id":"Q4666721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"288426e65ac2fac5195141d60fadb8769ab5f445","datavalue":{"value":{"amount":"+0.9216411","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1098764$CE367B1E-2159-4993-B09A-9217FE54D605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b07aa399ddad4b2f01fe4680c4fc36fc89f6c91","datavalue":{"value":{"entity-type":"item","numeric-id":958462,"id":"Q958462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"359f879784ae9406e57211099d986ef2b770dd27","datavalue":{"value":{"amount":"+0.9149595","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1098764$CB799A5A-EAD7-4A7C-A191-1A58B7704115","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcceff79e50a77f366d1936e03bb3d42407788f0","datavalue":{"value":{"entity-type":"item","numeric-id":4246618,"id":"Q4246618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"260d0852316c1cd98e24b82b68be5d4a5a9e33ab","datavalue":{"value":{"amount":"+0.9113211","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1098764$E0A8B48F-F004-4AE7-BBB5-A22597B75D94","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1098764","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1098764"}}}}}