TR20-02 (2020) – Multiple-Depot Vehicle Scheduling Problem Heuristics

Emanuel Florentin Olariu, Cristian Frasinaru

The Multiple-Depot Vehicle Scheduling Problem (MDVSP) is very important in the planning process of transport systems. It consists in assigning a set of trips to a set of vehicles in order to minimize a certain total cost. We introduce three fast and reliable heuristics for MDVSP based on a classical integer linear programming formulation and on graph theoretic methods of fixing the infeasible subtours gathered from an integer solution. Extensive experimentations using a large set of benchmark instances show that our heuristics are faster and give good or even better results compared with other existing heuristics.

Bibtex

@TechReport{mdvsph,
authors = "Emanuel Florentin Olariu, Cristian Frasinaru",
title = "Multiple-Depot Vehicle Scheduling Problem Heuristics”,
institution = "Alexandru Ioan Cuza University of Ia{\c s}i, Faculty of Computer Science",
year = "2020",
number = "TR 20-02",
note = "url{https://www.info.uaic.ro/en/tehnical_reports/}"
}