An application of the vehicle routing problem to a glass manufacturing firm

Abstract

This thesis presents an exact algorithm and a heuristic method for the delivery and transportation of glass plates for a glass manufacturing firm. A variant of the Capacitated Vehicle Routing Problem (CVRP) is proposed as a first attempt to solve the problem which minimizes total traveling of all the vehicles. Since the CVRP is known to be NP-hard, the solution method cannot obtain a solution to the model. Therefore an exact algorithm which is a kind of set-covering-based algorithm is proposed next. The CVRP is modeled as a set covering (SC) problem. Then column generation (CG) method is applied to the linear relaxation of the SC problem. The branch-and-price algorithm is utilized in finding an integer solution on the solution of the CG procedure. Numerical experimentations reveals that exact algorithm is slower, and fails finding a solution to larger size problems. Consequently a heuristic is developed as a generalization of petal algorithm. Initialization of this algorithm requires using some Traveling Salesman Problem (TSP) construction heuristics for finding a TSP tour, and a TSP improvement heuristic further improves the TSP tour. Then Petal Algorithm is applied to find all of the feasible petal routes to the TSP tour obtained. SP model helps the petal routes to find the best VRP routes. When the best VRP route is found, a VRP improvement heuristic attempts improving the VRP route. Finally, the number of delivery vehicles required and the vehicle routes are determined for the glass manufacturing firm

Bu tezde bir cam üretim firmasının dağıtım ve taşıma problemini çözmek için bir gerçek algoritma ve bir sezgisel yöntem geliştirilmiştir. İlk olarak yapılan yolu azaltmak amacıyla Kapasiteli Araç Rotalama Problemi (KARP) olarak modellenebilen bir model kurulmuştur. KARP NP-zor olarak bilinmektedir, bu nedenle kurulan model çözülememektedir. Bu yüzden bir tür küme kaplama temelli gerçek bir algoritma geliştirilmiştir. Bu algoritma için KARP, bir küme kaplama problemi olarak modellenmi ştir. Daha sonra sütun üretme methodu küme kaplama probleminin doğrusal gevşemesine uygulanmıştır. Bir tam sayılı çözüm bulabilmek için Dallandır -ve- Fiyatlandır yaklaşımı uygulanmıştır. Gerçek algoritmasının yavaş çalıştığı ve büyük problemler için sonuç almanın zor olduğu görülmütür. Bu nedenle petal algoritması geliştirilmiştir. Başlangıçta Gezgin Satıcı Problemi (GSP) yapım sezgisel yöntemleri kulanılarak bir GSP turu bulunmuştur ve GSP geliştirme sezgisel yöntemleri kullanılarak geliştirilmiştir. Petal algoritması uygulanmıştır. Küme bölüntüleme modeli en iyi ARP rotasını bulmuştur. ARP rotasını geliştirmek için ARP geliştirme sezgisel yöntemleri uygulanmıştır. Bütün bunların sonucunda cam üretim firmasının araçlarının yaptığı yol miktarı , kullanılan araç sayısı ve araçların rotaları belirlenmiştir