Formulations and heuristic procedures for location-allocation-routing problems (Larp`s)

Abstract

<ö z e t YER SEÇİMİ -PAYLj/ŞTIRMA-QÜZERGÂH ATAMA PROBLEMLERİ (YAGP) YURTSEVER, Tanju Yüksek Lisans Tezi, Endüstri Mühendisliği Bölümü Tez Yöneticisi: Doç. Dr. Ömer Kırca Eylül 1988, 95 Sayfa Bu çalışmada, Yer Seçimi -Paylaştırma-Güzargâh Atama Problemleri (YAGP) olarak adlandırılan, iki amaçlı ulaşım problemi ile uğraşılmıştır. İlk önce, problem tanımlanmış ve matematiksel formülasyonu sunulmuştur. Amaçlardaki bir takım değişikliklerle problemin değişik tanım ve formu lasyonl arı da verilmiştir. NP-Tam sınıfına giren bu probleme, büyük boyutlu gerçek yaşamda çözüm yöntemleri sağlayabilmek amacıyla `çıkarma` ve `ekleme` diye adlandırılan iki değişik sezgisel yöntem geliştirilmiştir. Sezgisel yöntemler çok sayıda rassal olarak yaratılmış, test problemleri üzerinde denenmiştir. Bu probleme, tam sonuç getiren bir algoritmanın yokluğu dolayısıyla, bu yöntemlerin performansları kendi içlerinde analiz edilmiştir. Anahtar Kelimeler: Gezgin satıcı Problemi, Taşıt Güzargahı Ataması Problemi, Ver Seçimi-Paylaştırma Problemi, Yer Seçimi-Paylastırma- Güzargâh Atama Problemi, Çıkarma-ERleme Sezgisel Yöntemleri İVT

ABSTRACT FORMULATIONS AND HEURISTIC PROCEDURES FOR IJXATION-ALLCCATION-ROUTING PROBLEMS (LARP's) YURTSEVER, Tanju Supervisor: Assoc. Prof. Dr. Ömer Kirca September 1988, 95 pages In this study, we dealt with a two-objective transportation problem, namely Location-Allocation-Routing Problem (LARP). Initially the problem is defined, and its mathematical formulation is presented. With certain changes in the objectives, different definitions and formulations of the problem are given. Since the problem falls in the category of NP -Complete, in order to provide solution procedures for large dimensioned real -life problems, two different heuristics, namely `deletion` and `insertion` heuristics have been developed. The heuristics are tested on several randomly generated, large scale problems. Due to the absence of an exact algorithm for these problems, the performance of the heuristics are analyzed against each other. Keywords: Traveling Salesman Problem, Vehicle Routing Problem, Location-Allocation Problem, Location-Allocation-Routing Problem, Insertion-Deletion Heuristics. ıii