期刊
IEEE ACCESS
卷 9, 期 -, 页码 155897-155923出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/ACCESS.2021.3128871
关键词
Planning; Costs; Vehicles; Urban areas; Scheduling; Schedules; Licenses; Iterated local search; matheuristic; multiple-depot vehicle and crew scheduling; public transportation; time-space network; variable neighborhood descent
资金
- Brazilian agency the Coordination for the Improvement of Higher Education Personnel (CAPES) [001]
- Brazilian agency National Council for Scientific and Technological Development (CNPq) [303266/2019-8]
- Brazilian agency Minas Gerais State Foundation for Research Support (FAPEMIG) [PPM/CEX/676-17]
- Federal University of Vales do Jequitinhonha e Mucuri (UFVJM)
- Federal University of Minas Gerais (UFMG)
- Federal University of Ouro Preto (UFOP)
This work addresses the multiple-depot vehicle and crew scheduling problem in public bus transport systems, proposing a matheuristic algorithm that combines branch-and-bound and variable neighborhood descent algorithms. The results show the algorithm's effectiveness in solving real-world and large-scale problems, outperforming existing approaches in the literature.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据