Solving a large real-world bus driver scheduling problem with a multi-assignment based heuristic algorithm
The bus driver scheduling problem (BDSP) under study consists in finding a set of duties that covers the bus schedule from a Brazilian public transportation bus company with the objective of minimizing the total cost. A deterministic 2-phase heuristic algorithm is proposed using multiple assignment...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Published: |
Verlag der Technischen Universität Graz
2017
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/44824/ |
| _version_ | 1848797006166753280 |
|---|---|
| author | Constantino, Ademir Aparecido de Mendonca, Candido F.X. de Araujo, Silvio Alexandre Landa-Silva, Dario Calvi, Rogerio dos Santos, Allainclair Flausino |
| author_facet | Constantino, Ademir Aparecido de Mendonca, Candido F.X. de Araujo, Silvio Alexandre Landa-Silva, Dario Calvi, Rogerio dos Santos, Allainclair Flausino |
| author_sort | Constantino, Ademir Aparecido |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | The bus driver scheduling problem (BDSP) under study consists in finding a set of duties that covers the bus schedule from a Brazilian public transportation bus company with the objective of minimizing the total cost. A deterministic 2-phase heuristic algorithm is proposed using multiple assignment problems that arise from a model based on a weighted multipartite graph. In the first phase, the algorithm constructs an initial feasible solution by solving a number of assignment problems. In the second phase, the algorithm attempts to improve the solution by two different procedures. One procedure takes the whole set of duties and divides them in a set of partial duties which are recombined. The other procedure seeks to improve single long duties by eliminating the overtime time and inserting it into another duty. Computational tests are performed using large-scale real-world data with more than 2,300 tasks and random instances extracted from real data. Three different objective functions are analyzed. The overall results indicate that the proposed approach is competitive to solve large BDSP. |
| first_indexed | 2025-11-14T19:57:00Z |
| format | Article |
| id | nottingham-44824 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:57:00Z |
| publishDate | 2017 |
| publisher | Verlag der Technischen Universität Graz |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-448242020-05-04T18:47:10Z https://eprints.nottingham.ac.uk/44824/ Solving a large real-world bus driver scheduling problem with a multi-assignment based heuristic algorithm Constantino, Ademir Aparecido de Mendonca, Candido F.X. de Araujo, Silvio Alexandre Landa-Silva, Dario Calvi, Rogerio dos Santos, Allainclair Flausino The bus driver scheduling problem (BDSP) under study consists in finding a set of duties that covers the bus schedule from a Brazilian public transportation bus company with the objective of minimizing the total cost. A deterministic 2-phase heuristic algorithm is proposed using multiple assignment problems that arise from a model based on a weighted multipartite graph. In the first phase, the algorithm constructs an initial feasible solution by solving a number of assignment problems. In the second phase, the algorithm attempts to improve the solution by two different procedures. One procedure takes the whole set of duties and divides them in a set of partial duties which are recombined. The other procedure seeks to improve single long duties by eliminating the overtime time and inserting it into another duty. Computational tests are performed using large-scale real-world data with more than 2,300 tasks and random instances extracted from real data. Three different objective functions are analyzed. The overall results indicate that the proposed approach is competitive to solve large BDSP. Verlag der Technischen Universität Graz 2017-05-28 Article PeerReviewed Constantino, Ademir Aparecido, de Mendonca, Candido F.X., de Araujo, Silvio Alexandre, Landa-Silva, Dario, Calvi, Rogerio and dos Santos, Allainclair Flausino (2017) Solving a large real-world bus driver scheduling problem with a multi-assignment based heuristic algorithm. Journal of Universal Computer Science, 23 (5). pp. 479-504. ISSN 0948-6968 bus driver scheduling crew management heuristic large real-world instances transportation http://www.jucs.org/jucs_23_5/solving_a_large_real |
| spellingShingle | bus driver scheduling crew management heuristic large real-world instances transportation Constantino, Ademir Aparecido de Mendonca, Candido F.X. de Araujo, Silvio Alexandre Landa-Silva, Dario Calvi, Rogerio dos Santos, Allainclair Flausino Solving a large real-world bus driver scheduling problem with a multi-assignment based heuristic algorithm |
| title | Solving a large real-world bus driver scheduling problem with a multi-assignment based heuristic algorithm |
| title_full | Solving a large real-world bus driver scheduling problem with a multi-assignment based heuristic algorithm |
| title_fullStr | Solving a large real-world bus driver scheduling problem with a multi-assignment based heuristic algorithm |
| title_full_unstemmed | Solving a large real-world bus driver scheduling problem with a multi-assignment based heuristic algorithm |
| title_short | Solving a large real-world bus driver scheduling problem with a multi-assignment based heuristic algorithm |
| title_sort | solving a large real-world bus driver scheduling problem with a multi-assignment based heuristic algorithm |
| topic | bus driver scheduling crew management heuristic large real-world instances transportation |
| url | https://eprints.nottingham.ac.uk/44824/ https://eprints.nottingham.ac.uk/44824/ |