A hybrid algorithm based on tabu search and large neighbourhood search for car sequencing problem

Abstract

The car sequencing problem (CSP) concerns a production sequence of different types of cars in the mixed-model assembly line. A hybrid algorithm is proposed to find an assembly sequence of CSP with minimum violations. Firstly, the hybrid algorithm is based on the tabu search and large neighborhood search (TLNS), servicing as the framework. Moreover, two components are incorporated into the hybrid algorithm. One is the parallel constructive heuristic (PCH) that is used to construct a set of initial solutions and find some high quality solutions, and the other is the small neighborhood search (SNS) which is designed to improve the new constructed solutions. The computational results show that the proposed hybrid algorithm (PCH+TLNS+SNS) obtains 100 best known values out of 109 public instances, among these 89 instances get their best known values with 100% success rate. By comparing with the well-known related algorithms, computational results demonstrate the effectiveness, efficiency and robustness of the proposed algorithm.

Keywords

car sequencing problem / large neighborhood search / tabu search / ratio constraint

References

[1] KisT. On the complexity of the car sequencing problem [J]. Operations Research Letters, 2004, 32(4): 331-335

[2] GentI P, WalshT. CSPLib: a benchmark library for constraints [C]. //Proceedings of the Principles and Practice of Constraint Programming, 1999, Springer Berlin Heidelberg, Berlin, Germany: 480481

[3] GottliebJ, PuchtaM, SolnonC. A study of greedy, local search, and ant colony optimization approaches for car sequencing problems [C]. //Applications of Evolutionary Computing, 2003, Springer Berlin Heidelberg, Berlin, Germany: 246257

[4] FliednerM, BoysenN. Solving the car sequencing problem via Branch & Bound [J]. European Journal of Operational Research, 2008, 191(3): 1023-1042

[5] ArtiguesC, HebrardE, Mayer-EichbergerV. SAT and hybrid models of the car sequencing problem [C]. //AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 2014, Springer International Publishing, Cham, Switzerland: 268283

[6] GolleU, RothlaufF, BoysenN. Iterative beam search for car sequencing [J]. Annals of Operations Research, 2015, 226(1): 239-254

[7] ZhangX-y, GaoL, WenL, HuangZ-dong. Parallel construction heuristic combined with constraint propagation for the car sequencing problem [J]. Chinese Journal of Mechanical Engineering, 2017, 30(2): 373-384

[8] SialaM, HebrardE, HuguetM J. A study of constraint programming heuristics for the car-sequencing problem [J]. Engineering Applications of Artificial Intelligence, 2015, 38: 34-44

[9] BautistaJ, PereiraJ, Adenso-DíazB. A GRASP approach for the extended car sequencing problem [J]. Journal of Scheduling, 2007, 11(1): 3-16

[10] SolnonC, CungV D, NguyenA. The car sequencing problem: Overview of state-of-the-art methods and industrial case-study of the ROADEF’2005 challenge problem [J]. European Journal of Operational Research, 2008, 191(3): 912-927

[11] CordeauJ F, LaporteG, PasinF. Iterated tabu search for the car sequencing problem [J]. European Journal of Operational Research, 2008, 191(3): 945-956

[12] BriantO, NaddefD, MouniéG. Greedy approach and multi-criteria simulated annealing for the car sequencing problem [J]. European Journal of Operational Research, 2008, 191(3): 993-1003

[13] GaoG-b, ZhangG-j, HuangG. Solving material distribution routing problem in mixed manufacturing systems with a hybrid multi-objective evolutionary algorithm [J]. Journal of Central South University, 2012, 19(2): 433-442

[14] PerronL, ShawP, FurnonV. Propagation guided large neighborhood search [C]. //Principles and Practice of Constraint Programming, 2004, Springer Berlin Heidelberg, Berlin, Germany: 468481

[15] GravelM, GagnéC, PriceW. Review and comparison of three methods for the solution of the car sequencing problem [J]. Journal of the Operational Research Society, 2005, 56(11): 1287-1295

[16] PrandtstetterM, RaidlG R. An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem [J]. European Journal of Operational Research, 2008, 191(3): 1004-1022

[17] ZinflouA, GagnéC, GravelM. Genetic algorithm with hybrid integer linear programming crossover operators for the car-sequencing problem [J]. INFOR: Information Systems and Operational Research, 2010, 48(1): 23-37

[18] ThiruvadyD R, MeyerB, ErnstA. Car sequencing with constraint-based ACO. [C]//Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, ACM, 2011163170

[19] ThiruvadyD, ErnstA, WallaceM. A Lagrangian-ACO matheuristic for car sequencing [J]. EURO Journal on Computational Optimization, 2014, 2(4): 279-296

[20] DrexlA, KimmsA. Sequencing JIT mixed-model assembly lines under station-load and part-usage constraints [J]. Management Science, 2001, 47(3): 480-491

[21] ShawP. Using constraint programming and local search methods to solve vehicle routing problems [C]. //Principles and Practice of Constraint Programming, 1998, Springer Berlin Heidelberg, Berlin, Germany: 417431

[22] PisingerD, RopkeS. Large neighborhood search. [M]//Handbook of metaheuristics, 2010399419

[23] Prud’HommeC, LorcaX, JussienN. Explanationbased large neighborhood search [J]. Constraints, 2014, 19(4): 339-379

[24] DemirE, BektaşT, LaporteG. An adaptive large neighborhood search heuristic for the Pollution-Routing Problem [J]. European Journal of Operational Research, 2012, 223(2): 346-359

[25] BlumC, RaidlG R. Hybridization based on large neighborhood search [M]. //Hybrid Metaheuristics, 2016, Springer International Publishing, Cham, Switzerland: 6382

[26] GavranovićH. Local search and suffix tree for car-sequencing problem with colors[J]. European Journal of Operational Research, 2008, 191(3): 972-980

[27] ZuffereyN. Tabu search approaches for two car sequencing problems with smoothing constraints metaheuristics for production systems [M]. Cham, Switzerland: Springer International Publishing, 2016167190

[28] RangaswamyB, JainA S, GloverF. Tabu search candidate list strategies in scheduling. [C]//Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search: Interfaces in Computer Science and Operations Research, 1998215233