4 Presentations

• 
  03:30 PM - 03:55 PM

  Anytime Optimization Approach for Dynamic Dial-a-Ride Problem

  • Elahe Amiri, presenter, Polytechnique Montréal
  • Antoine Legrain, Polytechnique Montréal
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal

  This study introduces an anytime optimization approach for the online Dial-a-Ride Problem within large-scale, real-time ride-sharing systems. Unlike traditional algorithms that rely on fixed-time epochs to batch requests, our method employs a rolling-horizon strategy with flexible time epochs. This hybrid approach effectively combines the strengths of optimization batch methods and smaller batch sizes, delivering fast and efficient solutions. Our approach utilizes a column generation-based framework enhanced with accelerated techniques for solving pricing subproblems. This enables rapid re-optimization and the creation of high-quality dispatching plans under dynamic conditions. By dynamically adjusting time epochs based on actual computation times, the system maintains high responsiveness while minimizing passenger waiting times. Extensive experiments conducted on large-scale New York City taxi data demonstrate that our method significantly enhances service quality compared to existing techniques. It proves highly effective in handling thousands of trip requests per hour, making it well-suited for large-scale and dynamic ride-sharing environments.

• 
  03:55 PM - 04:20 PM

  A relax-fix-and-exclude algorithm for an MINLP problem with multilinear interpolations

  • Bruno Machado Pacheco, presenter, Université de Montréal, CIRRELT
  • Pedro Marcolin Antunes, DAS, UFSC
  • Eduardo Camponogara, DAS, UFSC
  • Laio Oriel Seman, DAS, UFSC
  • Vinícius Ramos Rosa, Petrobras Research Center
  • Bruno Ferreira Vieira, Petrobras Research Center
  • Cesar Longhi, Petrobras Research Center

  This paper introduces a novel approach for solving Mixed-Integer Nonlinear Programming (MINLP) problems with multilinear interpolations of look-up tables. These problems arise when objective or constraints contain black-box functions only known at a finite set of evaluations on a predefined grid. We derive a piecewise-linear relaxation for the nonlinear constraints resulting from the multilinear interpolations used to approximate the black-box functions. Supported by the fact that our proposed relaxation defines the convex hull of the original problem, we propose a solution method that iteratively solves the MILP relaxation and refines the solution space through variable fixing and exclusion strategies. This approach ensures convergence to an optimal solution, which we demonstrate, while maintaining computational efficiency. We apply the proposed algorithm to a real-world offshore oil production optimization problem. In comparison to the Gurobi solver, our algorithm was able to find the optimal solution at least four times faster, and to consistently provide better incumbents under limited time.

• 
  04:20 PM - 04:45 PM

  Branch-and-Bound Algorithms for L0-norm Problems

  • Théo Guyard, presenter, Scale-AI Chair, MAGI Department, Polytechnique Montréal

  Optimization problems involving the L0-norm arise in various fields, including machine learning, operations research, and Statistics, among others. Despite their practical interest, they have not been widely adopted by practitioners since they are NP-hard. However, recent contributions from the discrete optimization community have proposed modern solution methods to tackle them, opening new application perspectives. In this presentation, we will show how specialized Branch-and-Bound algorithms can be devised to tackle L0-norm optimization problems. Specifically, we will discuss how the key components of these solution methods can be implemented in a generic and efficient manner. Finally, we will highlight ongoing research directions in L0-norm optimization and the different research communities contributing to this field.

• 
  04:45 PM - 05:10 PM

  Road Train Logistics with Synchronization: Optimizing Multi-trip Urban Delivery

  • Esteban Ogazón, presenter, Université Laval
  • Maryam Darvish, Université Laval
  • Hani Zbib, ESG - UQAM
  • Jacques Renaud, Université Laval, CIRRELT

  Road trains, vehicles with a tractor pulling multiple trailers, provide an efficient way to move goods from a central depot to urban areas. Yet, urban traffic rules and strict delivery schedules create complex logistical challenges. This study presents a new optimization problem focused on road train logistics, aiming to streamline multi-trip deliveries with a limited fleet of tractors. Unlike typical models that separate long-haul and local delivery fleets, our approach uses the same tractors for both, adapting their configurations at intermediate terminals to meet urban restrictions while ensuring timely deliveries. We develop a practical model that simplifies the coordination of trailer movements and truck routes, capturing key operations like attaching or detaching trailers and managing multiple trips. Testing on existing data, we explore how fleet size and work shift length affect performance, offering insights for logistics managers. This work enhances optimization techniques for transportation networks by tackling synchronization and flexibility issues, with potential applications in urban delivery and resource planning.