Hub Location Allocation Problems and Solution Algorithms

Hub Location Allocation Problems and Solution Algorithms

Peiman A. Sarvari (Istanbul Technical University, Turkey), Fatma Betül Yeni (Istanbul Technical University, Turkey) and Emre Çevikcan (Istanbul Technical University, Turkey)
DOI: 10.4018/978-1-5225-2944-6.ch005

Abstract

The Hub Location-Allocation Problem is one of the most important topics in industrial engineering and operations research, which aims to find a form of distribution strategy for goods, services, and information. There are plenty of applications for hub location problem, such as Transportation Management, Urban Management, locating service centers, Instrumentation Engineering, design of sensor networks, Computer Engineering, design of computer networks, Communication Networks Design, Power Engineering, localization of repair centers, maintenance and monitoring power lines, and Design of Manufacturing Systems. In order to define the hub location problem, the present chapter offers two different metaheuristic algorithms, namely Particle Swarm Optimization or PSO and Differential Evolution. The presented algorithms, then, are applied to one of the hub location problems. Finally, the performances of the given algorithms are compared in term of benchmarking.
Chapter Preview
Top

Introduction

In this chapter, we discuss some services, such as database transaction, movements of people, commodities, information or unfinished parts that take place between an origin-destination pair of nodes. Such pairs of nodes can be found in the domain of a manufacturing site or spread along continents, as each origin-destination pair needs a service different from the other pairs.

Hub location problem is one of the most important topics of location problems. The facility location problem, also known as location analysis or k-center problem is a branch of operations research and computational geometry. Facility location problems try to reduce the costs of operations considering some set of constraints and relevant demands with locating different ranges of facilities. Making decisions for facility location are critically challenging regarding strategic planning for all types of business entities. Property acquisition and establishment are naturally costly so that one can consider facility location and relocation operations as long-term investments. Decision makers are challenging with different geographical, demographical and trending factors for selecting profitable sites. Thus, selection of robust facility locations is an important task, as far as future events are uncertain and unpredictable.

Hub location problem is an extension of the classical facility location problems. Hubs are facilities that operate as consolidating, connecting, and switching points for flows between the stipulated origins and destinations (Farahani et al., 2013). Hubs are also defined as special facilities that serve as switching, transshipping and sorting points in many-to-many distribution systems. The hub location problem is concerned with locating hub facilities and allocating demand nodes to hubs in order to route the traffic between origin–destination pairs (Alumur & Kara, 2008). Many applications are available for the hub location problem, and this section is primarily dedicated to introducing this problem to readers.

In this chapter, we have tried to fit what moves between an origin-destination pair of nodes, like information, people and commodities into the concept of HLP. Basically, each different pair of origin-destination node has to be serviced exclusively. For instance, people traveling from i to j are not interchangeable with those traveling from j to i. In order to have a fully connected network (a network in which all nodes are connected) with N nodes, in which each node can be either an origin or a destination, the number of pairs (i-j pairs which are different from j-i pairs) should be N (N-1). Fig.1 illustrates a network composed of nodes and connections.

Figure 1.

A regular full-connected network with connections between nodes

Assuming that we have different traffic services in this network and that each vehicle can service five origin-destination pairs every day, with 18 vehicles, we will be able to service ten nodes every day. If we set one of the nodes as a hub node and connect it to all the other nodes, which are introduced as spokes, we will have 2(n-1) connections to service all origin-destination node pairs. This network is presented in Figure 2 (Daskin, 1995).

Assume, if there are different traffic services, and if each vehicle can provide service for origin-destination pairs every day, with 18 vehicles, we will be able to service 46 nodes every day. Thus, with fixed traffic resources, we can service more cities with a hub network than with a completely connected network. Multi-hub network is another type of hub and spoke network that is a formation of two or several hubs and spoke networks in which all hubs are fully connected to each other.

Figure 2.

A hub and spoke network

Key Terms in this Chapter

Database Transaction: A unit of work performed within a database management system (Sarvari et al., 2016 AU82: The in-text citation "Sarvari et al., 2016" is not in the reference list. Please correct the citation, add the reference to the list, or delete the citation. ).

Hybrid Manufacturing System: A system is one in which functional layout (generally job-shop type) and cells (manufacturing or assembly) coexist.

Quadratic Integer Programming: A special case of the None Linear Programming, when the objective function is in quadratic form and the constraints are linear.

Metaheuristics: In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimization problem, especially with incomplete or imperfect information or limited computation capacity (Bianchi et al., 2009 AU83: The in-text citation "Bianchi et al., 2009" is not in the reference list. Please correct the citation, add the reference to the list, or delete the citation. ).

Hub: The facilities that are servicing many origin-destination pairs as transformation and tradeoff nodes.

Uncapacitated Single Allocation p-Hub Median Problems (USApHMP): In the classical USApHMP, transportation costs are modeled as linear functions of the transport volume, where a fixed discount factor on hub-hub connections is introduced to simulate economies of scale.

Spoke: A none hub node that is connecting to a hub.

Complete Chapter List

Search this Book:
Reset