Drone ile teslimat rotalaması için bir matematiksel model

Year 2019, Volume: 25 Issue: 1, 89 - 97, 26.02.2019

Sinem Han Begüm Özer Barış Alioğlu Özgür Polat , Ayşe Tülin Aktin

Abstract

Lojistik,
bir ürünün nakliyesinin yanı sıra, depolanması, ambalajlanması ve dağıtımı gibi
süreçleri de kapsamakta ve tüm sürecin, ilk üreticiden nihai tüketiciye kadar
doğru bir biçimde çalışmasını hedeflemektedir. Maliyet ve hizmet bakımından
uygun bulunan karayolu taşımacılığı, günümüzde tercih edilen ulaşım
sistemlerinin başında gelmektedir. Ancak gelişen teknolojiyle birlikte, birçok
ürünün dağıtımında drone’lardan da yararlanıldığı görülmektedir. Bekleme
zamanlarını azaltmayı ve insangücü maliyetini ortadan kaldırmayı amaçlayan bu
sistem, yeni bir teslimat aracı olarak lojistik sürecinde yerini almıştır.
Karayolunda oluşan trafik yoğunluğu, ürünlerin müşteriye ulaşmasını
geciktirmekte, bu sırada artan CO₂ salımı da çevre ve ekonomi
üzerinde olumsuz etkilere neden olmaktadır. Bu çalışmanın amacı, drone
kullanımı ile hızlı ve doğa dostu bir teslimat gerçekleştirmek suretiyle
müşteri memnuniyetinde artış ve taşıma maliyetlerinde azalma sağlamak ve
yukarıda bahsedilen problemlere bir çözüm sunmaktır. Çalışmada, eczanelerin
günlük ilaç gereksinimlerinin drone’lar yardımıyla karşılanması ele alınmış ve
bu amaçla, İstanbul’un Bakırköy ilçesi pilot bölge olarak seçilmiştir. Önerilen
iki aşamalı yöntemin ilk aşamasındaki matematiksel model, kümeleme analizi
yapmaktadır. Bölgedeki eczanelerin koordinatları modele girdi olarak verilmiş
ve eczane kümeleri oluşturulmuştur. İkinci aşamada ise, oluşturulan kümelerden
birisi seçilerek, ağırlık merkezi yöntemiyle, burada bulunan eczanelere hizmet
verecek olan drone merkezinin yeri bulunmuştur. Daha sonra, bu kümeye ait
eczanelere ilaç dağıtımı yapılırken, aralarındaki toplam mesafeyi
enküçükleyecek şekilde drone’ların teslimat rotalarını belirleyen bir araç
rotalama modeli geliştirilmiştir. Modeller, GAMS/CPLEX çözücüsü ile
çözülmüştür. Bu çalışmanın yakın gelecekte literatürdeki “yeşil teslimat”
alanındaki yeni araştırmaları tetikleyeceğine inanılmaktadır

Keywords

Drone, Araç rotalama, Matematiksel modelleme

A mathematical model for the delivery routing problem via drones

Abstract

Logistics sector aims to distribute merchandise to designated places on
time, while focusing on the entire process that starts from storing the goods
at warehouses. Transportation by land is the most common and preferred way
in logistics in terms of cost and service. Studies
have been going on for drone transportation with the purpose of reducing the
service time and making the process automated. Advancement
of this technology has led to an increase in transportation with drones.
Traffic is a huge problem in land transportation
causing delays in delivery time. Furthermore, nature and economy are affected
because of the CO₂ emission, which is a consequence of intense
traffic. In this study, utilizing drones for
delivery is proposed with the aim of increasing customer satisfaction and
minimizing transportation cost per delivery in a green way. İstanbul’s Bakırköy
district is selected as the implementation region, and daily drug delivery to
pharmacies with drones is examined. In the
first stage, a mathematical model that uses pharmacy coordinates as an input is
developed for clustering analysis. In the
second stage, one of these clusters is selected, and the location of the
drone center that will serve pharmacies in the cluster is obtained by center of
gravity method. Then, a vehicle routing model is
proposed for finding the drone routes and calculating the total distance
travelled within this cluster. Mathematical
models are solved with GAMS/CPLEX solver. It is believed that this study will
trigger new studies in “green delivery” literature in near future.

