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

Zühal Kartal (), Mohan Krishnamoorthy () and Andreas T. Ernst ()
Additional contact information
Zühal Kartal: Anadolu University
Mohan Krishnamoorthy: University of Queensland
Andreas T. Ernst: Monash University

OR Spectrum: Quantitative Approaches in Management, 2019, vol. 41, issue 1, No 4, 99-145

Abstract: 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: Vehicle routing; Hub location; p-hub center and routing; Ant colony optimization; Discrete particle swarm optimization (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s00291-018-0526-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:orspec:v:41:y:2019:i:1:d:10.1007_s00291-018-0526-2

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-018-0526-2

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().