Investigating of Hybrid Meta-Heuristics to Solve the Large-Scale Multi-Source Weber Problems and Performance Measuring of them with Statistical Tests

Investigating of Hybrid Meta-Heuristics to Solve the Large-Scale Multi-Source Weber Problems and Performance Measuring of them with Statistical Tests

Abdolsalam Ghaderi (University of Kurdistan, Iran)
DOI: 10.4018/978-1-4666-2086-5.ch006
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

The location–allocation problems are a class of complicated optimization problems that requires finding sites for m facilities and to simultaneously allocate n customers to those facilities to minimize the total transportation costs. Indeed, these problems, belonging to the class NP-hard, have a lot of local optima solutions. In this chapter, three hybrid meta-heuristics: genetic algorithm, variable neighborhood search and particle swarm optimization, and a hybrid local search approach. These are investigated to solve the uncapacitated continuous location-allocation problem (multi-source Weber problem). In this regard, alternate location allocation and exchange heuristics are used to find the local optima of the problem within the framework of hybrid algorithms. In addition, some large-scale problems are employed to measure the effectiveness and efficiency of hybrid algorithms. Obtained results from these heuristics are compared with local search methods and with each other. The experimental results show that the hybrid meta-heuristics produce much better solutions to solve large-scale problems. Moreover, the results of two non-parametric statistical tests detected a significant difference in hybrid algorithms such that the hybrid variable neighborhood search and particle swarm optimization algorithm outperform the others.
Chapter Preview
Top

Introduction

Facility location theory involves a wide range of problems that share certain common elements. The first paper in this field was introduced by Weber (1909). After that, significant research has been carried out and many models with different assumptions have been introduced in this area of science. The literature on facility location theory is rich, and, since Weber’s work, many papers have been published that provide admirable introductions and reviews of the development in this field. One may refer to survey papers in this area such as (Klose and Drexl, 2005; Melo et al., 2009; ReVelle et al., 2008). In these survey papers, various strategies were employed to classify the facility location models based on different issues like discrete vs. continuous problems, deterministic vs. probabilistic problems, dynamic vs. static models and so on. P-median, P-center, covering location, hub location and location-allocation problems are just a few basic models in the literature that has been advocated most of research in this area of science. Various extensions of these models with emerging the real world assumptions like uncertainty in parameters, maximum available budget for investment in facilities and capacity constraints have been also proposed in the literature. Moreover, due to the high complexity of most models, different optimization approaches were presented to find the optimal or near-optimal solution.

The location-allocation problem, as a well known basic problem, is one of the toughest facility location problems that comprise of two main decisions: where to locate the central facilities (Location); and which subsets of the demand should be served from each facility (Allocation). Therefore, the objective of location-allocation problem is to locate m facilities and to simultaneously allocate n customers to those facilities to minimize the total transportation costs. n customers are located at fixed locations with associated discrete demands. Supply centres such as plants and warehouses may constitute the facilities while retailers and dealers may be considered as demand points (Aras et al., 2006). These problems occur in many practical settings where facilities provide a homogeneous service, such as the location of plants, warehouses, retail outlets, and public facilities (Jabalameli and Ghaderi, 2008).

The Euclidean uncapacitated location allocation problem is also known as the Multisource Weber Problem (MWP). Under the assumption that there are no capacity constraints on the new facilities, it can be shown that the demand at each point is satisfied by the nearest facility at minimum cost. This property is known as single assignment property and could be found in (Krarup and Pruzan, 1983). In the general case, most single-facility location problems are convex, and the optimal solutions can be developed through either optimal algorithms or some heuristics (Cooper, 1964). However, multi-facility location problems are non-convex and nonlinear, and known algorithms cannot solve large scale problems optimally. Cooper (1963) proves that the objective function of this problem is neither concave nor convex, and may contain several local minima. Hence, the multisource Weber problem falls in the realm of global optimization problems. Due to Non-deterministic Polynomial-time hard (NP-hard) nature of the problem, exact solution approaches are not able to solve the problem in realistically size and heuristic methods have been shown to be the best way to tackle the larger problems. Megiddo and Supowit (1984) represented the problem as an enumeration of the Voronoi partitions of the customer set and proved its NP-hardness. To tackle to these type of optimization models, modern heuristics such as Simulated Annealing (SA), Tabu Search (TS), Genetic Algorithm (GA), variable neighborhood search (VNS), and Ant Systems increase the chance of avoiding local optimality (Brimberg and Salhi, 2005).

Complete Chapter List

Search this Book:
Reset