T. C. Selçuk üNİversitesi fen biLİmleri enstiTÜSÜ

T.C.

SELÇUK ÜNİVERSİTESİ

FEN BİLİMLERİ ENSTİTÜSÜ

ZAMAN BAĞIMLI EŞ ZAMANLI TOPLA DAĞIT ARAÇ ROTALAMA PROBLEMİ Gözde CAN ATASAGUN YÜKSEK LİSANS Endüstri Mühendisliği Anabilim Dalını

Temmuz-2015

KONYA

Her Hakkı Saklıdır

TEZ KABUL VE ONAYI

Gözde CAN ATASAGUN tarafından hazırlanan “Zaman Bağımlı Eş Zamanlı Topla Dağıt Araç Rotalama Problemi” adlı tez çalışması 02/07/2015 tarihinde aşağıdaki jüri tarafından oy birliği ile Selçuk Üniversitesi Fen Bilimleri Enstitüsü Endüstri Mühendisliği Anabilim Dalı’nda YÜKSEK LİSANS TEZİ olarak kabul edilmiştir.

Jüri Üyeleri İmza
Başkan

Prof. Dr. Turan PAKSOY …………………..

Danışman

Yrd. Doç. Dr. İsmail KARAOĞLAN …………………..

Üye

Yrd. Doç. Dr. Kemal ALAYKIRAN …………………..

Yukarıdaki sonucu onaylarım.

Prof. Dr. Aşır GENÇ

FBE Müdürü

TEZ BİLDİRİMİ

Bu tezdeki bütün bilgilerin etik davranış ve akademik kurallar çerçevesinde elde edildiğini ve tez yazım kurallarına uygun olarak hazırlanan bu çalışmada bana ait olmayan her türlü ifade ve bilginin kaynağına eksiksiz atıf yapıldığını bildiririm.

DECLARATION PAGE
I hereby declare that all information in this document has been obtained and presented in accordance with academic rules and ethical conduct. I also declare that, as required by these rules and conduct, I have fully cited and referenced all material and results that are not original to this work.

İmza
Gözde CAN ATASAGUN

Tarih:

ÖZET

YÜKSEK LİSANS TEZİ
ZAMAN BAĞIMLI EŞ ZAMANLI TOPLA DAĞIT ARAÇ ROTALAMA PROBLEMİ

Gözde CAN ATASAGUN
Selçuk Üniversitesi Fen Bilimleri Enstitüsü

Endüstri Mühendisliği Anabilim Dalı
Danışman: Yrd. Doç. Dr. İsmail KARAOĞLAN
2015, 41 Sayfa
Jüri

Yrd. Doç. Dr. İsmail KARAOĞLAN

Prof. Dr. Turan PAKSOY

Yrd. Doç. Dr. Kemal ALAYKIRAN

Günümüzün rekabetçi ortamında var olan ve gelecekte de var olmak isteyen işletmeler her geçen gün kendilerinden ve rakiplerinden daha iyi olmaya çalışmaktadırlar. İşletmelerin dağıtım ağı süreçlerini eniyilemek ve etkin bir şekilde yönetmek amacıyla özellikle ulaştırma, taşıma ve dağıtım konularında çeşitli kararlar alması gerekmektedir. Bu kararlardan birisi de tesislerden müşterilere gerçekleştirilecek olan rotalama kararlarıdır.

Araç rotalama problemi için yapılmış çalışmaların çok büyük bir kısmında düğümler arası ulaşım süresinin sabit alındığı görülmektedir. Ancak, taşımacılıkta gün içerisinde taşımacılık yapan araçların hızı ve buna bağlı olarak da ulaşım süreleri kullanılan yol ve yolun kullanıma başlama zamanına bağlı olarak değişiklik göstermektedir. Bu problem literatürde Zaman Bağımlı Araç Rotalama Problemi olarak adlandırılmaktadır.

