Geri Dön

Karınca kolonisi optimizasyonu ve genetik algoritma tabanlı tramp gemi rotalama ve çizelgeleme

Ant colony optimization and genetic algorithm based tramp ship routing and scheduling

PDF İndir

  1. Tez No: 675019
  2. Yazar: SEHER SUENDAM ARICI
  3. Danışmanlar: DOÇ. DR. EMRE AKYÜZ
  4. Tez Türü: Yüksek Lisans
  5. Konular: Denizcilik, Marine
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2021
  8. Dil: Türkçe
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Lisansüstü Eğitim Enstitüsü
  11. Ana Bilim Dalı: Deniz Ulaştırma Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Deniz Ulaştırma Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: 151

Özet

Deniz yolu taşımacılığı, büyük hacimli yüklerin, uzak mesafelere ulaştırılma imkânı sağlaması, güvenli bir taşıma şekli olması ve diğer taşıma türleri ile karşılaştırıldığında daha uygun olması gibi nedenlerle ticarette en çok tercih edilen taşıma şeklidir. Deniz yolu taşımacılığı, gemilerin sefer düzenleri açısından düzenli (liner) ve düzensiz (tramp) deniz taşımacılığı olarak ikiye ayrılır. Düzenli hat deniz taşımacılığında gemilerin izleyecekleri rotalar ve bu rotalara ait zaman çizelgelemeleri önceden bilinir. Bu taşımacılık şeklinde önemli olan hizmetin devamlı olmasıdır. Gemilerin söz konusu seferleri yapması için tam dolu olmaları gerekmez ve programı aksatmamak için seferi gerçekleştirirler. Tramp taşımacılık modunda, gemilerin gidecekleri rotalar ve taşıyacakları yükler değişkenlik göstermektedir. Bu taşıma tipinde gemiler düzenli bir rotaya sahip değildirler ve taşıyacakları yükleri çoğunlukla seferden sefere bulurlar. Seferler belirli bir çizelgeye göre yapılmadığından ve gemiler karlı yük bulunan noktalara hareket ettiğinden tramp taşımacılık rekabet esaslıdır. Bu nedenle, birden çok gemisi bulunan bir filoda, gemiler tarafından hizmet verilecek kontratların, kontratlar için belirlenen zaman aralıkları içerisinde, söz konusu gemiler arasında uygun şekilde paylaştırılması önemli hale gelmektedir. Özellikle yakıt tüketiminin hız ve gidilen mesafe ile ilişkisi düşünüldüğünde, rota ve hızın optimizasyonu büyük önem içermektedir. Gemi rotalama ve çizelgeleme problemleri, araç rotalama problemlerinin deniz yolu taşımacılığına uyarlanmış halidir. Çok bilinmezli, çok değişkenli ve karmaşık bir yapıya sahip olan büyük boyutlu problemlerdir. Bu problem tipi, çok fazla kısıt, hizmet edilmesi gereken birçok müşteri, birbiriyle uyumsuz olan amaçlar barındırmaktadır ve yapısı itibari ile NP-hard problemlerdir. Bu tez çalışmasında, tramp deniz taşımacılığı yapan bir gemi filosunun zaman pencereli, çok depolu ve çok araçlı rotalama ve çizelgeleme problemi incelenmiştir. Çözülen problemin amacı; taşınacak her bir yük için oluşturulan kontratlara ve bu kontratlarda belirlenen zaman kısıtlamalarına bağlı kalarak, mevcut olan her bir sözleşmeye hizmet ederken toplam operasyonel maliyeti minimuma indirmektir. Bu aşamada, her bir gemi için limana varış, limandan kalkış ve bekleme zamanları probleme dahil edilmiştir. Problemde kapasite kısıtının göz ardı edilebilmesi için tüm gemilerin aynı tip (cape-size) olduğu kabul edilmiş ve tüm gemilerin uygun zaman ve konumda olduğu sürece, tüm kontratlara hizmet götürebileceği varsayılmıştır. Ayrıca, probleme heterojenlik katmak için gemilerin hızları ve belirtilen hızlardaki yakıt harcamaları farklılaştırılmıştır. Metodolojinin en önemli özelliği, kargo toplama ve teslim etme zaman pencerelerinin ayrıklaştırılmasıdır. Bu özellik, modele çok çeşitli değişken ve kısıtın dahil edilmesi imkanı vermektedir. Çalışmada, deniz taşımacılığında temel işletme maliyeti olan yakıt tüketimini kontrol etmek için seyir hızının ve gemiler arası optimum yük dağılımının etkisinin ölçümüne odaklanılmıştır. Problem, taşımacılık tipinin çalışma sistemi göz önünde alınarak, karma tam sayılı doğrusal programlama modeli olarak oluşturulmuştur. Veri toplama aşamasında, gemilerin yakıt tüketimlerine, seyir sürelerine, balastlı ya da yüklü seyir yapmalarına bağlı kalınarak gerçekçi veriler oluşturulmuştur. Varış-kalkış zaman pencerelerinin probleme dahil edilmesi ile gemiler için maliyet matrisleri oluşturulmuştur. NP-hard problemlerin çözümünde kesin çözüm yöntemleri ve sezgisel yöntemler kullanılabilmektedir. Kesin çözüm yöntemleri problem çözümünde optimum sonuçları vermektedir. Ancak, kesin çözüm yöntemlerinin çözüm kalitesi problem hacmi ile ters orantılıdır. Sezgisel yöntemler ise en iyi çözümü garanti etmez ancak büyük problem hacimleri için en iyiye yakın çözümleri makul çözüm sürelerinde verirler. Bu amaçla çalışmada, gemi sayıları ve kontrat sayıları gibi değişkenler arttırılarak farklı problem hacimleri oluşturulmuştur. Oluşturulan problemler öncelikle doğrusal programlama da Gurobi çözücüsü ile çözülmüştür. Ardından, kullanılan hibrit yöntemin karşılaştırılmasının yapılabilmesi amacıyla, model Genetik Algoritma ve Karınca Kolonisi Optimizasyonu Algoritmasının birlikte kullanıldığı hibrit meta-sezgisel yaklaşım ile çözülmüştür ve sonuçlar karşılaştırılmıştır. Sonuçlar göstermiştir ki, her iki yöntem maliyet hesaplaması açısından birbirine çok yakın değerler vermektedir. Ancak, problem hacminin büyümesi ile kesin çözüm yöntemlerinde optimum sonucu alma süresi artarken, hibrit yöntem, problemin hacmi ve karmaşıklığı arttıkça daha iyi çözüm süreleri vermektedir.

