Multiobjective Combinatorial Optimization Using a Single Deep Reinforcement Learning Model.

Area of Science:

• Artificial Intelligence
• Operations Research
• Computer Science

Background:

• Combinatorial multiobjective optimization problems (MOPs) are computationally challenging.
• Existing methods often struggle with scalability and real-time performance for large-scale MOPs.
• The multiobjective traveling salesman problem (MOTSP) is a canonical example of MOPs.

Purpose of the Study:

• To introduce a unified deep reinforcement learning (DRL) framework for solving MOPs.
• To develop an efficient method for generating approximate Pareto-optimal solutions for MOTSP.
• To demonstrate the real-time performance and superiority of the proposed DRL approach.

Main Methods:

• An encoder-decoder framework utilizing a novel routing encoder to process MOTSP instances.
• Adaptive aggregation of global and objective-specific embeddings via a routing network.
• A modified context embedding feeding into a parallel decoder for solution generation.
• A Top-k baseline for efficient training and data utilization.

Main Results:

• The proposed DRL method achieves real-time performance in solving MOTSP instances.
• The approach demonstrates superior performance compared to heuristic-based and learning-based algorithms.
• Effectiveness is particularly pronounced on large-scale MOTSP instances.

Conclusions:

• A single DRL model can effectively address combinatorial multiobjective optimization.
• The proposed method offers a scalable and efficient solution for MOTSP.
• This work advances the application of DRL in complex optimization domains.