Tesislerden müşterilere yapılacak taşıma işlemleri ile birlikte müşterilerden tesislere toplama işlemlerinin de aynı araçlarla gerçekleştirildiği problemler olarak tanımlanan topla-dağıt araç rotalama problemi ise son yıllarda üzerinde çeşitli çalışmaların yapıldığı bir problem türü olmuştur. Pratikte birçok örneği bulunan topla-dağıt araç rotalama problemi, araç rotalama probleminin genelleştirilmiş bir halidir.

Bu tez çalışmasında araç rotalama problemi kavramı ve çeşitleri genel olarak açıklanmış, zaman bağımlı araç rotalama problemi ve topla-dağıt araç rotalama problemi ayrıntılı olarak incelenerek tanımlanmış ve literatürde bu problemler için yapılmış çalışmalar kapsamlı bir şekilde araştırılarak her bir çalışmanın özellikleri detaylı olarak açıklanmıştır. Literatürde henüz çalışılmamış olan ve topla-dağıt araç rotalama probleminin çeşitlerinin en genel hali olarak kabul edilen eş zamanlı topla-dağıt araç rotalama problemi ile zaman bağımlı araç rotalama problemlerini birlikte çözebilmek için zaman bağımlı eş zamanlı topla-dağıt araç rotalama problemi için bir matematiksel model geliştirilerek literatürdeki mevcut test problemleri ile deneysel çalışmalar yapılmış ve yorumlanmıştır.

Anahtar Kelimeler: Araç Rotalama Problemi, Eş Zamanlı Topla Dağıt Araç Rotalama Problemi, Zaman Bağımlı Araç Rotalama Problemi

ABSTRACT

MS THESIS
TIME DEPENDENT SIMULTANEOUS PICK UP AND DELIVERY VEHICLE ROUTING PROBLEM

Gözde CAN ATASAGUN
THE GRADUATE SCHOOL OF NATURAL AND APPLIED SCIENCE OF SELÇUK UNIVERSITY

THE DEGREE OF MASTER OF SCIENCE

IN INDUSTRIAL ENGINEERING
Advisor: Asst. Prof. Dr. İsmail KARAOĞLAN
2015, 41 Pages
Jury

Asst. Prof. Dr. İsmail KARAOĞLAN

Prof. Dr. Turan PAKSOY

Asst. Prof. Dr. Kemal ALAYKIRAN

Nowadays, in the competitive market environment, companies make effort to be better than themselves and their opponents with each passing day. The companies have to make decisions about transportation and distribution processes for optimizing and efficiently managing their distribution networks. One of these decisions is about routing vehicles from facilities to customers.

In the most of the studies on the vehicle routing problem, it is assumed that travel times between nodes are constant. However vehicle speed and correspondingly the travel time differ by the time that the travel started, seasonal variations and such other factors. Thus, ignoring time dependent vehicle speeds while determining the routes can cause increased distribution costs and customer dissatisfaction. In the Time Dependent Vehicle Routing Problem, the vehicle speeds differ during the planning horizon and the travel times between nodes depend on the time that the travel started thus the demands of the customers are fully satisfied.

Pick-up and delivery vehicle routing problem is a generalized version of the vehicle routing problem and it is defined as the routing problems in which deliveries from facilities to customers and pick-ups from customers to facilities are carried out by the same vehicles.

In this study, the concept of vehicle routing problem and its variations are explained then the time dependent vehicle routing problem and the pick-up and delivery vehicle routing problem are defined in detail and their literatures are surveyed. A mathematical model is proposed for integrated solving of the time dependent vehicle routing problem and the simultaneous pick-up and delivery vehicle routing problem which is assumed as the most general form of pick-up and delivery vehicle routing problems. Experimental studies of the proposed mathematical model are performed on well-known test problems of the literature and the results are interpreted.