Özet (Çeviri)

Maritime transportation is the most preferred mode of transportation in trade, as it allows large volumes of cargo to be transported over long distances, is a safe mode of transportation, and is cheaper than other types of transportation. Factors such as developments in maritime transport, variability in freight prices, unstable costs, closed financing structure of the maritime sector, and international operation of ships make maritime transport a highly sensitive and competitive sector. Increasing of customer expectations day by day has started to move the maritime industry away from the concept of transportation.The changing direction of customer demands also increases the importance of correct planning for maritime companies. In this sector, which has large capital investments and high operating costs, companies aim to gain economic benefits by managing their existing fleets in the most efficient way. There are many cost factors in the maritime industry. Some of these costs can be minimized with proper planning. In this sense, optimization of operational costs based on the operation of ships becomes important. Optimization of fuel consumption, which is a function of speed and the route traveled, has an important place in reducing operational costs. Maritime transportation is divided into two parts as liner shipping and tramp shipping in terms of the voyage patterns of the vessels. In liner maritime transport, the routes that the ships will follow and the time schedules for these routes are known in advance.The important thing for this mode of transportation is the continuity of the service.Ships do not need to be fully loaded to carry out their voyages.The vessels have programs and they make the voyage in order not to interrupt the program. Container and Ro-Ro (Roll on Roll of) vessels are the ship types that are frequently used in liner transportation. Tramp transportation is a mode of maritime transport where the routes of vessels and the cargoes they carry are not stable. The voyage routes of the ships vary according to the market conditions. In this type of transport, ships often find their cargo from voyage to voyage. Tramp transportation is based on competition. Because the voyages are not predetermined and the ships move towards the ports where the cargoes will provide profit to the companies. Therefore, in a fleet with more than one ship, it becomes important to distribute the contracts to be served by the vessels appropriately among the specified vessels, within the time intervals determined for the contracts. Especially considering the relationship between fuel consumption and speed and distance traveled, optimization of route and speed is of great importance.Ship routing and scheduling problems are the adaptation of vehicle routing problems to maritime transport. The most important point that distinguishes ship routing problems from vehicle routing problems is that there are many additional constraints in the application phase. Ship capacities, ship dimensions, ship drafts, ship-port compatibility, compatibility of transported cargoes, time windows required for receiving and delivering cargo are examples of these constraints. These problems are large-scale problems with many unknowns, many variables and a complex structure. These types of problems have a lot of constraints, a lot of customers that need to be served, goals that are incompatible with each other. Ship routing and scheduling problems are NP-hard problems that are difficult to solve. In this thesis, the multi-vehicle and multi-depot routing and scheduling problem of a fleet of vessels operating as tramp is investigated with time windows. The purpose of solving the problem is to serve each existing contract and to minimize the total operational cost, taking into account the contracts created for each cargo to be transported and the time constraints determined in these contracts. At this stage, arrival, departure and waiting times for each ship are integrated into the problem. In order to ignore the capacity constraint in the problem, it is assumed that all ships have the same deadweight (cape-size) and it is assumed that all ships can serve all contracts as long as they are at the appropriate time and location. In addition, to add heterogeneity to the problem, the speeds of the ships and the fuel consumption at the specified speeds are differentiated. The most important characteristic of the model is discretization of cargo picking and delivery time windows. For each contract, there are 3 time windows in which the cargoes will be received and 3 time windows in which they will be delivered. This feature ensures that different costs are included in the calculation according to the early or late arrival of the ships to the port. It also allows the inclusion of a wide variety of variables and constraints in the model. The thesis focuses on measuring the effect of cruising speed and contract distribution optimization between ships to control fuel consumption, which is the main operating cost in maritime transportation. The problem was created as a mixed integer linear programming model, taking into account the operating system of the transportation mode. During the data collection phase, the fuel consumption of the ships, voyage times, ballast or loaded voyages were taken into consideration. Realistic data were obtained. By including the arrival-departure time windows in the problem, cost matrices for the ships were created. First of all, the distances between all ports were calculated and contract-to-contract transition matrices were prepared as much as the number of contracts in order to track the contract transitions of the ships. Contracts to be serviced are listed with priority on expiry dates. The time interval for each carriage contract to be serviced was accepted as 20 days and during this period, unsuitable ships were prevented from receiving cargo.While calculating the cost, the value of the distances between the ports in terms of time, the daily fuel expenditures of the ships at the determined speed and condition (empty/full) were used. The regions where the ships operate are ignored and the price of IFO380 per ton is calculated as 540 dollars. As experimental factors; number of contracts, time window level, number of vessels and speed variations are used. Exact solution methods and heuristic methods can be used in solving NP-hard problems. This solution methods give optimum results in problem solving.However, the solution quality of exact solution methods is inversely proportional to the problem volume. As the size of the problem increases, the solution time also increases exponentially according to the size of the problem and sometimes a solution cannot be produced. Heuristic methods do not guarantee the best solution, but for large problem volumes they give near-best solutions in reasonable solution times.There may be several situations that require the use of heuristic algorithms in problems. The first case is that the problem cannot be solved by exact solution techniques.In such a case, the only option is to solve the problem with heuristic methods.The second reason is that exact solution methods take a very long time to solve large volume problems. In the thesis, different problem volumes were created by increasing the variables such as the number of ships and the number of contracts.The problems created were firstly solved in linear programming with Gurobi solver. Then, the problem is solved with a hybrid method in which Genetic Algorithm and Ant Colony Optimization Algorithm are used together. In the hybrid method, routes are created with the Ant Colony Algorithm. Then, the created routes are improved with operators such as crossover, mutation, elitism in the Genetic Algorithm stage. Thus, the solutions approach the best. At the end of the application, the results of the linear programming and the hybrid method were compared. The results showed that both methods give very close values in terms of cost calculation. However, since the ship routing problem is an NP-hard problem, the time to get the optimum result in exact solution methods increases with the increase in the problem volume, while the hybrid method gives better solution times as the volume and complexity of the problem increase.

