Afet lojistiğinde araç rotalama problemi ve geliştirilen iki aşamalı bir optimizasyon yöntemi ile uygulama
Vehicle routing problem and a case study with evolved a two level optimization solution in humanitarian logistics
Yazar: MUSTAFA BAL
Danışman: PROF. DR. HÜSEYİN MURAT ÇELİK
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Şehir ve Bölge Planlama Ana Bilim Dalı / Bölge Planlama Bilim Dalı
Derece: Yüksek Lisans, 2020
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering ; Şehircilik ve Bölge Planlama = Urban and Regional Planning

Özet:
Günümüzde mal, hizmet veya insanların bir noktadan başka bir noktaya ulaştırılması faaliyetlerine dahil olan binlerce kuruluş bulunmaktadır. Çağımızın dinamik koşullarından dolayı kuruluşların hedefleri ve kısıtlamaları oldukça değişkendir. Bu kapsamda organizasyonların en çok karşılaştıkları sorunlardan biri de araçların hizmet noktalarına dağıtımı, ulaştırma ve lojistik gibi faaliyetlerinin doğru şekilde yapılamamasıdır. Bu kuruluşlardan biri de acil yardım durumlarında (afet vb. olaylar sonrası yardım hizmetleri) ulaştırma hizmeti veren organizasyonlardır. Bu faaliyetler için tahsis edilmiş araçların bahsedilen konuları gerçekleştirmek için bir rota üzerinden faaliyete geçtikleri andan bu rotayı tamamlama anına kadar geçen aradaki süre düşünülünce harcanan süre miktarı, oluşan maliyetler ile harcamalar ve bu hizmet sonunda elde edilecek fayda bu organizasyonlar için de geçerliliğini korumaktadır. Ulaştırma konusunda rota planları ve rotalama faaliyetleri tüm organizasyonlarda olduğu gibi acil durum hizmetleri (ambulans, kurtarma araçları gibi) kapsamında faaliyet gösteren organizasyonlar için de önemlidir. Afetlerin yol açtığı sonuçlar düşünüldüğünde ulaştırma konusundaki her türlü fayda organizasyonel başarıları artıracağı gibi toplumun da faydasını artırır. Toplumsal fayda aynı zamanda sosyal faydadır. Afetlerin ölümcül etkisini en aza indirme ve afet sonrası iyileştirme ile rehabilite çalışmaları ile sosyal fayda maksimize edilebilmektedir. Bunun için ulaştırma sistemlerinde yer alan her bir aracın afet bölgelerine en kısa sürede ulaşması oldukça mühimdir. Bu önem literatürde de ilk 72 saatlik zaman dilimi içerisinde yardımı ulaştırma şeklinde belirtilmiştir. Aynı şekilde deprem gibi yıkım gücü çok yüksek afetlerde ise ilk 12 saatte yardım hizmetlerinin ulaşması elzem bir konudur. Bu sebeplerden ötürü afet lojistiği için araç rotalarından oluşan bir ulaşım ağ planı oldukça önemlidir. Ulaştırma sisteminde yapılan planlamalar birer çizelgeleme örneğidir ve bu çizelgelemeler de rotalama ile özdeşlik göstererek konunun tamamlayıcısı haline gelmektedir. Araçların optimum rotalara sahip bir ağ içinde hareket etmesini sağlayacak planlama faaliyeti her sistem için uygulama alanı bulabilecek bir konudur ve bu özelliği ile sahip olduğu amaçlarda da çeşitlilik görülebilmektedir. Araç rotalama başlığı altında ulaşılmak istenen amaçlar çeşitlilik göstermektedir ve bunlardan bazıları, yolda harcanan sürenin minimum olması, maksimum müşteriye ulaşabilme, minimum maliyeti sağlama, maksimum karı elde etme ve minimum riske sahip yolların kullanılması gibidir. Bu amaçlar zaman içinde çeşitlenmiş ve daha detaylı hale gelmiştir. Araç rotalama ilk olarak Hamilton'un Halka Teorisi temelli ortaya çıkan gezgin satıcı problemi ile açıklanmaya çalışılmıştır. Zaman içerisinde de tır taşıma problemi olarak şekillenmiş ve günümüze araç rotalama problemi olarak ulaşmıştır. İlk ortaya çıktığında tüm müşterilere rota boyunca en fazla bir kere uğrayarak ulaşım ve ulaştırma hizmeti yükleme-boşaltma faaliyetlerine çözüm aramaya çalışmış ve günümüze kadar bu konu çeşitli sınıflandırmalarla daha detaylı hale gelmiştir. Son yıllarda ise afet sonrası yardım hizmetlerinde (afet lojistiğinde) detaylı araç rotalama çalışmaları kullanılarak çok sayıda başarılı rotalama faaliyetleri oluşturulmuştur. Bunların ışığında literatüre bakıldığında araç rotalama probleminin 12904 kere çalışıldığı görülmektedir. Bununla beraber afet lojistiği kapsamında bahsedilen araç rotalama faaliyeti için literatürde 109 adet çalışmanın mevcut olduğu da fark edilmiştir. Bölge planlama biliminin ulaştırma konusu çatısı altında mevcut olan bu iki ortak alt başlık incelendiğinde ikisinin keşişim noktası olarak ağ analizi, tez çalışmasına ışık tutan nokta olmuştur. Bu tez çalışması afet sonrası yardım hizmetleri için başarılı ulaşım ve ulaştırma ağı ortaya çıkarmayı hedeflemektedir. Aynı zamanda bir başka hedef ise, toplumda büyük yaralar açan afetlerin negatif dışsallığını minimum noktaya çekmeye çalışacak bir çalışma ortaya koymak olmuştur ve bu hedefi niceliksel yöntemlerle uygulamaya dökme mümkün kılınmaya çalışılmıştır. 
Afet lojistiğinde önemli kavramlardan biri de afetten sonra, kısa bir süre içinde afet bölgesine ulaşımın sağlanmasıdır. Afet lojistiği afetlere hazırlıklı olmak için alınan önlem olarak veya afet sonrası iyileştirme çalışması şeklinde iki temel amaçtan oluşmaktadır. Afet sonrası iyileştirme ve yardım çalışmaları daha hayati bir öneme sahiptir ve bu sebeple doğru yönlendirilmiş bir ulaşım ağı gereklidir. Afet lojistiğinde oluşturulan ulaşım ağı en az risk değerine sahip en kısa seyehat süreli araç rotalarından oluşmalıdır. En kısa ve en az süreli yollardan oluşan bir ağ analizi yapılmasında başka bir önemli husus da ağın taşıdığı risk değerinin minimum seviyede olmasıdır. Afet lojistiği kapsamında yapılacak uygulama ile optimum araç rotalarının oluşturulması faaliyetleri ile en kısa ve minimum riskli yolları bulma çalışması yapılacaktır. Bu sayede afet senaryolarındaki en kritik husus olan anında veya kısa sürede hizmeti istem sahiplerine sağlama konularına fayda sağlamaya çalışılacaktır. Afet durumları için uygulanabilecek bir konu olan araç rotalama problemlerinde Hazmat Ulaştırma Problemleri literatürden faydalanılarak bir optimizasyon çalışması yapılacaktır. Optimizasyon yöntemi olarak iki adımlı bir yöntem uygulanacaktır. İlk adımda en kısa rotalardan oluşan bir ağ tasarımı, ikinci adımda ise minimum risk değeri taşıyacak şekilde bir ağ için optimizasyon çalışması uygun görülmüştür. Hazmat Ulaştırma Problemlerinde diğer optimizasyon çalışmaları ise aşamalı optimizasyon ve fayda optimizasyonudur. İki aşamalı optimizasyonun iki aşamalıdan farklı olarak risk değerlendirmesini problemin bir kısıtı olarak kullanıp optimizasyonu tamamlamasıdır. Fayda optimizasyonu ise risk değerleri ve diğer kısıtlara atanan belli ağırlık dereceleri ile optimizasyonun yapılmasıdır. Çalışmada kullanılan iki adımlı optimizasyondaki ilk adımda uygulanacak optimizasyon için problem kümesinin karmaşıklığı arttıkça ve gerçek dünya problemleri ele alınmaya başladıkça, çözümlerinde bir o kadar zorlaştığı görülmektedir. Bu sebeple gerçek dünya problemlerinde klasik araç rotalama problemleri için daha kullanışlı çözümlere geçme gereği doğmuştur ve çözümler için birçok sezgisel algoritma oluşturulmuştur. Sezgisel algoritmalar özellik olarak esnek, hızlı ve kullanışlı bir yapıya sahiptir. Özellikleri ile karmaşık yapıya sahip araç rotalama problemleri için uygun çözüm yöntemleridir. 
İstanbul ili Avrupa yakası ilçelerine sağlanması düşünülen hizmetin uygulama ile optimize edilmesi amaç edinilerek çalışma tamamlanmaya çalışılacaktır. Bu konu çerçevesince söz konusu problemin büyüklüğü düşünüldüğünde sezgisel algoritmaların etkinliğinin daha yüksek olduğu bilinmektedir. Bu sebepten dolayı sezgisel algoritmalar içinden Karınca Koloni Optimizasyonu sezgiseli ile bahsedildiği gibi ilk adımın optimizasyonu için çözüm sağlanacaktır. Çalışma kapsamında Karınca Koloni Optimizasyonu meta-sezgiselinin seçimi ile alt algoritmalarının da nasıl olduğuna dair bilgilere yer verilmektedir. Bu bilgiler aynı zamanda algoritmanın ortaya çıkış sürecini, nasıl çalıştığını, gerekli bilgilerinin neler olduğu ve çözümün nasıl gerçekleşeceği gibi alt kırınımlarda incelenmiştir. Böylelikle araç rotalama optimizasyonu için ne derece uygun olduğu ortaya koyulmaya çalışarak ilk adım optimizasyonunun çözümü sağlanmıştır. 
Hata Ağacı Analizi ile risk analizi yapılarak ağın sahip olduğu risk değeri için minimizasyon çalışması da araç rotalamada yapılan ikinci adım optimizasyonunu oluşturmaktadır. Hata Ağacı Analizi, risk analizi çalışmalarında kullanılan bir yöntem olup kantitatif risk analizi için tercih edilen bir yöntemdir. Hata Ağacı Analizi ile belli risk olasılık değerlerine sahip alt elemanlar tespit edilerek, riski en aza indirmek için önlem alma çalışmaları mümkün olabilmektedir. Bu çalışma kapsamında da risk analizi için her rotadaki yolların risk olasıkları tespit edilerek bunların rota üzerindeki toplam risk değerleri hesaplanarak oluşturulan rota ağındaki risk minimizasyonuna geçiş yapılmıştır. 
Yapılan bu çalışma ile araç rotalama problemini tanımlayarak ne kadar detaylı olduğu konusunda sınıflandırmaları üzerinde durulmuş ve uygun bir algoritmayla çözüme geçilmesi düşünülmüştür. Çalışma kapsamında statik araç rotalama ana konu olarak ele alınmıştır. Çalışma afet lojistiği sistemine uygulanarak sistem içerisinde oluşabilecek değişikliklerin en iyiyi sağlaması, sistemin taşıdığı risk değerinin minimum düzeyde olması ve sistemin elde edeceği faydayı maksimum yapma amaçları hedeflenmiştir. Afet lojistiğinin temel kriterleri, kapsamı, ulaşım ağındaki yeri ve araç rotalama ile ilişkisi çalışmada ortaya koyularak elde edilmesi hedeflenen kriter için uygunluğu gösterilmeye çalışılmıştır. Bu hedef ile ulaşım sisteminin başarısı sağlanırken bölge düzeyinde ve büyük ölçekli perspektiften ulaşım sistemine de fayda sağlayacağı varsayılmıştır. Bu kapsamda afet sonrası hizmetlerinin olası afet bölgelerine ulaştırılması çalışmanın uygulama konusu olmak için kritik bir rol üstlenmektedir. Bu hedefi destekler nitelikte de "yapılan araç rotalama faaliyeti en kısa seyahat mesafelerini bulup seyahat süresini en aza indirerek afet sonrası mümkün olan en kısa sürede ve en az risk taşıyan yollardan hizmetin ulaştırılması ile afet lojistiğine fayda sağlayıcı faaliyet olacaktır" hipotezi test edilecektir. 
Sonuç olarak araç rotalama probleminin hassas ve tutarlı sonuçlar vermesi ile ulaştırma faaliyetlerine katkı sağlaması çalışmanın vizyonu olarak belirlenmiştir. Bunun yanı sıra hizmet almayı bekleyen istem bölgelerine en kısa mesafeden ve en az risk taşıyacak şekilde ulaşım sağlanması amaç edinilmiştir. Bu noktada amaç fonksiyonu olarak en kısa seyahat mesafesi ve en az risk değeri kullanılmıştır. Elde edilen kısa mesafeler daha kısa sürelerde hizmetle pekişir düşüncesiyle çalışma tamamlanacaktır. Bu kısa mesafelerinde güvenli yani riskinin düşük olması ise uygulama konusunun ehemmiyetine vurgu yapar nitelikte olması düşünülmüştür. Çalışmanın sonunda ise amaç fonksiyonları doğrultusunda optimum rota önerisine sahip bir ağ yapısı geliştirilip sunulacaktır. Bu rotaların da kötümser, iyimser ve olması muhtemel farklı senaryolar eşliğinde süre analizleri yapılacaktır. Bu şekilde de araç rotalama faaliyetinin sisteme olan katkısını görebilmek mümkün olacaktır. Önceki çalışmalarda önerilen zaman kısıtına uygunluğu da test edilmiş olacaktır. Gerçekleştirilen katkı ile de ortaya konulan hipotezi değerlendirme fırsatı bulunabilecektir.

