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:
- T.K.R., Capacitated Vehicle Routing and Some Related Problems, Rutgers University, Department of Industrial and Systems Engineering, Piscataway, NJ, November 2001 (PS PDF).
- T.K.R., A Branch and Cut Algorithm for the Vehicle Routing Problem, The Institute for Operations Research and Management Science Conference, San Antonio, TX, November 2000 (PS PDF).
- T.K.R., L. Kopman, W. Pulleyblank, and L.E. Trotter Jr., A Generic Separation Algorithm for Combinatorial Optimization, DONET Workshop on Combinatorial Optimization, Aussois, France, March 2000 (PS PDF).
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:
- T.K.R. and J.C. Hartman, Branch and Cut for Capacitated Network Routing, The Institute for Operations Research and Management Science Conference, Miami, FL, November 2001 (PS PDF).
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:
- T.K.R., On the Mixed Chinese Postman Problem, Operations Research Letters 14 (1993), 123 (Working paper version: PS PDF).
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.
