A METAHEURISTIC APPROACH FOR OPTIMIZATION OF DISTRIBUTION ROUTES

Yıl 2009, Cilt: 11 Sayı: 2, 171 - 190, 01.12.2009

Selçuk Çolak Hüseyin Güler

Öz

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.
In this study, some heuristic approaches and a metaheuristic, neural
networks, are hybridized and applied to solve the vehicle routing problem. The
two heuristics used are the well known nearest neighbor algorithm and Clarke
and Wright’s savings algorithm. In this approach, the VRP is framed as a
neural network with multiple layers of vehicles and customers. The connections
between the layers are characterized by weights. These weights are all same for
the first iteration but are modified for the subsequent iterations and feasible
solutions are generated with the help of the heuristic.
The proposed neural network approach has been coded in Visual Basic 6.0
programming language and implemented on a Intel® Quad Core 2.4GHz
personal computer. Three benchmark problem sets are used to evaluate the
performance of the algorithm. The first set consists of benchmark problem
instances of Christofides et al. (1979). The next two sets are the instances of
Taillard (1993) and the Fisher (1994).
Computational results on benchmark problems demonstrate the efficiency of
the proposed approach on VRP. The results of the algorithm are compared to
the single pass solution of heuristics shows significant improvements. It can also
be pointed out that the neural networks in conjunction with the savings
algorithms gives better results than the one with nearest neighbor algorithm.

Anahtar Kelimeler

Vehicle routing problem, heuristic approaches, neural networks.

DAĞITIM ROTALARI OPTİMİZASYONU İÇİN META SEZGİSEL BİR YAKLAŞIM

Öz

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. Elde edilen sonuçlar bu algoritmanın araç rotalama problemi üzerinde etkin olduğunu göstermiştir.

Anahtar Kelimeler

Araç rotalama problemi, sezgisel yöntemler, yapay sinir ağları.