School Seminars and Colloquia

"Integer Programming Based Local Search & Advances in Load Planning for Less-Than-Truckload Carriers"

ORSUM Seminar

by Martin Savelsbergh


Institution: Georgia Institute of Technology
Date: Mon 4th May 2009
Time: 1:00 PM
Location: Room 213, Richard Berry Building (M&S), The University of Melbourne

Abstract: Many local search algorithms for hard combinatorial
optimization problems only consider neighborhoods that
can be searched in polynomial-time. However, with current
technology, it is now possible to search neighborhoods
efficiently by solving small to medium sized integer
programs. To demonstrate the viability of this approach
to obtaining provably good solutions quickly to large
instances of NP-hard problems, we focus on a local
search algorithm for the Fixed Charge Network Flow (FCNF)
Problem using neighborhoods that involve solving
carefully chosen integer programs.

The most important tactical decision for a
less-than-truckload carrier is deciding the path that
freight follows from origin to destination.
Traditionally, freight follows the same path from origin
to destination every day of the week even though freight
volumes at the origin can vary substantially from day to
day. We develop integer programming based local search
technology to build day-differentiated load plans that
properly account for freight volume variations.
Computational experiments show that day-differentiated
load plans result in significant cost savings.

For More Information: contact Kerem Akartunali, email: kerema@unimelb.edu.au