To increase the size of the paint blocks while maintaining a workload-balanced vehicle sequence, automobile manufacturers use automated vehicle storage and retrieval systems that permit them to perturb the original sequence around the vehicle painting station.  The re-sequencing problem is a traveling salesman problem with time windows (TSPTW).  For a real-life sequence size of 750 cars and half-windows of 75 slots per car in either direction, direct modeling using the strongest known TSPTW formulation yields an integer program with up to 200,000 constraints and 14,000,000 variables.  Reduced formulations are still difficult to solve, even with the addition of polyhedral cuts.  We exploit special problem structure to solve a linear programming relaxation of this problem quickly using Lagrangean relaxation.  We prove and use an order-within-color property to construct an enumerative formulation, and use a greedy approach to bound the linear programming optimal value.  We decompose the problem and solve smaller enumerative formulations sequentially to quickly (less than two minutes on average) generate near-tight bounds on the optimal objective value (empirically within 2.5% of optimality).

Joel Sokol is an Assistant Professor in the School of Industrial and Systems Engineering at the Georgia Institute of Technology.  He received his Ph.D. in Operations Research from MIT in 1999.  His bachelor's degrees, a B.S. in Applied Sciences in Engineering and a B.A. in Mathematics and in Computer Sciences, are from Rutgers University.
Dr. Sokol's research interests in logistics include applications of network, linear, and combinatorial optimisation to transportation, manufacturing, and network design problems.  He is also interested in protein folding, robot design, and sports modelling.