.
Keywords: Vehicle Routing Problem, Simultaneous Pick-up and Delivery Vehicle Routing Problem, Time Dependent Vehicle Routing Problem.

ÖNSÖZ

Teknolojinin hızla ilerlemesiyle birlikte şirketler piyasalarda tutunmak, var olan müşteri potansiyelini korumak ve geliştirmek amacıyla maliyetlerini düşürmeye yönelik çalışmalar yapmakta, bu yapılan çalışmalarla birlikte ise hem maliyetlerini düşürmekte hem de kârlarını artırmaktadırlar. Bu çalışmanın amacı şirketlerin maliyet kalemlerinden birisi olan dağıtım maliyetlerini minimize edebilmek amacıyla araçların zamana bağlı olarak değişen hızlarını ve toplama ve dağıtım yapılan müşterilerinde göz önüne alınmasıyla birlikte modellenmesini sağlamaktır.

Yüksek lisans sürecimde değerli katkılarını ve desteklerini benden esirgemeyen Endüstri Mühendisliği Bölüm Başkanı Sayın Prof. Dr. Ahmet Peker’e, gösterdiği sabır ve özveri ile hiç bir zaman desteğini ve engin bilgilerini benden eksik etmeyen, çalışmalarımın her aşamasında önerileri ile beni yönlendiren değerli hocam ve sayın danışmanım Sayın Yrd. Doç. Dr. İsmail Karaoğlan’a, önerilerini ve bilgilerini benimle paylaşan değerli meslektaşım ve kıymetli eşim Arş. Gör. Yakup Atasagun’a ve son olarak bugüne kadar bıkmadan usanmadan her daim yanımda olan canım aileme sonsuz teşekkürlerimi ve şükranlarımı sunarım.

Gözde CAN ATASAGUN

KONYA-2015

İÇİNDEKİLER

ÖZET 4

ABSTRACT 5

ÖNSÖZ 6

İÇİNDEKİLER 7

SİMGELER VE KISALTMALAR 7

1. GİRİŞ 9

2. KAYNAK ARAŞTIRMASI 11

2.1. Zaman Bağımlı Araç Rotalama Problemi (ZB_ARP) 11

2.2. Topla- Dağıt Araç Rotalama Problemi (TD_ARP) 19

3. MATERYAL VE YÖNTEM 22

3.1.1. Araç rotalama problemi (ARP) 22

3.1.2 Araç Rotalama Problemi ve Çeşitleri 24

Şekil 3.1. ARP’nin Şekilsel Gösterimi 24

Klasik ARP’nin çözümü her rotanın depodan başlayarak yine depoda son bulduğu ve her müşteriye yalnızca birer defa uğrama kısıtının sağlandığı rotalar kümesidir. Bunun yanında problemin türüne göre bazı yan kısıtların da eklenmesi gerekebilir. En yaygın olan yan kısıtlar; kapasite kısıtı, bir rotada olabilecek en fazla talep noktası kısıtı, bir rotadaki aracın toplam süre kısıtı, talep noktalarına hizmetin başlanabileceği zaman penceresi kısıtı, bir talep noktasının başka bir talep noktasından önce ziyaret edilmesinin gerektiği öncelik kısıtlarıdır (Laporte, 1992). 25

Bu kısıtlara ve pratik hayattaki uygulama alanlarına göre ARP çeşitli şekillerde sınıflandırılmıştır. Bu sınıflandırma Şekil 3.2’deki gibidir. 25

Şekil 3.2. Araç Rotalama Probleminin Çeşitleri 25

Şekil 3.2’de gösterilen ARP çeşitleri kısaca şöyle özetlenebilir: 25

3.1.2.1. Kısıtlarına göre ARP 25

Bu alt bölümde ARP için çeşitli kısıtların göz önüne alındığı durumlar için bir sınıflandırma yapılmıştır. Buna göre dokuz farklı problem tipi mevcuttur. 25

