Abstracts Track 2025


Area 1 - Methodologies and Technologies

Nr: 5
Title:

An Empiric Complexity Analysis of Complexity in Integer Programming

Authors:

Ivan Derpich

Abstract: This research aims to explain the intrinsic difficulty of integer programming instances by using empirical measures of complexity based on the geometry of the polyhedron associated with the constraints of the linear programming problem generated by the relaxation of the integer variable condition. The variables used are associated with certain integer width dimensions of these problems and we try to explain the number of nodes visited by the B&B and the CPU time spent in solving the problems. The experimental design was validated with linear regression and correlations were found to be of more than 60% in most cases. This research aims to explain the intrinsic difficulty of integer programming instances by using empirical measures of complexity based on the geometry of the polyhedron associated with the constraints of the linear programming problem generated by the relaxation of the integer variable condition. The variables used are associated with certain integer width dimensions of these problems and we try to explain the number of nodes visited by the B&B and the CPU time spent in solving the problems. The experimental design was validated with linear regression and correlations above 60% were found in most cases. This is a half-way research, these first results show good correlations, but we intend to build a branching tree in which in each branch we can estimate separately the number of nodes to be branched. In this way the branch with the fewest nodes could be chosen to branch first.

Nr: 22
Title:

Stochastic Casualty Response Planning with Operational Details

Authors:

Michel Gendreau and Hossein Hashemi Doulabi

Abstract: In this study, we propose a two-stage stochastic programming model to consider patients with multiple injuries in casualty response planning problems with uncertain demands and hospital bed capacity. We concentrate on locating Alternative Care Facilities (ACFs) and aim to assign different types of resources in the first stage. Then, in the second stage, we allocate patients with multiple injuries to either ACFs or hospitals based on the availability of resources. We apply the L-shaped algorithm and its branch-and-cut (B&C) implementation to solve large-sized problems. To further enhance the efficiency of these algorithms, we incorporate several accelerator techniques, including Benders dual decomposition and lower bounding functional. Extensive computational results show that these features have led to a dramatic improvement in the B&C algorithm performance.

Nr: 63
Title:

Battery Electric Bus Scheduling with Multiple Charging Technologies and Infrastructure Location Decisions

Authors:

Yulitza Yazmin Jacobo, Omar Jorge Ibarra-Rojas and Dr. Diana L Huerta-Muñoz

Abstract: Public transportation provides a more environmentally sustainable alternative to private vehicles. Well-designed public transportation systems can also foster the use of renewable energies and cleaner technologies, further enhancing their environmental benefits. Optimizing these systems requires a comprehensive approach that considers factors such as infrastructure design, network configuration, passenger flow management, vehicle allocation, and driver scheduling. An integrated consideration of these aspects can improve the efficiency, sustainability, and user satisfaction of public transportation, contributing to more sustainable and livable cities. In this study, we address the Battery Electric Bus Scheduling problem, extending it to a multi-depot context and incorporating various charging technologies, specifically depot and on-route charging. Notably, on-route charging must occur while buses are in service, meaning that prolonged charging times negatively impact the user experience and are therefore restricted. Additionally, our optimization framework includes strategic decisions regarding the placement of charging stations. The objective is to minimize operational costs, accounting for fleet size, frequency of charging actions, and the required charging infrastructure. We formulate this problem as a Mixed-Integer Nonlinear Program (MINLP) and test our model on scenarios based on a transit network in Chile. Numerical results reveal that the model is intractable for real-size instances; however, we solve a simplified version of the problem to validate that interlining strategies can significantly reduce costs. Finally, we propose a metaheuristic optimization approach to tackle real-size instances.

Nr: 83
Title:

Collaborative Logistics for Retail Delivery Using Game Theory Approaches and Auction Mechanism

Authors:

Chefi Triki, Huy Nguyen and Tri-Dung Nguyen

Abstract: LLast-mile delivery systems are critical in the supply chain management and are evolving to handle increasing volumes of orders. The sector is in the process of being transformed from traditional offline stores to modern online sales channels. A significant challenge is to ensure seamless integration among these channels to consistently meet customers demands. Retail operations need restructuring to meet complex customer demands, with delivery playing a key role. This study examines how logistics service providers can collaborate, forming coalitions to exchange delivery requests, which reduces costs and increases profits. Collaborations occur via the auction mechanisms, allowing participants to bid for profitable contracts in order to exchange delivery requests. This research focuses on applying the combinatorial auction mechanism in retail logistics to assist carriers in addressing the bid generation problem (BGP), enabling them to identify feasible and profitable bundles of contracts to be exchanged with other carriers in the coalition. In the context of combinatorial auction, bidders submit one or multiple bids including each a bundle of contracts and its associated price. Then the auction clearing process should follow the all-or-nothing rule, i. e. every submitted bid should be accepted/rejected entirely with all its contracts. Even though this combinatorial aspect makes the BGP very complex, it allows the carriers to take advantage of the synergy present among the different contracts. The BGP consists, indeed, in efficiently embedding the most promising set of auctioned contracts within the carrier’s existing delivery network with the aim of reducing the empty trucks movements and generating additional profits. The BGP also involves the pricing aspect that entails the determination of the most appropriate price for each bundle of contracts (bid) such a way to ensure not only profitability but also to result successful within the highly competitive auction context. In previous studies, significant methodological improvements have been achieved to help carriers addressing several subproblems related to the BGP, specifically the routing problem, the bundle generation problem and the pricing problem. In this study we aim at integrating all the three subproblems within the same optimization framework. The integrated problem becomes even more complex when considering the uncertainty related to the behavour of the competitors while determining their bidding prices. Previous approaches tackled such a stochastic variant of the BGP through estimating the clearing prices using probabilistic or recourse models. In this study we investigate the application of the game theory to create an efficient bidding and pricing mechanism. This integration enhances the carriers’ capability to address the complexities of the BGP considering the dynamic and competitive environment characterizing the last-mile delivery systems through auction collaboration. By applying game-theoretic principles, our approach ensures that each carrier can independently determine the most convenient bundles of contracts and their bidding prices while accounting for strategic interactions with other participants. A stochastic mathematical model for the BGP is developed to help carriers determine optimal bidding strategies in order to increase their chances of being successful in the auctions.

