Multi-Task Multi-Objective Evolutionary Search Based on Deep Reinforcement Learning for Multi-Objective Vehicle Routing Problems with Time Windows

Jianjun Deng, Junjie Wang, Xiaojun Wang, Yiqiao Cai, Peizhong LiuSymmetry 2024 · OpenReview

TL;DR

This paper introduces MTMO/DRL-AT, a novel algorithm that combines Deep Reinforcement Learning (DRL) with Evolutionary Multi-Task Optimization (EMTO) to tackle the complex Multi-Objective Vehicle Routing Problem with Time Windows (MOVRPTW). By framing the problem as a multi-task learning scenario with an "assisted" simpler task, the approach effectively leverages knowledge transfer to achieve superior performance in finding optimal routes.

What Problem Does This Paper Address?

The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known challenge in logistics and supply chain management. A particularly difficult variant is the Multi-Objective VRPTW (MOVRPTW), which involves optimizing five conflicting objectives simultaneously: minimizing the number of vehicles, total travel distance, longest route travel time, total waiting time, and total delay time. Traditional optimization methods struggle with the high dimensionality and conflicting nature of these objectives. While Deep Reinforcement Learning (DRL) has shown promise for single-objective routing problems, its application to many-objective scenarios, especially those with interdependencies between objectives, remains a significant challenge. This paper aims to bridge this gap by developing an approach that can effectively handle multiple conflicting objectives in VRPTW.

Methods

The core of the proposed solution is the MTMO/DRL-AT algorithm, which integrates DRL with EMTO. Here's a breakdown of the key techniques:

  • Multi-Task Learning Framework: The MOVRPTW is treated as a main task. A simpler, two-objective "assisted task" (minimizing total travel distance and longest route travel time) is constructed. This allows the algorithm to learn from a less complex, related problem.
  • DRL-based Subproblem Solving: Each objective (or a combination of objectives in the assisted task) is decomposed into scalar optimization subproblems. These subproblems are then solved using an attention model trained via DRL. The trained DRL models provide high-quality initial solutions.
  • Knowledge Transfer: The algorithm leverages a transfer reproduction operator to share learned knowledge between the main task and the assisted task. This helps to improve the search efficiency and solution quality for the main problem.
  • Evolutionary Multi-Task Optimization (EMTO): The main and assisted tasks are optimized concurrently within a multitasking scenario, allowing for the exploitation of synergies between them.
  • Local Search Operators: Objectivewise local searches are employed to further refine the solutions obtained from the evolutionary and DRL components.

Datasets

The paper utilizes a set of 45 real-world MOVRPTW instances for evaluation. These instances were originally described in [9] and are derived from data from an actual distribution company. They vary in the number of customers (50, 150, or 250), time window profiles (1-5), and vehicle capacities. For model training, synthetic instances were generated with asymmetric distance and time matrices, reflecting real-world conditions.

Key Insights and Ideas

  • Assisted Task for Complexity Reduction: Constructing a simpler, related "assisted task" is a powerful strategy to guide the optimization of a complex multi-objective problem. It provides a more manageable learning target that can inform the more challenging main task.
  • DRL as an Intelligent Initializer: Using DRL-trained models to generate initial solutions for an evolutionary algorithm significantly outperforms random initialization. This suggests DRL can effectively capture problem structure and provide a strong starting point.
  • Synergy of DRL and EMTO: The combination of DRL's ability to learn complex patterns and EMTO's capacity for multitasking and knowledge sharing creates a potent approach for tackling multi-objective optimization problems.
  • Knowledge Transfer is Crucial: The experimental results strongly support the effectiveness of the knowledge transfer strategy between the main and assisted tasks, demonstrating its positive impact on both convergence and diversity.

Key Results

The MTMO/DRL-AT demonstrated superior performance compared to several state-of-the-art algorithms:

  • vs. LSMOVRPTW: The MTMO/DRL-AT significantly outperformed LSMOVRPTW on 41 out of 45 instances for the IGD metric and all 45 instances for the HV metric. Statistical analysis (Wilcoxon test) confirmed significant differences.
  • vs. MMA-ALSC and HEMT: The MTMO/DRL-AT showed superior performance against both MMA-ALSC and HEMT. For IGD, it outperformed MMA-ALSC on 35 instances and HEMT on 40 instances. For HV, it outperformed both on all 45 instances.
  • Overall Comparison: In a comprehensive comparison using Friedman's test, MTMO/DRL-AT achieved the top ranking for both IGD and HV metrics.

Limitations and Future Work

  • Parameter Sensitivity: The authors acknowledge that the chosen parameter settings might not be globally optimal and that further investigation into their impact is warranted.
  • Future Work:
    • Enhancing DRL modeling by incorporating more informative structural information from problem instances.
  • Exploring more effective strategies for leveraging knowledge from assisted tasks.
  • Conducting a thorough investigation into the impact of key parameters.
  • Extending the application of MTMO/DRL-AT to other multi-objective combinatorial optimization problems.

Summary updated

Abstract

The vehicle routing problem with time windows (VRPTW) is a widely studied combinatorial optimization problem in supply chains and logistics within the last decade. Recent research has explored the potential of deep reinforcement learning (DRL) as a promising solution for the VRPTW. However, the challenge of addressing the VRPTW with many conflicting objectives (MOVRPTW) still remains for DRL. The MOVRPTW considers five conflicting objectives simultaneously: minimizing the number of vehicles required, the total travel distance, the travel time of the longest route, the total waiting time for early arrivals, and the total delay time for late arrivals. To tackle the MOVRPTW, this study introduces the MTMO/DRP-AT, a multi-task multi-objective evolutionary search algorithm, by making full use of both DRL and the multitasking mechanism. In the MTMO/DRL-AT, a two-objective MOVRPTW is constructed as an assisted task, with the objectives being to minimize the total travel distance and the travel time of the longest route. Both the main task and the assisted task are simultaneously solved in a multitasking scenario. Each task is decomposed into scalar optimization subproblems, which are then solved by an attention model trained using DRL. The outputs of these trained models serve as the initial solutions for the MTMO/DRL-AT. Subsequently, the proposed algorithm incorporates knowledge transfer and multiple local search operators to further enhance the quality of these promising solutions. The simulation results on real-world benchmarks highlight the superior performance of the MTMO/DRL-AT compared to several other algorithms in solving the MOVRPTW.
BibTeX
@inproceedings{deng2024multi,
  author = {Jianjun Deng and Junjie Wang and Xiaojun Wang and Yiqiao Cai and Peizhong Liu},
  title = {{Multi-Task Multi-Objective Evolutionary Search Based on Deep Reinforcement Learning for Multi-Objective Vehicle Routing Problems with Time Windows}},
  booktitle = {Symmetry},
  year = {2024},
  url = {https://openreview.net/forum?id=Kn6S5tScxs},
}
Figure