Modeling static and dynamic dial-a-ride problem
Müşteri rotalama probleminin statik ve dinamik olarak modellenmesi
- Tez No: 538498
- Danışmanlar: DOÇ. DR. SANEM SARIEL
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: 93
Özet
Hızlı teslimat şirketlerinin, müşterilerin en hızlı ve en uygun fiyatlı hizmeti alma taleplerinin artmasına bağlı olarak son yıllarda önem kazandığı görülmektedir. Bahsi geçen, aynı günde sipariş teslimatı yapan şirketler, kullanıcılara en hızlı ve en ucuz teslimatın garantisini vermekle birlikte; müşteri memnuniyetini, teslimat sürecini ve toplam maliyeti optimize etmeyi amaçlamaktadırlar. Amaca yönelik olarak, bu şirketlerin birbirinden farklı konseptlerde hizmet sunduğu görülmektedir. Hızlı teslimat, hasta veya engelli kişilerin bir yerden bir yere ulaştırılması olabileceği gibi acil ihtiyaçların teslimatı da olabilmektedir. Buna göre, hasta veya engelli kişileri bir noktadan başka bir noktaya ulaştırmayı amaçlayan teslimat şirketleri ile sipariş edilen bir ürünün bir noktadan alınarak başka bir noktaya teslimatını amaçlayan şirketler arasında problemin modellenmesi açısından fark bulunmaktadır. Birinci durumdaki bir örnekte, randevu bir gün veya daha öncesinde oluşturulabilmekte, hatta bu servisi sağlayan şirketler en geç bir gün öncesinde randevunun oluşturulmuş olması şartını koyabilmektedirler. Bu durumda optimizasyonun yapılarak rotalamanın oluşturuldugu anda, tüm siparişler önceden biliniyor olmaktadır. İkinci durumda ise, siparişler acil ihtiyaçlara yönelik olduğundan, dinamik olarak çoğunlukla çevrimiçi bir arayüz aracılığı ile alınmakta ve siparişin oluşturulduğu andan belirli bir süre sonrasına kadar teslimatın tamamlanması gerekmektedir. Bu durumda tasarlanacak olan optimizasyon algoritmasının dinamik olarak gelen siparişleri karşılayacak ve anında çözümler üretebilecek bir algoritma olması gerekmektedir. Bu çalışma bir gerçek dünya problemini çözmek üzere yapılmış olup Kapgel adlı şirketin kullanımına yönelik müşterilerin rotalanması probleminin çözülmesi amaçlanmıştır. İstanbul'da kurulmuş olan bir şirket olan Kapgel, müşteriler tarafından bir mobil uygulama aracılığı ile alınan siparişlerin belirli bir noktadan alınarak müşterinin belirttiği başka bir noktaya teslimatını yapmaktadır. Siparişler çevrimiçi olarak alınmakta ve alındığı andan itibaren teslimat süreci başlamaktadır. Ürünlerin teslimatı şirkete ait olan araçlarla yapılmaktadır. Her aracın kendi rotasına sabit bir depo lokasyonundan başlayıp rotayı aynı lokasyonda tamamlaması gerekmektedir. Sipariş edilen ürünler öncelikle bir servis noktasından alınır ve sonra müşterinin belirlediği adrese teslim edilir. Şirket ürünlerin teslimatının 1 saat içerisinde sabit bir fiyata yaptığının garantisini vermektedir. Proje kapsamında, Kapgel için kuryelerin lojistik olarak siparişleri alıp dağıtabilmesini sağlayacak şekilde yönlendirilmesini gerçekleştirecek olan yazılımın geliştirilmesi hedeflendiğinden, çoklu araç rotalama problemleri incelenmiştir. İncelenen problemlerdeki kısıtlar ve Kapgel'in ihtiyaçları göz önüne alınarak, Müşteri Rotalama Problemi (Dial-a Ride Problem, DARP) model olarak kullanılmıştır. Müşteri rotalama probleminde (Dial-a-Ride Problem, DARP), kuryelerin siparişleri belirli bir başlangıç noktasından (pick-up noktası) belirli bir varış noktasına (drop-offnoktası) verilen bir zaman penceresi içerisinde taşıması formüle edilir. Amaç, tüm kısıtlar sağlanırken, araçlar için en düşük maliyetli rotaları bulan bir model tasarlamaktır. Problem, zaman penceresi kısıtı içerdiğinden dolayı Başlangıç ve Varış noktası olan Araç Rotalama Problemi'nin (Vehicle Routing Problem with Pick-up and Delivery, VRPPD) ve ayrıca Zaman Penceresi olan Gezgin Satıcı Problemi'nin (Traveling Salesman Problem with Time Window, TSPTW) genelleştirilmiş bir versiyonudur. Bu sebepten, NP-Hard bir problem olarak sınıflandırılır. Literatürde, müşteri rotalama probleminin farklı versiyonları üzerine çalışmalar yapıldığı görülmüştür. Bu çalışmada, çoklu-araç tek-objektif müşteri rotalama problemi (multi-vehicle single-objective DARP) ve çoklu-araç çoklu-objektif müşteri rotalama problemleri incelenmiştir. Çoklu-araç tek-objektif müşteri rotalama probleminde maliyet veya müşteri memnuniyeti gibi yalnız tek bir kriterin optimize edilmesi amaçlanır. Çoklu-araç çoklu-objektif müşteri rotalama probleminde ise maliyet, müşteri memnuniyeti, araç sayısı, sürüş süresi ihlali gibi birden çok kriterin içerildiği bir objektif fonksiyon optimize edilir. Bu çalışmada müşteri rotalama problemi, tüm kuryelerin siparişleri teslim etmek için katettiği mesafelerin toplamını ifade eden, maliyetleri optimize edilecek şekilde tek-objektif fonksiyonlu olarak ve maliyet ve müşteri memnuniyeti birlikte optimize edilecek şekilde çoklu-objektif fonksiyon kullanılarak iki ayrı şekilde formüle edilmiştir. Müşteri memnuniyeti, rota ve sipariş süresi ihlalleri baz alınarak hesaplanmıştır. Problem kısıtları; her aracın kendi rotasına baslangıç noktasından başlayıp rotayı baslangıç noktasında bitirmesi, siparişlerin ideal durumda bir saat içerisinde teslim edilmesi, tüm araçlar icin belirli bir maximum sürüş süresi uygulanması, her aracın bir kapasitesinin olması ve belirli bir sayıda aracın kullanılabilir olmasından oluşmaktadır. Bu tezin amacı, bir gerçek dünya sorununu çözmek olduğundan, müşteri rotalama problemi statik ve dinamik olmak üzere iki ayrı alt başlıkta incelenmiştir. Statik modellemede, rotalama için gerekli olan tüm veriler önceden bilinmektedir. Program, çalışma zamanı sırasında bölünemez ve yeni bir sipariş mevcut rotalamaya eklenemez. Dinamik modellemede ise, rotalama ilk siparişin gelmesi ile başlar ve peşisıra dinamik olarak yeni siparişlerin gelmesi ile devam eder. Program, çalışma zamanında yeni bir siparişin oluşturulması ile bölünür, sipariş mevcut kuryelerin durumuna göre herhangi bir kısıtı ihlal etmeyecek şekilde bir araca atanır ve rotalar tekrar optimize edilir. Statik müşteri rotalama problemi iki farklı yöntem ile incelenmiştir. Öncelikle, lineer programlama ile Karışık Tamsayı Programlama (Mixed Integer Programming) yöntemi kullanılmıştır. Bu yöntemde problem, çoklu-araç tek-objektif Müşteri Rotalama Problemi olarak formüle edilmiştir. İkinci olarak, problem çoklu-araç çoklu-objektif Müşteri Rotalama Problemi olarak formüle edilmiş ve sezgisel yöntemlerle problemin çözülmesi amaçlanmıştır. Bu amaçla, problem önce kümelere ayırma, sonra rotaların oluşturulması (cluster-first, route-second) yöntemi kullanılarak modellenmiştir. Kümelerin oluşturulması için genetik algoritma kullanılmış, oluşturulan kümelerin rotalanması için ise en yakın komşu algoritması kullanılmıştır. Dinamik müşteri rotalama problemini çözmek için öncelikle problemin dinamik yapısına uygun şekilde bir modelleme yapılmış ve mimari oluşturulmuştur. Dinamik modellemede en önemli faktör zaman olduğundan, zaman ile ilgili sorunları çözecek şekilde bir Olay Yöneticisi tasarlanmıştır. Dinamik olarak oluşturulan siparişlerin tespit edilebilmesi için zaman, Olay Yöneticisi tarafından 1 dakikalik aralıklara bölünmüştür. Her 1 dakikada yeni bir sipariş olup olmadığı kontrol edilmekte, yeni bir siparişin tespit edilmesi ile birlikte Karar Algoritması devreye girerek yeni siparişin atanacağı uygun bir aracı, mevcut atamaları bozmadan ve kısıtları ihlal etmeden bulmaya çalışmaktadır. Ekleme Algoritması ise yeni siparişin tüm araçlar için ve eğer boşta bekleyen araç var ise bu araç için maliyetini hesaplamaktadır. Maliyet hesabı Ekleme Algoritması tarafından, yeni sipariş ile teslimatta olan kuryelerin o andaki mevcut lokasyonları ve depoda beklemekte olan araçlara olan mesafelerin hesaplanması ile yapılır. En ucuz ekleme maliyetini sağlayan araca yeni siparişin ataması yapılır veya mevcutta depoda beklemede olan araç varsa ve yeni araç eklenmesi daha ucuz ise sisteme yeni bir araç eklenir. Yeni siparişin ataması yapıldıktan sonra, Optimizasyon Algoritması, değişiklik olan küme için optimum rotayı tekrar bulmak üzere, statik algoritmanın rotalama kısmında olduğu gibi, en yakın komşu algoritmasını kullanır. Tüm hesaplamaların yapılabilmesi ve yeni siparişlerin sisteme eklenebilmesi, kuryelerin mevcut lokasyonlarının ve mevcut zamanın bilinmesini gerektirdiğinden; lokasyon ve zaman bilgisi hafızada tutulur ve sürekli olarak ideal durumların yaşandığı ve kuryelerin herhangi bir dış etken tarafından müdahale edilmeden sabit bir hızla planlanmış rotalarında hareket ettiği varsayılarak, güncellenir. Statik ve dinamik müşteri rotalama algoritmaları, şirket tarafından temin edilen veri üzerinde test edilmiştir. İlgili veri 167 adet sipariş içermektedir ve tüm siparişler tek bir güne aittir. Statik problemi çözmek için kullanılan lineer programlama ve sezgisel yöntemler tarafından elde edilen sonuçlar, maliyet ve programın çalışma zamanı baz alınarak karşılaştırılmıştır. Karşılaştırma sonucunda lineer programlama ile elde edilen sonuçların en iyi maliyet sonucunu verdiği ancak belli bir müşteri sayısından büyük veri içeren örnekler için, kabul edilebilir bir süre zarfında verilen kaynaklar ile çözüm bulamadığı görülmüştür. Bu yöntem ile ancak 14 siparişe kadar olan veri için çözüm bulunabilmiştir. Sezgisel yöntemden elde edilen sonuçların ise maliyet bakımından lineer yönteme oldukça yakın sonuçları gerçek-dünya probleminin kabul edebileceği çalışma zamanında üretebildiği görülmüştür. Sezgisel yöntem, verilen tüm veri örnekleri için çözüm üretebilmiştir. Problem dinamik olarak ise başarılı bir şekilde modellenmiş, çevrimiçi olarak oluşturulan siparişler anında rotalamaya dahil edilerek optimize rotalar oluşturulmuştur. Geliştirilen model ve algoritma, oluşturulan tüm yeni siparişleri, mevcutta teslimat sürecinde olan siparişleri bozmadan ve kısıtları ihlal etmeden, sezgisel yöntemler kullanarak sisteme ekleyebilmiştir. Bu çalışmanın amacı, bir gerçek dünya problemine uygulanabilir çözümler üretmektir. Problemin kısıtları ve ilgili şirketin ihtiyaçları göz önüne alınarak, problem Müşteri Rotalama Problemi olarak modellenmiş, hedeflere ulaşabilmek amacıyla statik ve dinamik olarak iki farklı alt başlıkta incelenmiş ve çözüm yöntemleri uygulanmiştır. Uygulanan yöntemlerden başarılı sonuçlar elde edilmesine rağmen gelecekte, daha iyi sonuçlar elde etmek amacıyla, sezgisel yöntemlerin geliştirilmesi ve farklı yöntemlerin denenmesi amaçlanmıştır.
Özet (Çeviri)
As consumers expect faster and cheaper services from the retailers, same day delivery services gained importance in the last years. The same-day delivery companies ensure that the user has the fastest and the cheapest delivery while optimizing the costs and delivery process. There exist different concepts of delivery services that are identified by the main purpose of the service. The main purpose could be the transportation of the disabled and handicapped people as well as to deliver the urgent needs of the people. This thesis is based on a real-world scenario and it deals with modeling the scheduling process of an on-demand instant delivery start-up company called Kapgel. Located in Istanbul, Turkey, Kapgel aims to pick-up the products that are ordered by the customers via a mobile application from a certain location and deliver them to a certain location. Orders arrive ideally online and processed as soon as they are generated. Transportation of the products are performed by the vehicles owned by the company. Vehicles start and end their routes at a depot location. Products ordered by the customers are first picked-up from a point such as shop or coffee house and they are dropped-off to a requested delivery point. The company claims to deliver the orders in one hour at a fixed price. The problem that is to deliver products to the customers from their corresponding pick-up points to the desired drop-off points within a guaranteed time interval is modeled as a Dial-a-Ride Problem (DARP). DARP mainly deals with finding the optimal routes for the vehicles while optimizing the costs and user satisfaction and obeying the time and capacity constraints. It has been seen in the literature that there are works on the different versions of DARP. In this thesis, the focus was to work on two versions : multi-vehicle single-objective DARP and multi-vehicle multi-objective DARP. Multi-vehicle single-objective DARP is to find routes for multiple vehicles while optimizing a single objective function such as costs or user satisfaction. Multi-vehicle multi-objective DARP finds also routes for multiple vehicles but optimizes a multi-objective function which includes several different criteria such as costs, user satisfaction, number of vehicles, ride time violation etc. In this thesis, DARP is formulated as multi-vehicle single-objective DARP to optimize only the costs of the transportation which is the total distances that are travelled by the all vehicles to deliver the all orders in route and it is formulated as multi-vehicle multi-objective DARP to optimize costs and user satisfaction together. User satisfaction is identified by the ride time violations and so the waiting time for the customer. Problem is constrained so that each vehicle starts and ends the route at the depot, orders are delivered ideally in 1 hour, a maximum ride time is applied to all vehicles which makes the drivers not work more than a defined period of time, each vehicle has a maximum capacity and there are certain number of vehicles. Since a real-world case is investigated in this thesis, DARP is analyzed as static and dynamic DARP. In the static mode of an optimization problem, the information regarding the orders such as pick-up and delivery time and location is known beforehand. The program is not interrupted during the execution time since all the input data is already given and the solution is generated according to the already known orders. In the dynamic mode of an optimization problem, on the other hand, scheduling starts within the arrival of the first request and continues with the arrival of the next requests dynamically. Therefore the optimization algorithm is interrupted at the point that a new request is detected and the new request is adapted into the system to be processed without violating the constraints and optimization of the objectives. Static DARP is investigated under two different frameworks in this thesis. First, an exact method is implemented to solve static DARP to see if it is adequate to solve the problem in question considering the scale of the real-world scenario. Multi-vehicle single-objective DARP formulation is used and Mixed Integer Programming (MIP) is applied as a Linear Programming (LP) method to solve the static DARP. Second, a heuristic method is implemented to obtain faster solutions using multi-vehicle multi-objective DARP formulation. The problem is modeled heuristically using cluster-first, route-second algorithm. The algorithm solves the scheduling problem as generating first the clusters and then the routes for the clusters. In the clustering part of the algorithm, Genetic Algorithm (GA) is used as a heuristic method and the orders are assigned to different vehicles, i.e. clustered while in the routing part the routes are found for the different clusters that are identified in the clustering part using Nearest Neighbor Heuristic (NNH) algorithm. To solve the dynamic DARP, the mechanism is modeled so that the program could handle with the dynamic structure of the problem. Since the time becomes an important issue when solving a dynamic optimization problem, an Event Manager that handles with the time is modeled. The time is split into 1-minute intervals to detect and welcome the dynamically arriving requests by the Event Manager. In case a new request is detected, a Decision Algorithm takes the duty to find an available vehicle for this request without violating the optimization. Insertion Heuristic makes a calculation and provides an insertion cost for the request that should be inserted into the scheduling system so that it can be determined which vehicle provides the cheapest cost for the request. Insertion cost is calculated according to the distance between the pick-up point of the new request and the current positions of each vehicle or the location of the new vehicle, if there is any available vehicle. Once the request that has the cheapest insertion cost is assigned into a cluster, Optimization Algorithm finds the best route for the cluster using Nearest Neighbor Algorithm (NNH). Because the location and time information at the time that the insertion cost is calculated is needed to calculate the insertion cost of a new request and assign it to a vehicle, time and location information is kept in the memory in the dynamic mode assuming that the vehicles move with a certain speed without distracting by the environmental factors. Static and dynamic DARP algorithms are tested on a simulated data that is provided by the company. The data includes 167 requests and all of the requests belong to one day. The results of the exact and heuristic methods of static DARP implementation are compared in terms of objective values and runtime. It has been seen that exact algorithm provides the best cost values but only up to a certain number of requests. After 14 requests, exact method was not able to find feasible solutions in a reasonable time with the given resources. On the other hand, cost values that are quite close to the ones given by exact algorithm are obtained from heuristic algorithm. Heuristic algorithm was able to solve the all the instances in a very short runtime. The results of the dynamic DARP implementation was satisfactory in terms of modeling the dynamic architecture. The algorithm was able to handle with all the online requests, assign them to a vehicle without violating the requests in transit and do the optimization using heuristic algorithms. The main focus of this research was to provide a qualitative solution to a real-world problem. The real-world problem is modeled successfully for this purpose as a DARP and several algorithms are implemented and tested. Although the problem of scheduling requests to be picked-up and delivered from predetermined locations by the vehicles is implemented as static and dynamic DARP successfully, improvement of the heuristics and implementing different methods to obtain better solutions is left as future work.
Benzer Tezler
- Perdelerle güçlendirilmiş yapıların bazı özellikleri ve kolon-kiriş birleşim bölgelerinin deneysel olarak incelenmesi
Some features of strenthening by shear walls and energy absorbtion capa city of the vicinity of beam-column collections
HASAN ANAÇ
- Kule yapılarının deprem etkisinde sonlu elemanlarla modellenmesi ve simülasyonu
Finite element modeling and similation of tower structures under earthquake loads
ALİ BABUR
Yüksek Lisans
Türkçe
2012
İnşaat MühendisliğiOndokuz Mayıs Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. AZER A. KASIMZADE
- Sezgisel arama algoritmaları ile trafik sinyal optimizasyonu
Traffic signal optimization via heuristic search algorithms
ABDULLAH KARAAĞAÇ
Doktora
Türkçe
2020
Mühendislik BilimleriErciyes ÜniversitesiHarita Mühendisliği Ana Bilim Dalı
DOÇ. DR. BÜLENT BOSTANCI
- Predicting human behavior using static and dynamic models
Statik ve dinamik modeller ile insan davranışının tahmini
BERAT MERT ALBABA
Yüksek Lisans
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ YILDIRAY YILDIZ
- Static and dynamic analysis of axisymmetric structures using harmonic solid ring finite element modeling
Harmonik halka sonlu eleman modellemesi kullanarak eksenel simetrik yapıların statik ve dinamik analizi
ALİ İHSAN KARAKAŞ
Yüksek Lisans
İngilizce
2012
İnşaat MühendisliğiKaradeniz Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. AYŞE DALOĞLU