A Matheuristic Algorithm for the Multiple-Depot Vehicle and Crew Scheduling Problem
This work addresses the multiple-depot vehicle and crew scheduling problem (MDVCSP). In MDVCSP, we deal with two NP-hard problems in an integrated way: the multiple-depot vehicle scheduling problem (MDVSP) and the crew scheduling problem (CSP). For solving the MDVCSP, we define the vehicles ...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9617637/ |
| _version_ | 1798002008217616384 |
|---|---|
| author | Emiliana Mara Lopes Simoes Lucas De Souza Batista Marcone Jamilson Freitas Souza |
| author_facet | Emiliana Mara Lopes Simoes Lucas De Souza Batista Marcone Jamilson Freitas Souza |
| author_sort | Emiliana Mara Lopes Simoes |
| collection | DOAJ |
| description | This work addresses the multiple-depot vehicle and crew scheduling problem (MDVCSP). In MDVCSP, we deal with two NP-hard problems in an integrated way: the multiple-depot vehicle scheduling problem (MDVSP) and the crew scheduling problem (CSP). For solving the MDVCSP, we define the vehicles’ operational routine and the workdays of the crews of a public bus transport system with multiple depots. Given the difficulty of solving real-world instances of the MDVCSP using exact mathematical methods, we propose a matheuristic algorithm for solving it. This matheuristic algorithm combines two strategies into an iterated local search (ILS) based framework: a branch-and-bound algorithm for solving the MDVSP and a variable neighborhood descent (VND) based algorithm for treating the associated CSPs. We compared the proposed ILS-MDVCSP with five approaches in the literature that use the same benchmark test instances. We also solved a real-world problem of one of Brazil’s largest cities. For this problem, we proposed a formulation based on a time-space network to address the MDVSP subproblem. The results obtained showed the effectiveness of ILS-MDVCSP, mainly to deal with real-world and large-scale problems. The algorithm was able to solve the largest instances from the literature, for which there was no reported solution. Regarding the run time, as the instances’ size increases, our approach becomes substantially less costly than the others from the literature. For the Brazilian instances, the ILS-MDVCSP saved, on average, the use of 12 vehicles per day and reduced by up to 15% the daily operational time of the vehicles. |
| first_indexed | 2024-04-11T11:45:21Z |
| format | Article |
| id | doaj.art-4b97d9d4ca42431b9b1eb1b5c94b69e5 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-11T11:45:21Z |
| publishDate | 2021-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-4b97d9d4ca42431b9b1eb1b5c94b69e52022-12-22T04:25:37ZengIEEEIEEE Access2169-35362021-01-01915589715592310.1109/ACCESS.2021.31288719617637A Matheuristic Algorithm for the Multiple-Depot Vehicle and Crew Scheduling ProblemEmiliana Mara Lopes Simoes0https://orcid.org/0000-0003-0036-7120Lucas De Souza Batista1https://orcid.org/0000-0002-7444-3440Marcone Jamilson Freitas Souza2https://orcid.org/0000-0002-7141-357XInstitute of Science and Technology, Federal University of Vales do Jequitinhonha e Mucuri, Diamantina, BrazilDepartment of Electrical Engineering, Federal University of Minas Gerais, Belo Horizonte, BrazilDepartment of Computing, Federal University of Ouro Preto, Ouro Preto, BrazilThis work addresses the multiple-depot vehicle and crew scheduling problem (MDVCSP). In MDVCSP, we deal with two NP-hard problems in an integrated way: the multiple-depot vehicle scheduling problem (MDVSP) and the crew scheduling problem (CSP). For solving the MDVCSP, we define the vehicles’ operational routine and the workdays of the crews of a public bus transport system with multiple depots. Given the difficulty of solving real-world instances of the MDVCSP using exact mathematical methods, we propose a matheuristic algorithm for solving it. This matheuristic algorithm combines two strategies into an iterated local search (ILS) based framework: a branch-and-bound algorithm for solving the MDVSP and a variable neighborhood descent (VND) based algorithm for treating the associated CSPs. We compared the proposed ILS-MDVCSP with five approaches in the literature that use the same benchmark test instances. We also solved a real-world problem of one of Brazil’s largest cities. For this problem, we proposed a formulation based on a time-space network to address the MDVSP subproblem. The results obtained showed the effectiveness of ILS-MDVCSP, mainly to deal with real-world and large-scale problems. The algorithm was able to solve the largest instances from the literature, for which there was no reported solution. Regarding the run time, as the instances’ size increases, our approach becomes substantially less costly than the others from the literature. For the Brazilian instances, the ILS-MDVCSP saved, on average, the use of 12 vehicles per day and reduced by up to 15% the daily operational time of the vehicles.https://ieeexplore.ieee.org/document/9617637/Iterated local searchmatheuristicmultiple-depot vehicle and crew schedulingpublic transportationtime-space networkvariable neighborhood descent |
| spellingShingle | Emiliana Mara Lopes Simoes Lucas De Souza Batista Marcone Jamilson Freitas Souza A Matheuristic Algorithm for the Multiple-Depot Vehicle and Crew Scheduling Problem IEEE Access Iterated local search matheuristic multiple-depot vehicle and crew scheduling public transportation time-space network variable neighborhood descent |
| title | A Matheuristic Algorithm for the Multiple-Depot Vehicle and Crew Scheduling Problem |
| title_full | A Matheuristic Algorithm for the Multiple-Depot Vehicle and Crew Scheduling Problem |
| title_fullStr | A Matheuristic Algorithm for the Multiple-Depot Vehicle and Crew Scheduling Problem |
| title_full_unstemmed | A Matheuristic Algorithm for the Multiple-Depot Vehicle and Crew Scheduling Problem |
| title_short | A Matheuristic Algorithm for the Multiple-Depot Vehicle and Crew Scheduling Problem |
| title_sort | matheuristic algorithm for the multiple depot vehicle and crew scheduling problem |
| topic | Iterated local search matheuristic multiple-depot vehicle and crew scheduling public transportation time-space network variable neighborhood descent |
| url | https://ieeexplore.ieee.org/document/9617637/ |
| work_keys_str_mv | AT emilianamaralopessimoes amatheuristicalgorithmforthemultipledepotvehicleandcrewschedulingproblem AT lucasdesouzabatista amatheuristicalgorithmforthemultipledepotvehicleandcrewschedulingproblem AT marconejamilsonfreitassouza amatheuristicalgorithmforthemultipledepotvehicleandcrewschedulingproblem AT emilianamaralopessimoes matheuristicalgorithmforthemultipledepotvehicleandcrewschedulingproblem AT lucasdesouzabatista matheuristicalgorithmforthemultipledepotvehicleandcrewschedulingproblem AT marconejamilsonfreitassouza matheuristicalgorithmforthemultipledepotvehicleandcrewschedulingproblem |