Exact methods for the discrete multiple allocation (r|p) hub-centroid problem. (April 2020)

• Record Type: Journal Article
• Authors: Andrade de Araújo, Antonio Camargo; Roboredo, Marcos Costa; Pessoa, Artur Alves; Pereira, Valdecy
• Is Part Of: Computers & operations research. Volume 116(2020)
• Publication Date: 2020-04
• Subjects: Hub location -- Competitive location -- Branch-and-cut; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2019.104870
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We propose two Mixed Integer Linear Programming Formulations and a branch-and-cut algorithm for the discrete multiple allocation ( r | p ) hub-centroid problem. We prove that the discrete multiple allocation ( r | p ) hub-centroid problem is ∑ 2 p -hard. We show that our algorithm is faster than the exact one present in the literature for most instances. Abstract: In the ( r | p ) hub-centroid problem (( r | p ) HCP ), two noncooperative firms, leader and follower, locate hubs sequentially in order to maximize their own total flow being transported through system. The leader locates p hubs, knowing that the follower will react by locating r hubs. After location decisions, each flow is transported by one hub or a pair of hubs placed by either leader or follower according to the lowest cost criteria. The problem consists of optimizing the leader decision. For the discrete multiple allocation version of the ( r | p ) HCP, we prove that this version is ∑ 2 p -hard, propose for the first time two mixed integer linear programming formulations with a polynomial number of variables and present exact branch-and-cut algorithms to solve the formulations. The algorithms are compared to the best exact one found in the literature, obtaining better results for almost all instances. Furthermore, we present the optimal solution for several open instances.