1.Kapasite kısıtlı ARP (KK_ARP): ARP’nin en yaygın türüdür. Literatürde KK_ARP ile ilgili yapılan pek çok çalışma mevcuttur. KK_ARP’de her aracın belirli bir kapasitesi vardır ve müşteri talepleri önceden bilinmektedir. KK_ARP’nin en basit halinde ise her aracın kapasitesi birbirine eşittir. Araçlar depodan harekete başlayarak yine depoya dönerler. Müşteri taleplerinin parçalanması söz konusu değildir. 25

KK_ARP aşağıdaki kriterleri sağlamak koşulu ile araç rotalarının tasarlanmasından oluşur (Santos ve ark., 2010): 25

Her bir talep noktasına tek bir araç tarafından hizmet verilmelidir, 25

Her bir rota depodan başlayıp depoda son bulmalıdır, 25

Bir aracın hizmet verdiği bütün talep noktalarının toplam talebi aracın kapasitesini aşmamalıdır, 25

Toplam araç rotalama maliyeti minimize edilmelidir. 25

2.Mesafe kısıtlı ARP (MK_ARP): MK_ARP’de her aracın gidebileceği belirli bir mesafe kısıtı söz konusudur. KK_ARP’de her bir rota için olan kapasite kısıtı yerini maksimum mesafe ya da maksimum zaman kısıtına bırakır (Toth ve Vigo, 2002a). 26

MK_ARP’de rotalara atanmış her aracın kat edebileceği belirli bir toplam mesafe olmalıdır. Bu durum gerçek bir dağıtım probleminde taşınan ürünün cinsinden, araç veya sürücü kısıtlarından dolayı söz konusu olabilir. Eğer taşınan ürünün uzun süre taşıma nedeniyle bozulabilmesi söz konusuysa, ya da araç kullanıcısının sürekli olarak belirli bir süreden daha fazla yolculuk yapamaması söz konusu ise bu kısıt eklenmelidir (Dursun, 2009). 26

3.Zaman pencereli ARP (ZP_ARP): ZP_ARP’de klasik ARP’den farklı olarak her müşteriye uğranılması gereken belirli zaman aralıkları vardır. Belirli bir zamanda depodan çıkan bir araç müşteriye ulaşmak için belirli bir seyahat süresi geçirmekte ve müşteri için belirli bir süre hizmet verilmektedir. Her müşteri için belirli olan bu servisler o müşterinin içerisinde bulunduğu zaman penceresi içinde başlamalı ve hizmet verilmelidir. Eğer müşteriye erken ulaşılması söz konusu ise zaman penceresine kadar beklemeye izin verilmektedir. Banka teslimatları, posta teslimatı, endüstriyel atık toplama, okul servis aracı rotalama ve çizelgeleme vb. ZP_ARP’nin günlük hayatta karşılaşılan örneklerindendir. 26

Zaman Pencereli ARP iki alt sınıfa ayrılmaktadır Bunlar (Badeau ve ark., 1997); 26

i.Sıkı Zaman Pencereli ARP (Hard Time Windows VRP): Eğer bir araç, müşterinin söz konusu zaman penceresinin başlangıcından önce müşteriye ulaşmışsa zaman penceresi başlayana kadar beklemek durumundadır. Zaman penceresinin bitişinden sonra servis verilememektedir. 26

ii.Esnek Zaman Pencereli ARP (Soft Time Windows VRP): Esnek Zaman Pencereli ARP’de ise müşterilere ilgili zaman pencerelerinin dışında hizmet verilebilmektedir, fakat bu durumda bir ceza maliyeti söz konusudur. 26

4.Bölünmüş talepli ARP (BT_ARP): ARP’nin bu çeşidinde bir müşterinin talepleri birden fazla araç tarafından temin edilebilmekte, yani bir müşteriye farklı araçlar tarafından birden fazla uğranabilmektedir (Koç, 2012). BT_ARP’de en az bir müşterinin talebi araç kapasitesinden büyük olmalıdır. ARP’yi BT_ARP’ye dönüştürmenin kolay bir yolu, her müşteri siparişini daha küçük olan ve bölünemeyen siparişlere ayırarak, dağıtımların parçalanmasına izin vermektir. 26

