Heuristic algorithms for the single allocation p-hub center problem with routing considerations

Zühal Kartal, Mohan Krishnamoorthy, Andreas T. Ernst

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Given a network with n nodes, the p-hub center problem locates p hubs and allocates the remaining non-hub nodes to the hubs in such a way that the maximum distance (or time) between all pairs of nodes is minimized. Commonly, it is assumed that a vehicle is available to operate between each demand center and hub. Thus traditional p-hub center models assume that vehicles do not visit more than one non-hub node. However, in many-to-many distribution systems, there are some cases where nodes do not have enough demand to justify direct connections between the non-hub nodes and the hubs. This results in unnecessarily increasing the total number of vehicles on the network. Therefore, the optimal hub network design ought to include location-allocation and routing decisions simultaneously to form the routes among the nodes allocated to the same hubs. In this paper, through the observations from real-life hub networks, we introduce the p-hub center and routing network design problem (pHCVRP) and propose a mixed integer programming (MIP) formulation to model this problem formally. The aim is to locate p hubs, allocate demand centers to the hubs and determine the routes of vehicles for each hub such that the maximum travel time between all origin-destination pairs is minimized. We prove that pHCVRP is NP-hard and therefore only very small instances can be solved to optimality using a MIP solver. Hence, we develop two heuristics based on ant colony system (ACS) and discrete particle swarm optimization (DPSO) to obtain solutions for realistic instance sizes. Our design of the DPSO is quite different to the standard DPSO methods. In our DPSO, we combine concepts from simulated annealing (SA) and ACS to update the particles. We also use iterated local search (ILS) as a baseline algorithm to observe the improvements from a pure local search through more complex algorithms. We test the performance of the heuristics that we develop on the Turkish network and Australia Post data set and compare the performance of these methods.

Original languageEnglish
Pages (from-to)99–145
Number of pages47
JournalOR Spectrum
Volume41
Issue number1
DOIs
Publication statusPublished - Mar 2019

Keywords

  • Ant colony optimization
  • Discrete particle swarm optimization
  • Hub location
  • p-hub center and routing
  • Vehicle routing

Cite this

Kartal, Zühal ; Krishnamoorthy, Mohan ; Ernst, Andreas T. / Heuristic algorithms for the single allocation p-hub center problem with routing considerations. In: OR Spectrum. 2019 ; Vol. 41, No. 1. pp. 99–145.
@article{0a1d90bee9e848ad93cbd6763bbeb2b4,
title = "Heuristic algorithms for the single allocation p-hub center problem with routing considerations",
abstract = "Given a network with n nodes, the p-hub center problem locates p hubs and allocates the remaining non-hub nodes to the hubs in such a way that the maximum distance (or time) between all pairs of nodes is minimized. Commonly, it is assumed that a vehicle is available to operate between each demand center and hub. Thus traditional p-hub center models assume that vehicles do not visit more than one non-hub node. However, in many-to-many distribution systems, there are some cases where nodes do not have enough demand to justify direct connections between the non-hub nodes and the hubs. This results in unnecessarily increasing the total number of vehicles on the network. Therefore, the optimal hub network design ought to include location-allocation and routing decisions simultaneously to form the routes among the nodes allocated to the same hubs. In this paper, through the observations from real-life hub networks, we introduce the p-hub center and routing network design problem (pHCVRP) and propose a mixed integer programming (MIP) formulation to model this problem formally. The aim is to locate p hubs, allocate demand centers to the hubs and determine the routes of vehicles for each hub such that the maximum travel time between all origin-destination pairs is minimized. We prove that pHCVRP is NP-hard and therefore only very small instances can be solved to optimality using a MIP solver. Hence, we develop two heuristics based on ant colony system (ACS) and discrete particle swarm optimization (DPSO) to obtain solutions for realistic instance sizes. Our design of the DPSO is quite different to the standard DPSO methods. In our DPSO, we combine concepts from simulated annealing (SA) and ACS to update the particles. We also use iterated local search (ILS) as a baseline algorithm to observe the improvements from a pure local search through more complex algorithms. We test the performance of the heuristics that we develop on the Turkish network and Australia Post data set and compare the performance of these methods.",
keywords = "Ant colony optimization, Discrete particle swarm optimization, Hub location, p-hub center and routing, Vehicle routing",
author = "Z{\"u}hal Kartal and Mohan Krishnamoorthy and Ernst, {Andreas T.}",
year = "2019",
month = "3",
doi = "10.1007/s00291-018-0526-2",
language = "English",
volume = "41",
pages = "99–145",
journal = "OR Spectrum",
issn = "0171-6468",
publisher = "Springer-Verlag London Ltd.",
number = "1",

}

