Tesis yeri seçim problemleri için akış tabanlı modellerin ve çözüm metodolojilerinin geliştirilmesi

Abstract

Tesis yeri seçim problemleri, yoğun olarak akademik çalışmaların yürütüldüğü alanlardan_x000D_ biridir. Ancak, bazı araştırmacılar tarafından, tesis yeri seçim modellerinin gerçek hayat_x000D_ uygulamalarını temsil etme ve çözmedeki yeterliliği uzun süredir sorgulanmakta ve yeni_x000D_ modellerin geliştirilmesine ihtiyaç olduğu ifade edilmektedir. Literatürdeki modellerin büyük_x000D_ bir çoğunluğu, modellerin gerçek hayattaki uygulama alanlarını sınırlandıran belirli_x000D_ varsayımlara dayanmaktadır. Bu varsayımların en önemlilerinden biri, modellerde girdi olarak_x000D_ kullanılan serim ve veri yapısıyla ilgilidir. Literatürdeki modeller, düğümler arası mesafe_x000D_ matrisinde en kısa yol uzunluklarının kullanıldığı tam serim (complete network) yapısı üzerine_x000D_ kuruludur. Modellerde tam serim yapısının kullanılması, gerçek hayattaki serimlerin (örneğin,_x000D_ demiryolları ya da karayolları) tam serim yapısında olmasından ziyade, araştırmacıların_x000D_ bazen doğrudan bazen de dolaylı olarak kabul ettiği bir varsayıma dayanmaktadır._x000D_ Araştırmacılar, gerçek hayat serimlerine en kısa yol algoritmalarının uygulanması suretiyle,_x000D_ düğümler arasında en kısa yolların kullanıldığı bir tam serim yapısının oluşturulduğunu_x000D_ varsaymaktadır. Diğer bir ifadeyle, modellerde girdi olarak kullanılan serim yapısı, düğümler_x000D_ arası mesafelerin üçgen eşitsizliğini sağladığı tam serimdir. Bu yaklaşım genel olarak kabul_x000D_ görmekle beraber, gerçek serim ve veri yapısının modellerde doğrudan girdi olarak_x000D_ kullanılmaması, modelleme ve çözüm açısından bazı dezavantajlara sebep olmaktadır. Daha_x000D_ da önemlisi, gerçek hayatta en kısa yolların tercih edilmediği veya üçgen eşitsizliğinin_x000D_ sağlanmadığı birçok durum vardır. Söz konusu tespitlerden hareketle, literatürdeki_x000D_ yaklaşımlardan tamamen farklı olarak, tam olmayan gerçek serim yapısının modellerde_x000D_ doğrudan girdi olarak kullanıldığı tesis yeri seçim problemleri tanımlanmıştır. Projede, tesis_x000D_ yeri seçiminde klasikler arasında kabul edilmeleri ve diğer tesis yeri seçim modellerinin_x000D_ temelini oluşturmaları nedeniyle, p-ortanca ve p-hub ortanca problemleri ele alınmıştır. Bu_x000D_ problemlerin, ayrıt/düğüm kapasiteli, kapasitesiz, tek ve çoklu atama ile farklı topolojilere izin_x000D_ veren versiyonları için modeller ve çözüm yöntemleri geliştirilmiştir. Geliştirilen modeller, hem_x000D_ gerçek serim yapısı, hem de (üçgen eşitsizliğini sağlamayan dahil) tam serim yapısı ile doğru_x000D_ sonuçlar vermektedir. Geliştirilen formülasyonlarda, daha çok tesis-talep noktası atama_x000D_ kararlarına dayanan literatürdeki modellerin aksine, ayrıt tabanlı akışlar esas alınmıştır._x000D_ Modellerin çözümü için, Benders Ayrıştırma ve Lagrange gevşetme algoritmaları_x000D_ geliştirilmiştir. Modellerin ve geliştirilen algoritmaların performansları, çeşitli problemler_x000D_ kullanılarak test edilmiştir.Facility location problems are one of the mostly-studied areas. However, some researchers_x000D_ have been questioning the applicability of the facility location models to solve real-world_x000D_ problems and stating that there is a need to develop new models to better model real-world_x000D_ problems for quite long time. Most models in the literature depend on several assumptions_x000D_ that limit their application areas in in real life. One of the most important assumptions is about_x000D_ the network and data structures used as an input in the models. The models in the literature_x000D_ are based on the complete network structure where the distance matrix represents the_x000D_ shortest-path distances between node pairs. This starting point is not necessarily from_x000D_ assuming that the underlying real-world network (e.g., physical network such as road and rail_x000D_ networks) on which the hub system will operate is complete. It is implicitly or explicitly_x000D_ assumed that a complete-network structure is constructed from the shortest-path lengths_x000D_ between origin-destination pairs on the underlying real-world network through a shortest-path_x000D_ algorithm. Thus, the network structure used as an input in most models is a complete_x000D_ network with the distances satisfying the triangle inequality. Even though this approach has_x000D_ gained acceptance, not using the real-world network and its data structure directly in the_x000D_ models may result in several computational and modeling disadvantages. More importantly,_x000D_ there are cases in which the shortest path is not preferred or the triangle inequality is not_x000D_ satisfied. In this regard, we take a new direction completely different from the literature and_x000D_ define the facility location problems directly on non-complete networks that are_x000D_ representative of many real- world networks. p-median and p-hub median problems have_x000D_ been addressed in the project as they are accepted among the classical facility location_x000D_ models and form the building blocks of many other facility location models. Arc/node_x000D_ capacitated, uncapacitated, single- and multi-assignment versions with general topologies_x000D_ (e.g., allowing tree structure between hubs) of these problems have been investigated. The_x000D_ models can be used for both real networks and complete networks (including the ones not_x000D_ satisfying the triangle inequality). Unlike most models in the literature that are based on_x000D_ facility-demand point assignments, the new formulations are based on arc-based flows. To_x000D_ solve the models, Benders decomposition and Lagrangean based algorithms have been_x000D_ developed. The performances of the proposed models and algorithms have been assessed_x000D_ using several test problems.