| This master thesis concerns the multiple depot vehicle scheduling problem (MDVSP). This problem consists of covering a set of tasks with vehicles from several depots at minimum cost. In our case, each task has a precise starting time. The cost is the sum of a fixed cost, for each vehicle used and a cost proportional to the total distance traveled. The purpose of this master thesis is to compare and combine the column generation algorithm with a tabu search to solve this problem. In the first, chapter, we present the framework of the problem. In the second chapter, we use a heuristic column generation algorithm to solve the problems. Chapter 3 describes the tabu search used to solve the problems and then some adaptations. In the final chapter, we introduce an algorithm that combines a meta-heuristic with a column generation that regularly produces feasible solutions whose cost decreases. (Abstract shortened by UMI.)... |
