vehicle routing

The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

  • Ricardo Fukasawa
    • Categories Combinatorial Optimization, Integer Programming, Stochastic Programming Tags , ,

    The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains … Read more

    Routing and resource allocation in non-profit settings with equity and efficiency measures under demand uncertainty

  • Faisal Alkaabneh
  • Karmel S. Shehadeh
  • Ali Diabat
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

    Motivated by food distribution operations for non-profit organizations, we study a variant of the stochastic routing-allocation problem under demand uncertainty, in which one decides the assignment of trucks for demand nodes, the sequence of demand nodes to visit (i.e., truck route), and the allocation of food supply to each demand node. We propose three stochastic … Read more

    Minimizing earliness-tardiness costs in supplier networks – A Just-in-time Truck Routing Problem

  • Julian Baals
  • Simon Emde
  • Turkensteen Marcel
    • Categories Meta Heuristics, Production and Logistics Tags , , , ,

    We consider a routing problem where orders are transported just-in-time from several suppliers to an original equipment manufacturer (OEM). This implies that shipments cannot be picked up before their release date when they are ready at the supplier and should be delivered as close as possible to their due date to the OEM. Every shipment … Read more

    A new family of route formulations for split delivery vehicle routing problems

  • Isaac Balster
  • Teobaldo Bulhões
  • Pedro Munari
  • Artur Alves Pessoa
  • Ruslan Sadykov
    • Categories Combinatorial Optimization, Integer Programming, Transportation Tags , , , ,

    We propose a new family of formulations with route-based variables for the split delivery vehicle routing problem with and without time windows. Each formulation in this family is characterized by the maximum number of different demand quantities that can be delivered to a customer during a vehicle visit. As opposed to previous formulations in the … Read more

    Heuristic approaches for split delivery vehicle routing problems

  • Aldair Álvarez
  • Pedro Munari
    • Categories Branch and Cut Algorithms, Meta Heuristics, Transportation Tags , , , ,

    We propose a matheuristic approach to solve split delivery variants of the vehicle routing problem (VRP). The proposed method is based on the use of several mathematical programming components within an Iterated Local Search metaheuristic framework. In addition to well-known VRP local search heuristics, we include new types of improvement and perturbation strategies that are … Read more

    Multi-depot routing with split deliveries: Models and a branch-and-cut algorithm

  • Luís Gouveia
  • Markus Leitner
  • Mario Ruthmair
    • Categories Applications - OR and Management Sciences Tags , , , ,

    We study the multi-depot split-delivery vehicle routing problem (MDSDVRP) which combines the advantages and potential cost-savings of multiple depots and split-deliveries and develop the first exact algorithm for this problem. We propose an integer programming formulation using a small number of decision variables and several sets of valid inequalities. These inequalities focus on ensuring the … Read more

    Solving the Home Service Assignment, Routing, and Appointment Scheduling (H-SARA) problem with Uncertainties

  • Syu-Ning Johnn
  • Yiran Zhu
  • Andrés Miniguano-Trujillo
  • Akshay Gupte
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming, Transportation Tags , , , ,

    The Home Service Assignment, Routing, and Appointment scheduling (H-SARA) problem integrates the strategical fleet-sizing, tactical assignment, operational vehicle routing and scheduling subproblems at different decision levels, with a single period planning horizon and uncertainty (stochasticity) from the service duration, travel time, and customer cancellation rate. We propose a two-stage stochastic mixed-integer linear programming model for … Read more

    Decomposition strategies for vehicle routing heuristics

  • Alberto Santini
  • Michael Schneider
  • Thibaut Vidal
  • Daniele Vigo
    • Categories Meta Heuristics, Transportation Tags , ,

    Decomposition techniques are an important component of modern heuristics for large instances of vehicle routing problems. The current literature lacks a characterisation of decomposition strategies and a systematic investigation of their impact when integrated into state-of-the-art heuristics. This paper fills this gap: we discuss the main characteristics of decomposition techniques in vehicle routing heuristics, highlight … Read more

    Robust Vehicle Routing under Uncertainty via Branch-Price-and-Cut

  • Chrysanthos E. Gounaris
  • Anirudh Subramanyam
  • Akang Wang
    • Categories Production and Logistics, Robust Optimization, Transportation Tags , , , , , ,

    This paper contemplates how branch-price-and-cut solvers can be employed along with the robust optimization paradigm to address parametric uncertainty in the context of vehicle routing problems. In this setting, given postulated uncertainty sets for customer demands and vehicle travel times, one aims to identify a set of cost-effective routes for vehicles to traverse, such that … Read more

    Improving Column-Generation for Vehicle Routing Problems via Random Coloring and Parallelization

  • Viswanath Nagarajan
  • Siqian Shen
  • Miao Yu
    • Categories Network Optimization, Parallel Algorithms, Transportation Tags , , , ,

    We consider a variant of the Vehicle Routing Problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation based linear-programming relaxation … Read more