Multi-depot vehicle scheduling with disruptions

Yıldız, Ezgi (2011) Multi-depot vehicle scheduling with disruptions. [Thesis]

[thumbnail of EzgiYildiz_411242.pdf] PDF

Download (575kB)


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.
Item Type: Thesis
Uncontrolled Keywords: Multi-depot vehicle scheduling. -- Disruption management. -- Column generation. -- Column and row generation. -- Vehicle shedulling. -- Çok depolu araç rotalama problemi. -- Aksaklık yönetimi. -- Sütün türetme. -- Satır ve sütün türetme. -- Araç çizelgeleme.
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 02 Jul 2014 16:52
Last Modified: 26 Apr 2022 10:01

Actions (login required)

View Item
View Item