Transportation

Interval-based Dynamic Discretization Discovery for Solving the Continuous-Time Service Network Design Problem

  • Natashia Boland
  • Mike Hewitt
  • Luke Marshall
  • Martin Savelsbergh
    • Categories (Mixed) Integer Linear Programming, Transportation Tags

    We introduce an effective and efficient iterative algorithm for solving the Continuous-Time Service Network Design Problem. The algorithm achieves its efficiency by carefully and dynamically refining partially time-expanded network models so that only a small number of small integer programs, defined over these networks, need to be solved. An extensive computational study shows that the … Read more

    Dynamic Courier Routing for a Food Delivery Service

  • Mark Karwan
  • Chase Murray
  • Zachary Steever
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Transportation

    Services like Grubhub and UberEats have revolutionized the way that diners can find and order from restaurants. The standard business model for such services, however, allows diners to order from only one restaurant at a time. Inspired by a food delivery service in the southeastern United States, this paper proposes the framework for a more … Read more

    Delay and disruption management at ATM: technical details

  • Federico Malucelli
  • Emanuele Tresoldi
    • Categories Applications - OR and Management Sciences, Transportation Tags , , , , ,

    Most of the local public transit companies have vehicle monitoring systems able to collect huge quantities of data in real-time. Typically, these data are used to measure the performance of the transportation system, and rarely they are fully exploited to improve it and to tackle disruptions. In this report we take into consideration the case … Read more

    Decision Diagrams for Solving Traveling Salesman Problems with Pickup and Delivery in Real Time

  • Karla Hoffman
  • Ryan J. O'Neil
    • Categories Transportation

    The Traveling Salesman Problem with Pickup and Delivery seeks a minimum cost path with pickups preceding deliveries. It is important in on-demand last-mile logistics, such as ride sharing and meal delivery. We examine the use of low-width Decision Diagrams in a branch-and-bound with and without Assignment Problem inference duals as a primal heuristic for finding … Read more

    Robust Optimization of a Broad Class of Heterogeneous Vehicle Routing Problems under Demand Uncertainty

  • Chrysanthos E. Gounaris
  • Anirudh Subramanyam
  • Panagiotis P. Repoussis
    • Categories Robust Optimization, Transportation Tags , , , , ,

    This paper studies robust variants of an extended model of the classical Heterogeneous Vehicle Routing Problem (HVRP), where a mixed fleet of vehicles with different capacities, availabilities, fixed costs and routing costs is used to serve customers with uncertain demand. This model includes, as special cases, all variants of the HVRP studied in the literature … Read more

    Integer Models for the Asymmetric Traveling Salesman Problem with Pickup and Delivery

  • Karla Hoffman
  • Ryan J. O'Neil
    • Categories Transportation

    We propose a new Mixed Integer Programming formulation for the Asymmetric Traveling Salesman Problem with Pickup and Delivery, along with valid inequalities for the Sarin-Sherali-Bhootra formulation. We study these models in their complete forms, relax complicating constraints of these models, and compare their performance. Finally, we present computational results showing the promise of these formulations … Read more

    Rapid prototyping of parallel primal heuristics for domain specific MIPs: Application to maritime inventory routing

  • Shabbir Ahmed
  • Lluís-Miquel Munguía
  • George L. Nemhauser
  • Dimitri J. Papageorgiou
  • David A. Bader
  • Yufen Shao
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms, Transportation

    Parallel Alternating Criteria Search (PACS) relies on the combination of computer parallelism and Large Neighborhood Searches to attempt to deliver high quality solutions to any generic Mixed-Integer Program (MIP) quickly. While general-purpose primal heuristics are widely used due to their universal application, they are usually outperformed by domain-specific heuristics when optimizing a particular problem class. … Read more

    Optimizing Package Express Operations in China

  • Martin Savelsbergh
  • Barış Yıldız
    • Categories Airline Optimization, Combinatorial Optimization, Transportation Tags , , ,

    We explore optimization models to support the planning and operations functions at package express carriers in China. The models simultaneously consider ground and air transportation, company-owned and purchased capacity, multiple service products, and shipments becoming available throughout the day. An extensive computational study using real-life data shows the efficacy of the models, provides insights into … Read more

    An Iterative Re-optimization Framework for the Dynamic Vehicle Routing Problem with Roaming Delivery Locations

  • Gizem Ozbaygin
  • Martin Savelsbergh
    • Categories Network Optimization, Transportation Tags , , ,

    Branch-and-price has established itself as an effective solution methodology for a wide variety of planning problems. We investigate its potential as a solution method- ology for solving operational problems. Specifically, we explore its potential in the context of a dynamic variant of the vehicle routing problem with roaming delivery locations, in which customer itineraries may … Read more

    The Distributionally Robust Chance Constrained Vehicle Routing Problem

  • Shubhechyya Ghosal
  • Wolfram Wiesemann
    • Categories Robust Optimization, Stochastic Programming, Transportation Tags , ,

    We study a variant of the capacitated vehicle routing problem (CVRP), which asks for the cost-optimal delivery of a single product to geographically dispersed customers through a fleet of capacity-constrained vehicles. Contrary to the classical CVRP, which assumes that the customer demands are deterministic, we model the demands as a random vector whose distribution is … Read more