Keywords

Drone, Vehicle routing problem, Mathematical modelling

References

• Fahrney DS, RADM USN. "The birth of guided missiles". United States Naval Institute Proceedings, 106, 56-57, 1980.
• Keane JF, Carr SS. “A brief history of early unmanned aircraft”. Johns Hopkins APL Technical Digest, 32(3), 558-569, 2013.
• BBC News. “Amazon Makes First Drone Delivery”. http://www.bbc.com/news/technology-38320067 (2016).
• Deutsche Post DHL Group. “DHL Parcelcopter 3.0”. http://www.dpdhl.com/en/media_relations/specials/parcelcopter.html (11.04.2018).
• Brar S, Rabbat R, Raithatha V, Runcie G, Yu A. “Drones for Deliveries”. Sutardja Center for Entrepreneurship & Technology, University of California, Berkeley, Technical Report, 2015.11.8, 2015.
• Federal Aviation Administration. “Summary of Small Unmanned Aircraft Rule”. https://www.faa.gov/uas/media/Part_107_Summary.pdf(2016).
• Directorate General of Civil Aviation (DGCA). http://web.shgm.gov.tr/en (11.04.2018).
• Dave M, Gianey R. “Different Clustering Algorithms for Big Data Analytics: A Review: Procedures in Jaipur, Rajsthan and India”. Computer Science Department, Jagan Nath University, 2016.
• Xu R, Wunsch D. “Survey of clustering algorithms”. IEEE Transactions on Neural Networks, 16(13), 645-678, 2005.
• Çalış A, Boyacı A, Baynal K. “Data mining application in banking sector with clustering and classification methods”. Proceedings of the 2015 International Conference on Industrial Engineering and Operations Management, Dubai, United Arab Emirates, 3-5 March 2015.
• Onnela N. Determining the Optimal Distribution Center Location. MSc Thesis, Tampere University of Technology, Tampere, Finland, 2015.
• Abbasi M. Storage, Warehousing and Inventory Management. Editors: Farahani RZ, Rezapour S, Kardar L. Logistics Operations and Management, Elsevier, 2011.
• Dantzig GB, Ramser JH. “The truck dispatching problem”. Management Science, 6(1), 80-91, 1959.
• Toro E, Escobar A, Granada M. “Literature review on the vehicle routing problem in the green transportation context”. Luna Azul, 42, 362-387, 2016.
• Blecha C, Goetschalckx M. “The Vehicle Routing Problem with Backhauls: Properties and Solution Algorithms”. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia, USA, 1992.
• Cordeau JF, Laporte G, Savelsbergh MWP, Vigo D. Vehicle Routing. Editors: Barnhart C, Laporte G. Handbook in OR & MS, Elsevier, 2007.
• Greblicki J, Walczyński M. Determination of the Optimal Routes for Autonomous Unmanned Aerial Vehicle Under Varying Wind with Using of the Traveling Salesman Problem Algorithm. Editors: Saeed K, Homenda W. Computer Information Systems and Industrial Management, Springer, 2016.
• Dorling K, Heinrichs J, Messier G, Magierowski S. "Vehicle routing problems for drone delivery". IEEE Transactions on Systems, Man and Cybernetics: Systems, 47(1), 70-85, 2017.
• Wang X, Poikonen S, Golden, B. “The vehicle routing problem with drones: several worst-case results”. Optimization Letters, 11(4), 679-697, 2017.
• Poikonen S, Wang X, Golden B. “The vehicle routing problem with drones: Extended models and connections”. Networks, 70(1), 34-43, 2017.
• Schermer D, Moeini M, Wendt O. Algorithms for Solving the Vehicle Routing Problem with Drones. Editors: Nguyen N, Hoang D, Hong TP, Pham H, Trawiński B. Intelligent Information and Database Systems, Springer, 2018.
• Akış A, Sırma Z, Yalçın Z. Route Design in a Pharmaceutical Warehouse via Mathematical Programming. Unpublished Graduation Project, İstanbul Kültür University, İstanbul, Turkey, 2013.
• IBM. “ILOG CPLEX Optimization Studio”. www.ibm.com/software/integration/optimization/cplex-optimization-studio (04.05.2017).