Research: Applications

This page is devoted to applied projects, some of which have been undertaken in collaboration with industrial partners. To see more about these project, click on the links below.

The Vehicle Routing Problem

Using SYMPHONY, we have developed a branch and cut algorithm for solving the VRP. We are currently working on methods of solving integrated location, routing, and scheduling problems. .

Recent publications related to vehicle routing:

  • Z. Akca, R. Berger, and T.K.R., A Branch-and-Price Algorithm for Combined Location and Routing Problems Under Capacity Restrictions, The Proceedings of the Eleventh INFORMS Computing Society Meeting (2009), 309-330 (Working paper version: PDF)
  • Z. Akca, R. Berger, and T.K.R., Modeling and Solving Location, Routing, and Scheduling Problems, COR@L Laboratory Technical Report (2008) (PDF)
  • T.K.R., Parallel Branch and Cut for Capacitated Vehicle Routing, Parallel Computing, 29 (2003), 607 (Working paper version: PS PDF).
  • T.K.R., L. Kopman, W.R. Pulleyblank, and L.E. Trotter Jr., On the Capacitated Vehicle Routing Problem, Mathematical Programming Series B 94 (2003), 343 (On-line version: PDF Working paper version: PS PDF).

Recent presentations related to vehicle routing:

Capacitated Network Routing Problems

In previous research, we developed a solver for a general class of problems involving routing and packing constraints that we call Capacitated Network Routing Problems. This class can be described using a flow-based IP formulation similar to that used for network design problems. The formulation models a wide range of related problems that can all be seen as special cases of this general model with common structure. A rudimentary version of the solver is available at here, but it is not being further developed at the moment. The solver was built using the the SYMPHONY framework.

Recent publications related to network routing:

  • T.K.R., M.J. Saltzman, and M.M. Wiecek, An Improved Algorithm for Biobjective Integer Programming and Its Application to Network Routing Problems Lehigh University Industrial and Systems Engineering Technical Report 04T-001 (2004) (PS PDF).
  • T.K.R. and J.C. Hartman, Capacitated Network Routing (A Preliminary Progress Report), Lehigh University Industrial and Systems Engineering Working Paper 01W-009 (2001) (PS PDF).

Recent presentations related to network routing:

Mixed Postman Problem.

In previous research, we developed a rudimentary solver for the Mixed Postman Problem using SYMPHONY, but this solver is not currently under active development.

Recent publications related to the mixed postman problem:

Winner Determination in Combinatorial Auctions.

Building on work by M. Eso developing a solver for the set partitioning problem using SYMPHONY, we are investigating computational aspects of solving the winner determination problem in combinatorial auctions and the use of integer programming duality to develop feedback mechanisms for combinatorial auctions.

If you find something here useful, buy me a beer!