5.Çok depolu ARP (ÇD_ARP): Klasik ARP problemlerinde ve literatürde bulunan çoğu çalışmada mevcut depo sayısının tek olduğu kabul edilmektedir. ÇD_ARP’ de ise birden fazla depoya izin verilmektedir. Bu problemde depoların ve müşterilerin konumları önceden bilinmektedir ve her depo tüm müşterilerin toplam taleplerini karşılayabilecek kapasiteye sahiptir. Bu problemde her araç hareket ettiği depoya geri dönmek durumundadır. Birden fazla deposu olan bir dağıtım şirketinin araç rotalaması yapılmakta ise çok depolu olma durumunu yapılan modele ilave etmek gerekecektir. ÇD_ARP, NP-zor bir problemdir ve en iyi çözümün elde edilebileceği verimli bir yöntem bulunmamaktadır (Ho ve ark., 2008). 27

6.Topla-dağıt ARP (TD_ARP): Tesislerden müşterilere gerçekleştirilen taşıma işlemleri ile birlikte müşterilerden de tesislere toplama işlemlerinin aynı araçlarla gerçekleştirildiği problemler olarak tanımlanan TD_ARP son yıllarda üzerinde sıkça çalışılan bir problem türü olmuştur. Tez çalışması kapsamında olan TD_ARP çalışmanın sonraki bölümünde daha detaylı olarak incelenecektir. 27

7.Periyodik ARP (P_ARP): ARP’nin bir başka çeşidi olan P_ARP’de belirli bir dönemin planı yapılmaktadır ve müşteriler bu süreçte birden çok kez hizmet alabilirler. Daha sonrasında ise problem her müşteri için ziyaret kombinasyonunun eş zamanlı seçiminden ve planlama dönemi için araç rotalarını oluşturmaktan ibarettir. Müşterilere yapılacak servis sayısı müşterilerin talep miktarlarına, stok alanlarına göre değişmektedir. 27

Bu problem sınıfı bakkaliye, içecek endüstrisi, atık toplama gibi alanlarda ortaya çıkmaktadır (Hemmelmayr ve ark., 2009). 27

8.Stokastik ARP (S_ARP): S_ARP klasik ARP’nin, problem elemanlarından bir ya da birkaçının rassal olduğu durumlarda karşılaşılan bir problem çeşididir. 27

S_ARP’nin 3 farklı türü vardır (Ekizler, 2011); 27

Stokastik müşteriler: Her i müşterisi pi olasılığı ile vardır, 1-pi olasılığıyla yoktur. 27

Stokastik talepler: Her müşterinin talebi, rassal bir değişkendir. 27

Stokastik zamanlar: Servis zamanları ve dolaşım zamanları rassal değişkenlerdir. 27

9.Zaman bağımlı ARP (ZB_ARP): ARP için yapılan çalışmaların çok büyük bir kısmında düğümler arası ulaşım süresinin sabit alındığı görülmektedir. Ancak, şehir içi taşımacılıkta gün içerisinde taşımacılık yapan araçların hızı ve buna bağlı olarak da ulaşım süreleri kullanılan yol ve yolun kullanıma başlama zamanına bağlı olarak değişiklik göstermektedir. Bu problem literatürde ZB_ARP olarak adlandırılmaktadır. ZB_ARP problemi çalışmanın ikinci bölümünde daha detaylı olarak incelenmiştir. 28

3.1.2.2. Yolların durumuna göre ARP 28

3.1.2.3. Rotalama durumlarına göre ARP 28

