A Combined Diffusion Model and Reinforcement Learning Approach for Solving the Vehicle Routing Problem With Multiple Soft Time Windows
The Vehicle Routing Problem with Multiple Soft Time Windows (VRPMSTW) is a challenging combinatorial optimization problem where a fleet of vehicles must deliver goods to a set of customers, adhering to time windows while minimizing costs. In this paper, we propose a novel solution approach that comb...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/11053837/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849424091503656960 |
|---|---|
| author | Yu Qiao Jianjun Miao Xiaoying Huang |
| author_facet | Yu Qiao Jianjun Miao Xiaoying Huang |
| author_sort | Yu Qiao |
| collection | DOAJ |
| description | The Vehicle Routing Problem with Multiple Soft Time Windows (VRPMSTW) is a challenging combinatorial optimization problem where a fleet of vehicles must deliver goods to a set of customers, adhering to time windows while minimizing costs. In this paper, we propose a novel solution approach that combines a Diffusion Model with Reinforcement Learning (RL) to efficiently solve the VRPMSTW. The Diffusion Model generates feasible vehicle routes by denoising a noise distribution, ensuring that constraints such as vehicle capacity, travel distance, and time windows are respected. Subsequently, the RL module fine-tunes these paths by optimizing the objective function, which minimizes the number of vehicles, travel distance, and time window penalties. We evaluate our approach on benchmark datasets and compare it with other state-of-the-art methods. The results demonstrate that our combined model outperforms traditional heuristics, achieving better optimization in terms of the number of vehicles, travel cost, and time window violations. The proposed method provides a promising solution for solving complex real-world vehicle routing problems with soft time window constraints. |
| format | Article |
| id | doaj-art-2ec4e693cb5a4568a2d26cbb038bbe02 |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-2ec4e693cb5a4568a2d26cbb038bbe022025-08-20T03:30:20ZengIEEEIEEE Access2169-35362025-01-011311352911354310.1109/ACCESS.2025.358398411053837A Combined Diffusion Model and Reinforcement Learning Approach for Solving the Vehicle Routing Problem With Multiple Soft Time WindowsYu Qiao0https://orcid.org/0009-0006-7874-639XJianjun Miao1Xiaoying Huang2School of Management, Guangzhou Huali College, Guangzhou, ChinaSchool of Economics and Management, Nanjing University of Aeronautics and Astronautics, Nanjing, ChinaInstitute of Foreign Languages and Trade, Guangzhou Vocational and Technical University of Science and Technology, Guangzhou, ChinaThe Vehicle Routing Problem with Multiple Soft Time Windows (VRPMSTW) is a challenging combinatorial optimization problem where a fleet of vehicles must deliver goods to a set of customers, adhering to time windows while minimizing costs. In this paper, we propose a novel solution approach that combines a Diffusion Model with Reinforcement Learning (RL) to efficiently solve the VRPMSTW. The Diffusion Model generates feasible vehicle routes by denoising a noise distribution, ensuring that constraints such as vehicle capacity, travel distance, and time windows are respected. Subsequently, the RL module fine-tunes these paths by optimizing the objective function, which minimizes the number of vehicles, travel distance, and time window penalties. We evaluate our approach on benchmark datasets and compare it with other state-of-the-art methods. The results demonstrate that our combined model outperforms traditional heuristics, achieving better optimization in terms of the number of vehicles, travel cost, and time window violations. The proposed method provides a promising solution for solving complex real-world vehicle routing problems with soft time window constraints.https://ieeexplore.ieee.org/document/11053837/Vehicle routing problem (VRP)multiple soft time windows (VRPMSTW)diffusion modelreinforcement learning (RL)combinatorial optimizationpath generation |
| spellingShingle | Yu Qiao Jianjun Miao Xiaoying Huang A Combined Diffusion Model and Reinforcement Learning Approach for Solving the Vehicle Routing Problem With Multiple Soft Time Windows IEEE Access Vehicle routing problem (VRP) multiple soft time windows (VRPMSTW) diffusion model reinforcement learning (RL) combinatorial optimization path generation |
| title | A Combined Diffusion Model and Reinforcement Learning Approach for Solving the Vehicle Routing Problem With Multiple Soft Time Windows |
| title_full | A Combined Diffusion Model and Reinforcement Learning Approach for Solving the Vehicle Routing Problem With Multiple Soft Time Windows |
| title_fullStr | A Combined Diffusion Model and Reinforcement Learning Approach for Solving the Vehicle Routing Problem With Multiple Soft Time Windows |
| title_full_unstemmed | A Combined Diffusion Model and Reinforcement Learning Approach for Solving the Vehicle Routing Problem With Multiple Soft Time Windows |
| title_short | A Combined Diffusion Model and Reinforcement Learning Approach for Solving the Vehicle Routing Problem With Multiple Soft Time Windows |
| title_sort | combined diffusion model and reinforcement learning approach for solving the vehicle routing problem with multiple soft time windows |
| topic | Vehicle routing problem (VRP) multiple soft time windows (VRPMSTW) diffusion model reinforcement learning (RL) combinatorial optimization path generation |
| url | https://ieeexplore.ieee.org/document/11053837/ |
| work_keys_str_mv | AT yuqiao acombineddiffusionmodelandreinforcementlearningapproachforsolvingthevehicleroutingproblemwithmultiplesofttimewindows AT jianjunmiao acombineddiffusionmodelandreinforcementlearningapproachforsolvingthevehicleroutingproblemwithmultiplesofttimewindows AT xiaoyinghuang acombineddiffusionmodelandreinforcementlearningapproachforsolvingthevehicleroutingproblemwithmultiplesofttimewindows AT yuqiao combineddiffusionmodelandreinforcementlearningapproachforsolvingthevehicleroutingproblemwithmultiplesofttimewindows AT jianjunmiao combineddiffusionmodelandreinforcementlearningapproachforsolvingthevehicleroutingproblemwithmultiplesofttimewindows AT xiaoyinghuang combineddiffusionmodelandreinforcementlearningapproachforsolvingthevehicleroutingproblemwithmultiplesofttimewindows |