Scheduling with latest arrival consolidation in service network design problems

Abstract

Bu tezde, kara taşımacılığı temelli bir dağıtım sisteminde bulunan ürün taleplerinin başlangıç noktaları ile varış noktaları arasındaki rotalarının belirlendiği bir servis ağı tasarımı problemi üzerinde çalışılmıştır. Bir ürün başlangıç noktasından varış noktasına direk taşıma yönetimi ile gönderilebilir. Fakat bu şekildeki bir rotalama taşıma araçlarının verimsiz kullanımına neden olmaktadır. Ölçek ekonomisinden faydalanmak için, bir ağ tasarımı yöntemi olan ürünlerin birleştirilmesi politikası servis ağı tasarımı problemlerinde yaygın olarak kullanılmaktadır. Biz de, farklı ürünlerin birleştirilip ortak taşıma araçları ile dağıtıldıkları ve ürün birleştirme işlemlerinin istasyonlarda gerçekleştirildiği bir ürün birleştirme yapısını temel alan bir model oluşturduk. Uyguladığımız birleştirme yönteminde istasyonların bir kısmı terminal olarak seçilmektedir. Ürünlerin istasyonlara/terminallere eş zamanlı ulaşmamaları beklemelere neden olmaktadır. Servis ağı tasarımı problemlerindeki en geç ulaşanlara göre birleştirme, terminallerdeki gecikmelere odaklanan ve varış noktasına en geç ulaşan ürünün ulaşma vaktini eniyileyen bir modeldir. Bu modelin çözümü için geliştirilmiş olan kesin ve sezgisel yöntemler sunulacaktır. Kesin çözüm yöntemi olarak bir Genelleştirilmiş Benders Ayrışım algoritması geliştirilmiştir. Daha büyük servis ağları için de Geniş Komşuluk Esaslı Arama sezgisel yönetimi kullanılarak bir algoritma geliştirilmiştir. Sezgisel çözüm yöntemimizin etkisi geniş bir kapsamda gerçekleştirdiğimiz hesaplamalı deneyler ile gösterilmiştir. Modellediğimiz servis ağında, istasyonlar arasındaki direk transferlerin aynı taşıma aracı ile gerçekleştirildiği varsayılmıştır. Bu varsayımın kapsamını direk transferlerin birden fazla taşıma aracı ile gerçekleştirilebileceği şekilde genişleterek ve olay-etkinlik-ağı gösterimini kullanarak, en geç ulaşanlara göre birleştirme yönetiminin uygulandığı servis ağları için bir gecikme yönetim modelini de geliştirdik.

In this thesis, we consider the service network design problem of a ground-transportation based delivery system, in which routes of demands of commodities between any origin-destination pair are determined. A commodity can be sent from its origin to its destination through direct delivery, however such a routing would not effectively make use of the vehicles used for transportation. To benefit from economies of scale, a networking policy based on consolidation is generally applied in service networks. We consider freight-consolidation, in which different commodities are consolidated to be transported using common vehicles and consolidation operations are performed at stations, some of which are chosen as terminals. Nonsimultaneous arrival of commodities necessitates waiting times at stations/terminals. The latest arrival consolidation in service network design problem is then, a minimax model that considers the delays at terminals and focuses on minimization of the arrival time of the last arrived commodity to its destination. For the solution of the model, we present exact and heuristic solution procedures. We develop a tailored Generalized Benders Decomposition algorithm and to address larger size networks, we develop a Large Neighborhood Search based algorithm. We show the effectiveness of the heuristic solution procedure by performing extensive computational experiments. In the constructed service network, each direct ride between stations is assumed to be performed by the same vehicle. Extending this assumption to allow multiple vehicles and using event-activity-network representation, we develop a delay management model for service networks that apply latest arrival consolidation.