Loading…

General hybrid column generation algorithm for crew scheduling problems using genetic algorithm

This paper describes a general hybrid column generation algorithm for crew scheduling problems, using genetic algorithm to speed up the generation of new columns, combined with an integer programming exact method to assure optimality. The subproblem of the column generation must generate a new feasi...

Full description

Saved in:

Bibliographic Details
Main Authors:	dos Santos, A.G., Mateus, G.R.
Format:	Conference Proceeding
Language:	English
Subjects:	Base stations Cost function Genetic algorithms Hybrid power systems Integer linear programming Linear programming Mathematical model NP-hard problem Partitioning algorithms Scheduling algorithm
Citations:	Items that cite this one
Online Access:	Request full text
Tags:	Add Tag No Tags, Be the first to tag this record!

cited_by	cdi_FETCH-LOGICAL-c222t-f4cbe55da669ba938befb3ecf185b5c9f136e2e96936a01c4ba215a042bd8f7c3
cites
container_end_page	1806
container_issue
container_start_page	1799
container_title
container_volume
creator	dos Santos, A.G. Mateus, G.R.
description	This paper describes a general hybrid column generation algorithm for crew scheduling problems, using genetic algorithm to speed up the generation of new columns, combined with an integer programming exact method to assure optimality. The subproblem of the column generation must generate a new feasible set of tasks to be assigned to a crew member. It is modeled as a shortest path with resource constraints problem in a graph, which virtually can be applied to all kinds of crew scheduling problems. The genetic algorithm is also general, and knowledge about specific problems may be incorporated. The hybrid algorithm is tested with instances from the literature and also with real instances, and the results show that the genetic algorithm is able to quickly generate most of the columns needed to solve the problem, while the exact method generates the last columns to find the optimal solution. The algorithm can also incorporate other kind of heuristics.
doi_str_mv	10.1109/CEC.2009.4983159
format	conference_proceeding
fullrecord	<record><control><sourceid>ieee_CHZPO</sourceid><recordid>TN_cdi_ieee_primary_4983159</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>4983159</ieee_id><sourcerecordid>4983159</sourcerecordid><originalsourceid>FETCH-LOGICAL-c222t-f4cbe55da669ba938befb3ecf185b5c9f136e2e96936a01c4ba215a042bd8f7c3</originalsourceid><addsrcrecordid>eNpFkE1LAzEYhONHwbZ6F7zkD2zN527eoyxtFQpeFLyVJPumjexHyW6R_ntbLfQ0zDzMHIaQR85mnDN4LuflTDAGMwVGcg1XZMKVUEqABn1NxhwUzxgT-c0FmOL2CJiBrCjM14hMjgMGmCkk3JFJ338zxpXmMCbrJbaYbE23B5diRX1X75uWbv7SIXYttfWmS3HYNjR0ifqEP7T3W6z2dWw3dJc6V2PT031_sqfeEP2ldE9GwdY9Ppx1Sj4X84_yNVu9L9_Kl1XmhRBDFpR3qHVl8xycBWkcBifRB2600x4ClzkKhBxkbhn3ylnBtWVKuMqEwsspefrfjYi43qXY2HRYny-Tv6wWXC0</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>General hybrid column generation algorithm for crew scheduling problems using genetic algorithm</title><source>IEEE Xplore All Conference Series</source><creator>dos Santos, A.G. ; Mateus, G.R.</creator><creatorcontrib>dos Santos, A.G. ; Mateus, G.R.</creatorcontrib><description>This paper describes a general hybrid column generation algorithm for crew scheduling problems, using genetic algorithm to speed up the generation of new columns, combined with an integer programming exact method to assure optimality. The subproblem of the column generation must generate a new feasible set of tasks to be assigned to a crew member. It is modeled as a shortest path with resource constraints problem in a graph, which virtually can be applied to all kinds of crew scheduling problems. The genetic algorithm is also general, and knowledge about specific problems may be incorporated. The hybrid algorithm is tested with instances from the literature and also with real instances, and the results show that the genetic algorithm is able to quickly generate most of the columns needed to solve the problem, while the exact method generates the last columns to find the optimal solution. The algorithm can also incorporate other kind of heuristics.</description><identifier>ISSN: 1089-778X</identifier><identifier>ISBN: 1424429587</identifier><identifier>ISBN: 9781424429585</identifier><identifier>EISSN: 1941-0026</identifier><identifier>EISBN: 1424429595</identifier><identifier>EISBN: 9781424429592</identifier><identifier>DOI: 10.1109/CEC.2009.4983159</identifier><identifier>LCCN: 2008908739</identifier><language>eng</language><publisher>IEEE</publisher><subject>Base stations ; Cost function ; Genetic algorithms ; Hybrid power systems ; Integer linear programming ; Linear programming ; Mathematical model ; NP-hard problem ; Partitioning algorithms ; Scheduling algorithm</subject><ispartof>2009 IEEE Congress on Evolutionary Computation, 2009, p.1799-1806</ispartof><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c222t-f4cbe55da669ba938befb3ecf185b5c9f136e2e96936a01c4ba215a042bd8f7c3</citedby></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/4983159$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2058,27925,54555,54796,54920,54932</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/4983159$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>dos Santos, A.G.</creatorcontrib><creatorcontrib>Mateus, G.R.</creatorcontrib><title>General hybrid column generation algorithm for crew scheduling problems using genetic algorithm</title><title>2009 IEEE Congress on Evolutionary Computation</title><addtitle>CEC</addtitle><description>This paper describes a general hybrid column generation algorithm for crew scheduling problems, using genetic algorithm to speed up the generation of new columns, combined with an integer programming exact method to assure optimality. The subproblem of the column generation must generate a new feasible set of tasks to be assigned to a crew member. It is modeled as a shortest path with resource constraints problem in a graph, which virtually can be applied to all kinds of crew scheduling problems. The genetic algorithm is also general, and knowledge about specific problems may be incorporated. The hybrid algorithm is tested with instances from the literature and also with real instances, and the results show that the genetic algorithm is able to quickly generate most of the columns needed to solve the problem, while the exact method generates the last columns to find the optimal solution. The algorithm can also incorporate other kind of heuristics.</description><subject>Base stations</subject><subject>Cost function</subject><subject>Genetic algorithms</subject><subject>Hybrid power systems</subject><subject>Integer linear programming</subject><subject>Linear programming</subject><subject>Mathematical model</subject><subject>NP-hard problem</subject><subject>Partitioning algorithms</subject><subject>Scheduling algorithm</subject><issn>1089-778X</issn><issn>1941-0026</issn><isbn>1424429587</isbn><isbn>9781424429585</isbn><isbn>1424429595</isbn><isbn>9781424429592</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2009</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNpFkE1LAzEYhONHwbZ6F7zkD2zN527eoyxtFQpeFLyVJPumjexHyW6R_ntbLfQ0zDzMHIaQR85mnDN4LuflTDAGMwVGcg1XZMKVUEqABn1NxhwUzxgT-c0FmOL2CJiBrCjM14hMjgMGmCkk3JFJ338zxpXmMCbrJbaYbE23B5diRX1X75uWbv7SIXYttfWmS3HYNjR0ifqEP7T3W6z2dWw3dJc6V2PT031_sqfeEP2ldE9GwdY9Ppx1Sj4X84_yNVu9L9_Kl1XmhRBDFpR3qHVl8xycBWkcBifRB2600x4ClzkKhBxkbhn3ylnBtWVKuMqEwsspefrfjYi43qXY2HRYny-Tv6wWXC0</recordid><startdate>200905</startdate><enddate>200905</enddate><creator>dos Santos, A.G.</creator><creator>Mateus, G.R.</creator><general>IEEE</general><scope>6IE</scope><scope>6IL</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIL</scope></search><sort><creationdate>200905</creationdate><title>General hybrid column generation algorithm for crew scheduling problems using genetic algorithm</title><author>dos Santos, A.G. ; Mateus, G.R.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c222t-f4cbe55da669ba938befb3ecf185b5c9f136e2e96936a01c4ba215a042bd8f7c3</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2009</creationdate><topic>Base stations</topic><topic>Cost function</topic><topic>Genetic algorithms</topic><topic>Hybrid power systems</topic><topic>Integer linear programming</topic><topic>Linear programming</topic><topic>Mathematical model</topic><topic>NP-hard problem</topic><topic>Partitioning algorithms</topic><topic>Scheduling algorithm</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>dos Santos, A.G.</creatorcontrib><creatorcontrib>Mateus, G.R.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan All Online (POP All Online) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE/IET Electronic Library (IEL)</collection><collection>IEEE Proceedings Order Plans (POP All) 1998-Present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>dos Santos, A.G.</au><au>Mateus, G.R.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>General hybrid column generation algorithm for crew scheduling problems using genetic algorithm</atitle><btitle>2009 IEEE Congress on Evolutionary Computation</btitle><stitle>CEC</stitle><date>2009-05</date><risdate>2009</risdate><spage>1799</spage><epage>1806</epage><pages>1799-1806</pages><issn>1089-778X</issn><eissn>1941-0026</eissn><isbn>1424429587</isbn><isbn>9781424429585</isbn><eisbn>1424429595</eisbn><eisbn>9781424429592</eisbn><abstract>This paper describes a general hybrid column generation algorithm for crew scheduling problems, using genetic algorithm to speed up the generation of new columns, combined with an integer programming exact method to assure optimality. The subproblem of the column generation must generate a new feasible set of tasks to be assigned to a crew member. It is modeled as a shortest path with resource constraints problem in a graph, which virtually can be applied to all kinds of crew scheduling problems. The genetic algorithm is also general, and knowledge about specific problems may be incorporated. The hybrid algorithm is tested with instances from the literature and also with real instances, and the results show that the genetic algorithm is able to quickly generate most of the columns needed to solve the problem, while the exact method generates the last columns to find the optimal solution. The algorithm can also incorporate other kind of heuristics.</abstract><pub>IEEE</pub><doi>10.1109/CEC.2009.4983159</doi><tpages>8</tpages></addata></record>
fulltext	fulltext_linktorsrc
identifier	ISSN: 1089-778X
ispartof	2009 IEEE Congress on Evolutionary Computation, 2009, p.1799-1806
issn	1089-778X 1941-0026
language	eng
recordid	cdi_ieee_primary_4983159
source	IEEE Xplore All Conference Series
subjects	Base stations Cost function Genetic algorithms Hybrid power systems Integer linear programming Linear programming Mathematical model NP-hard problem Partitioning algorithms Scheduling algorithm
title	General hybrid column generation algorithm for crew scheduling problems using genetic algorithm
url	http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-01T13%3A09%3A34IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_CHZPO&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=General%20hybrid%20column%20generation%20algorithm%20for%20crew%20scheduling%20problems%20using%20genetic%20algorithm&rft.btitle=2009%20IEEE%20Congress%20on%20Evolutionary%20Computation&rft.au=dos%20Santos,%20A.G.&rft.date=2009-05&rft.spage=1799&rft.epage=1806&rft.pages=1799-1806&rft.issn=1089-778X&rft.eissn=1941-0026&rft.isbn=1424429587&rft.isbn_list=9781424429585&rft_id=info:doi/10.1109/CEC.2009.4983159&rft.eisbn=1424429595&rft.eisbn_list=9781424429592&rft_dat=%3Cieee_CHZPO%3E4983159%3C/ieee_CHZPO%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c222t-f4cbe55da669ba938befb3ecf185b5c9f136e2e96936a01c4ba215a042bd8f7c3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=4983159&rfr_iscdi=true