Applications – OR and Management Sciences

Cluster branching for vehicle routing problems

  • Joao Marcos P Silva
  • Eduardo Uchoa
  • Anand Subramanian
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming Tags , , ,

    This article introduces Cluster Branching, a novel branching strategy for exact algorithms solving Vehicle Routing Problems (VRPs). While branching is crucial for the efficiency of branch-and-bound-based algorithms, existing branching types such as Edge Branching, CutSet Branching, and Ryan&Foster Branching have their limitations. The proposed branching strategy aggregates multiple edge variables into higher-level decision structures corresponding … Read more

    Computational Methods for the Household Assignment Problem

  • Ulf Friedrich
  • Lucas Moschen
  • Ralf Münnich
  • Martin Schmidt
    • Categories Applications - OR and Management Sciences, Approximation Algorithms, Integer Programming Tags , , , ,

    We consider the household assignment problem as it occurs in the geo-referencing step of spatial microsimulation models. The resulting model is a maximum weight matching problem with additional side constraints. For real-world instances such as the one for the city of Trier in Germany, the number of binary variables exceeds 10^9, and the resulting instances … Read more

    Routing a fleet of unmanned aerial vehicles: a trajectory optimisation-based framework

  • Walton P. Coutinho
  • Jörg Fliege
  • Maria Battarra
  • Anand Subramanian
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Systems governed by Differential Equations Optimization Tags , ,

    We consider an aerial survey operation in which a fleet of unmanned aerial vehicles (UAVs) is required to visit several locations and then land in one of the available landing sites while optimising some performance criteria, subject to operational constraints and flight dynamics. We aim to minimise the maximum flight time of the UAVs. To … Read more

    A Toll-Setting Problem with Robust Wardrop Equilibrium Conditions Under Budgeted Uncertainty

  • Yasmine Beck
  • Martine Labbé
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Robust Optimization, Transportation Tags , , , ,

    We consider the problem of determining optimal tolls in a traffic network in which a toll-setting authority aims to maximize revenues and the users of the network act in the sense of Wardrop’s user equilibrium. The setting is modeled as a mathematical problem with equilibrium constraints and a mixed-integer, nonlinear, and nonconvex reformulation is presented … Read more

    Incorporating Service Reliability in Multi-depot Vehicle Scheduling: A Chance-Constrained Approach

  • Margarita P Castro
  • Merve Bodur
  • Amer Shalaby
    • Categories Cutting Plane Approaches, Stochastic Programming, Transportation Tags , , ,

    The multi-depot vehicle scheduling problem (MDVSP) is a critical planning challenge for transit agencies. We introduce a novel approach to MDVSP by incorporating service reliability through chance-constrained programming (CCP), targeting the pivotal issue of travel time uncertainty and its impact on transit service quality. Our model guarantees service reliability measured by on-time performance (OTP), a … Read more

    Robustness Analysis for Adaptive Optimization With Application to Industrial Decarbonization in the Netherlands

  • Justin Starreveld
  • Dick den Hertog
  • Jaron Davelaar
    • Categories Applications - OR and Management Sciences, Energy, Robust Optimization Tags , , ,

    Robustness analysis assesses the performance of a particular solution under variation in the input data. This is distinct from sensitivity analysis, which assesses how variation in the input data changes a model’s optimal solution. For risk assessment purposes, robustness analysis has more practical value than sensitivity analysis. This is because sensitivity analysis, when applied to … Read more

    Efficient Project Scheduling with Autonomous Learning Opportunities

  • Alessandro Hill
  • Thomas Vossen
    • Categories Combinatorial Optimization, Scheduling

    We consider novel project scheduling problems in which the experience gained from completing selected activities can be used to accelerate subsequent activities. Given a set of potential learning opportunities, our model aims to identify the opportunities that result in a maximum reduction of the project makespan when scheduled in sequence. Accounting for the impact of … Read more

    Counterfactual Explanations for Linear Optimization

  • Jannis Kurtz
  • Ş. İlker Birbil
  • Dick den Hertog
    • Categories Applications - OR and Management Sciences, Linear Programming Tags , , ,

    The concept of counterfactual explanations (CE) has emerged as one of the important concepts to understand the inner workings of complex AI systems. In this paper, we translate the idea of CEs to linear optimization and propose, motivate, and analyze three different types of CEs: strong, weak, and relative. While deriving strong and weak CEs … Read more

    Relay-Hub Network Design for Consolidation Planning Under Demand Variability

  • Onkar Anand Kulkarni
  • Mathieu Dahan
    • Categories Branch and Cut Algorithms, Supply Chain Management, Transportation Tags , , , , , ,

    Problem description: We study the problem of designing large-scale resilient relay logistics hub networks. We propose a model of Capacitated Relay Network Design under Stochastic Demand and Consolidation-Based Routing (CRND-SDCR), which aims to improve a network’s efficiency and resilience against commodity demand variability through integrating tactical decisions. Methodology: We formulate CRND-SDCR as a two-stage stochastic … Read more