Transportation

A scenario decomposition algorithm for strategic time window assignment vehicle routing problems

  • Chrysanthos E. Gounaris
  • Anirudh Subramanyam
  • Akang Wang
    • Categories Stochastic Programming, Transportation Tags , , , , ,

    We study the strategic decision-making problem of assigning time windows to customers in the context of vehicle routing applications that are affected by operational uncertainty. This problem, known as the Time Window Assignment Vehicle Routing Problem, can be viewed as a two-stage stochastic optimization problem, where time window assignments constitute first-stage decisions, vehicle routes adhering … Read more

    An Approximation Algorithm for Vehicle Routing with Compatibility Constraints

  • Viswanath Nagarajan
  • Siqian Shen
  • Miao Yu
    • Categories Approximation Algorithms, Transportation Tags , ,

    We study a multiple-vehicle routing problem with a minimum makespan objective and compatibility constraints. We provide an approximation algorithm and a nearly-matching hardness of approximation result. We also provide computational results on benchmark instances with diverse sizes showing that the proposed algorithm (i) has a good empirical approximation factor, (ii) runs in a short amount … Read more

    Solving Time Dependent Traveling Salesman Problems with Time Windows

  • Natashia Boland
  • Mike Hewitt
  • Martin Savelsbergh
  • Duc Minh Vu
    • Categories Transportation Tags , , ,

    We present a new solution approach for the Time Dependent Traveling Salesman Prob- lem with Time Windows. This problem considers a salesman who departs from his home, has to visit a number of cities within a pre-determined period of time, and then returns home. The problem allows for travel times that can depend on the … Read more

    Provably High-Quality Solutions for the Meal Delivery Routing Problem

  • Martin Savelsbergh
  • Barış Yıldız
    • Categories Integer Programming, Optimization of Systems modeled by PDEs, Transportation Tags , , , , ,

    Online restaurant aggregators with integrated meal delivery networks have become more common and more popular in the past few years. Meal delivery is arguably the ultimate challenge in last mile logistics: a typical order is expected to be delivered within an hour (much less if possible), and within minutes of the food becoming ready. We … Read more

    Acyclic Mechanism Design for Freight Consolidation

  • Maged M. Dessouky
  • Alejandro Toriello
  • Nelson A. Uhan
  • Wentao Zhang
    • Categories Game Theory, Supply Chain Management, Transportation Tags , ,

    Freight consolidation is a logistics practice that improves the cost-effectiveness and efficiency of transportation operations, and also reduces energy consumption and carbon footprint. A “fair” shipping cost sharing scheme is indispensable to help establish and sustain the cooperation of a group of suppliers in freight consolidation. In this paper, we design a truthful acyclic mechanism … Read more

    An Integrated Car-and-ride Sharing System for Mobilizing Heterogeneous Travelers with Application in Underserved Communities

  • Siqian Shen
  • Miao Yu
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming, Transportation Tags , , , ,

    The fast-growing carsharing and ride-hailing businesses are generating economic benefits and societal impacts in the modern society. However, both have limitation to cover demand from diverse populations, e.g., travelers in low-income, underserved communities. In this paper, we consider two types of travelers: Type~1 who rent shared cars and Type~2 who need shared rides. We propose … Read more

    Models and algorithms for the robust resource constrained shortest path problem

  • Fatma Gzara
  • Da Lu
    • Categories Network Optimization, Robust Optimization, Transportation Tags , , ,

    We study the robust resource constrained shortest path problem (RCSPP) under uncertainty in cost and multiple resource consumption. Contrary to the deterministic RCSPP where the cost and the consumption of resources on an arc are known and fixed, the robust RCSPP models the case where both the cost and the resource consumption are random, and … Read more

    Branch-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs

  • Qie He
  • Yongjia Song
  • Stefan Irnich
    • Categories Transportation Tags , , , ,

    Two critical yet frequently conflicting objectives for logistics and transportation service companies are improving customer satisfaction and reducing transportation cost. In particular, given a net- work of customer requests with preferred service times, it is very challenging to find vehicle routes and service schedules simultaneously that respect all operating constraints and minimize the total transportation … Read more

    Revisiting the Hamiltonian p-median problem: a new formulation on directed graphs and a branch-and-cut algorithm

  • Tolga Bektas
  • Luís Gouveia
  • Daniel Santos
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Transportation

    This paper studies the Hamiltonian p-median problem defined on a directed graph, which consists of finding p mutually disjoint circuits of minimum total cost, such that each node of the graph is included in one of the circuits. Earlier formulations are based on viewing the problem as one resulting from the intersection of two subproblems. … Read more