ARP, rotaların bir depoda başlayıp aynı depoda sona ermesi veya aracın depodan bağımsız olarak seyir güzergâhının en son müşteride bitirilebilmesi durumlarına göre açık ve kapalı uçlu olmak üzere ikiye ayrılır. 29

3.1.2.4. Çevre durumuna göre ARP 29

Araç rotalama problemleri dinamik ve statik olmak üzere de iki sınıfa ayrılabilir. 30

3.2.1. Problem tanımı 30

3.2.2. Matematiksel model 32

4. ARAŞTIRMA SONUÇLARI VE TARTIŞMA 35

4.1. Deney tasarımı 36

4.2. Deneysel sonuçlar 37

5. SONUÇLAR VE ÖNERİLER 42

5.1 Sonuçlar 42

5.2 Öneriler 43

KAYNAKLAR 43

ÖZGEÇMİŞ 48

SİMGELER VE KISALTMALAR

Kısaltmalar
ARP : Araç Rotalama Problemi

AU_ARP : Açık Uçlu Araç Rotalama Problemi

A_ARP : Asimetrik Araç Rotalama Problemi

BT_ARP : Bölünmüş Talepli Araç Rotalama Problemi

ÇD_ARP : Çok Depolu Araç Rotalama Problemi

D_ARP : Dinamik Araç Rotalama Problemi

ETD_ARP : Eş Zamanlı Topla Dağıt Araç Rotalama Problemi

KTD_ARP : Karma Topla Dağıt Araç Rotalama Problemi

KK_ARP : Kapasite Kısıtlı Araç Rotalama Problemi

KU_ARP : Kapalı Uçlu Araç Rotalama Problemi

MK_ARP : Mesafe Kısıtlı Araç Rotalama Problemi

ÖDST_ARP : Önce Dağıt Sonra Topla Araç Rotalama Problemi

P_ARP : Periyodik Araç Rotalama Problemi

STK_ARP : Stokastik Araç Rotalama Problemi

S_ARP : Simetrik Araç Rotalama Problemi

ST_ARP : Statik Araç Rotalama Problemi

TD_ARP : Topla Dağıt Araç Rotalama Problemi

ZB_ARP : Zaman Bağımlı Araç Rotalama Problemi

ZB_ETD_ARP : Zaman Bağımlı Eş Zamanlı Topla Dağıt Araç Rotalama Problemi

ZBAUSF : Zamana Bağlı Adımsal Ulaşım Süresi Fonksiyonu

ZBHF : Zamana Bağlı Hız Fonksiyonu

ZP_ARP : Zaman Pencereli Araç Rotalama Problemi

1. GİRİŞ
Günümüzün rekabetçi ortamında var olan ve gelecekte de var olmak isteyen işletmeler rakiplerinden daha iyi olmaya çalışmaktadırlar. İşletmelerin dağıtım ağı süreçlerini eniyilemek ve etkin bir şekilde yönetmek amacıyla özellikle ulaştırma, taşıma ve dağıtım konularında çeşitli kararlar alması gerekmektedir. Bu kararlardan birisi de tesislerden müşterilere gerçekleştirilecek olan rotalama kararlarıdır. Ulaştırma, taşıma ve dağıtım konularında üzerinde durulan ilk problemlerden biri Araç Rotalama Problemi (ARP)’dir.

