A Novel Co-Evolutionary Algorithm for Solving a Bilevel Pricing and Hubs Location Problem under a Tree Topology

Víctor Blanco † , José-Fernando Camacho-Vallejo ‡ , and Carlos Corpus ⋆ † Institute of Mathematics (IMAG), Universidad de Granada, Spain ‡ Tecnologico de Monterrey, Escuela de Ingeniería y Ciencias, Monterrey, México ⋆ Centro de Investigación en Ciencias Físico-Matemáticas (CICFIM), Universidad Autó · 2025

Read A Novel Co-Evolutionary Algorithm for Solving a Bilevel Pricing and Hubs Location Problem under a Tree Topology by Víctor Blanco † , José-Fernando Camacho-Vallejo ‡ , and Carlos Corpus ⋆ † Institute of Mathematics (IMAG), Universidad de Granada, Spain ‡ Tecnologico de Monterrey, Escuela de Ingeniería y Ciencias, Monterrey, México ⋆ Centro de Investigación en Ciencias Físico-Matemáticas (CICFIM), Universidad Autó (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-00561.txt.

Introduction

Víctor Blanco, José-Fernando Camacho-Vallejo, and Carlos Corpus design a joint search method for a pricing puzzle in this 2025 paper. A network owner lays out a tree of hub stations and sets fees for using them. A shipper then picks the cheapest way to move goods through that tree.

The owner wants top profit, while the shipper wants least cost, so the puzzle has two layers. The team restates it as one layer, then solves it with twin evolving groups. Each group holds part of the owner's choices, and the shipper's best reply is computed for each layout. Wide tests on three known data sets check how the method performs.

Catalog record

CREATORVíctor Blanco † , José-Fernando Camacho-Vallejo ‡ , and Carlos Corpus ⋆ † Institute of Mathematics (IMAG), Universidad de Granada, Spain ‡ Tecnologico de Monterrey, Escuela de Ingeniería y Ciencias, Monterrey, México ⋆ Centro de Investigación en Ciencias Físico-Matemáticas (CICFIM), Universidad Autó
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE92 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-00561

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Novel Co-Evolutionary Algorithm for Solving a Bilevel Pricing and Hubs Location Problem under a Tree Topology Víctor Blanco † , José-Fernando Camacho-Vallejo ‡ , and Carlos Corpus ⋆ † Institute of Mathematics (IMAG), Universidad de Granada, Spain ‡ Tecnologico de Monterrey, Escuela de Ingeniería y Ciencias, Monterrey, México ⋆ Centro de Investigación en Ciencias Físico-Matemáticas (CICFIM), Universidad Autónoma de Nuevo León, México [email protected] , [email protected] , [email protected] Abstract . This paper introduces the Bilevel Tree-of-Hubs Location Problem with Prices (BTHLPwP). The BTHLPwP is a multiple-allocation hub location problem in which, in addition to determining the nodes and links of a tree-shaped hub backbone network, the prices for using this network must also be set. We assume that two different types of agents make decisions in this problem. On the one hand, one agent (the leader) determines the structure and sets the prices for using the hub backbone network. On the other hand, the other agent (follower) decides on the optimal usage of the network. The leader seeks to maximize its profit, while the follower aims to minimize the costs incurred for using the network to ship their commodities. We present a bilevel optimization formulation for this problem, followed by an equivalent single-level reformulation. Then, we propose a novel Co-Evolutionary Algorithm (Co-EA) to solve three well-known datasets of instances adapted for our problem. The main novelty of the proposed Co-EA lies in the way the co-evolving populations are considered. While traditionally one population focuses on the leader’s solutions and the other on the follower’s, in our approach, each population is associated with a subset of the leader’s decision variables. Consequently, the follower’s optimal reaction is obtained for a specific decision made by the leader, resulting in bilevel feasible solutions. We then analyze the results obtained from extensive computational experimentation using the proposed Co-EA. To validate its performance, we use the best solution found by the Co-EA as a warm-start solution in the single-level reformulation, which is then solved by a general-purpose solver. Additionally, we provide interesting managerial insights regarding the increase in the number of hubs in the backbone network. This research concludes with recommendations for further research on this topic. 1. Introduction Globalization demands dynamic commercial connections that ensure the reliable delivery of commodities to users worldwide. The adequate design of commercial networks is crucial for both companies and users, enhancing their convenience. This type of decision typically involves addressing Hub Location Problems (HLPs), which integrate tools from Network Design and Location Science. In HLPs, the objective is to determine the optimal placement of certain special nodes in a network (hub nodes), which serve as transshipment points for routing commodities. Hub backbone networks provide practical benefits from an operational perspective, as they concentrate flow within a smaller network (the hub backbone network), facilitating efficient delivery monitoring and reducing users’ routing costs. HLPs have garnered significant attention from researchers over the past decade due to their practical relevance and the mathematical and computational challenges they present (see Campbell (1994) ; Contreras and O’Kelly (2019) for further details on hub location). Recently, HLPs have been applied in various systems, including air transportation ( Farahani et al., 2013 ) , postal services ( Bagherinejad et al., 2020 ) , cargo delivery ( Khaleghi and Eydi, 2021 ) , and supply chains for perishable goods ( Eydi et al., 2025 ) . As mentioned earlier, HLPs integrate decisions from Location Science, which determines the optimal positions of hub nodes and links, and Network Design, which facilitates the routing of commodities through the hub backbone network. Location Science focuses on identifying the optimal placement of services to adequately meet user demand. A substantial body of literature addresses various location problems and their solution methodologies. Prominent problems include the Weber Problem Weber (1929) , the Uncapacitated Facility Location Problem Cornuéjols et al. (1983) , the Maximal Covering Location Problem Church and ReVelle (1974) , and the p -median problem Hakimi (1983) . When the placement of services is influenced by routing costs associated with sending flows among users, location problems transition into HLPs, which have received extensive attention in recent years, emerging as an active research area Alumur Alev and Kara (2008) ; Blanco and Puerto (2022) ; Blanco et al. (2023) ; Hekmatfar and Pishvaee (2009) ; Nickel et al. (2001) . Most HLPs assume a complete hub backbone network, though this assumption is often unrealistic when the costs of installing links between hub nodes are disproportionately high. This discrepancy has spurred the exploration of alternative hub backbone network topologies, such as star-star Labbé and Yaman (2008) , cycle Contreras et al. (2017) , tree Contreras et al. (2009) ; Contreras et al. (2010) , or general shapes O’Kelly et al. (2015) ; O’Kelly et al. (2015) . In the Tree-of-Hubs Location Problem (THLP), the hub backbone network is assumed to have a tree structure. This topology is particularly relevant in HLP scenarios where the setup costs for hub links exceed the routing costs, making it advantageous to construct a minimally connected network linking the activated hub nodes. In this paper we analyze the Bilevel Tree-of-Hubs Location Problem with Prices (BTHLPwP). In the BTHLPwP, two hierarchical agents are involved in the decision-making process. The agent with higher hierarchy (leader) determines the design of the tree-of-hubs network (as in the THLP) and sets the prices users must pay for using the links of the hub backbone network. The leader’s objective is to maximize profit, calculated as the total revenue from customer payments minus the maintenance and setup costs. The agent with lower hierarchy (follower) makes decisions on network usage based on the hub backbone network’s structure and the prices set by the leader. Typically, multiple followers are involved in this decision-making process. Their objective is to minimize routing costs for their commodities. In most HLPs, the unitary transportation costs incurred by users are typically assumed to be known and fixed by the decision maker ( Contreras and O’Kelly, 2019 , see e.g.) . In this paper, apart from making decisions about activating hub nodes, establishing links, and routing commodities, we extend the analysis to decide also the prices paid by customers for using the hub links. This is particularly useful when constructing a (physical or virtual) hub backbone network from scratch and the investment made to construct the network want to be recovered. However, if the prices are not adequately stablished, it may have a negative effect, since if the prices are high (as optimal strategy for the decision maker maximizing its profit), the users may decide to use route the commodity by their selves or use the services of a third-party with better prices, being null the return for the leader agent. Thus, finding an equilibrium between the profit received by the leader agent and the costs incurred in the users is far from trivial, and a specialized study is required. We model the BTHLPwP as a Bilevel Optimization Problem. Bilevel optimization is a valuable tool for decision-making in contexts where a predefined hierarchy exists among multiple interacting agents. In these mathematical optimization problems certain constraints are defined by the solutions of another nested optimization problem. In such scenarios, one agent (the leader) makes

Read the complete text