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&#x20...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Emiliana Mara Lopes Simoes, Lucas De Souza Batista, Marcone Jamilson Freitas Souza
Formato:	article
Lenguaje:	EN
Publicado:	IEEE 2021
Materias:	Iterated local search matheuristic multiple-depot vehicle and crew scheduling public transportation time-space network variable neighborhood descent Electrical engineering. Electronics. Nuclear engineering TK1-9971
Acceso en línea:	https://doaj.org/article/4b97d9d4ca42431b9b1eb1b5c94b69e5
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:4b97d9d4ca42431b9b1eb1b5c94b69e5
record_format	dspace
spelling	oai:doaj.org-article:4b97d9d4ca42431b9b1eb1b5c94b69e52021-12-01T00:00:39ZA Matheuristic Algorithm for the Multiple-Depot Vehicle and Crew Scheduling Problem2169-353610.1109/ACCESS.2021.3128871https://doaj.org/article/4b97d9d4ca42431b9b1eb1b5c94b69e52021-01-01T00:00:00Zhttps://ieeexplore.ieee.org/document/9617637/https://doaj.org/toc/2169-3536This 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.Emiliana Mara Lopes SimoesLucas De Souza BatistaMarcone Jamilson Freitas SouzaIEEEarticleIterated local searchmatheuristicmultiple-depot vehicle and crew schedulingpublic transportationtime-space networkvariable neighborhood descentElectrical engineering. Electronics. Nuclear engineeringTK1-9971ENIEEE Access, Vol 9, Pp 155897-155923 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Iterated local search matheuristic multiple-depot vehicle and crew scheduling public transportation time-space network variable neighborhood descent Electrical engineering. Electronics. Nuclear engineering TK1-9971
spellingShingle	Iterated local search matheuristic multiple-depot vehicle and crew scheduling public transportation time-space network variable neighborhood descent Electrical engineering. Electronics. Nuclear engineering TK1-9971 Emiliana Mara Lopes Simoes Lucas De Souza Batista Marcone Jamilson Freitas Souza A Matheuristic Algorithm for the Multiple-Depot Vehicle and Crew Scheduling Problem
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.
format	article
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
title	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_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_sort	matheuristic algorithm for the multiple-depot vehicle and crew scheduling problem
publisher	IEEE
publishDate	2021
url	https://doaj.org/article/4b97d9d4ca42431b9b1eb1b5c94b69e5
work_keys_str_mv	AT emilianamaralopessimoes amatheuristicalgorithmforthemultipledepotvehicleandcrewschedulingproblem AT lucasdesouzabatista amatheuristicalgorithmforthemultipledepotvehicleandcrewschedulingproblem AT marconejamilsonfreitassouza amatheuristicalgorithmforthemultipledepotvehicleandcrewschedulingproblem AT emilianamaralopessimoes matheuristicalgorithmforthemultipledepotvehicleandcrewschedulingproblem AT lucasdesouzabatista matheuristicalgorithmforthemultipledepotvehicleandcrewschedulingproblem AT marconejamilsonfreitassouza matheuristicalgorithmforthemultipledepotvehicleandcrewschedulingproblem
_version_	1718406136761155584

A Matheuristic Algorithm for the Multiple-Depot Vehicle and Crew Scheduling Problem

Ejemplares similares