ARP ilk kez 1959 yılında Dantzig ve Ramser tarafından önerilmiştir. ARP, bir depodan başlayarak belirli bir coğrafi alana dağılmış olarak bulunan müşterilere giden ve tekrar depoya dönen, toplam maliyeti en küçüklemeyi amaçlayarak depodan çıkan araç sayısı kadar rotanın bulunması olarak tanımlanabilir. ARP’de her müşterinin yalnızca bir kez ziyaret edilmesi, tüm rotaların depodan başlayıp depoda bitmesi gibi temel kısıtların yanı sıra diğer bazı kısıtların da sağlanması gerekir. ARP ile ilgili yapılan çalışmaların çok büyük bir kısmında düğümler arası ulaşım süresinin sabit kabul edildiği görülmektedir. Ancak bu durum pratikte karşılaşılan duruma pek uygun değildir. Şehir içi trafikte gün içerisinde trafiğin yoğunluğuna bağlı olarak araçların hızları ve ulaşım süreleri farklılık göstermektedir. Örneğin şehrin merkezine yakın yerlerde mesai saatinin başlama ve bitiş saatlerinde trafik, günün diğer saatlerine göre çok daha yoğun olmaktadır. Dolayısıyla bu saatlerde o yolu kullanmak isteyen araçlar daha yavaş yol kat edebilmektedirler. Bu problem literatürde zaman bağımlı araç rotalama problemi (ZB_ARP) olarak adlandırılmaktadır. ZB_ARP’de düğümler arası ulaşım sürelerinin gün içerisinde değiştiği durum ele alınmaktadır. Planlama periyodu zaman aralıklarına bölünerek bu zaman aralıklarında her bir yol için sabit bir hız tanımlanmaktadır. Bir düğümden çıkan araç çıkış zamanına ve kullanacağı yola bağlı olarak belli bir hız ile bir sonraki düğüme seyahat etmektedir. Eğer seyahat esnasında sıradaki düğüme bir sonraki zaman dilimine geçiş olursa, araç yeni zaman dilimi için tanımlanmış olan hız ile yoluna devam edecektir.

Dünyadaki kaynakların giderek azalması buna bağlı olarak insanların geri dönüşüm konusunda bilinçlenmesi ile birlikte günümüz lojistik faaliyetlerinin önemli bir unsuru da müşterilerden işletmelere gerçekleştirilen mal taşımacılığıdır. Tüketim sonucu oluşan atıkların toplanıp ekonomik değere sahip ürünler haline dönüştürülmesi, müşterilerin satın aldıkları üründen memnun olmamalarından dolayı ürünlerin geri iadesi gibi durumlar geri dönüşümlere örnek olarak verilebilir. ARP’nin türlerinden birisi de topla-dağıt araç rotalama problemi (TD_ARP)’dir. Tesislerden müşterilere yapılacak taşıma işlemleri ile birlikte müşterilerden tesislere toplama işlemlerinin de aynı araçlarla gerçekleştirildiği problemler olarak tanımlanan TD_ARP, son yıllarda üzerinde çeşitli çalışmaların yapıldığı bir problem türü olmuştur.

Bu tez çalışmasında ARP kavramı ve çeşitleri genel olarak açıklanacak, ZB_ARP ve TD_ARP ayrıntılı olarak incelenerek tanımlanacaktır. Ayrıca literatürdeki ZB_ARP ve TD_ARP çalışmaları kapsamlı bir şekilde araştırılarak açıklanacaktır. Literatürde henüz çalışılmamış olan TD_ARP’nin en genel hali olan Eş Zamanlı Topla Dağıt Araç Rotalama Problemi (ETD_ARP) ile ZB_ARP entegre edilerek ve zamana bağlı hız fonksiyonu özelliği kullanılarak, müşterilerden eş zamanlı olarak toplama ve dağıtım yapılmasına olanak sağlayan, kesin hesaplama gerçekleştiren, doğrusal yapıya sahip bir matematiksel model önerilecektir. Önerilecek olan bu model literatürdeki test problemleri üzerinde denenerek elde edilen sonuçlar yorumlanacaktır.

Tez çalışmasının bundan sonraki bölümleri şu şekilde düzenlenmiştir. İkinci bölümde ZB_ARP ve TD_ARP için literatür taraması verilmiştir. Üçüncü bölümde ARP ve çeşitleri tanımlanarak açıklanmış daha sonra ETD_ARP ve ZB_ARP birlikte çözebilmek için bir matematiksel model geliştirilerek sunulmuştur. Dördüncü bölümde ise literatürdeki mevcut test problemleri ile deneysel çalışmalar yapılmış ve yorumlanmıştır.

