Iterated tabu search for the car sequencing problem. (English) Zbl 1156.90374
Summary: This paper introduces an iterated tabu search heuristic for the daily car sequencing problem in which a set of cars must be sequenced so as to satisfy requirements from the paint shop and the assembly line. The iterated tabu search heuristic combines a classical tabu search with perturbation operators that help escape from local optima. The resulting heuristic is flexible, easy to implement, and fast. It has produced very good results on a set of test instances provided by the French car manufacturer Renault.
References:
| [1] | Delaval, M., Castelain, E., Gentina, J.C., 1995. Dynamic resequencing of cars on assembly lines using simulated annealing. In: Proceedings of the 28th International Symposium on Automotive Technology and Automation, Dedicated Conference on Lean/Agile Manufacturing in the Automotive Industries, Stuttgart, Germany, 1995, pp. 169-175.; Delaval, M., Castelain, E., Gentina, J.C., 1995. Dynamic resequencing of cars on assembly lines using simulated annealing. In: Proceedings of the 28th International Symposium on Automotive Technology and Automation, Dedicated Conference on Lean/Agile Manufacturing in the Automotive Industries, Stuttgart, Germany, 1995, pp. 169-175. |
| [2] | Gagné, C.; Gravel, M.; Price, W. L., Solving real car sequencing problems with ant-colony optimization, European Journal of Operational Research., 174, 1427-1448 (2006) · Zbl 1103.90409 |
| [3] | Gottlieb, J.; Puchta, M.; Solnon, C., A study of greedy, local search and ant colony optimization approaches for car sequencing problems, (Cagnoni, S.; etal., EvoWorkshops 2003. EvoWorkshops 2003, Lecture Notes in Computer Science, vol. 2611 (2003), Springer: Springer Berlin), 246-257 · Zbl 1033.90503 |
| [4] | Gravel, M.; Gagné, C.; Price, W. L., Review and comparison of three methods for the solution of the car sequencing problem, Journal of the Operational Research Society, 56, 1287-1295 (2005) · Zbl 1082.90590 |
| [5] | Hindi, K. S.; Ploszajski, G., Formulation and solution of a sequencing problem in car manufacture, Computers & Industrial Engineering, 26, 203-211 (1994) |
| [6] | Kis, T., On the complexity of the car sequencing problem, Operations Research Letters, 32, 331-335 (2004) · Zbl 1054.90034 |
| [7] | Lourenço, H. R.; Martin, O. C.; Stützle, T., Iterated local search, (Glover, F.; Kochenberger, G., Handbook of Metaheuristics (2002), Kluwer: Kluwer Boston), 321-353 · Zbl 1116.90412 |
| [8] | Misevicius, A., Using iterated tabu search for the traveling salesman problem, Information Technology and Control, 3, 32, 29-40 (2004) |
| [9] | Muhl, E.; Charpentier, P.; Chaxel, F., Optimization of physical flows in an automotive manufacturing plant: Some experiments and issues, Engineering Applications of Artificial Intelligence, 16, 293-305 (2003) |
| [10] | Perron, L.; Shaw, P., Combining forces to solve the car sequencing problem, (Régin, J.-C.; Rueher, M., CPAIOR 2004. CPAIOR 2004, Lecture Notes in Computer Science, vol. 3011 (2004), Springer: Springer Berlin), 225-239 · Zbl 1094.68651 |
| [11] | Ponnambalam, S. G.; Aravindan, P.; Rao, M. S., Genetic algorithms for sequencing problems in mixed model assembly lines, Computers & Industrial Engineering, 45, 669-690 (2003) |
| [12] | Smith, K.; Palaniswami, M.; Krishnamoorthy, M., Traditional heuristic versus Hopfield neural network approaches to a car sequencing problem, European Journal of Operational Research, 93, 300-316 (1996) · Zbl 0912.90165 |
| [13] | Solnon, C., Solving permutation constraint satisfaction problems with artificial ants, (Horn, W., Proceedings of the 14th European Conference on Artificial Intelligence (2000), IOS Press: IOS Press Amsterdam), 118-122 |
| [14] | Solnon, C., Cung, V.D., Nguyen, A., Artigues, C., in press. The car sequencing problem: Overview of state-of-the-art methods and industrial case-study of the ROADEF’2005 challenge problem. European Journal of Operational Research. doi:10.1016/j.ejor.2007.04.033; Solnon, C., Cung, V.D., Nguyen, A., Artigues, C., in press. The car sequencing problem: Overview of state-of-the-art methods and industrial case-study of the ROADEF’2005 challenge problem. European Journal of Operational Research. doi:10.1016/j.ejor.2007.04.033 · Zbl 1156.90323 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
