Multi-depot vehicle scheduling with disruptions

Abstract

Bu çalışma, çok depolu araç rotalama probleminde operasyon aşamasında ortaya çıkabilecek aksaklıkları yönetmeyi amaçlamaktadır. Ulaşım sektöründe, ilgili problemler yapısı itibari ile çok farklı aksaklıklar içerse de, bu tez kapsamında özellikle aşırı müşteri talebi ve gecikmiş seferler göz önünde bulundurulmuştur. Sözü edilen aksaklıklar ek sefer ve gecikmiş sefer problemleri olarak isimlendirilmiştir. Bu iki probleme çözüm olarak, uygun iki rotayı çaprazlayan bir yöntem geliştirilmiştir. Geleneksel araç rotalama problemi her bir seferi bir kez kapsayacak şekilde seferler dizisinden oluşan rotaların yaratılması ve bu rotaların küme bölüntüleme modelinde kullanılması ile çözülür. Amaç fonksiyonunun, toplam boş sefer mesafesini en küçüklemek olduğu bu model üssel sayıda değişken içerdiğinden sütun türetme yaklaşımı kullanılır. Fakat aksaklıkların yönetimi için küme bölüntüleme modeline eklenen yan kısıtlar modelin standart sütun türetme yöntemi ile çözümünü imkansız hale getirmiştir. Bu yeni modeli çözebilmek için iki farklı alt probleme ihtiyaç duyulmuştur. Alt problemlerden ilki tek bir rota oluşturulmasını amaçlarken diğer problem rota çifti oluşturmaktadır. Rota çiftleri oluşturan bu problem değişkenler ile birlikte kısıtlarıda beraberinde getirdiği için satır-ve-sütun türetme yaklaşımı geliştirilmiş ve yöntemin en iyilik durumu ispat edilmiştir. Önerilen yöntemin hesaplama sonuçlarının gösterdiği üzere elde edilen sonuçlar aksaklıklara çözüm sunarken, geleneksel yöntemin amaç fonksiyonunda sınırlı miktarda artışa sebep olmuştur.

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 routes, which consist of sequence of trips. 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, 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.