An Improved Genetic Algorithm for Solving the Semi-Soft Clustered Vehicle Routing Problem
The Semi-Soft Clustered Vehicle Routing Problem (SemiSoftCluVRP) is a relaxed version of the Clustered Vehicle Routing Problem (CluVRP) and an enhanced variant of the Soft Clustered Vehicle Routing Problem (SoftCluVRP). In the SemiSoftCluVRP, all customers are partitioned into several clusters, and...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-04-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/15/9/4871 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850277564096970752 |
|---|---|
| author | Yihao Miao Xiaoguang Bao |
| author_facet | Yihao Miao Xiaoguang Bao |
| author_sort | Yihao Miao |
| collection | DOAJ |
| description | The Semi-Soft Clustered Vehicle Routing Problem (SemiSoftCluVRP) is a relaxed version of the Clustered Vehicle Routing Problem (CluVRP) and an enhanced variant of the Soft Clustered Vehicle Routing Problem (SoftCluVRP). In the SemiSoftCluVRP, all customers are partitioned into several clusters, and these clusters are further divided into two types: hard clusters and soft clusters. Within a hard cluster, customers must be served by the same vehicle without interruption, whereas within a soft cluster, customers must also be served by the same vehicle, but interruptions are permitted. To solve this problem, a mathematical model is first developed, followed by the design of a two-level genetic algorithm that integrates a variable neighborhood descent method. Computational experiments demonstrate that the proposed algorithm produces high-quality solutions and exhibits excellent performance. Compared with the results of CluVRP and SoftCluVRP, the results of SemiSoftCluVRP can reduce and increase logistics costs by up to 6.50% and 7.52%, respectively. In practical applications, by adjusting the hard and soft attributes of clusters, more flexible decision-making references can be provided for relevant decision-makers. |
| format | Article |
| id | doaj-art-73c73116c4ef490a9d74368613691a98 |
| institution | OA Journals |
| issn | 2076-3417 |
| language | English |
| publishDate | 2025-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj-art-73c73116c4ef490a9d74368613691a982025-08-20T01:49:50ZengMDPI AGApplied Sciences2076-34172025-04-01159487110.3390/app15094871An Improved Genetic Algorithm for Solving the Semi-Soft Clustered Vehicle Routing ProblemYihao Miao0Xiaoguang Bao1College of Information Technology, Shanghai Ocean University, Shanghai 201306, ChinaCollege of Information Technology, Shanghai Ocean University, Shanghai 201306, ChinaThe Semi-Soft Clustered Vehicle Routing Problem (SemiSoftCluVRP) is a relaxed version of the Clustered Vehicle Routing Problem (CluVRP) and an enhanced variant of the Soft Clustered Vehicle Routing Problem (SoftCluVRP). In the SemiSoftCluVRP, all customers are partitioned into several clusters, and these clusters are further divided into two types: hard clusters and soft clusters. Within a hard cluster, customers must be served by the same vehicle without interruption, whereas within a soft cluster, customers must also be served by the same vehicle, but interruptions are permitted. To solve this problem, a mathematical model is first developed, followed by the design of a two-level genetic algorithm that integrates a variable neighborhood descent method. Computational experiments demonstrate that the proposed algorithm produces high-quality solutions and exhibits excellent performance. Compared with the results of CluVRP and SoftCluVRP, the results of SemiSoftCluVRP can reduce and increase logistics costs by up to 6.50% and 7.52%, respectively. In practical applications, by adjusting the hard and soft attributes of clusters, more flexible decision-making references can be provided for relevant decision-makers.https://www.mdpi.com/2076-3417/15/9/4871vehicle routing problemclustered vehicle routing problemhard clusterssoft clustersgenetic algorithmvariable neighborhood descent |
| spellingShingle | Yihao Miao Xiaoguang Bao An Improved Genetic Algorithm for Solving the Semi-Soft Clustered Vehicle Routing Problem Applied Sciences vehicle routing problem clustered vehicle routing problem hard clusters soft clusters genetic algorithm variable neighborhood descent |
| title | An Improved Genetic Algorithm for Solving the Semi-Soft Clustered Vehicle Routing Problem |
| title_full | An Improved Genetic Algorithm for Solving the Semi-Soft Clustered Vehicle Routing Problem |
| title_fullStr | An Improved Genetic Algorithm for Solving the Semi-Soft Clustered Vehicle Routing Problem |
| title_full_unstemmed | An Improved Genetic Algorithm for Solving the Semi-Soft Clustered Vehicle Routing Problem |
| title_short | An Improved Genetic Algorithm for Solving the Semi-Soft Clustered Vehicle Routing Problem |
| title_sort | improved genetic algorithm for solving the semi soft clustered vehicle routing problem |
| topic | vehicle routing problem clustered vehicle routing problem hard clusters soft clusters genetic algorithm variable neighborhood descent |
| url | https://www.mdpi.com/2076-3417/15/9/4871 |
| work_keys_str_mv | AT yihaomiao animprovedgeneticalgorithmforsolvingthesemisoftclusteredvehicleroutingproblem AT xiaoguangbao animprovedgeneticalgorithmforsolvingthesemisoftclusteredvehicleroutingproblem AT yihaomiao improvedgeneticalgorithmforsolvingthesemisoftclusteredvehicleroutingproblem AT xiaoguangbao improvedgeneticalgorithmforsolvingthesemisoftclusteredvehicleroutingproblem |