An Iterative Local Search Based hybrid algorithm for the service area problem

摘要: This article presents a hybrid algorithm for the service area problem. The design of service areas is one of the essential issues in providing efficient services in both the public and private sectors. For a geographical region with a number of small spatial units, the service area problem is to assign the service-demand units to the service-supply units such that each facility has a service area. The basic criteria for the service areas are the highest service accessibility, the contiguous service areas, and that the service demand does not exceed the service supply in each service area. A hybrid algorithm for the service area problem is proposed by extending iterative local search (ILS) algorithm with three schemes: population-based ILS, variable neighborhood descent (VND) search, and set partitioning. The performance of the algorithm was tested using 60 well-designed instances. Experimentation showed that the instances could be solved effectively and efficiently. The solutions found by the hybrid algorithm approximate optimal solutions or the lower bounds with an average gap of 0.15%.