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 biridir. Ancak, bazı araştırmacılar tarafından, tesis yeri seçim modellerinin gerçek hayat uygulamalarını temsil etme ve çözmedeki yeterliliği uzun süredir sorgulanmakta ve yeni modellerin geliştirilmesine ihtiyaç olduğu ifade edilmektedir. Literatürdeki modellerin büyük bir çoğunluğu, modellerin gerçek hayattaki uygulama alanlarını sınırlandıran belirli varsayımlara dayanmaktadır. Bu varsayımların en önemlilerinden biri, modellerde girdi olarak kullanılan serim ve veri yapısıyla ilgilidir. Literatürdeki modeller, düğümler arası mesafe matrisinde en kısa yol uzunluklarının kullanıldığı tam serim (complete network) yapısı üzerine kuruludur. Modellerde tam serim yapısının kullanılması, gerçek hayattaki serimlerin (örneğin, demiryolları ya da karayolları) tam serim yapısında olmasından ziyade, araştırmacıların bazen doğrudan bazen de dolaylı olarak kabul ettiği bir varsayıma dayanmaktadır. Araştırmacılar, gerçek hayat serimlerine en kısa yol algoritmalarının uygulanması suretiyle, düğümler arasında en kısa yolların kullanıldığı bir tam serim yapısının oluşturulduğunu varsaymaktadır. Diğer bir ifadeyle, modellerde girdi olarak kullanılan serim yapısı, düğümler arası mesafelerin üçgen eşitsizliğini sağladığı tam serimdir. Bu yaklaşım genel olarak kabul görmekle beraber, gerçek serim ve veri yapısının modellerde doğrudan girdi olarak kullanılmaması, modelleme ve çözüm açısından bazı dezavantajlara sebep olmaktadır. Daha da önemlisi, gerçek hayatta en kısa yolların tercih edilmediği veya üçgen eşitsizliğinin sağlanmadığı birçok durum vardır. Söz konusu tespitlerden hareketle, literatürdeki yaklaşımlardan tamamen farklı olarak, tam olmayan gerçek serim yapısının modellerde doğrudan girdi olarak kullanıldığı tesis yeri seçim problemleri tanımlanmıştır. Projede, tesis yeri seçiminde klasikler arasında kabul edilmeleri ve diğer tesis yeri seçim modellerinin temelini oluşturmaları nedeniyle, p-ortanca ve p-hub ortanca problemleri ele alınmıştır. Bu problemlerin, ayrıt/düğüm kapasiteli, kapasitesiz, tek ve çoklu atama ile farklı topolojilere izin veren versiyonları için modeller ve çözüm yöntemleri geliştirilmiştir. Geliştirilen modeller, hem gerçek serim yapısı, hem de (üçgen eşitsizliğini sağlamayan dahil) tam serim yapısı ile doğru sonuçlar vermektedir. Geliştirilen formülasyonlarda, daha çok tesis-talep noktası atama kararlarına dayanan literatürdeki modellerin aksine, ayrıt tabanlı akışlar esas alınmıştır. Modellerin çözümü için, Benders Ayrıştırma ve Lagrange gevşetme algoritmaları geliştirilmiştir. Modellerin ve geliştirilen algoritmaların performansları, çeşitli problemler kullanılarak test edilmiştir.

Facility location problems are one of the mostly-studied areas. However, some researchers have been questioning the applicability of the facility location models to solve real-world problems and stating that there is a need to develop new models to better model real-world problems for quite long time. Most models in the literature depend on several assumptions that limit their application areas in in real life. One of the most important assumptions is about the network and data structures used as an input in the models. The models in the literature are based on the complete network structure where the distance matrix represents the shortest-path distances between node pairs. This starting point is not necessarily from assuming that the underlying real-world network (e.g., physical network such as road and rail networks) on which the hub system will operate is complete. It is implicitly or explicitly assumed that a complete-network structure is constructed from the shortest-path lengths between origin-destination pairs on the underlying real-world network through a shortest-path algorithm. Thus, the network structure used as an input in most models is a complete network with the distances satisfying the triangle inequality. Even though this approach has gained acceptance, not using the real-world network and its data structure directly in the models may result in several computational and modeling disadvantages. More importantly, there are cases in which the shortest path is not preferred or the triangle inequality is not satisfied. In this regard, we take a new direction completely different from the literature and define the facility location problems directly on non-complete networks that are representative of many real- world networks. p-median and p-hub median problems have been addressed in the project as they are accepted among the classical facility location models and form the building blocks of many other facility location models. Arc/node capacitated, uncapacitated, single- and multi-assignment versions with general topologies (e.g., allowing tree structure between hubs) of these problems have been investigated. The models can be used for both real networks and complete networks (including the ones not satisfying the triangle inequality). Unlike most models in the literature that are based on facility-demand point assignments, the new formulations are based on arc-based flows. To solve the models, Benders decomposition and Lagrangean based algorithms have been developed. The performances of the proposed models and algorithms have been assessed using several test problems.