Benzer Tezler

  1. Tez No

    328328

    Modeling and solving mixed-model assembly line balancing problem with setups

    Karma modelli montaj hattı dengeleme probleminin hazırlık zamanları ile modellenmesi ve çözülmesi

    ŞENER AKPINAR

    Doktora

    İngilizce

    İngilizce

    2013

    Endüstri ve Endüstri MühendisliğiDokuz Eylül Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. ADİL BAYKASOĞLU

  2. Tez No

    765699

    Kablosuz algılayıcı ağlarda küme başı seçiminde sezgisel algoritmaların performanslarının değerlendirilmesi

    Intuitive cluster head selection in wireless sensor networks evaluation of the performance of algorithms

    ABDÜLBAKİ DEMİREL

    Yüksek Lisans

    Türkçe

    Türkçe

    2022

    Bilim ve TeknolojiMuğla Sıtkı Koçman Üniversitesi

    Bilişim Sistemleri Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ GÜRCAN ÇETİN

  3. Tez No

    275194

    Bakteriyel besin arama optimizasyonu algoritması ile montaj hattı dengeleme

    Assembly line balancing by bacterial foraging optimization algorithm

    YAKUP ATASAGUN

    Yüksek Lisans

    Türkçe

    Türkçe

    2010

    Endüstri ve Endüstri MühendisliğiSelçuk Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. YAKUP KARA

  4. Tez No

    178014

    PID kontrolörün karınca kolonisi / genetik algoritma tabanlı optimizasyonu ve Gunt RT 532 basınç prosesinin kontrolü

    Optimization of PID controller using ant colony / genetic algorithms and control of the Gunt RT 532 pressure process

    MUHAMMET ÜNAL

    Yüksek Lisans

    Türkçe

    Türkçe

    2008

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara Üniversitesi

    Elektronik-Bilgisayar Eğitimi Ana Bilim Dalı

    YRD. DOÇ. HASAN ERDAL

    YRD. DOÇ. VEDAT TOPUZ

  5. Tez No

    877474

    Kötü amaçlı android tabanlı yazılım tespitinin güncel meta-sezgisel algoritmalar ile karşılaştırmalı analizi

    Comparative analysis of malicious android based software detection with recent metaheuristic algorithms

    MEHMET ŞİRİN BEŞTAŞ

    Yüksek Lisans

    Türkçe

    Türkçe

    2024

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSiirt Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ ÖZLEM BATUR DİNLER

Geri Dön