An Integrated Assignment-Routing Problem With Time Windows

Abstract

Bu tez çalışmasında İzmir Türkiye'de bulunan bir bağış merkezindeki bir gerçek hayat kamu hizmeti problemi ele alınmıştır. Merkez bağışlanan ürünlerin bağış sahiplerinden toplanılması, bu ürünlerin gelen istekler doğrultusunda ihtiyaç sahibi vatandaşlara atanması ve dağıtımından sorumludur. Atanamayan ürünler tek bir depoda geçici olarak bekletilmektedir. Günlük dağıtım ve toplama için tek araç kullanılmakta, gelen bağışçı ve ihtiyaç sahiplerinin ziyaret edilme saatlerine dair zaman aralıkları bulunmaktadır. Bu çalışmada problem için yeni ve özgün, fayda bazlı atama ve rotalamayı bir arada yapan tamsayılı programlama modelleri önerilmektedir. Modellerde bağışçı ve ihtiyaç sahiplerinin hizmet aldıkları zaman aralıkları bağlayıcı ve bağlayıcı olmayan kısıtlar olarak ele alınmıştır. Bağlayıcı olmayan kısıtlara sahip modelin performansının sayısal olarak değerlendirilmesi için geliştirilen deney tasarımı ve sonuçları ayrıntılarıyla sunulmuş ve tartışılmıştır. Bu tez çalışmasıyla hem rotalama literatürüne yeni ve özgün modellerle katkıda bulunmak, hem de pratik öneme sahip insani bir probleme optimal çözümler getirmek amaçlanmıştır.

In this thesis, we consider a real-life public service problem at a donation center in Izmir, Turkey. The center is responsible for picking up incoming donated items from donors, assigning these items to incoming requests of the needy residents/clients in the district, and distributing the items. The unmatched items are stored at the single depot. A single vehicle is used for daily pickup and delivery, and the incoming requests have associated time windows for pickup or delivery. We propose novel utility-based assignment/routing integer programming models for this problem that assumes hard and soft time windows for service start times of the donors and clients. The details of the experiment design used for evaluating the performance of the developed model with soft time windows are presented, and computational results are discussed. With this thesis, we intend to contribute to the routing literature by introducing a novel integrated model, as well as providing optimal solutions to a practical and important humanitarian problem.