4.5 Article

The hub location problem with market selection

Journal

COMPUTERS & OPERATIONS RESEARCH
Volume 127, Issue -, Pages -

Publisher

PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2020.105136

Keywords

Hub location; Mixed integer programming; Heuristics; Lagrangian relaxation; Profit-maximizing; Benders decomposition

Funding

  1. National Key R&D Program of China [2018AAA0101705]
  2. National Natural Science Foundation of China [71872092]

Ask authors/readers for more resources

This study proposes a hub location problem with market selection and introduces a mixed integer programming model along with a subgradient-based Lagrangian relaxation method to solve the problem. The proposed method achieves optimal solutions for small-sized test instances and better solution qualities than the commercial software package for large-sized test instances.
We propose a hub location problem with market selection. The problem has a given number of markets with each market associated with predetermined demand and fixed revenue. The selected market demand has to be shipped from the origin to the destination via a hub-and-spoke system. The overall objective is to maximize the overall margins that are equal to the total revenue of the selected markets minus the total costs, including the leasing costs of hubs, transportation costs, and outsourcing costs. We propose a mixed integer programming model to formulate the problem with service and flow capacity constraints. For this problem, we propose a subgradient-based Lagrangian relaxation method that exploits the rich structure of the Lagrangian subproblems to obtain its objective values and bounds efficiently. Specifically, we treat the Lagrangian subproblems as knapsack problems and solve them by using a dynamic programming method. Furthermore, we propose a polynomial algorithm to quickly generate objective values of the original problem at each iteration of the Lagrangian relaxation. Computational results show that the proposed method can obtain optimal solutions for small-sized test instances and achieve much better solution qualities than the commercial software package (Cplex) for large-sized test instances. The proposed method also achieves better solutions than a Benders decomposition method for the tested instances. (C) 2020 Elsevier Ltd. All rights reserved.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.5
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available