Browsing by Author "Kara, İmdat"

Now showing 1 - 8 of 8

Çok gezginli en küçük gecikme problemi için yeni karar modelleri
(Başkent Üniversitesi Fen Bilimleri Enstitüsü, 2015) Önder, Gözde; Kara, İmdat
En küçük Gecikme Problemi (EGP) rotalama problemlerinin temelini oluşturan Gezgin Satıcı Probleminin (GSP) bir türü olmaktadır. EGP, bir başlangıç düğümünden başlayarak, tüm düğümlere uğradıktan sonra başlangıç noktasında veya verilen bir düğümde sona eren Hamilton turunu veya yolunu araştırmaktadır. GSP bütün müşterilere uğramak için gerekli olan toplam zamanı en küçük yapmayı amaçlamakta, EGP ise tüm müşterilerin toplam gecikme zamanını en küçük yapmayı amaçlamaktadır. EGP„nin en önemli özel durumu olarak görülen çok gezginli uzantısı için kaynaklardaki yapılan çalışmalar incelendiğinde polinom sayıda ve üstel sayıda kısıta sahip iki farklı matematiksel model olduğu ancak bu modellere bakıldığında kısa sürede çözüme ulaşma açısından verimli olmadığı belirlenmiştir. Bu nedenle yeni karar modellerine ihtiyaç olduğu görülmüştür. Bu çalışma kapsamında ise, temel konu olarak ele alınan çok gezginli EGP için yapılacak çalışmanın altyapısını oluşturması amacıyla öncelikle EGP modelleri kaynaklarda bulunan kıyaslama problemi verileri kullanılarak sayısal analizlere tabi tutulmuştur. İşlem süresi (CPU) ve doğrusal programlama (LP) gevşetme değerleri yönüyle en iyi performans gösteren model belirlenmiştir. Çok gezginli EGP için üç tanesi yeni model bir tanesi kaynaklarda yer alan bir model olmak üzere toplam dört model ele alınıp kaynaklardaki farklı düğüm sayısına sahip kıyaslama problemleri ve gezgin sayıları için çözdürülerek en iyi performans gösteren model önerilmiştir. Yapılan bu karşılaştırmalı analizler sonucunda problem boyutu ve CPU süresi arasındaki ilişki ve gezgin sayısı ile CPU süresi arasındaki ilişki ile ilgili çıkarımlar da elde edilmiştir. Bu çalışmanın en önemli sonucu çok gezginli EGP için yeni bir modelin bilime katkı olarak sunulmasıdır. The Minimum Latency Problem (MLP) is a kind of Traveling Salesman Problem (TSP) which is the basis of the routing problems. MLP investigates the Hamilton tour or path, which starts from an initial node, after visiting all nodes, it ends at the starting or any given node. While TSP aims to make the smallest total time required to visit all customers, MLP aims to minimize total delay time of customers. When we review the literatüre, MLP with multiple traveler which is regarded as the most important exception of MLP, is modeled in two different ways: one with polynomial and the other with exponential number of constraints. However, both models are not efficient in terms of reaching a solution in a short time. Therefore the need for a new decision model is obvious. In this study, firstly MLP models are subjected to several quantitative analysis using available benchmarking problems in the literature. The purpose of this analysis is to create an infrastructure for the multiple traveling MLP. The best performing model is determined in terms of processing time (CPU) and linear programming (LP) relaxation values. Four models, one from literature and three new ones, are solved for benchmark problems with different number of nodes and different number of travelers and the best performing model is selected accordingly. As a result of this comparative analysis, we observe the relationship between problem size and CPU time and also the relationship between the number of travelers and CPU time. The most important result of this study is presented as a contribution to science, a new model for multiple traveling MLP.
New mathematical models for team formation of sports clubs before the match
(2019) Budak, Gercek; Kara, İmdat; İc, Yusuf Tansel; Kasimbeyli, Refail
Coaches of sports clubs aim to form the team that optimally determines the roles of positions before the match. These types of decisions are referred to as the team formation problem, and they are critical for the sports industry in the financial sense. Finding the optimal solution to the team formation problem is more difficult without the use of systematical approaches, as the number of players and their past performance records have increased substantially in recent years. In this paper, we discuss previous studies on the team formation problems of sports clubs and outline the deficiencies of their results in real-life decision processes. Then, we propose two new formulations that address coaches' preferences in the decision-making process. A real-life application of the proposed models is displayed for a volleyball team that participates in the first division of the Turkish Volleyball League.
Önce dağıt sonra topla araç rotalama problem için tamsayılı karar modelleri
(Başkent Üniversitesi Fen Bilimleri Enstitüsü, 2008) Keçeci, Barış; Kara, İmdat
Bir coğrafi bölgedeki müsteriler, “Ürün Dağıtılacak Müsteriler” ve “Ürün Toplanacak Müsteriler” olmak üzere iki alt kümeye ayrılsın. Dağıtım planının, araçların önce dağıtım yapılacak müsterilere, sonrada ürün toplanacak müsterilere uğrayarak depoya dönmeleri seklinde yapılmak istenmesi halinde, araç rotalama probleminin özel bir türü ortaya çıkar. Bu çalısmada bu tür problemler “Önce Dağıt Sonra Topla Problemlerinde Araç Rotalama (Vehicle Routing Problem with Backhauls)” olarak isimlendirilmistir. Çalısmanın hareket noktası, yapılan arastırmalarda ilgili kaynaklarda, yalnız ve yalnız önce dağıtım yapıp, sonra toplama bölgesine geçilmesi durumunda polinom büyüklükte bir matematiksel modelin bulunmayısıdır. Çalısmada yeni gelistirilen polinom büyüklükte iki tam sayılı karar modeli sunulmakta ve hem kaynaklarda yer alan test problemlerinin hem de rassal olarak üretilen problemlerin her iki modelle çözüm sonuçlarına yer verilmektedir. In a geographical region suppose that the customers are divided into two subsets as “Linehaul Customers” and “Backhual Customers”. If a distribution plan is built up such that the vehicles must visit the linehaul customers first and backhaul customers later and come back to the depot, then a special kind of the Vehicle Routing Problem arises. This problem is called Vehicle Routing Problem with Backhauls. The motivation of this study is the lack of polinomial size mathematical models which are exactly called Vehicle Routing Problems with Backhauls and has the situation that vehicles must visit the backhaul customers after the linehaul customers, in the literature as much as we accessed. In this study two polinomial size mathematical models are proposed and the computational results which were gathered by the solution of these two models with test instances from literature and ramdomly generated test instances, are given.
Seçici gezgin satıcı problemi için yeni matematiksel modeller
(Başkent Üniversitesi Fen Bilimleri Enstitüsü, 2014) Yalçın, Papatya Sevgin; Kara, İmdat
Gezgin Satıcı Problemi (GSP), araç rotalama, çizelgeleme vb. pek çok gerçek hayat problemlerinin temelini oluşturur. Kaynaklardaki çalışmalara bakıldığında, GSP ve uzantılarında amaç olarak genellikle, toplam maliyetin, toplam kat edilen yolun veya toplam harcanan sürenin enküçüklenmesi esas alına gelmiştir. Son yıllarda, serimdeki tüm düğümlere uğrama kısıtı gevşetilerek, verilen bir bütçe veya seyahat süresi kısıtı altında, gezginin uğrayabileceği düğümlerden elde edilecek kar, kazanç vb. getiriler toplamının enbüyük olması istenen problemler de araştırmacıların ilgi odağı olmuştur. Kaynaklarda ”Orienteering problemi veya Seçici GSP (The Selective TSP)”, “Getiri Toplamalı GSP-(The Price Collecting TSP)” veya “Karlı Tur Problemi (Profitable Tour Problem)” olarak isimlendirilen bu tür problemler, “Getiri Yönlü GSP (Traveling Salesman Problems with Profits)” başlığı altında toplanmaktadır. Farklı isimlendirmeler olmakla birlikte, bu tür problemlerde, aynı kısıtlar altında farklı amaç fonksiyonlarının ele alındığı görülmektedir. GSP ve uzantılarında olduğu gibi, getiri yönlü problemlerin çözüm yaklaşımlarının da öncelikle sezgiseller veya özel algoritmalar üzerine yoğunlaştığı, matematiksel modellere yeterince önem verilmediği görülmektedir. Söz konusu durum göz önüne alınarak, bu çalışmada ilk olarak, getiri yönlü GSP’nin kaynaklarda var olan modelleri incelenmiş, sonra getiri yönlü GSP’lerin benzer matematiksel yapısı nedeniyle bu problemlerden biri olan Seçici GSP, diğer adıyla Orienteering problemi için bir düğüm tabanlı bir de ayrıt tabanlı iki yeni karar modeli önerilmiştir. Önerilen modeller, kısıt ve tamsayı değişken sayısı itibariyle polinom büyüklüktedir ve tamsayılı karar modellerini çözen herhangi bir paket programla doğrudan kullanılabilecek özelliktedir. Önerilen modellerin performanslarını görmek amacıyla, kaynaklarda yer alan karşılaştırma problemleri Vansteenwegen-Souffriau-Oudheusden modeli ve yeni modellerle, CPLEX 12.5 paket programı kullanılarak çözülmüştür. Elde edilen sonuçlar, çözüm süreleri ve doğrusal programlama gevşetme değerleri yönleriyle analiz edilmiş ve önerilen yeni ii modellerin çok üstün olduğu görülmüştür. Ayrıca, matematiksel karar modelleri ile bulunan eniyi değerlerin, kaynaklarda sezgisel algoritmalarla bulunan bilinen eniyi değerlerin çoğundan daha büyük olduğu tespit edilmiştir.
Sipariş kabul ve çizelgeleme problemi ve uzantılarına ilişkin yeni matematiksel modeller
(Başkent Üniversitesi Fen Bilimleri Enstitüsü, 2020) Bıçakcı, Papatya Sevgin; Kara, İmdat
Siparişe göre üretim yapan sistemlerde, siparişleri çizelgelerken her siparişin yapılması zorunluluğu bulunmamaktadır. Bu konu kaynaklarda sipariş kabul ve çizelgeleme problemi olarak ele alınmaktadır. Bu tez kapsamında, sipariş kabul ve çizelgeleme problemi ile ilgili kaynaklarda var olan matematiksel modellere erişilmiş ve modeller incelenip, irdelenmiştir. Sipariş kabul ve çizelgeleme probleminin en erken başlama zamanlarının, sıra-bağımlı hazırlık sürelerinin ve son teslim tarihlerinin olduğu özel bir durumu ele alınmıştır. Genel çizelgeleme kaynaklarında, hazırlık süresi ve en erken başlama zamanı arasındaki ilişkiler araştırılmış ve ortak bir yaklaşım olmadığı fark edilmiştir. Bu duruma bir çözüm olarak ortak ve yeni bir yaklaşım geliştirilmiştir. Söz konusu durumlara ilişkin O(n2) kısıt sayısı O(n2) karar değişkeni sayısı bulunan yeni modeller önerilmiştir. Yanı sıra, yukarıda belirtilen özel problemin özdeş paralel makineler durumu ele alınmış ve bu konuda da O(n2) kısıt sayısı O(n2) karar değişkeni sayısı bulunan yeni bir model önerilmiştir. Önerdiğimiz modellerin performansları kaynaklardan seçilen özgün ve güncel modellerle karşılaştırılmıştır. Sonuç olarak, önerdiğimiz modellerin belli bir süre kısıtı altında ulaşılan eniyi değer sayısı ve çözüm süresi açısından diğer modellere göre çok üstün olduğu anlaşılmıştır. Özdeş paralel makineler durumu için önerdiğimiz model ile büyük boyutlu problemler verilen sürede çözülemediğinden, bu problemleri yaklaşık olarak çözebilmek için değişken komşu arama tabanlı bir tavlama benzetimi algoritması geliştirilmiştir. Matematiksel model yardımıyla sezgisel algoritmanın etkililiği test edilmiş ve problem yapısı zorlaştıkça sezgisel algoritmanın çok daha kısa sürelerde daha iyi çözümler verdiği sonucuna varılmıştır. In make-to-order production environment, when scheduling the orders, it is not an obligatory to process all the orders. This topic is treated order acceptance and scheduling problem in the literature. In the scope of this thesis, the mathematical formulations in the literature are determined, examined, and analyzed. The form of order accepted and scheduling problem with sequence-dependent setup times, release dates and deadlines is considered. The relationship between setup times and release dates are researched in the general scheduling literature and it is detected that there is not a common approach regarding this relationship. As a solution to this, a new and a common approach is proposed. New mathematical formulations with O(n2) the number of decision variables and O(n2) the number of constraints are presented. Besides, identical parallel machines form of above-mentioned problem is considered and a new mathematical formulation with O(n2) the number of decision variables and O(n2) the number of constraints is presented. The performances of the formulations are compared with the original and the recent ones from the literature. As a result, it is concluded that our proposed formulations are much superior to the existing ones regarding the number of optimal values obtained in a limited time and the run times. Since large-sized problems cannot be solved with mathematical formulation in a reasonable time, a variable neighborhood search based simulated annealing algorithm is developed to solve these problems approximately. The effectiveness of the heuristic algorithm is tested by means of the mathematical formulation. It is colcluded that the heuristic algorithm yields better solutions in quite shorter time as the problem structure gets harder.
Spor kulüplerinde maç öncesi takım kurma problemi için yeni karar modelleri: Voleybol kulubü uygulaması
(Başkent Üniversitesi Fen Bilimleri Enstitüsü, 2017) Budak, Gerçek; Kara, İmdat
Spor kulüplerinde maç öncesi takım kurma problemi, antrenörün maçı kazanmak için kadroda yer alan oyuncuların içerisinden sahada konumlandırılmış mevkilere oyuncu atama problemidir. Son yıllarda, hızla büyüyen spor endüstrisinde, takım kurma problemleri ekonomik ve sportif başarı yönüyle büyük bir önem kazanmıştır. Oyuncu sayısının ve teknolojik gelişmelerin getirdiği veri kaydı ve veri elde edilebilirliğinin artmasından dolayı, antrenörler nicel ve nitel yığınla bilgiyi bir arada değerlendirmek zorunda kalmaktadırlar. Bu sebeplerden ötürü takım kurma problemleri üzerinde yapılan bilimsel çalışmaların sayısında son yıllarda artış olmuştur. Bu tez çalışmasında, ilkin spor kulüplerinde takım kurma problemi ile ilgili çalışmalar ayrıntılı bir şekilde incelenerek irdelenip, farklı bakış açıları ve yaklaşımların gereği ortaya konmuştur. Daha sonra, sistem yaklaşımı ile paydaşları göz önüne alarak, antrenörlerin takım kurma kararında kendisine destek olacak 4 farklı karar modeli geliştirilerek, bu modellerin hangi durumlarda nasıl kullanılacağı belirtilmiştir. İlk model, tartılı toplam performansların en büyüklendiği, ikinci model ise antrenörün performans beklentilerini hedef değerler olarak ele alıp, buna bağlı şekillenen hedef programlama modelleridir. Üçüncü model takım ve oyuncu uyumunun en büyüklendiği; son model ise performansın ve uyumun iki ölçüt olarak ele alındığı modeldir. Önerilen karar modellerinin gerçek hayat problemlerinde kullanılabilirliği için modellere ait parametrelerin bulunması, elde edilmesi veya tahmin edilmesi gerekmektedir. Belirtilen amaçlarla, kullanılabilir yöntemler ve model kullanıcılarının hangi durumlarda hangi yöntemi seçmesi gerektiği genel çerçevede sunulmuştur. Geliştirilen modellerin gerçek hayat problemlerinde nasıl uygulanabileceğini örneklemek için önerilen yaklaşım, Ankara’da yer alan ve Türkiye Erkekler 1. liginde mücadele eden bir voleybol kulübünde uygulanmıştır. Uygulama öncesi model parametrelerinin nicel değerleri tahmin edilip, karar vericinin belirlediği değerlerde göz önüne alınarak, modeller CPLEX 12.6.0.0 versiyonuyla çözdürülmüştür. Modellerin çözümleri arasındaki ilişkiler ve karar vericinin öncelikleri ve beklentileri doğrultusunda anlamlı ve uygulanabilir sonuçlar verdiği gözlemlenmiştir. Tezde, uygulamada model sonuçlarının anlamları, çözüm sonrası analizler ve antrenörün bunları nasıl kullanabileceğine yer verilmiştir. Team formation problem for sports clubs before the match stage is a player assignment problem that coach assigns the players among the squat to the identified in-field positions to win the match. In recent years, in the rapidly growing sports industry, team building problems have gained great importance for economic and sporting success. Because of the increase in the number of players and the increased availability of data and data provided by technological developments, coaches are forced to evaluate huge amount of quantitative and qualitative information. For these reasons, the number of scientific studies on team forming problems has increased in recent years. In this thesis, firstly, the studies related with team formation problem for sports clubs are analyzed in detail and the need for new points of view and approaches are addressed. Then, regarding the systems approach 4 different decision models are developed to give aid to the coach on the team forming decision and how to use these models are pointed out. The first model is the one that maximizes the weighted total performance and the second model is the goal programming models that take the performance expectancies of the coach as target values. The third model maximizes the team and player harmony and the last model is a multi-objective model of performance and harmony. Proposed decision models’ parameters must be found, forecasted or obtained for the usability of the models in real life problems. With the stated purposes, the available techniques are presented for the model users in general sense. Then a guideway for which technique must be used under which circumstances is outlined. In order to illustrate how the proposed models can be used in real life problems, the proposed approach is applied to a volleyball club in Ankara which is competing in the men's league. To do this, we first predicted and determined relevant parameters of the models and then the models are solved by using CPLEX 12.6.0.0 version. It has been observed that the models give meaningful and applicable results in relation to the solutions and the decision maker's priorities and expectations. The implications of model results, post-optimality analysis and how the coach can use them are also included in the application.
Yöneylem araştırmasının yöntembilimi
(1985) Kara, İmdat
Zaman pencereli tamirci problemi ve uzantılarının yeni matematiksel modelleri
(Başkent Üniversitesi Fen Bilimleri Enstitüsü, 2021) Uzun, Gözde Önder; Kara, İmdat
Tamirci Problemi (TP) rotalama problemlerinin temelini oluşturan Gezgin Satıcı Probleminin (GSP) bir türüdür. TP müşteri memnuniyetini esas alıp, tüm müşterilerin toplam gecikme zamanını enküçük yapmayı amaçlar. TP, başlangıç düğümünden yola çıkan bir tamircinin, tüm müşterilere hizmet verdikten sonra başlangıç noktasında veya verilen bir düğümde sona eren, toplam gecikmeyi enküçükleyen Hamilton turunu veya yolunu bulmaktır. Tez kapsamında, TP’nin gerçek hayat uygulamalarında en çok karşılaşılan, zaman pencereli TP (ZPTP), çok gezginli zaman pencereli TP (ÇZPTP) ve çok depolu zaman pencereli TP (DZPTP) uzantıları ele alınmıştır. Öncelikle, ZPTP için kaynaklarda var olan iki matematiksel model incelenerek, ZPTP için polinom sayıda kısıta ve karar değişkenine sahip dört yeni matematiksel model geliştirilmiştir. Yapılan sayısal analizler sonucunda, geliştirilen matematiksel modellerden iki tanesinin performansının, CPU süreleri ve sapma oranları yönüyle, diğerlerine göre çok üstün olduğu görülmüştür. Ardından, ÇZPTP ele alınarak, yapılan kaynak araştırması sonucunda homojen ve heterojen durum için toplam iki matematiksel model bulunmuştur. Tez kapsamında homojen ÇZPTP için düğüm tabanlı ve ayrıt tabanlı olmak üzere iki adet ve heterojen ÇZPTP için düğüm tabanlı ve ayrıt tabanlı olmak üzere iki adet, polinom sayıda kısıta ve karar değişkenine sahip matematiksel model geliştirilmiştir. Kaynaklarda var olan modeller ve geliştirilen yeni modeller farklı tamirci sayıları ele alınarak, karşılaştırma problemlerinin çözüm için gerekli CPU süreleri ve sapma oranları yönüyle incelenmiştir. Sayısal analizler sonucunda, düğüm tabanlı modellerin hem homojen hem heterojen durum için üstün performans gösterdiği görülmüştür. Çalışmanın bu aşamasından sonra DZPTP üzerine odaklanılmış ve kaynak araştırması yapıldığında bu alanda hiçbir çalışma olmadığı anlaşılmıştır. DZPTP için gerçek hayatta karşılaşılabilecek beş farklı duruma yönelik matematiksel modeller geliştirilmiştir. Kaynaklardaki test problemleri çözülerek yapılan sayısal analizlerde, bazı problemler için tamirci sayılarında artış yapılarak eniyi çözümler elde edilebilmiştir ve modellerin performansları problemlerin çözümleri için geçerli olan CPU süreleri ve sapma oranları yönüyle değerlendirilmiştir. Büyük boyutlu problemlerin az tamirci sayısı ile süre sınırı içerisinde eniyi çözümlerine erişilemediğinden dolayı metasezgisel bir algoritma olan Biyocoğrafya Tabanlı Eniyileme (BTE) algoritması geliştirilmiştir. BTE algoritmasının parametre değerleri deney tasarımı yapılarak belirlenmiştir. Sayısal analizler ile algoritmanın etkinliği incelenmiş ve bu aşamada eniyi değerden sapma oranı, değişim katsayısı ve çözüm zamanı ölçütleri temel alınmıştır. BTE algoritması ile büyük boyutlu problemler için kabul edilebilir zamanda yüksek kaliteli çözümler elde edilmiş ve algoritmanın üstün başarı gösterdiği görülmüştür. Bu çalışmanın en önemli sonuçları ZPTP, ÇZPTP ve DZPTP için önerilen yeni matematiksel modellerin ve DZPTP için geliştirilen metasezgisel algoritmanın bilime katkı olarak sunulmasıdır. The Traveling Repairman Problem (TRP) is a variant of the Traveling Salesman Problem (TSP) which is the basis of the routing problems. TRP is based on customer satisfaction and aims to minimize total delay time of customers. TRP involves finding a Hamiltonian tour or path starting from an initial node, after visiting all customers, it ends at the starting or any given node in such a way that, total delay time is minimized. In this study, TRP with time windows (TRPTW), multiple traveler TRPTW (kTRPTW) and multi depot TRPTW (DTRPTW) are considered. Firstly, we observe that there exist only two mathematical models for TRPTW and four new mathematical models with polynomial number of constraints and decision variables are developed. Benchmark problems are solved by existing and new models for TRPTW and CPU times and deviation rates are analyzed. We conclude that two of the new mathematical models are superior to the others. Then, for kTRPTW, two mathematical models are found for homogeneous and heterogeneous case in the literature. Two new mathematical models which are node-based and arc-based with polynomial number of constraints and decision variables are developed for homogeneous and heterogeneous kTRPTW. The performances of the existing and new models for kTRPTW are compared by using benchmark problems in terms of CPU times and deviation rates with different number of repairmen. As a result of computational analysis, we observe that, the node-based models show superior performance for both cases. Lastly, it is focused on DTRPTW and we could not find any study for DTRPTW in the literature. Five mathematical models with polynomial number of constraints and decision variables are proposed for various types of the DTRPTW. The performances of new formulations are analyzed in terms of CPU times and deviation rates for solving problems. Since the optimal solutions cannot be reached with mathematical formulation by using small number of repairmen for some large-sized problems in a reasonable time, a metaheuristic algorithm named as Biogeography-Based Optimization (BBO) is developed to solve them approximately. The parameter values of BBO algorithm are estimated by experimental design. The efficiency of the algorithm is evaluated by using deviation rate from the optimal value, coefficient of variation and solution time. The proposed metaheuristic algorithm represents a high performance to find good quality solutions within acceptable CPU times for large-size problems. The main contribution of this study is to present new mathematical models for TRPTW, kTRPTW, DTRPTW and the metaheuristic algorithm for DTRPTW.