*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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).