Abstract:
Current days, there are thousands of organizations involved in the activities of delivering goods, services or people from one place to another. Due to the dynamic conditions of our era, the goals and constraints of organizations in practice are highly variable. In this context, one of the problems that organizations face most is that their activities such as vehicle distribution, service delivery, transportation and logistics cannot be done correctly. One of these organizations is the organizations that provide humanitarian logistics (relief servives after disasters). When considering the time elapsed from the start of the service period through a means to realize the issues enumerated for these activities, and the time taken until the moment of completing this route, the time spent, the costs, expenditures and the benefit to be obtained keep its importance. Transportation issues such as the plan of bus routes, distribution of taxis to customers, as well as emergency services (such as ambulance and rescue vehicles) can also be covered in this regard. Considering the consequences caused by disasters, all kinds of transportation benefits will increase organizational success as well as the benefit of the society. The benefit of the society is also a social benefit and is defined by minimizing the deadly impact of disasters and rehabilitation after disaster recovery. It is too crucial for each relief service vehicle in the transportation systems to reach disaster regions as soon as possible. This importance has been stated in the literature in the form of delivering relief for disaster regions within the first 72 hours. Similarly, in disasters with high destructive effect such as earthquakes, it is an essential issue that relief and rehabilitation services arrive in the first 12 hours. For these reasons, a transportation network plan consisting of vehicle routes for disaster logistics is an important part of transportation. In order to provide complete transportation system without any errors, every parts of it have not to been considered separate. For this reason, not only vehicle routing activities but also disaster logistics activities are important with relations of it with transportation systems. Routing activities contain scheduling and sequencing; therefore, activities are a complementary part of transportation because all transportation network needs scheduling and sequencing. Planning activities that enable the vehicles to move in a network with optimum routes is a subject that can find implementation areas for every system and with this feature, it shows diversity with its objectives. There are several objectives to be achieved under these issues, such as the minimum time spent on the road, reaching the maximum customer, providing the minimum cost, achieving maximum profit, and obtaining routes with minimum risk. These objectives have been diversified and more detailed over time. First of all, the problem of traveling salesman problem based on Hamilton's Cycle Theory has tried to explain this issue. Over time, the truck dispatching problem has been shaped as a transportation problem and has reached the present day as a vehicle routing problem. When it first appeared, it tried to find a solution to all transportation and transportation service loading-unloading activities by reaching the customers at most once throughout the route and to this day, this issue has become more detailed with various classifications. In recent years, many successful vehicle routing activities has been studied by using detailed vehicle routing studies at disaster logistics. In this scope, vehicle routing problem had been studied 12.904 times in time horizon till half of 2020, when literature is reviewed. In the literature, until half of 2020, there are also 109 vehicle routing studies with disaster logistics. When these two common subtitles, which are available under the scope of transportation of the regional planning science, are reviewed, network analysis which is intersection of the two become the point that light to this thesis. This study aims to successful network with routing for disaster logistics. Besides, another objective is to minimize negative externalities of disasters which have destructive effects at society, and quantitative methods have been used to reach this aim.
One of the important concepts in disaster logistics is to reach to the disaster regions within a short period of time. When vehicle routing problem is studied with prevention to be prepared for disasters or rehabilitation activities, routes have to have minimum risk and the shortest travel times. Another important issue in conducting a network analysis consisting of the shortest routes is the minimum risk value of the network. Two-step optimization will be applied at this vehicle routing problem for disaster logistics. At first step, optimization for the network with shortest routes and at second step, optimization for risk value is proper method. Generally, vehicle routing problems are solved with one steps with exact methos or heuristic methods. However, when risk values are considered for this study, Hazmat (Hazardous Material Transportation) problems are used to compute risk values and optimize route's risk. In Hazmat literature, two-level optimization, two-step optimization, and utility. At two-level optimization, objective function has risk variables and distance variable, and it solves them with together. At utility, risk values and other variables have importance weight. For this study, two-step optimization is used. It optimize routes firstly, and a route set which matches objective function are obtained with first step optimization. At second step, risk optimization is made to obtained sets. By this way, optimization terminates for mininum distances and risk values. So, in this study first step optimization will be optimized distances and there exist a route set which are the closest solutions to optimum solution. These are obtained by changing parameter in the model. Then risk optimization will be applied to routes to find the safest route.
At first optimization step in studies, solutions get difficult when complexity of problem increases; therefore, for real world problems, the need to go to beyond applying classic vehicle routing solution methods. Heuristic solution methods have been developed for real world problems. Basic properties of heuristic solution methods are flexible for many types of problems, time effective, and easy applicable. Due to basic properties of heuristic methods, they are the most suitable and effective methods for complex vehicle routing problems which reflect real world issues. Also, they can be adapted so many problem types. By this flexibility property, applying of technological development to heuristic method is easy. Another main property is time effectiveness, mentioned above, which provides to save time when comparing exact solution methods. It needs to speciy that heuristics have two main types which are meta-heuristics and normal heuristics. Meta-heuristics become spesical based on specisific problems. On the other hand, normal heuristics can be applied to many problem types by using its main rules.
With the application to be carried out within the scope of disaster logistics, to create optimum vehicle routes and to find the shortest and routes will be done. In addition, optimization provides to obtain routes which have minimum risk values. In this way, in disaster scenarios the most critical issue which provides to service to the regions instantly or in a short time will be solved.  This study will be completed with the aim of optimizing the service that is planned to be provided to the European side districts of Istanbul province. Effectiveness of heuristic algorithms are the higher than exact solution methods when this problem size considers in this concept. For this reason, optimization will be made with Ant Colony Optimization that is a meta-heuristic method (a type of heuristic methods). In this study, detailed information about principle of working and chosing of Ant Colony Optimization meta-heuristic is explained. Explanations contain historical perspective, working principles, necessities to solve problems, application areas of it, algorithm types of Ant Colony Optimization and solution methods of algorithms. Thus, the solution of the first step optimization was provided by trying to reveal how suitable it is for vehicle routing optimization. 
The second step in vehicle routing is optimization for the risk value of the network by performing risk analysis with Fault Tree Analysis. Fault Tree Analysis is a method used in risk analysis studies and is a preferred method for quantitative risk analysis. Risk analaysis can be divided into with respect to analysis methods. One of them is qualitative and the other is quantitative. Qualitative methods describes, defines, presents solution techniques, and summarizes risk analysis with all sides of risk. Quantitative methods calculates risk values with set risk propabilities, and it presents what will be risk effects with its risk values. Quantitative methods use several techniques to calculate risk. Fault Tree Analysis, Markovian Modelling and Event Tree Analysis are the most common techniques. In this thesis Fault Tree Analysis is selected technique to determine risk values in order to optimize route. With the Fault Tree Analysis, it is possible to determine the sub-elements with certain risk probability values and take measures to minimize the risk. Within the scope of this study, risk possibilities of roads in each route were determined and the risk minimization in the route network was created by calculating the total risk values of them on the route. In second optimization level of problem, risk values obtained form Fault Tree Analysis will be inputs of optimization algorithm.
At this study, vehicle routing problem is defined and tried to solve. In addition to definition of vehicle routing problem disaster, disaster logistics and main concept of post-disaster activities and relief operations are presented. Then, classifications of them are expained. After presentation of them main problem of thesis which is vehicle routing problem is considered. Static vehicle routing problem is thought as a main subtype of problem. By applying the study to the disaster logistics system, it is aimed to provide the best possible results in the system, to minimize the risk value of the system and to maximize the benefits that the system will obtain. At this study, it is tried to reveal consistency of aimed objectives by explaining basic rules, contents, place at transportation system, and relation with vehicle routing of disaster logistics. With mentioned objectives, it is assumed to benefit to trasportation system with large scale and regional perspective. Post-disaster service tranportation has a crucial role as implemantation area for vehicle routing activities at these perspectives. In order to support to objectives it needs to have a hypothesis like "vehicle routing activity will be beneficial activity for disaster logistics with routes have minimum delivery time and risk by providing the shortest travel distances and total travel times." This hypothesis will be tested when study had been finished. 
As a result, vision of study is to benefit to transportation activities with accurate and consistent results of vehicle routing problem. Also, it is aimed to be beneficial to regions are affected from disaster by delivering post-disaster services with routes which are the shortest and have minimum risk. At this point, objective functions of study are the shortest travel distance and minimum risk value. The study will be completed with the shortest travel time calculations by obtaining the shortest travel distances. However, the important point is that the shortest travel distance must have minimum risk value because of disaster logistics risky nature. To deliver relief service to regions, it needs to use safe road that means they must not have any dangerous. At the end of the study, a transportation network for disaster logistics in European side of Istanbul with optimum routes will be developed and presented by supporting objective functions. These routes also will be tested for time analysis with pessimistic, optimistic, and expected scenarios by computing of travel times with distance and speed limits of roads. It can be possible to observe contribution to transportation system with these three scenarios. Then, a comparison with former studies about time limit for delivering of service will be made at the end of the study. 
The aim of this comparison is to check if the travel times which are outputs of optimization, are less than 12 hours because this duration is a critical threshold for disaster logistics. Finally, hyposthesis of this thesis can be asserted with outputs of vehicle routing for disaster logistics.