Filo Büyüklüğü ve Karma Araç Rotalama Problemleri İçin Yeni Bir Yapısal Rotalama Algoritması

Year 2014, Volume: 18 Issue: 2, 45 - 53, 25.09.2014

Kenan Karagül

Abstract

Bu çalışmada, Filo Büyüklüğü ve Karma Araç Rotalama Problemleri için yeni bir yapısal rotalama yaklaşımı önerilmiştir. Önerilen yaklaşım Ochi rotalama yaklaşımı ile matematiksel olarak benzerlik göstermesine rağmen, tamamen farklı ve yeni bir yaklaşımdır. Çünkü bu yaklaşım araç tiplerini yani kapasitelerini dikkate alırken, Ochi yaklaşımı boş kalan kapasitenin maliyetlerini dikkate almaktadır.
Önerilen yeni rotalama yaklaşımı ve Ochi rotalama yaklaşımlarına ilişkin algoritmalar verilmiştir. Örnek bir problem ile verilen rotalama yaklaşımlarının çözüm aşamaları detaylı bir şekilde anlatılmıştır. Örnekte rasgele seçilen bireyler için algoritmalardan farklı rotalar ve farklı maliyetler elde edilmiştir. Önerilen yeni yaklaşımla daha düşük maliyetli rotaların elde edildiği görülmüştür. Ancak örnek problem üzerindeki çalışmaların yeterli olmayacağı düşünülerek Golden'ın 12 test problemi (Sabit Maliyetli Filo Büyüklüğü ve Karma Araç Rotalama Problemi) üzerinde bu rotalama yaklaşımları karşılaştırılmıştır. Golden'ın test problemlerinde ortalama zaman karmaşıklığı ve ortalama çözüm performansı açısından önerilen yeni yaklaşımın üstünlüğü ortaya çıkmıştır. Böylece önerilen yaklaşımın, Sabit Maliyetli Filo Büyüklüğü ve Karma Araç Rotalama Problemleri için farklı ve yeni bir yaklaşım olduğu sonucuna varılmıştır.

Keywords

Filo Büyüklüğü ve Karma, Yapısal Sezgiseller, Araç Rotalama Problemi, Rotalama Algoritmaları, Ochi Rotalama Algoritması

A Novel Constructive Routing Algorithm for Fleet Size and Mix Vehicle Routing Problem

Abstract

In this study, a new constructive routing algorithm for fleet size and mix vehicle routing problem is proposed in which residual costs rather than vehicle types are considered for route selection. The algorithm of the proposed routing approach is given and then the solution phases of a sample problem are shown by using the given algorithm. In order to highlight the performance of the routing approach, Golden’s 12 test problems (Fleet Size and Mix Vehicle Routing Problem with Fixed Cost) are used. It is seen that the proposed method has better average time complexity and cost performances than Ochi’s routing approach. Therefore, the solutions of the proposed method that uses vehicle type information are better than those of the methods that use residual cost based on the vehicle type information

Keywords

Fleet Size and Mix Vehicle, Routing Problem, Constructive Heuristics, Vehicle Routing Problem, Routing Algorithms, Ochi’s Routing Approach

References

• Baldacci, R., Battarra, M.,Vigo, D., 2008. Routing a Heterogeneous Fleet of Vehicles. Operations Research/Computer Science Interfaces, 43, 3-27.
• Brandao, J., 2009. A Deterministic Tabu Search