期刊
COMPUTERS & OPERATIONS RESEARCH
卷 127, 期 -, 页码 -出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2020.105136
关键词
Hub location; Mixed integer programming; Heuristics; Lagrangian relaxation; Profit-maximizing; Benders decomposition
类别
资金
- National Key R&D Program of China [2018AAA0101705]
- National Natural Science Foundation of China [71872092]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据