Upgrading nodes in tree-shaped hub location

DOI10.1016/J.COR.2018.10.007MaRDI QIDQ1628119zbMATH OpenOpenAlexWikidataFDO

Authors Víctor Blanco, Alfredo Marín

Publication date 3 December 2018

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.05252

zbMATH Keywords

hub locationspanning treeupgrading

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Discrete location and assignment (90B80) Mixed integer programming (90C11) Programming involving graphs or networks (90C35)

Abstract: In this paper, we introduce the Tree of Hubs Location Problem with Upgrading, a mixture of the Tree of Hubs Location Problem, presented by Contreras et. al (2010), and the Minimum Cost Spanning Tree Problem with Upgraded nodes, studied for the first time by Krumke (1999). In addition to locate the hubs, to determine the tree that connects the hubs and to allocate non-hub nodes to hubs, a decision has to be made about which of the hubs will be upgraded, taking into account that the total number of upgraded nodes is given. We present two different Mixed Integer Linear Programming formulations for the problem, tighten the formulations and generate several families of valid inequalities for them. A computational study is presented showing the improvements attained with the strengthening of the formulations and comparing them.

Recommendations

• The tree of hubs location problem
• Lagrangian and branch-and-cut approaches for upgrading spanning tree problems
• Improving spanning trees by upgrading nodes
• Optimal approaches for upgrading selective obnoxious p-median location problems on tree networks
• Improving spanning trees by upgrading nodes

Cites work

• \(p\)-hub median problem for non-complete networks
• A biased random-key genetic algorithm for the tree of hubs location problem
• A branch‐and‐cut algorithm for the single‐commodity, uncapacitated, fixed‐charge network flow problem
• A quadratic integer program for the location of interacting hub facilities
• An improved Benders decomposition algorithm for the tree of hubs location problem
• Efficient algorithms for the uncapacitated single allocation p-hub median problem
• Exact and heuristic algorithms for the uncapacitated multiple allocation \(p\)-hub median problem
• Exact and heuristic approaches for the cycle hub location problem
• Formulations and decomposition methods for the incomplete hub location network design problem with and without hop-constraints
• scientific article; zbMATH DE number 1803765 (Why is no real title available?)
• Hub arc location problems: I. Introduction and results
• Hub Arc Location Problems: Part II—Formulations and Optimal Algorithms
• Hub network design with single and multiple allocation: A computational study
• Improving Minimum Cost Spanning Trees by Upgrading Nodes
• Integer programming formulations of discrete hub location problems
• Integer Programming: Methods, Uses, Computations
• Lagrangian and branch-and-cut approaches for upgrading spanning tree problems
• MIP models for connected facility location: a theoretical and computational study
• Network hub location problems: The state of the art
• Network upgrading problems
• Networking Policies for Hub-and-Spoke Systems with Application to the Air Transportation System
• The Location of Emergency Service Facilities
• The tree of hubs location problem
• Tight bounds from a path based formulation for the tree of hub location problem
• Tight linear programming relaxations of uncapacitated p-hub median problems
• Tree network design avoiding congestion
• Upgrading Shortest Paths in Networks
• Upgrading the 1-center problem with edge length variables on a tree

Cited in

(16)

• A branch-and-price approach for the continuous multifacility monotone ordered median problem
• A two-level off-grid electric distribution problem on the continuous space
• Planning and design of intermodal hub networks: a literature review
• Multiple allocation tree of hubs location problem for non-complete networks
• Upgrading edges in the maximal covering location problem
• Improving spanning trees by upgrading nodes
• Lowering eccentricity of a tree by node upgrading
• Upgrading edges in the graphical TSP
• The p-median problem with upgrading of transportation costs and minimum travel time allocation
• On hub location problems in geographically flexible networks
• On the complexity of the upgrading version of the maximal covering location problem
• The tree-of-hubs location problem with interhub stopovers
• Some upgrading problems on networks related to eccentricity concept
• Edge downgrades in the maximal covering location problem
• Stability radius and an upgrading model of median location on trees
• The covering tour problem with path upgrades

This page was built for publication: Upgrading nodes in tree-shaped hub location

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1628119)