Dağıtım rotaları optimizasyonu için meta sezgisel bir yaklaşım

Dağıtım rotalarının optimizasyonunu amaçlayan Araç Rotalama Problemi (ARP) literatürde çözümü zor problemler sınıfında yer alan ve üzerinde yaklaşık 50 yıldır çalışılan önemli bir problemdir. ARP'nde merkezi bir depoda bulunan araçların depodan ayrılıp belirli bir sayıda müşteriyi ziyaret ederek tekrar depoya dönmesi sırasında kat ettikleri toplam mesafenin minimum yapılması amaçlanır. Bu problemde müşteri sayısının az olduğu durumlarda kesin çözüm algoritmaları ile sonuca ulaşılabilmektedir. Diğer yandan, müşteri sayısı arttıkça çözüm için gerekli olan bilgisayar işlem süresi katlanarak arttığından dolayı bu yöntemleri uygulamak mümkün olmamaktadır. Bu sebeple son yıllarda daha çok sezgisel ve meta sezgisel yöntemler ARP'ne uyarlanmıştır. Bu çalışmada sezgisel yöntemler ve meta sezgisel bir yaklaşım olan yapay sinir ağları ile araç rotalama problemine çözüm aranmıştır. Önerilen algoritma Visual Basic dilinde kodlanmış ve literatürde yer alan referans test problemleri üzerinde çalıştırılmıştır.

Araç Rotalama Problemi ,

Sezgisel Yaklaşım ,

Yapay Sinir Ağları ,

The Vehicle Routing Problem (VRP) consists of constructing minimum cost routes that includes a depot, vehicles with capacity constraints, and customers with known demands where the vehicles leave the depot, visit each customer exactly once, and return to the depot. This problem was first introduced by Dantzig and Ramser in 1959. Since the problem has broad application areas such as food, beverage, and newspaper distribution, cargo and mail delivery, transportation of military equipment, routing of school buses etc., it has attracted the researches in both academia and industry for a long period. Recent technological developments and competitive marketplace makes distribution problem more and more important. Because of this reason, the companies try to decrease their logistic costs by building better routes to survive in today's competitive world. The VRP belongs to the class of the NP-hard combinatorial optimization problems. This problem contains both the Traveling Salesman Problem (TSP) and the Bin Packing Problem (BPP) as special cases and lies at the intersection of these two well known NP-hard problems. Several mathematical methods, heuristics and metaheuristic approaches are applied to solve the vehicle routing problem. Although exact algorithms can reach the optimum solutions easily when the number of customers is less, they are not practical in real life problems with an increasing number of customers since the computation time for finding the solution grows exponentially. Therefore, heuristics and metaheuristics have been widely used by researchers. Clarke and Wright's (1964) savings algorithm, Gillett and Miller's (1974) sweep algorithm, and Bentley's (1992) nearest addition method are some popular heuristic algorithms for this problem. The metaheuristic methods such as tabu search, simulated annealing, genetic algorithms, deterministic annealing and ant colonies have been applied to solve the VRP and good solutions have been obtained. Even though these methods do not guarantee the optimal solution, they provide satisfactory solutions in short computation time. In the vehicle routing problem, capacity constrained vehicles leave the depot, stop by one or more customers and then return back to the depot. Here, the loading capacity for each vehicle is the same and the demand for each customer is known. The constraints are as follows: each customer can only be visited by one vehicle; the total customer demand on the route for a vehicle cannot exceed the vehicle capacity; and all vehicles have to return back to the depot. The objective of VRP is to minimize the total travelling distance or cost.

Vehicle Routing Problem, ,

Heuristic Approaches, ,

Neural Networks ,