Congratulations to our most recent doctor in Electrical Engineering - Emiliana

July 13, 2022

Congratulations to our most recent D.sc. in Electrical Engineering, Emiliana Mara Lopes Simões. The title of the thesis was “A Matheuristic Algorithm For The Multiple-depot Vehicle And Crew Scheduling Problem”. The full thesis is available on here. The abstract is available below.

Congratulations, D.sc. Emiliana Simões! Completing your degree is an amazing feat and we are incredibly proud of your achievement.

“This thesis 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 25 vehicles per day and reduced on average by 16% the daily operational time of the vehicles considering four depots together.”