Abstract:
This paper describes and compares several heuristic approaches for the car
sequencing problem. We first study greedy heuristics, and show that
dynamic ones clearly outperform their static counterparts. We then
describe local search and ant colony optimization (ACO) approaches, that
both integrate greedy heuristics, and experimentally compare them on benchmark instances. ACO yields the best solution quality for smaller time limits, and it is comparable to local search for larger limits. Our best algorithms proved one instance being feasible, for which it was formerly unknown whether it is satisfiable or not.
Full paper (postscript)