Scholarlink

<p>This paper studies the Euclidean travelling salesman problem (TSP) with a set of time windows. As a variant of the classical TSP, the Euclidean TSP with time windows is restricted into the Euclidean plane and generalized by time windows, which are used to appoint when to visit each node in the graph. Under practical environment of modern logistics, solving this problem is economically significant, because it can be viewed as a special case of the vehicle routing problem (VRP) with time windows, which has one vehicle and unlimited load capacity. The contribution of this paper is proposing two polynomial time approximation schemes (PTASs) for solving the Euclidean TSP with time windows, such that the length of each time window is softly relaxed to <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(1 + \text {O}(\epsilon )\)</EquationSource> </InlineEquation> times, where <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\epsilon \)</EquationSource> </InlineEquation> is an arbitrarily small approximation parameter. On the probability of expectation, the two PTASs can both output a solution with approximation ratio <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(1 + \text {O}(\epsilon )\)</EquationSource> </InlineEquation>.</p>

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

PTAS for Euclidean travelling salesman problem with soft time windows

  • 期刊论文

  • 发表日期：

    2026年1月19日

查看全文
  • Liang Song,
  • Songsong Wu,
  • Yongxuan Lai,
  • Chunyan Liu,
  • Hejiao Huang,
  • Hongwei Du

摘要

This paper studies the Euclidean travelling salesman problem (TSP) with a set of time windows. As a variant of the classical TSP, the Euclidean TSP with time windows is restricted into the Euclidean plane and generalized by time windows, which are used to appoint when to visit each node in the graph. Under practical environment of modern logistics, solving this problem is economically significant, because it can be viewed as a special case of the vehicle routing problem (VRP) with time windows, which has one vehicle and unlimited load capacity. The contribution of this paper is proposing two polynomial time approximation schemes (PTASs) for solving the Euclidean TSP with time windows, such that the length of each time window is softly relaxed to \(1 + \text {O}(\epsilon )\) times, where \(\epsilon \) is an arbitrarily small approximation parameter. On the probability of expectation, the two PTASs can both output a solution with approximation ratio \(1 + \text {O}(\epsilon )\) .