Network Optimization

Optimizing Drone-Assisted Last-Mile Deliveries: The Vehicle Routing Problem with Flexible Drones

  • Ilke Bakir
  • Gizem Ozbaygin
    • Categories Network Optimization, Transportation

    The ever-widening acceptance and deployment of drones in last-mile distribution continue to increase the need for planning and managing the delivery operations involving drones effectively. Motivated by the growing interest towards drone-assisted last-mile transportation, we study a hybrid delivery system in which (multiple) trucks and (multiple) drones operate in tandem. In particular, we introduce the … Read more

    A note on the Lasserre hierarchy for different formulations of the maximum independent set problem

  • Miguel F. Anjos
  • Youssouf Emine
  • Andrea Lodi
  • Zhao Sun
    • Categories Integer Programming, Linear, Cone and Semidefinite Programming, Network Optimization Tags , , ,

    In this note, we consider several polynomial optimization formulations of the max- imum independent set problem and the use of the Lasserre hierarchy with these different formulations. We demonstrate using computational experiments that the choice of formulation may have a significant impact on the resulting bounds. We also provide theoretical justifications for the observed behavior. … Read more

    The Star Degree Centrality Problem: A Decomposition Approach

  • Mustafa Can Camur
  • Thomas C. Sharkey
  • Chrysafis Vogiatzis
    • Categories 0-1 Programming, Cutting Plane Approaches, Network Optimization Tags , ,

    We consider the problem of identifying the induced star with the largest cardinality open neighborhood in a graph. This problem, also known as the star degree centrality (SDC) problem, has been shown to be š¯’©š¯’«-complete. In this work, we first propose a new integer programming (IP) formulation, which has a fewer number of constraints and … Read more

    Optimizing the Response for Arctic Mass Rescue Events

  • Mustafa Can Camur
  • Clare Dorsey
  • Martha Grabowski
  • Thomas C. Sharkey
  • William A. Wallace
    • Categories Applications - OR and Management Sciences, Network Optimization Tags , ,

    We study a model that optimizes the response to a mass rescue event in Arctic Alaska. The model contains dynamic logistics decisions for a large-scale maritime evacuation with the objectives of minimizing the impact of the event on the evacuees and the average evacuation time. Our proposed optimization model considers two interacting networks – the … Read more

    A Robust Rolling Horizon Framework for Empty Repositioning

  • Ilke Bakir
  • Alan L. Erera
  • Martin Savelsbergh
    • Categories Network Optimization, Robust Optimization, Transportation

    Naturally imbalanced freight flows force consolidation carriers to reposition resources empty. When constructing empty repositioning plans, the cost of repositioning resources empty needs to be weighed against the cost of corrective actions in case of unavailable resources. This is especially challenging given the uncertainty of future demand. We design and implement a robust rolling horizon … Read more

    Solving Mixed-Integer Nonlinear Optimization Problems using Simultaneous Convexification – a Case Study for Gas Networks

  • Frauke Liers
  • Maximilian Merkert
  • Alexander Martin
  • Nick Mertens
  • Dennis Michaels
    • Categories Applications - Science and Engineering, Global Optimization, Network Optimization Tags , , ,

    Solving mixed-integer nonlinear optimization problems (MINLPs) to global optimality is extremely challenging. An important step for enabling their solution consists in the design of convex relaxations of the feasible set. Known solution approaches based on spatial branch-and-bound become more effective the tighter the used relaxations are. Relaxations are commonly established by convex underestimators, where each … Read more

    A Simulated Annealing Algorithm for the Directed Steiner Tree Problem

  • Shabbir Ahmed
  • George L. Nemhauser
  • Matias Siebert
    • Categories Combinatorial Optimization, Dynamic Programming, Network Optimization Tags , , ,

    In \cite{siebert2019linear} the authors present a set of integer programs (IPs) for the Steiner tree problem, which can be used for both, the directed and the undirected setting of the problem. Each IP finds an optimal Steiner tree with a specific structure. A solution with the lowest cost, corresponds to an optimal solution to the … Read more

    Quantum Bridge Analytics II: Network Optimization and Combinatorial Chaining for Asset Exchange

  • Yu Du
  • Fred Glover
  • Gary Kochenberger
  • Moses Ma
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Network Optimization Tags , , , , ,

    Quantum Bridge Analytics relates to methods and systems for hybrid classical-quantum computing, and is devoted to developing tools for bridging classical and quantum computing to gain the benefits of their alliance in the present and enable enhanced practical application of quantum computing in the future. This is the second of a two-part tutorial that surveys … Read more

    Autonomous traffic at intersections: an optimization-based analysis of possible time, energy, and CO2 savings

  • Do Duc Le
  • Maximilian Merkert
  • Stephan Sorgatz
  • Mirko Hahn
  • Sebastian Sager
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Network Optimization Tags , , , , , ,

    In the growing field of autonomous driving, traffic-light controlled intersections as the nodes of large traffic networks are of special interest. We want to analyze how much an optimized coordination of vehicles and infrastructure can contribute to a more efficient transit through these bottlenecks. In addition, we are interested in sensitivity of the results with … Read more

    Computing Technical Capacities in the European Entry-Exit Gas Market is NP-Hard

  • Lars Schewe
  • Martin Schmidt
  • Johannes ThĆ¼rauf
    • Categories Applications - Science and Engineering, Network Optimization Tags , , , ,

    As a result of its liberalization, the European gas market is organized as an entry-exit system in order to decouple the trading and transport of natural gas. Roughly summarized, the gas market organization consists of four subsequent stages. First, the transmission system operator (TSO) is obliged to allocate so-called maximal technical capacities for the nodes … Read more