Transportation

A Robust Branch-Cut-and-Price Algorithm for the Heterogeneous Fleet Vehicle Routing Problem

  • Artur Alves Pessoa
  • Marcus Poggi de Aragão
  • Eduardo Uchoa
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Transportation Tags , ,

    This paper presents a robust branch-cut-and-price algorithm for the Heterogeneous Fleet Vehicle Routing Problem (HFVRP), vehicles may have various capacities and fixed costs. The columns in the formulation are associated to $q$-routes, a relaxation of capacitated elementary routes that makes the pricing problem solvable in pseudo-polynomial time. Powerful new families of cuts are also proposed, … Read more

    Optimizing Highway Transportation at the United States Postal Service

  • Edward J. Matto
  • Anthony Pajunas
  • Michael Trick
  • Luis F. Zuluaga
    • Categories (Mixed) Integer Linear Programming, Transportation

    The United States Postal Service (USPS) delivers more than 200 billion items per year. Transporting these items in a timely and cost-efficient way is a key issue if USPS is to meet its service and financial goals. The Highway Corridor Analytic Program (HCAP) is a tool that aids transportation analysts in identifying cost saving opportunities … Read more

    E-model for Transportation Problem of Linear Stochastic Fractional Programming

  • Vincent Charles
    • Categories Applications - OR and Management Sciences, Stochastic Programming, Transportation Tags , , ,

    This paper deals with the so-called transportation problem of linear stochastic fractional programming, and emphasizes the wide applicability of LSFP. The transportation problem, received this name because many of its applications involve in determining how to optimally transport goods. However, some of its applications (e.g., production scheduling) actually have nothing to do with transportation. The … Read more

    The Impact of Collusion on the Price of Anarchy in Nonatomic and Discrete Network Games

  • Tobias Harks
    • Categories Game Theory, Network Optimization, Transportation Tags , , ,

    Hayrapetyan, Tardos and Wexler recently introduced a framework to study the impact of collusion in congestion games on the quality of Nash equilibria. We adopt their framework to network games and focus on the well established price of anarchy as a measure of this impact. We first investigate nonatomic network games with coalitions. For this … Read more

    An efficient method to compute traffic assignment problems with elastic demands

  • Frédéric Babonneau
  • Jean-Philippe Vial
    • Categories Convex Optimization, Transportation Tags , ,

    The traffic assignment problem with elastic demands can be formulated as an optimization problem, whose objective is sum of a congestion function and a disutility function. We propose to use a variant of the Analytic Center Cutting Plane Method to solve this problem. We test the method on instances with different congestion functions (linear with … Read more

    Formulations and Valid Inequalities for the Heterogeneous Vehicle Routing Problem

  • Hande Yaman
    • Categories (Mixed) Integer Nonlinear Programming, Transportation Tags , , , ,

    We consider the vehicle routing problem where one can choose among vehicles with different costs and capacities to serve the trips. We develop six different formulations: the first four based on Miller-Tucker-Zemlin constraints and the last two based on flows. We compare the linear programming bounds of these formulations. We derive valid inequalities and lift … Read more

    Efficiency and Fairness of System-Optimal Routing with User Constraints

  • Andreas S. Schulz
  • Nicolás Stier-Moses
    • Categories Network Optimization, Transportation Tags , , , , ,

    We study the route-guidance system proposed by Jahn, Möhring, Schulz and Stier-Moses (2004) from a theoretical perspective. This approach computes a traffic pattern that minimizes the total travel time subject to user constraints, which ensure that routes suggested to users are not much longer than shortest paths. We show that when distances are measured with … Read more

    Robust Capacity Expansion of Transit Networks

  • Fernando Ordóñez
  • Jiamin Zhao
    • Categories Network Optimization, Robust Optimization, Transportation Tags ,

    In this paper we present a methodology to decide capacity expansions for a transit network that finds a robust solution with respect to the uncertainty in demands and travel times. We show that solving for a robust solution is a computationally tractable problem under conditions that are reasonable for a transportation system. For example, the … Read more

    Solving large scale linear multicommodity flow problems with an active set strategy and Proximal-ACCPM

  • Frédéric Babonneau
  • Jean-Philippe Vial
  • Olivier du Merle
    • Categories Network Optimization, Nonsmooth Optimization, Transportation Tags , ,

    In this paper, we propose to solve the linear multicommodity flow problem using a partial Lagrangian relaxation. The relaxation is restricted to the set of arcs that are likely to be saturated at the optimum. This set is itself approximated by an active set strategy. The partial Lagrangian dual is solved with Proximal-ACCPM, a variant … Read more

    Vehicle routing and staffing for sedan service

  • Oktay Gunluk
  • Lazslo Ladanyi
  • Baruch Schieber
  • Tracy Kimbrel
  • Gregory B. Sorkin
    • Categories Integer Programming, Transportation Tags , , ,

    We present the optimization component of a decision support system developed for a sedan service provider. The system assists supervisors and dispatchers in scheduling driver shifts and routing the fleet throughout the day to satisfy customer demands within tight time windows. We periodically take a snapshot of the dynamic data and formulate an integer program, … Read more