2. KAYNAK ARAŞTIRMASI

Bu bölümde ZB_ARP ve TD_ARP problemleri tanıtılarak bu problemlere ilişkin literatür taramaları sunulmuştur.
2.1. Zaman Bağımlı Araç Rotalama Problemi (ZB_ARP)

1959 yılında Dantzig ve Ramser tarafından önerilen ARP, geçen zaman içerisinde birçok alt dallara ayrılarak pratik hayata uyarlanmaya çalışılmıştır. Bu amaç doğrultusunda pratik hayatın önemli sorunlarına çözüm bulmaya çalışan ARP’nin çeşitlerinden birisi de ZB_ARP’dir.

ARP için yapılan çalışmaların çok büyük bir kısmında düğümler arası ulaşım süresinin sabit alındığı görülmektedir. Ancak, şehir içi taşımacılıkta gün içerisinde taşımacılık yapan araçların hızı ve buna bağlı olarak da ulaşım süreleri kullanılan yol ve yolun kullanıma başlama zamanına bağlı olarak değişiklik göstermektedir. Bu problem literatürde ZB_ARP olarak adlandırılmaktadır.

ZB_ARP’de düğümler arası ulaşım sürelerinin gün içerisinde değiştiği ve her müşteriye giriş ve çıkışların önceden belirli zaman aralıkları içerisinde gerçekleştirildiği durum ele alınmaktadır. Bu bağlamda, planlama periyodu (örneğin bir gün) zaman aralıklarına bölünerek bu zaman aralıklarında her bir yol için sabit bir hız tanımlanmaktadır. Bir düğümden çıkan araç çıkış zamanına ve kullanacağı yola bağlı olarak belli bir hız ile bir sonraki düğüme seyahat etmektedir. Eğer sıradaki düğüme seyahat esnasında bir sonraki zaman dilimine geçiş olursa, araç yeni zaman dilimi için tanımlanmış olan hız ile yoluna devam edecektir. Bu varsayım pratikte karşılaşılan durumlara oldukça benzerlik göstermektedir.

Örneğin, gün içerisinde, iş merkezlerinin yoğunlukta olduğu bölgelere giren/çıkan yollarda sabah mesai başlangıcında (07.00-09.00), öğle mola saatlerinde (12.00-13.00) ve akşam iş çıkış saatlerinde (17.00-19.00) yüksek trafik yoğunluğu (düşük araç hızları) görülürken, diğer zaman aralıklarında ise düşük trafik yoğunluğu (yüksek araç hızları) söz konusudur (Koç, 2012).

Trafiğin yoğun olduğu bir kentte, iki nokta arasındaki seyahat süresi, araç hızı sabit olamadığından dolayı bir fonksiyon olarak göz önüne alınamaz. Gün içerisinde trafik yoğunluğunda meydana gelen değişiklikler, araçların seyahat hızında değişikliklere bu da seyahat süresinde değişimlere neden olur. Bu çeşitliliği doğuran nedenlerin ilk bölümü; meydana gelen trafik kazaları, hava durumundaki değişiklikler ya da diğer rassal değişikliklerdir. İkinci bölümü; trafikteki en sıkışık zamanları oluşturan durumlar olan saatlik, haftalık, aylık ve mevsimsel yoğunluklardır (Malandraki ve Daskin, 1992).

ZB_ARP’de toplam maliyet enküçüklemesinin yanı sıra; enaz seyahat mesafesi, enaz maliyet, enaz seyahat süresi ve enaz araç sayısı gibi amaçlar da göz önüne alınmaktadır.

Çizelge 2.1.’de ZB_ARP ile ilgili literatürde yapılmış çalışmalar sentezlenerek kronolojik sırada özetlenmiştir.