Scholarlink

<p>The Vehicle Routing Problem (VRP) and its variant, the Capacitated VRP (CVRP), are significant optimization challenges in transportation and logistics, impacting fleet management and delivery services. The CVRP focuses on finding efficient delivery routes for a fleet of vehicles while adhering to capacity constraints. This study introduces two algorithms to address this problem: the Hybrid Genetic Search (HGS) and the Parallel Hybrid Genetic Search (PHGS). The HGS combines genetic algorithms with local search techniques for optimal CVRP solutions. In contrast, the PHGS enhances the HGS by incorporating parallel processing through the Island Genetic Algorithm, leading to improved performance and better resource utilization. The PHGS runs the HGS as an evolutionary algorithm on multiple islands, allowing for independent evolution while sharing information during migration. Performance comparisons show that PHGS surpasses HGS across all metrics: it achieves a lower average gap, a higher number of best-known solutions (BKS), and faster times for finding these solutions. Thus, the PHGS proves to be a more effective approach to solving the CVRP.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A Parallel Hybrid Genetic Search for Solving the Capacitated Vehicle Routing Problem

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年11月17日

查看全文
  • Mohammad Jamshidi,
  • Mehdi Alirezanejad,
  • Homayun Motameni,
  • Rasul Enayatifar

摘要

The Vehicle Routing Problem (VRP) and its variant, the Capacitated VRP (CVRP), are significant optimization challenges in transportation and logistics, impacting fleet management and delivery services. The CVRP focuses on finding efficient delivery routes for a fleet of vehicles while adhering to capacity constraints. This study introduces two algorithms to address this problem: the Hybrid Genetic Search (HGS) and the Parallel Hybrid Genetic Search (PHGS). The HGS combines genetic algorithms with local search techniques for optimal CVRP solutions. In contrast, the PHGS enhances the HGS by incorporating parallel processing through the Island Genetic Algorithm, leading to improved performance and better resource utilization. The PHGS runs the HGS as an evolutionary algorithm on multiple islands, allowing for independent evolution while sharing information during migration. Performance comparisons show that PHGS surpasses HGS across all metrics: it achieves a lower average gap, a higher number of best-known solutions (BKS), and faster times for finding these solutions. Thus, the PHGS proves to be a more effective approach to solving the CVRP.