An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation

By Roberto Baldacci, E. Hadjiconstantinou, Aristide Mingozzi. Operational Research, 2004

324 citations recorded by the source corpus.

Subfields: Automotive Engineering, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/6bf591763ef5cd95fcd185691a87ba09a8cec050

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Automotive Engineering

In Industrial and Manufacturing Engineering

Citations in the corpus

Energy Minimizing Vehicle Routing Problem (2007, background): “(Baldacci et al.[1], Toth and Vigo [17], Desrochers et al.”
The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach (2012, methodology): “A flow-based formulation Motivated by the success of flow-based formulations in solving different variants of the vehicle routing problem [48,49,47,59], we propose a flow-based formulation for the LRPSPD (referred to as F1flow).”
A Survey on the Vehicle Routing Problem and Its Variants (2012, background): “[9] proposed a twocommodity flow formulation of the CVRP.”
A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty (2008, background): “(2003), Baldacci et al. (2004), Lysgaard et al. (2004), and Fukasawa et al. (2006). The most studied areas in the stochastic VRP literature are the VRP with Stochastic Demands (VRPSD) and the VRP with Stochastic Customers (VRPSC).”
New Heuristics for the Vehicle Routing Problem (2005, methodology): “, Naddef and Rinaldi (2002); Baldacci et al. (2004)) can only solve relatively small instances and their computational times are highly variable. To this day, heuristics remain the only reliable approach for the solution of practical instances. In contrast to exact algorithms, heuristics are better ”
Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints (2012, methodology): “Baldacci et al. (2004) proposed a two-commodity ﬂow formulation of the CVRP which extends the TSP model introduced by Finke et al. (1984).”
New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem (2011, methodology): “Baldacci et al. (2004) described a branch-and-cut (bc) algorithm based on a two-commodity network flow formulation of the cvrp. Lysgaard et al. (2004) proposed a bc algorithm that enhances the method of Augerat et al. (1995).”
What you should know about the vehicle routing problem (2007, methodology): “[6], the vehicle flow formulation can be rewritten in terms of the zr variables by using the following identity:”
An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts (2008, methodology): “[6]) by setting: xi j = ∑ r∈R ηr i j yr , ∀{i, j} ∈ E, (11)”