Scholarlink

The Cumulative Vehicle Routing Problem (Cu-VRP) extends the classic Vehicle Routing Problem by incorporating fuel consumption considerations, which are crucial in transportation and logistics. In Cu-VRP with Stochastic Demands (Cu-VRPSD), the demand of each customer is unknown until the vehicle visits it. In this paper, we propose a randomized 2.5-approximation algorithm for splittable deliveries and a randomized 3.5-approximation algorithm for unsplittable deliveries, improving the best-known approximation ratios of 3.25 and 6, respectively. For Cu-VRP, since it is a special case of Cu-VRPSD, our algorithms also improve the best-known approximation ratios of 3.186 and 4, respectively. We apply our algorithms on the benchmark sets and the experimental results show that the quality of our computed solutions is much closer to optimality than the provable approximation ratio.

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

Improved Approximation Algorithms for the Cumulative Vehicle Routing Problem

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Jingyang Zhao,
  • Mingyu Xiao

摘要

The Cumulative Vehicle Routing Problem (Cu-VRP) extends the classic Vehicle Routing Problem by incorporating fuel consumption considerations, which are crucial in transportation and logistics. In Cu-VRP with Stochastic Demands (Cu-VRPSD), the demand of each customer is unknown until the vehicle visits it. In this paper, we propose a randomized 2.5-approximation algorithm for splittable deliveries and a randomized 3.5-approximation algorithm for unsplittable deliveries, improving the best-known approximation ratios of 3.25 and 6, respectively. For Cu-VRP, since it is a special case of Cu-VRPSD, our algorithms also improve the best-known approximation ratios of 3.186 and 4, respectively. We apply our algorithms on the benchmark sets and the experimental results show that the quality of our computed solutions is much closer to optimality than the provable approximation ratio.