A two-leveled multi-objective symbiotic evolutionary algorithm for the hub and spoke location problem

Journal of Advanced Transportation, Winter, 2009 by Kyoung Seok Shin, Jun Hyuk Kim, Yeo Keun Kim

We consider a hub and spoke location problem (HSLP) with multiple scenarios. The HSLP consists of four sub-problems: hub location, spoke location, spoke allocation, and customer allocation. Under multiple scenarios, we aim to provide a set of well-distributed solutions, close to the true Pareto optimal solutions, for decision makers. We present a novel multi-objective symbiotic evolutionary algorithm to solve the HSLP under multiple scenarios. The algorithm is modeled as a two-leveled structure, which we call the two-leveled multi-objective symbiotic evolutionary algorithm (TMSEA). In TMSEA, two main processes imitating symbiotic evolution and endosymbiotic evolution are introduced to promote the diversity and convergence of solutions. The evolutionary components suitable for each sub-problem are defined. TMSEA is tested on a variety of test-bed problems and compared with existing multi-objective evolutionary algorithms. The experimental results show that TMSEA is promising in solution convergence and diversity.

1. Introduction

In logistics environments, network design problems often consist of several sub-problems such as location, allocation, and transportation problems that are tightly interrelated with each other. In tackling such problems, it is critical to use an integrated approach to avoid the sub-optimization of logistics solutions and consequently to increase overall network efficiency.

In this paper, we consider a hub and spoke location problem (HSLP). Hub location problems (HLPs) involve locating a set of fully interconnected facilities called hubs among a potential set of locations, which serve as consolidation and re-routing points for flow between specified origins and destinations, and assigning spokes to the hubs (Campbell, 1994).

In the HSLP addressed here, we take into account the customer nodes that become potential spokes. The spoke locations are therefore selected among the customer locations and the remaining customers are assigned to the spokes. The flow of the customers is transferred to the corresponding spoke by vehicles. The HSLP consists of sub-problems involved in hub and spoke location, and in spoke and customer allocation. We solve the sub-problems simultaneously by using an integrated approach.

At the network design stage, input data such as the amount of flow, fixed and varying costs, and cost parameters are generally uncertain due to a lack of complete knowledge of the future. Kouvelis and Yu (1997) have suggested the robustness approach for such environments, the aim of which is to produce solutions that will have a reasonable objective value under any likely input data scenario to the problem being considered. Let [f.sub.s](x) denote the objective function of the decision vector x under scenario s. When the number of scenarios is l, the objective vector f(x) can be represented as f(x) = ([f.sub.1](x), [f.sub.2](x), ..., [f.sub.l](x)). The problem with multiple scenarios can be transformed into a multi-objective problem. Under multiple scenarios, a decision maker is able to choose one of the Pareto optimal solutions based on individual preference. A Pareto optimal solution is a solution such that no other solutions are superior to the solution in all objectives.

A variety of formulations for the multiple objectives in location problems have been proposed by Current et al. (1990), ReVelle (1993), ReVelle and Laporte (1996), and Fernandez and Puerto (2003). In particular, Fernandez and Puerto (2003) have dealt with scenario analysis for the uncapacitated plant location problem. They have presented an exact and an approximate approach based on dynamic programming to obtain a set of non-dominated solutions.

It is well known that evolutionary algorithms (EAs) are very promising for solving multiple objective optimization problems (Van Veldhuizen and Lamont, 2000). EAs can search for many Pareto optimal solutions in parallel by maintaining a set of solutions. Therefore, in recent years, multi-objective evolutionary algorithms (MOEAs) have received considerable attention from researchers and practitioners (Deb et al., 2000; Zitzler et al., 2001; Tan et al, 2002; Deb et al., 2005). MOEAs aim at finding a set of well-distributed solutions close to the true Pareto optimal solutions, thereby providing multiple good and diverse solutions for decision makers instead of linear objective function aggregation in a subjective manner.

This paper presents a novel multi-objective symbiotic evolutionary algorithm to solve the HSLP under multiple scenarios. The symbiotic evolutionary algorithm, developed in the 1990's, is a search technique that imitates symbiotic evolution in nature, which describes the evolutionary process of different species as a result of each species adapting to other species (Potter, 1997). On application of symbiotic evolutionary algorithms, the different species can be regarded as sub-problems. This leads the algorithm to solve the problem of integrating sub-problems simultaneously. It is well recognized that the algorithm is a promising approach to solving complex and dynamic problems (Potter, 1997; Kim et al., 2000; Kim et al., 2001). Therefore, the symbiotic evolutionary algorithm is adopted in this paper. Note that the HSLP is NP-hard since both a hub location problem and a location-routing problem are NP-hard (O'Kelly, 1987; Dilek and Laura, 1999).