Araç rotalama problemleri için matematiksel modeller ve subgradyant temelli çözüm yaklaşımı

Abstract

Bu tez kapsamında, literatürde yoğun çalışılan kapasite kısıtlı ve heterojen filolu araç rotalama problemleri incelenmiş ve bu problemlere yönelik yeni çözüm yaklaşımları önerilmiştir. Araç rotalama problemi tamsayı kısıtlarından dolayı NP-zor olarak nitelendirilen problem türünden olan, dışbükey olmayan ve türevlenemeyen bir kombinatoryal en iyileme problemidir. Önerilen çözüm yaklaşımları Kasımbeyli tarafından geliştirilen kısıtlı en iyileme problemlerinin dışbükeylik ve türevlenebilirlik koşullarını gerektirmeyen, genişletilmiş subgradyant yöntemine dayalıdır. Bu yöntem her iterasyonda bir alt problem oluşturur. Alt problemlerin çözümü için bu çalışmada, araç rotalama problemlerinde etkin bir metasezgisel yöntem olan genetik algoritma uygulanmıştır. Böylece, çözüm yöntemi, Genişletilmiş Subgradyant Algoritması ile genetik algoritmanın melezi şeklinde tasarlandığından, `Melez Subgradyant Yöntemi` olarak adlandırılmıştır. Bu çalışmada ayrıca, melez subgradyant yöntemi, heterojen filolu araç rotalama problemi için geliştirilen çok amaçlı matematiksel modelin çözümü ve irdelenmesi için de uygulanmıştır. Bu yöntem, kısıtların gevşetilmesi yaklaşımı ile birleştirilerek heterojen filolu araç rotalama probleminin çözümüne uygulanmış ve elde edilen çözümler karşılaştırılmıştır. Önerilen tüm çözüm yöntemlerinin performansları, literatürde yer alan test problemleri kullanılarak araştırılmış, elde edilen hesaplamalı sonuçlar analiz edilmiş ve gelecek çalışmalara ilişkin öneriler sunulmuştur.Anahtar Sözcükler: Araç rotalama, Genetik algoritma, Heterojen filo, Genişletilmiş subgradyant

In this thesis, capacitated vehicle routing problem and heterogeneous fleet vehicle routing problem which are widely studied in the literature are examined and new solution approaches are proposed for the regarding problems. The vehicle routing problem is a nonconvex and nondifferentiable combinatorial optimization problem, which is a type of problem that is considered NP-hard due to integer variable constraints. The proposed solution approaches are based on the modified subgradiant method introduced by Kasımbeyli, which does not require the convexity and differentiability conditions of constrained optimization problems. The algorithm creates a subproblem for each iteration. In this study, genetic algorithm which is an effective metaheuristic algorithm in vehicle routing problems, is applied for the solution of the subproblem. Since the solution method is designed as a hybrid of the genetic algorithm and the Modified Subgradient Algorithm, it is called `Hybrid Subgradient Method`. In this study, hybrid subgradient method is also applied to solve and examine the multi-objective mathematical model developed for the heterogeneous fleet vehicle routing problem. This method is applied to solve the heterogeneous fleet vehicle routing problem by combining the relaxation of constraints approach and the obtained solutions are presented with comparison. The performances of all proposed solution methods are investigated by using the test problems from the literature, the obtained computational results are analyzed and suggestions for future studies are presented.Keywords: Vehicle routing, Genetic algorithm, Heterogeneous fleet, Modified subgradient