Multi-depot vehicle scheduling with disruptions

Abstract

This thesis aims at solving a multi-depot vehicle scheduling problem with disruptions at the operational level. Although there are many cases of disruptions in transportation, we mainly focus on the excessive customer demand for a specific destination and late arrival of vehicles. We refer to these problems as extra trip and delayed trip problems, respectively. Then we propose a solution method that is based on swapping two routes. Conventional vehicle scheduling problem is solved by generating a sequence of trips known as routes. By using a set partitioning model, it is ensured that each trip is covered exactly once while the total deadheading cost is minimized. Since the set partitioning model has exponentially many variables, the column generation algorithm is used to solve the problem efficiently. However, with our proposed swapping strategy, a set partitioning model with side constraints is formulated. To solve this new model, we need to use two different subproblems. The first one is a standard one, which follows the column generation algorithm directly. The second subproblem generates pairs of routes (columns) and along with these pairs constraints are added to the problem. To handle this difficulty, we propose to apply a column-and-row generation algorithm and discuss the optimality of this approach. The proposed method is tested on a set of randomly generated problem instances. Computational results show that the proposed approach can effectively handle the disruptions at the expense of a slight increase in the cost of the conventional model.