Transportation

The robust vehicle routing problem with time windows: compact formulation and branch-price-and-cut method

  • Douglas Alem
  • Jonathan De La Vega
  • Jacek Gondzio
  • Reinaldo Morabito
  • Pedro Munari
  • Alfredo Moreno
    • Categories Applications - OR and Management Sciences, Robust Optimization, Transportation

    We address the robust vehicle routing problem with time windows (RVRPTW) under customer demand and travel time uncertainties. As presented thus far in the literature, robust counterparts of standard formulations have challenged general-purpose optimization solvers and specialized branch-and-cut methods. Hence, optimal solutions have been reported for small-scale instances only. Additionally, although the most successful methods … Read more

    The Continuous Time Inventory Routing Problem

  • Natashia Boland
  • Felipe Lagos
  • Martin Savelsbergh
    • Categories Integer Programming, Transportation Tags ,

    We consider a continuous time variant of the Inventory Routing Problem in which the maximum quantity that can delivered at a customer depends on the customer’s storage capacity and product inventory at the time of the delivery. We investigate critical components of a dynamic discretization discovery algorithm and demonstrate in an extensive computational study that … Read more

    Network Models with Unsplittable Node Flows with Application to Unit Train Scheduling

  • Danial Davarnia
  • Jean-Philippe P. Richard
  • Ece Icyuz-Ay
  • Bijan Taslimi
    • Categories Cutting Plane Approaches, Network Optimization, Transportation

    We study network models where flows cannot be split or merged when passing through certain nodes, i.e., for such nodes, each incoming arc flow must be matched to an outgoing arc flow of identical value. This requirement, which we call “no-split no-merge” (NSNM), appears in railroad applications where train compositions can only be modified at … Read more

    Exact Methods for Solving Traveling Salesman Problems with Pickup and Delivery in Real Time

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

    The Traveling Salesman Problem with Pickup and Delivery (TSPPD) describes the problem of finding a minimum cost path in which pickups precede their associated deliveries. The TSPPD is particularly important in the growing field of Dynamic Pickup and Delivery Problems (DPDP). These include the many-to-many Dial-A-Ride Problems (DARP) of companies such as Uber and Lyft, … Read more

    Branch-and-Price for Routing with Probabilistic Customers

  • Mathias A. Klapp
  • Felipe Lagos
  • Alejandro Toriello
    • Categories Integer Programming, Transportation Tags ,

    The Vehicle Routing Problem with Probabilistic Customers (VRP-PC) is a fundamental building block within the broad family of stochastic routing models, and has two decision stages. In the first stage, a dispatcher determines a set of vehicle routes serving all potential customer locations, before actual requests for service realize. In the second stage, vehicles are … Read more

    Crowd-based City Logistics

  • Afonso Sampaio
  • Martin Savelsbergh
  • Lucas Veelenturf
  • Tom Van Woensel
    • Categories Applications - OR and Management Sciences, Production and Logistics, Transportation Tags , , , , ,

    Cities are drivers of economic development, providing infrastructure to support countless activities and services. Today, the world’s 750 biggest cities account for more than 57% of the global GDP and this number is expected to increase to 61% by 2030. More than half of the world’s population lives in cities, or urban areas, and this … Read more

    The forwarder planning problem in a two-echelon network

  • Massimo Di Francesco
  • Manlio Gaudioso
  • Enrico Gorgone
  • Paola Zuddas
    • Categories Approximation Algorithms, Transportation Tags , ,

    This paper is motivated by the case of a forwarder in dealing with inland transportation planning from a seaport, where inbound containers from the sea are filled with pallets, which have different destinations in the landside. Although this forwarder does not have or control any vehicle, he is required to plan the assignment of containers … Read more

    Same-Day Delivery with Drone Resupply

  • John-Paul Clarke
  • Iman Dayarian
  • Martin Savelsbergh
    • Categories Applications - OR and Management Sciences, Transportation

    Unmanned Aerial Vehicles (UAVs), commonly referred to as drones, have recently seen an increased level of interest as their potential use in same-day home delivery has been promoted and advocated by large retailers and courier delivery companies. We introduce a novel way to exploit drones in same-day home delivery settings: drone resupply. We consider a … Read more

    Comparative Analysis of Capacitated Arc Routing Formulations for Branch-Cut-and-Price Algorithms

  • Diego Pecin
  • Eduardo Uchoa
    • Categories Combinatorial Optimization, Integer Programming, Transportation

    The current best exact algorithms for the Capacitated Arc Routing Problem are based on the combination of cut and column generation. This work presents a deep theoretical investigation of the formulations behind those algorithms, classifying them and pointing similarities and differences, advantages and disadvantages. In particular, we discuss which families of cuts and branching strategies … Read more