European Master's Program in Computational Logic

Search:
05 December 2016

Master Thesis Defence by Mr Emmanouil Thanos

Mr Emmanouil Thanos defended hist master thesis on 'A Constrained Multi-Start Approach to the Drivers Daily Activities Problem with Depot Discontinuity'


Mr Emmanouil Thanos defended hist master thesis on 'A Constrained Multi-Start Approach to the Drivers Daily Activities Problem with Depot Discontinuity' at NOVA on 12 October 2016.

Abstract: Public Transportation influences many aspects of everyday life and the minimization of its
operation cost has been of great importance in recent years. In this thesis we study the Drivers Daily
Activities Problem with Depot Discontinuity (DD). The DD factor means that a driver can take
over services in different locations from the ones the same driver last stopped.
The underlying problem is a task-based scheduling one and is a cost-based variant of the
Bus Driver Scheduling Problem, which in the literature has been mostly addressed by Mixed
Integer/Linear Programming and Multi-Start meta-heuristics.
To moderate the increased complexity introduced by the DD factor, we built a Constraint
Programming model using an integer representation, different than the classical binary one, in order
to reduce the number of constraints and variables. We develop a greedy constructive algorithm
based on this model and we propose 3 different heuristics for the value selection strategy.
To reduce the solutions’ cost we developed a multi-start optimization method with evolutionary
characteristics aiming at the gradual minimization of the number of overpriced duties, based on the
enforcement of targeted constraints at each call of the constructive algorithm.
We perform experiments of both real-world and randomly created instances to test our method
over a wide range of bus itineraries structure, through which we verify as well the different directions
of duties-based and cost-based approach. The results show that our approach leads to considerable
performance improvement and produces highly efficient solutions within reasonable amounts of
time. They also verify the contribution of DD factor to the cost reduction and justify the choice of
our model representation. They finally indicate the dominance of one of the proposed heuristics over
the other two, yet producing interesting observations regarding the strategies’ overall behaviour.