# Large neighborhood improvements for solving car sequencing problems

Bertrand Estellon; Frédéric Gardi; Karim Nouioua

RAIRO - Operations Research - Recherche Opérationnelle (2006)

- Volume: 40, Issue: 4, page 355-379
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topEstellon, Bertrand, Gardi, Frédéric, and Nouioua, Karim. "Large neighborhood improvements for solving car sequencing problems." RAIRO - Operations Research - Recherche Opérationnelle 40.4 (2006): 355-379. <http://eudml.org/doc/245831>.

@article{Estellon2006,

abstract = {The $\{\mathcal \{N\}P\}$-hard problem of car sequencing has received a lot of attention these last years. Whereas a direct approach based on integer programming or constraint programming is generally fruitless when the number of vehicles to sequence exceeds the hundred, several heuristics have shown their efficiency. In this paper, very large-scale neighborhood improvement techniques based on integer programming and linear assignment are presented for solving car sequencing problems. The effectiveness of this approach is demonstrated through an experimental study made on seminal CSPlib’s benchmarks.},

author = {Estellon, Bertrand, Gardi, Frédéric, Nouioua, Karim},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {combinatorial optimization; car sequencing/scheduling; very large-scale neighborhood search; integer programming; assignment},

language = {eng},

number = {4},

pages = {355-379},

publisher = {EDP-Sciences},

title = {Large neighborhood improvements for solving car sequencing problems},

url = {http://eudml.org/doc/245831},

volume = {40},

year = {2006},

}

TY - JOUR

AU - Estellon, Bertrand

AU - Gardi, Frédéric

AU - Nouioua, Karim

TI - Large neighborhood improvements for solving car sequencing problems

JO - RAIRO - Operations Research - Recherche Opérationnelle

PY - 2006

PB - EDP-Sciences

VL - 40

IS - 4

SP - 355

EP - 379

AB - The ${\mathcal {N}P}$-hard problem of car sequencing has received a lot of attention these last years. Whereas a direct approach based on integer programming or constraint programming is generally fruitless when the number of vehicles to sequence exceeds the hundred, several heuristics have shown their efficiency. In this paper, very large-scale neighborhood improvement techniques based on integer programming and linear assignment are presented for solving car sequencing problems. The effectiveness of this approach is demonstrated through an experimental study made on seminal CSPlib’s benchmarks.

LA - eng

KW - combinatorial optimization; car sequencing/scheduling; very large-scale neighborhood search; integer programming; assignment

UR - http://eudml.org/doc/245831

ER -

## References

top- [1] R.K. Ahuja, Ö. Ergun, J.B. Orlin and A.P. Punnen, A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics 123 (2002) 75–102. Zbl1014.68052
- [2] E. Aarts and J.K. Lenstra, Local Search in Combinatorial Optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Chichester, UK (1997). Zbl0869.00019MR1458630
- [3] V-.D. Cung and A. Nguyen (2003). Challenge ROADEF’2005. http://www.prism.uvsq.fr/ vdc/ROADEF/CHALLENGES/2005/
- [4] V-.D. Cung and A. Nguyen Le problème du Car Sequencing RENAULT et le Challenge ROADEF’2005, in Actes des JFPC 2005, les 1${}^{\mathrm{res}}$ Journées Francophones de Programmation par Contraintes, Lens, France, edited by C. Solnon (2005) 3–10
- [5] B. Estellon, F. Gardi and K. Nouioua, Ordonnancement de véhicules dans les usines RENAULT: une approche par recherche locale à voisinage large, in Actes de ROADEF 2005, le 6${}^{\mathrm{e}}$ Congrès de la Société Française de Recherche Opérationnelle et d’Aide à la Décision, Tours, France, edited by J.-C. Billaut (2005) 33–34.
- [6] B. Estellon, F. Gardi and K. Nouioua, Ordonnancement de véhicules dans les usines RENAULT: une approche par recherche locale à voisinage réduit, in Actes de ROADEF 2005, le 6${}^{\mathrm{e}}$ Congrès de la Société Française de Recherche Opérationnelle et d’Aide à la Décision, Tours, France, edited by J.-C. Billaut (2005) 35–36.
- [7] B. Estellon, F. Gardi and K. Nouioua, Ordonnancement de véhicules: une approche par recherche locale à voisinage large, in Actes des JFPC 2005, les 1${}^{\mathrm{res}}$ Journées Francophones de Programmation par Contraintes, Lens, France, edited by C. Solnon (2005) 21–28.
- [8] B. Estellon, F. Gardi and K. Nouioua, Two local search approaches for solving real-life car sequencing problems. Submitted to European Journal of Operational Research (2006). Zbl1156.90361
- [9] M. Fischetti and A. Lodi, Local branching. Mathematical Programming Series B 98 (2003) 23–47. Zbl1060.90056
- [10] I.P. Gent, Two results on car sequencing problem. APES Research Report 02-1998. Department of Computer Science, University of Strathclyde, Glasgow, Scotland, UK (1998).
- [11] I.P. Gent and T. Walsh, CSPlib: a benchmark library for constraints. APES Research Report 09-1999. Department of Computer Science, University of Strathclyde, Glasgow, Scotland, UK (1999). http://www.csplib.org/
- [12] J. Gottlieb, M. Puchta and C. Solnon, A study of greedy, local search and ant colony optimization approaches for car sequencing problems, in Proceedings of EvoWorkshops 2003 on Applications of Evolutionary Computing, edited by G.R. Raidl et al., Springer-Verlag, Berlin, Germany, Lect. Notes. Comput Sci. 2611 (2003) 246–257. Zbl1033.90503
- [13] M. Gravel, C. Gagné and W.L. Price, Review and comparison of three methods for the solution of the car sequencing problem. J. Oper. Res. Soc. 56 (2005) 1287–1295. Zbl1082.90590
- [14] R. Jonker and A. Volgenant, A shortest augmenting path algorithm for dense ans sparse linear assignment problems. Computing 38 (1987) 325–340. http://www.magiclogic.com/assignment.html Zbl0607.90056
- [15] Y. Khacheni and A. Nguyen, Personnal communication (2006).
- [16] T. Kis, On the complexity of the car sequencing problem. Oper. Res. Lett. 32 (2004) 331–335. Zbl1054.90034
- [17] A. Makhorin, GLPK library (GNU Linear Programming Kit, version 4.9) (2006). http://www.gnu.org/software/glpk/
- [18] T. Mautor and P. Michelon, MIMAUSA: a new hybrid method combining exact solution and local search, in MIC 97, the 2nd Metaheuristics International Conference, Sophia-Antipolis, France (1997).
- [19] S. Morin, C. Gagné, M. Gravel and W.L. Price, Trace de phéromone spécialisée dans un algorithme de fourmi pour le problème de “car sequencing”, in Actes de MOSIM 2006, la 6ème Conférence Francophone de Modélisation et Simulation, Rabat, Maroc, edited by M. Gournand and F. Riane (2006) 22–29.
- [20] L. Michel and P. Van Hentenryck, A constraint-based architecture for local search, in Proceedings of OOPSLA 2002, the 2002 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications, ACM Press, New York, NY SIGPLAN Notices 37 (2002) 83–100.
- [21] M. Palpant, Recherche exacte et approchée en optimisation combinatoire: schémas d’intégration et applications, Ph.D. Thesis. Laboratoire d’Informatique d’Avignon, Université d’Avignon et des Pays de Vaucluse, Avignon, France (2005).
- [22] M. Palpant, C. Artigues and P. Michelon, LSSPER: solving the ressource-constrained project scheduling problem with large neighborhood search. Ann. Oper. Res. 31 (2004) 237–257. Zbl1066.90037
- [23] L. Perron and P. Shaw, Combining forces to solve the car sequencing problem, in Proceedings of CPAIOR 2004, the 1st International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, edited by J.-C. Rëgin and M. Rueher, Springer-Verlag, Berlin, Germany, Lect. Note Comput Sci. 3011 (2004) 225–239. Zbl1094.68651
- [24] L. Perron, P. Shaw and V. Furnon, Propagation guided large neighborhood search, in Proceedings of CP 2004, the 10th International Conference on Principles and Practice of Constraint Programming, edited by M. Wallace, Springer-Verlag, Berlin, Germany, Lect. Note Comput Sci. 3258 (2004) 468–481. Zbl1152.68572
- [25] M. Prandtstetter and G.R. Raidl, A variable neighborhood search approach for solving the car sequencing problem, in Proceedings of the 18th Mini Euro Conference on Variable Neighborhood Search, edited by P. Hansen, N. Mladenovic, J.A. Moreno Pérez, J.M. Moreno Vega and B. Melián Batista, Tenerife, Spain (2005). Zbl1156.90321
- [26] M. Prandtstetter and G.R. Raidl, An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem. Technical Report TR-186-1-05-01. Institut for Computer Graphics and Algorithms, Vienna University of Technology, Vienna, Austria (2005).
- [27] M. Prandtstetter, Personnal communication (2006).
- [28] M. Puchta and J. Gottlieb, Solving car sequencing problems by local optimization, in Proceedings of EvoWorkshops 2002 on Applications of Evolutionary Computing, edited by S. Cagnoni et al., Springer-Verlag, Berlin, Germany, Lect. Note Comput Sci. 2279 (2002) 132–142. Zbl1044.68791
- [29] J.-C. Régin and J.-F. Puget, A filtering algorithm for global sequencing constraints, in Proceedings of CP 97, the 3rd International Conference on Principles and Practice of Constraint Programming, edited by G. Smolka, Springer-Verlag, Berlin, Germany, Lect. Note Comput Sci. 1330 (1997) 32–46.
- [30] C. Ribeiro, D. Aloise, T. Noronha, C. Rocha and S. Urrutia, A hybrid heuristic for a real-life car sequencing problem with multiple requirements, in Proceedings of the 18th Mini Euro Conference on Variable Neighborhood Search, edited by P. Hansen, N. Mladenovic, J.A. Moreno Pérez, J.M. Moreno Vega and B. Melián Batista, Tenerife, Spain (2005). Zbl1156.90322
- [31] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency. Springer-Verlag, Berlin, Germany, Algorithms and Combinatorics 24 (2003). Zbl1041.90001
- [32] C. Solnon, Solving permutation contraint satisfaction problems with artificial ants, in Proceedings of ECAI 2000, the 14th European Conference on Artificial Intelligence, edited by H. Werner, IOS Press, Amsterdam, The Netherlands, (2000) 118–122.
- [33] C. Solnon, Des fourmis pour le problème de l’ordonnancement de voitures, in Actes des JFPC 2006, les 2${}^{\mathrm{es}}$ Journées Francophones de Programmation par Contraintes, Nîmes, France, edited by L. Henocque (2006) 305–316.
- [34] R.E. Tarjan, Data Structures and Network Algorithms. SIAM Publications, Philadelphie, PA, CBMS-NSF Regional Conference Series in Applied Mathematics 44 (1983). Zbl0584.68077MR826534