Quadratic Unconstrained Binary Optimization for the Automotive Paint Shop Problem
The Binary Paint Shop Problem (BPSP) is a combinatorial optimization problem which draws inspiration from the automotive paint shop. Its binary nature, making it a good fit for Quadratic Unconstrained Binary Optimization (QUBO) solvers, has been well studied but its industrial applications are limit...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2023-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10246152/ |
| _version_ | 1827818137684279296 |
|---|---|
| author | Pieter Debevere Masahiko Sugimura Matthieu Parizy |
| author_facet | Pieter Debevere Masahiko Sugimura Matthieu Parizy |
| author_sort | Pieter Debevere |
| collection | DOAJ |
| description | The Binary Paint Shop Problem (BPSP) is a combinatorial optimization problem which draws inspiration from the automotive paint shop. Its binary nature, making it a good fit for Quadratic Unconstrained Binary Optimization (QUBO) solvers, has been well studied but its industrial applications are limited. In this paper, in order to expand the industrial applications, QUBO formulations for two generalizations of the BPSP, which are the Multi-Car Paint Shop Problem (MCPSP) and the Multi-Car Multi-Color Paint Shop Problem (MCMCPSP), are proposed. Given the multiple colors, the MCMCPSP is no longer natively binary which increases the problem size and introduces additional constraint factors in the QUBO formulation. Resulting QUBOs are solved using Scatter Search (SS). Furthermore, extensions of the SS that can exploit k-hot constrained structures within the formulations are proposed to compensate the additional complexity introduced by formulating non-binary problems into QUBO. Since no public benchmark database currently exists, random problem instances are generated. Viability of the proposed QUBO solving methods for the MCPSP and MCMCPSP, is highlighted through comparison with an integer-based Random Parallel Multi-start Tabu Search (RPMTS) and a greedy heuristic for the problems. The greedy heuristic has negligible computational requirements and therefore serves as a lower bound on the desired performance. The results for both problems show that better results can be obtained than the greedy heuristic and integer-based RPMTS, by using the novel k-hot extensions of the SS to solve the problems as QUBO. |
| first_indexed | 2024-03-12T00:43:40Z |
| format | Article |
| id | doaj.art-ea30d37e906146d3a6da3c73bf92711c |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-03-12T00:43:40Z |
| publishDate | 2023-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-ea30d37e906146d3a6da3c73bf92711c2023-09-14T23:01:28ZengIEEEIEEE Access2169-35362023-01-0111977699777710.1109/ACCESS.2023.331310210246152Quadratic Unconstrained Binary Optimization for the Automotive Paint Shop ProblemPieter Debevere0https://orcid.org/0009-0001-9553-5838Masahiko Sugimura1https://orcid.org/0009-0006-8117-9752Matthieu Parizy2https://orcid.org/0000-0002-5777-7756Fujitsu Ltd., Kawasaki, JapanFujitsu Ltd., Kawasaki, JapanFujitsu Ltd., Kawasaki, JapanThe Binary Paint Shop Problem (BPSP) is a combinatorial optimization problem which draws inspiration from the automotive paint shop. Its binary nature, making it a good fit for Quadratic Unconstrained Binary Optimization (QUBO) solvers, has been well studied but its industrial applications are limited. In this paper, in order to expand the industrial applications, QUBO formulations for two generalizations of the BPSP, which are the Multi-Car Paint Shop Problem (MCPSP) and the Multi-Car Multi-Color Paint Shop Problem (MCMCPSP), are proposed. Given the multiple colors, the MCMCPSP is no longer natively binary which increases the problem size and introduces additional constraint factors in the QUBO formulation. Resulting QUBOs are solved using Scatter Search (SS). Furthermore, extensions of the SS that can exploit k-hot constrained structures within the formulations are proposed to compensate the additional complexity introduced by formulating non-binary problems into QUBO. Since no public benchmark database currently exists, random problem instances are generated. Viability of the proposed QUBO solving methods for the MCPSP and MCMCPSP, is highlighted through comparison with an integer-based Random Parallel Multi-start Tabu Search (RPMTS) and a greedy heuristic for the problems. The greedy heuristic has negligible computational requirements and therefore serves as a lower bound on the desired performance. The results for both problems show that better results can be obtained than the greedy heuristic and integer-based RPMTS, by using the novel k-hot extensions of the SS to solve the problems as QUBO.https://ieeexplore.ieee.org/document/10246152/Automotive paint shopevolutionary algorithmsk-hot constraintsquadratic unconstrained binary optimizationscatter search |
| spellingShingle | Pieter Debevere Masahiko Sugimura Matthieu Parizy Quadratic Unconstrained Binary Optimization for the Automotive Paint Shop Problem IEEE Access Automotive paint shop evolutionary algorithms k-hot constraints quadratic unconstrained binary optimization scatter search |
| title | Quadratic Unconstrained Binary Optimization for the Automotive Paint Shop Problem |
| title_full | Quadratic Unconstrained Binary Optimization for the Automotive Paint Shop Problem |
| title_fullStr | Quadratic Unconstrained Binary Optimization for the Automotive Paint Shop Problem |
| title_full_unstemmed | Quadratic Unconstrained Binary Optimization for the Automotive Paint Shop Problem |
| title_short | Quadratic Unconstrained Binary Optimization for the Automotive Paint Shop Problem |
| title_sort | quadratic unconstrained binary optimization for the automotive paint shop problem |
| topic | Automotive paint shop evolutionary algorithms k-hot constraints quadratic unconstrained binary optimization scatter search |
| url | https://ieeexplore.ieee.org/document/10246152/ |
| work_keys_str_mv | AT pieterdebevere quadraticunconstrainedbinaryoptimizationfortheautomotivepaintshopproblem AT masahikosugimura quadraticunconstrainedbinaryoptimizationfortheautomotivepaintshopproblem AT matthieuparizy quadraticunconstrainedbinaryoptimizationfortheautomotivepaintshopproblem |