A clustering based heuristic for location routing problems

Abstract

In this thesis we address the location routing problem (LRP) in which vehicle routing and warehouse location/allocation decisions are made simultaneously. LRP deals with determining the optimal number of warehouses as well as their locations while assigning customers to warehouses so that the shortest vehicle routes are achieved. The objective is to minimize total vehicle related costs (fixed vehicle cost and route cost) and the cost of operating the warehouses. To solve this NP-hard problem, we propose a clustering based heuristic approach which consists of three parts. Firstly, we determine the customer clusters based on vehicle capacities, i.e. all customers in the cluster are serviced by the same vehicle. Secondly, we solve a traveling salesman problem for each cluster. Thirdly, we attempt to improve the routes by using local search techniques. Finally, the routed clusters are assigned to warehouses.