Algorithm design for real-world combinatorial optimisation problems

• Main Author: Zhang, Xianli
• Other Authors: Zhang Jie
• Format: Thesis-Master by Research
• Language: English
• Published: Nanyang Technological University 2024
• Subjects: Computer and Information Science; Combinatorial optimisation
• Online Access: https://hdl.handle.net/10356/181412
• Institution: Nanyang Technological University

Recently, there has been a noticeable trend in applying Combinatorial Optimisation Problem (COP) research to solve practical problems related to people’s daily lives such as logistics and production management. COPs have drawn much attention in research because of their Non-deterministic Polynomial (NP) hard challenges. Many solvers, including heuristic and learning-based methods, have been designed to solve COPs. The rise of Deep Learning, particularly the Transformer neural network architecture, has led to considerable progress in learning-based methods, which contrasts with heuristic methods that apply domain knowledge to design handcrafted rules. These solvers successfully solve COPs, but they both face challenges when solving real-world scenarios because real-world problems have characteristics of large scale and complicated constraints. Specifically, for routing problems, although the learning-based method has outperformed the heuristic, the learned model faces the challenge of poor generalisation ability. In real-world scheduling problems, the complexity of constraints makes it a challenge for current learning-based methods and traditional heuristics to handle effectively. To study such a gap, this thesis selects two practical problems in the categories of routing and scheduling as two representative COPs that are are the large-scale Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and the Complex Job Shop Scheduling Problem (CJSSP). This thesis begins by addressing the generalisation ability of learning-based routing Deep Learning models for CVRPTW on a large scale. It takes a pre-trained model as the base model and then enhances the generalisation ability of the model by fine-tuning it. We propose a novel pretraining and fine-tuning algorithm, Enhancing-to-Generalise, to adapt the pre-trained models to specific problem instances. With this algorithm, the pre-trained models are fine-tuned with label information from the exact instances. Additionally, TopK strategy is introduced in the trajectory of the solution optimisation process, which leads to the increase of exploration space. Extensive experiments show that our Enhancing-to-Generalise algorithm is comparable with the state-of-the-art (SOTA) method. Especially on benchmark datasets and large-scale real-world datasets, our algorithm performs better than SOTA. Next, the thesis addresses CJSSP with complex constraints. This highly constrained scheduling problem can hardly be handled by a learning-based method, and traditional heuristics are inefficient in terms of discrete solution space caused by constraints. Under the Genetic Algorithm (GA) framework, we propose a dedicated chromosome encoding scheme that includes all the constraints in the chromosome search space, and two chromosome decoding algorithms are proposed to ensure that the solutions are feasible. Our novel-designed and well-coupled encoding and decoding scheme can handle complex constraints and ensure that solutions are in a feasible search space so that they can search for optimal solutions globally and, therefore, efficiently. Experiments show our GA is comparable with SOTA methods. Our algorithm, especially on the industrial semiconductor manufacturing dataset, has better performance. Overall, this thesis studies two representative real-world COPs. For CVRPTW, we design a learning-based algorithm to enhance the generalisation ability of the pre-trained model. For CJSSJP, this thesis designs a GA with dedicated encoding and decoding schemes to tackle complex constraints from real-world manufacturing scenarios. Regarding the routing problem, tests are conducted on datasets with different distributions to verify the model’s performance after fine-tuning, and comparisons are made with the SOTA. Regarding the scheduling problem, comparisons are made with the SOTA using industrial data. The results show the advantages of the GA in searching for the global optimal solution.