event

The Supply Chain and Logistics Seminar Series

Primary tabs

The Supply Chain and Logistics Seminar Series
Date: Friday, September 28
Time: 11:45 - 12:30 (Note new time)
Location: Executive Classroom #228, ISyE Main

Speaker: Demetrio Lagana
Assistant Professor of Operations Research at University of Calabria, Italy

Title: The Capacitated Arc Routing Problem

Abstract:

The Capacitated Arc Routing Problem (CARP) consists of determining a set of least cost capacitated vehicle routes servicing a set of arcs. Applications of the CARP arise in garbage collection, snow removal, street sweeping and gritting, mail delivery, meter reading, school bus routing, etc.

While the CARP is a central problem in arc routing and has been known for a long time, it is still almost exclusively tackled by means of heuristics. The only available exact method for the CARP is a parallel branch-and-bound algorithm proposed by Hirabayashi et al. (1992), and Kiuchi et al. (1995), in which a lower bound is computed at each node through a node duplication lower bounding procedure (Hirabayashi et al., 1992). Transformations of the CARP into an equivalent node routing problem (namely the Capacitated Vehicle Routing Problem, CVRP) have been proposed by Pearn (1987), Longo et al. (2006), and Baldacci and Maniezzo (2006). Lower bounds have been obtained by Belenguer and Benavent (1992, 1998, 2003) through cutting plane procedures, and Wels (1994) has proposed valid inequalities and separation procedures for the directed version of the CARP.

Recently, Ghiani et al. (2007) proposed a pure binary linear integer program for the undirected CARP, on the basis of an extension of a previous formulation by Belenguer and Benavent (1998), and they developed a fully automated branch-and-cut algorithm. Computational results indicate that the algorithm is able to solve, for the first time ever, all the benchmark instances proposed by DeArmon (1981), and Benavent et al. (1992).

Pizza and refreshments sponsored by The Supply Chain Logistics Institute (SCL).

Status

  • Workflow Status:Published
  • Created By:Ruth Gregory
  • Created:10/12/2009
  • Modified By:Fletcher Moore
  • Modified:10/07/2016