Heuristic algorithms for the single allocation p-hub center problem with routing considerations. / Kartal, Zühal; Krishnamoorthy, Mohan; Ernst, Andreas T.

In: OR Spectrum, Vol. 41, No. 1, 03.2019, p. 99–145.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Heuristic algorithms for the single allocation p-hub center problem with routing considerations

AU - Kartal, Zühal

AU - Krishnamoorthy, Mohan

AU - Ernst, Andreas T.

PY - 2019/3

Y1 - 2019/3

N2 - Given a network with n nodes, the p-hub center problem locates p hubs and allocates the remaining non-hub nodes to the hubs in such a way that the maximum distance (or time) between all pairs of nodes is minimized. Commonly, it is assumed that a vehicle is available to operate between each demand center and hub. Thus traditional p-hub center models assume that vehicles do not visit more than one non-hub node. However, in many-to-many distribution systems, there are some cases where nodes do not have enough demand to justify direct connections between the non-hub nodes and the hubs. This results in unnecessarily increasing the total number of vehicles on the network. Therefore, the optimal hub network design ought to include location-allocation and routing decisions simultaneously to form the routes among the nodes allocated to the same hubs. In this paper, through the observations from real-life hub networks, we introduce the p-hub center and routing network design problem (pHCVRP) and propose a mixed integer programming (MIP) formulation to model this problem formally. The aim is to locate p hubs, allocate demand centers to the hubs and determine the routes of vehicles for each hub such that the maximum travel time between all origin-destination pairs is minimized. We prove that pHCVRP is NP-hard and therefore only very small instances can be solved to optimality using a MIP solver. Hence, we develop two heuristics based on ant colony system (ACS) and discrete particle swarm optimization (DPSO) to obtain solutions for realistic instance sizes. Our design of the DPSO is quite different to the standard DPSO methods. In our DPSO, we combine concepts from simulated annealing (SA) and ACS to update the particles. We also use iterated local search (ILS) as a baseline algorithm to observe the improvements from a pure local search through more complex algorithms. We test the performance of the heuristics that we develop on the Turkish network and Australia Post data set and compare the performance of these methods.

AB - Given a network with n nodes, the p-hub center problem locates p hubs and allocates the remaining non-hub nodes to the hubs in such a way that the maximum distance (or time) between all pairs of nodes is minimized. Commonly, it is assumed that a vehicle is available to operate between each demand center and hub. Thus traditional p-hub center models assume that vehicles do not visit more than one non-hub node. However, in many-to-many distribution systems, there are some cases where nodes do not have enough demand to justify direct connections between the non-hub nodes and the hubs. This results in unnecessarily increasing the total number of vehicles on the network. Therefore, the optimal hub network design ought to include location-allocation and routing decisions simultaneously to form the routes among the nodes allocated to the same hubs. In this paper, through the observations from real-life hub networks, we introduce the p-hub center and routing network design problem (pHCVRP) and propose a mixed integer programming (MIP) formulation to model this problem formally. The aim is to locate p hubs, allocate demand centers to the hubs and determine the routes of vehicles for each hub such that the maximum travel time between all origin-destination pairs is minimized. We prove that pHCVRP is NP-hard and therefore only very small instances can be solved to optimality using a MIP solver. Hence, we develop two heuristics based on ant colony system (ACS) and discrete particle swarm optimization (DPSO) to obtain solutions for realistic instance sizes. Our design of the DPSO is quite different to the standard DPSO methods. In our DPSO, we combine concepts from simulated annealing (SA) and ACS to update the particles. We also use iterated local search (ILS) as a baseline algorithm to observe the improvements from a pure local search through more complex algorithms. We test the performance of the heuristics that we develop on the Turkish network and Australia Post data set and compare the performance of these methods.

KW - Ant colony optimization

KW - Discrete particle swarm optimization

KW - Hub location

KW - p-hub center and routing

KW - Vehicle routing

UR - http://www.scopus.com/inward/record.url?scp=85049948347&partnerID=8YFLogxK

U2 - 10.1007/s00291-018-0526-2

DO - 10.1007/s00291-018-0526-2

M3 - Article

VL - 41

SP - 99

EP - 145

JO - OR Spectrum

JF - OR Spectrum

SN - 0171-6468

IS - 1

ER -