Authors: | Brimberg, Jack Todosijević, Raca Urošević, Dragan Mladenović, Nenad |
Affiliations: | Computer Science Mathematical Institute of the Serbian Academy of Sciences and Arts |
Title: | Efficient flow models for the uncapacitated multiple allocation p-hub median problem on non-triangular networks | Journal: | Computers and Industrial Engineering | Volume: | 162 | First page: | 107723 | Issue Date: | 1-Dec-2021 | Rank: | ~M21 | ISSN: | 0360-8352 | DOI: | 10.1016/j.cie.2021.107723 | Abstract: | This paper examines the uncapacitated multiple allocation p-hub median problem (UMApHMP) in a general setting where a given network may violate the triangle inequality, thus leading to flow paths with more than two hubs connecting origin-to-destination pairs. We present two improved flow formulations using a new ”augmented graph” that allows a substantial reduction in the number of constraints, and significant improvement in performance of a standard off-the-shelf MILP solver compared to the recent 4-index flow model proposed in Brimberg et al. (2020). Results presented even surpass the performance of specialized algorithms developed for solving the standard ”triangular” case. The linear programming relaxations of the presented models are also investigated. |
Keywords: | Flow formulations | Hub location | Multiple allocation | p-hub | Triangle inequality | Publisher: | Elsevier |
Show full item record
SCOPUSTM
Citations
3
checked on Nov 11, 2024
Page view(s)
20
checked on Nov 11, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.