Heuristic methods for continuous capacitated location-allocation and location-routing problems

Abstract

In this work, we consider two problems and develop heuristic methods for theirsolution. The first one is the capacitated continuous location-allocation problem andcan be defined as locating facilities with capacities in order to satisfy the demands of existing customers at the minimum cost. This cost is a function of the distance betweenthe facilities and customers. Distances can be measured as the lp, rectilinear, Euclideanor Squared Euclidean distance. In the capacitated location-allocation problem, if thelocations of the facilities are given, the problem turns into the transportation problem. The solution to the location-allocation problem always occurs in the basic feasiblesolution set of the transportation problem. When the flows are fixed, then singlefacility location problems are obtained each of which can be solved sperately. Usingthe neighborhood structure developed, simulated annealing, threshold accepting and genetic algorithm heuristics are proposed for the solution of the problem.Continuous capacitated location-routing problemis the integration of the locationallocationand vehicle routing problems. Vehicles depart from a facility, serve one ormore customers and return back to the same facility. The objective is the minimization of the total route lengths. The facilities have limited capacity and can be locatedanywhere on the continuous plane. In this thesis, a self organizing map heuristic isproposed for this problem.