Scholarlink

<p>A fundamental variant of the classical vehicle routing problem (VRP) is known as <i>capacitated path routing problem</i> (CPRP), where a fleet of capacitated vehicles departs from multiple depots to fulfill customer demands without the requirement to return to the depot, i.e., operating along open routes. As with the VRP, the CPRP arises in a wide range of applications in modern logistics. This work focuses on a split-delivery extension of the CPRP (referred to as SDPRP), where each customer’s demand can be served by more than one vehicle. Inspired by practical logistics scenarios, we particularly address two critical modeling considerations: (i) whether to include the travel cost from the depot/terminal to the first/last customer in the objective function, and (ii) whether vehicle-to-depot assignment is required. These modeling choices give rise to a family of SDPRP variants. By extending the approximation framework for the multi-depot split delivery vehicle routing problem (Lai et al. [<CitationRef CitationID="CR20">20</CitationRef>]), we develop new parameterized constant-ratio approximation algorithms for several variants of the SDPRP.</p>

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

Approximating Split Delivery Path Routing Problems

  • 期刊论文

  • 发表日期：

    2025年12月29日

查看全文
  • Jun Wu,
  • Feng Chu,
  • Zhen Yang,
  • Yongxi Cheng

摘要

A fundamental variant of the classical vehicle routing problem (VRP) is known as capacitated path routing problem (CPRP), where a fleet of capacitated vehicles departs from multiple depots to fulfill customer demands without the requirement to return to the depot, i.e., operating along open routes. As with the VRP, the CPRP arises in a wide range of applications in modern logistics. This work focuses on a split-delivery extension of the CPRP (referred to as SDPRP), where each customer’s demand can be served by more than one vehicle. Inspired by practical logistics scenarios, we particularly address two critical modeling considerations: (i) whether to include the travel cost from the depot/terminal to the first/last customer in the objective function, and (ii) whether vehicle-to-depot assignment is required. These modeling choices give rise to a family of SDPRP variants. By extending the approximation framework for the multi-depot split delivery vehicle routing problem (Lai et al. [20]), we develop new parameterized constant-ratio approximation algorithms for several variants of the SDPRP.