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

ABSTRACTAN APPLICATION OF THE VEHICLE ROUTING PROBLEM TO A GLASSMANUFACTURING FIRMSeyran, İpekThis thesis presents an exact algorithm and a heuristic method for the delivery and transportation of glassplates for a glass manufacturing firm. A variant of the Capacitated Vehicle Routing Problem (CVRP) isproposed as a first attempt to solve the problem which minimizes total traveling of all the vehicles. Sincethe CVRP is known to be NP-hard, the solution method cannot obtain a solution to the model. Therefore anexact algorithm which is a kind of set-covering-based algorithm is proposed next. The CVRP is modeled asa set covering (SC) problem. Then column generation (CG) method is applied to the linear relaxation of theSC problem. The branch-and-price algorithm is utilized in finding an integer solution on the solution of theCG procedure. Numerical experimentations reveals that exact algorithm is slower, and fails finding asolution to larger size problems. Consequently a heuristic is developed as a generalization of petalalgorithm. 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 TSPtour. Then Petal Algorithm is applied to find all of the feasible petal routes to the TSP tour obtained. SPmodel helps the petal routes to find the best VRP routes. When the best VRP route is found, a VRPimprovement heuristic attempts improving the VRP route. Finally, the number of delivery vehicles requiredand the vehicle routes are determined for the glass manufacturing firm.