×

Local search and suffix tree for car-sequencing problem with colors. (English) Zbl 1156.90375

Summary: This paper describes an approximation solution method for the car sequencing problem with colors. Firstly, we study the optimality of problems with a single ratio constraint. This study also introduces a data structure for efficient calculation of the penalties related to ratio constraints. We describe the constructive greedy algorithm and variable neighborhood search adjusted for the problem with colors. Tabu metaheuristic is used to improve the results obtained by VNS. We then represent the cars with their constraints as letters over an alphabet and apply the algorithm to spell the motifs in order to improve the number of batch colors without decreasing the costs associated to the set of ratio constraints. The algorithm achieves 19 out of the 64 best results for instance sets \(A\) and \(B\). These instances are the reference instances for Challenge ROADEF.

MSC:

90B40 Search theory
90C29 Multi-objective and goal programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Davenport, A.; Tsang, E. P.K., Solving constraint satisfaction sequencing problems by iterative repair: an application to car sequencing, The Practical Application of Constraint Technologies and Logic Programming Conference - PACLP99 (1999), The Practical Application Company Ltd, pp. 345-358
[2] A.J. Davenport, E.P.K. Tsang, C.J. Wang, K. Zhu, GENET: a connectionist architecture for solving constraint satisfaction problems by iterative improvement, in: Proceedings of the 12th National Conference on Artificial Intelligence (AAAI), vol. 1, 1994, pp. 325-330.; A.J. Davenport, E.P.K. Tsang, C.J. Wang, K. Zhu, GENET: a connectionist architecture for solving constraint satisfaction problems by iterative improvement, in: Proceedings of the 12th National Conference on Artificial Intelligence (AAAI), vol. 1, 1994, pp. 325-330.
[3] I. Gent, Two results on car-sequencing problems, APES Report APES-02-1998, April 1998, http://www.dcs.st-and.ac.uk/apes/apesreports.html; I. Gent, Two results on car-sequencing problems, APES Report APES-02-1998, April 1998, http://www.dcs.st-and.ac.uk/apes/apesreports.html
[4] Gottlieb, J.; Puchta, M.; Solnon, C., A study of greedy, local search and ant colony optimization approaches for car sequencing problems, (Lecture Notes in Computer Science, N2611 (2003), Springer), 246-257 · Zbl 1033.90503
[5] M. Risler, M. Chiarandini, L. Paquete, T. Schiavinotto, T. Stützle, An algorithm for the car sequencing problem of the ROADEF 2005 Challenge, Technical Report AIDA0406, FG Intellektik, TU Darmstadt, March 2004.; M. Risler, M. Chiarandini, L. Paquete, T. Schiavinotto, T. Stützle, An algorithm for the car sequencing problem of the ROADEF 2005 Challenge, Technical Report AIDA0406, FG Intellektik, TU Darmstadt, March 2004.
[6] Sagot, M.-F., Spelling approximate repeated or common motifs using a suffix tree, (Lucchesi, C. L.; Moura, A. V., LATIN’98: Theoretical Informatics, Lecture Notes in Computer Science (1998), Springer-Verlag), 111-127
[7] Solnon, C., Solving Permutation Constraint Satisfaction Problems with Artificial Ants Christine Solnon, 14th European Conference on Artificial Intelligence (ECAI 2000) (2000), IOS Press, pp. 118-122
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.