Heuristic Approaches for Multi Depot Vehicle Routing Problems With Heterogeneous Vehicle Fleet

Abstract

Bu tezde, Çok-depolu Geri-toplamalı Heterojen ARP (ÇGHARP) araştırılmıştır. Problem, mevcut üç rotalama probleminin (çok-depolu ARP, heterojen araç filolu problem ve geri-toplamalı rotalama problemi) bir genellemesi olmasına rağmen, bu birleştirilmiş rotalama problemi ilk kez araştırılmıştır. Önce matematiksel bir model sunulmuş, ardından bazı kısıtları daraltılmıştır. Değişken Komşuluk Araması (DKA) ile Aç gözlü Rastsal Adaptif Hafıza Programlama Araması (ARAHPA), kısaca DKA-ARAHPA, birleştirilerek güçlü ve özgün bir birleşik meta-sezgisel önerilmiştir. Kıyaslama ve değerlendirme yapabilmek için herhangi bir problem örneği bulunmadığından, mevcut araç rotalama problem örneklerini birleştirerek veri setleri oluşturulmuştur. Önerilen meta-sezgisel, küçük örnekler için bir dizi optimal çözüm elde edebilmiş ve sırasıyla CPLEX ve temel DKA ile elde edilen yaklaşık %40 ve %20 ortalama aralık değerlerine kıyasla alt sınırlardan yaklaşık %13 aralık değeri elde etmiştir. Tek depo, çok depo, heterojen araç filosu ve geri toplama özelliklerine sahip araç rotalama problemlerini DKA-ARAHPA meta-sezgiseli ile çözebilen bir Karar Destek Sistemi (KDS) geliştirilmiştir. Geliştirilen KDS, ADVISER2 olarak adlandırılan görsel etkileşimli bir çözüm aracıdır. Kullanıcı, çözülmesi gereken problemleri ve elde ettiği çözümleri KDS veritabanına kaydedebilmekte ve kaydedilen çözümün raporunu yazdırabilmektedir. Kullanıcı, çözülecek problemi seçtikten sonra DKA-ARAHPA ile problemi çözebilmekte ve çözüm üzerinde interaktif değişiklikler yapabilmektedir. Geliştirilen KDS, 5 farklı problem için literatürde önerilen problem örnekleri üzerinde test edilmiş ve Geri toplamalı Çok-depolu ARP hariç en iyi bilinen çözümlerden maksimum %5,87 ortalama aralık değeri ile kısa bir CPU süresinde çözüm bulabilmiştir. Ayrıca, DKA-ARAHPA ile Sabit Filolu ve Karma ARP için bir problemin ve çok-depolu ARP için 3 problemin yeni en iyi çözümleri bulunmuştur.

In this thesis, we investigated the Multi-Depot Heterogeneous Vehicle Routing Problems (VRP) with Backhauls. Though the problem is a generalisation of three existing routing problems: Multi-depot VRP, the heterogeneous vehicle fleet problem and the routing problem with backhauls, this is the first time this combined routing problem was investigated. A mathematical formulation was first presented followed by some tightening. A powerful and novel unified hybridisation of Variable Neighbourhood Search (VNS) with the Greedy Randomized Adaptive Memory Programming Search (GRAMPS), VNS-GRAMPS for short, was proposed. As there are no problem instances available for bench-marking, we generated data sets by combining those from existing VRPs. The proposed meta-heuristic obtained a number of optimal solutions for small instances and yields about 13% gap from the lower bounds compared to nearly 40% and 20% average gap values for our CPLEX implementation and the VNS without hybridisation, respectively. Moreover, a Decision Support System (DSS) was developed that can solve VRPs with single-depot, multi-depot, heterogeneous vehicle fleet and backhaul features with VNS-GRAMPS meta-heuristic. The developed DSS is a visual interactive solution tool called as ADVISER2. The user can save the problems to be solved and the solutions obtained into the database of DSS, and print the report of the saved solution. After selecting the problem to be solved, the user can solve the problem with VNS-GRAMPS and can make interactive changes on the solution. The developed DSS was tested on the problem instances suggested in the literature for 5 different problems, and it was able to find solutions in a short CPU time with a maximum average gap value of 5.87% from the best known solutions, except for the Multi-depot VRP (MVRP) with backhauls problem. Moreover, new best solutions of one problem for fleet size and mix VRP and 3 problems for MVRP were found with VNS-GRAMPS.