branch-cut-and-price

Cluster branching for vehicle routing problems

  • Joao Marcos P Silva
  • Eduardo Uchoa
  • Anand Subramanian
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming Tags , , ,

    This article introduces Cluster Branching, a novel branching strategy for exact algorithms solving Vehicle Routing Problems (VRPs). While branching is crucial for the efficiency of branch-and-bound-based algorithms, existing branching types such as Edge Branching, CutSet Branching, and Ryan&Foster Branching have their limitations. The proposed branching strategy aggregates multiple edge variables into higher-level decision structures corresponding … Read more

    New cuts and a branch-cut-and-price model for the Multi Vehicle Covering Tour Problem

  • Bruno Oliveira
  • Artur Alves Pessoa
  • Marcos Roboredo
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Integer Programming Tags , , , ,

    The Multi-Vehicle Covering Tour Problem (m-CTP) involves a graph in which the set of vertices is partitioned into a depot and three distinct subsets representing customers, mandatory facilities, and optional facilities. Each customer is linked to a specific subset of optional facilities that define its coverage set. The goal is to determine a set of … 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

    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