A branch‐and‐cut algorithm for hub network design problems with profits
研究带利润的枢纽网络设计问题，提出路径型公式和Benders分解，开发精确分支切割算法求解，允许每条运输路线使用多个枢纽连接以提高利润。
Abstract Hub network design problems with profits (HNDPPs) extend the classical hub location problems (HLPs), with the profit maximization objective. HNDPPs aim to design a service network with hub nodes and hub links, select the commodities to be served, and determine the transportation routes for the selected commodities. In this article, we allow the transportation route of each commodity to contain more than one hub link, which generalizes existing HNDPPs and is known to be more profitable. A new path‐based formulation is proposed, which is then reformulated in a Benders decomposition fashion, and an exact branch‐and‐cut algorithm is developed to solve the Benders master problem. At the nodes of the enumeration tree, Benders decomposition algorithm is used to solve a linear relaxation of the Benders master problem. When implementing the Benders decomposition algorithm, the special structure of the subproblem is explored, based on which an efficient method is proposed to generate Benders cuts. In addition, refinements and a heuristic strategy are used to speed up the branch‐and‐cut algorithm. Extensive numerical experiments on benchmark instances have been carried out to verify the effectiveness and efficiency of the proposed solution method.