Area 2 - Applications

Nr: 87
Title:

A Network Approach to Scope 3 Emissions

Authors:

Nicolás Romero Díaz, David Veredas, Maxi Udenio and Wim Van Hyfte

Abstract: Scope 3 emissions constitute the majority of a company’s greenhouse gas emissions but are notoriously difficult to measure due to data quality and coverage issues. To address these challenges, we develop a methodology that uses Scope 1 and 2 emissions, as well as mathematical properties of complex networks, to estimate a company’s upstream and downstream emissions. Our model is constructed under the reasoning that, in a closed economy, a company’s indirect emissions result from the direct emissions of clients, partners, and suppliers in the supply chain. As a result, calculating indirect emissions can be reframed as a question of attribution of direct emissions in a client-supplier network. This fact informs the two assumptions needed for constructing our model: First, we assume that we have complete knowledge of business-to-business (B2B) transactions among firms in a client-supplier network. Second, we assume that we observe all Scope 1 and 2 emissions of the companies in this network. This initial derivation of our model represents the ideal case where transaction network data and environmental data are fully available. For this reason, we refer to this as the Full Information scenario. Unfortunately, the conditions for this scenario are seldom achieved in practice. The breakdown of our assumptions motivates a second, less strict version of the model. In this second version, we relax the requirement of knowing the values of all B2B transactions between companies. Instead, this requirement is simplified to a binary Yes or No indicator of whether two companies are engaged in a commercial transaction. Two main implications arise from this change of definition. In the Full Information scenario, the B2B transaction data was used to assign the weight to each client (supplier) represented in a company’s downstream (upstream) emissions. Since the information on B2B data is replaced by a binary indicator, this will result in all clients (suppliers) receiving an equal weight in our calculations. Because of this equal weighting, we refer to this case as the Naïve scenario. On the other hand, since client and supplier disclosure data is much more ubiquitous than B2B transaction values, this change results in a considerable expansion in the number of companies in our sample of production network data. In the final sections of our paper, we present results from an empirical application of our methodology on two datasets: FactSet Supply Chain Relationships for production network data and Trucost for data on Scope 1, 2, and 3 emissions. Our sample includes company data from 2010 until 2021 and produces two main results. First, we find a very high correlation when comparing the results of the Full Information and Naïve scenarios. This result has important implications since it indicates that the more flexible, applicable, Naïve scenario provides a reasonable estimate for the more robust Full Information scenario. Second, we apply the Naïve model to our complete sample. When comparing these results to the reported Scope 3 figures in Trucost, our calculations generate larger estimates in more than 60% of instances. Because of the high correlation between both scenarios, this 60% figure may indicate that the more accurate Full Information scenario might produce a similar result.

Nr: 89
Title:

Patrolling Routes for the Amazonas River Navigation System

Authors:

André Bergsten Mendes, Marcos Vinicius Carvalho Luz, Yanko Verissimo Costa and Carlos Henrique Freitas Zigiotti

Abstract: The Amazon River and its tributaries form an extensive and intricate network spanning over 10,000 km, comprising numerous significant waterways. These rivers are vital for regional connectivity, supporting trade and commerce, and providing essential access to services for local communities. Effective patrolling of these waterways is critical to combating illegal activities, preserving biodiversity, and safeguarding local populations. This research focuses on developing patrolling routes for the Amazon River navigation system, conceptualized as a variation of the Periodic Arc Routing Problem (PARP). The study incorporates various factors, including: 1) One or more bases from which patrol vessels depart and to which they must return. 2) The extended navigation time span, with some routes lasting up to 40 days. 3) Seasonal variations, such as floods and droughts, can restrict route availability. 4) Different visitation frequencies required for each river stretch. 5) Minimum and maximum intervals for visiting arcs, rather than fixed, regular intervals. 6) Each arc has a measure of benefit for being traversed; the greater the benefit, the greater the security risk the arc poses. The problem is modeled as a profit-collection problem, where benefits are derived from monitoring and securing specific arcs. A Mixed Integer Programming (MIP) formulation is proposed and evaluated using real-world data. The model counts the number of times each arc is visited as a means to impose the visiting frequency and control the visiting interval. The model supports decision-making related to the fleet size of patrol vessels. By varying the fleet size, it is possible to assess the benefits of increased patrol frequency. Additionally, the model accommodates scenarios where the current fleet is insufficient to meet the required visitation frequencies. In such cases, it permits infeasible solutions by penalizing those that fail to meet the prescribed frequency requirements.