Approximation schemes for Euclidean vehicle routing problems with time windows

详细信息    查看全文

• 作者：Liang Song ; Hejiao Huang ; Hongwei Du
• 关键词：Modern logistics ; VRPTW ; Approximation algorithm
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：32
• 期：4
• 页码：1217-1231
• 全文大小：674 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886
• 卷排序：32

文摘

The vehicle routing problem with time windows (VRPTW) is a variant of the classical vehicle routing problem. The paper considers two dimensional and one dimensional VRPTW, in which each demand must be serviced within the time window which is designated by its customer. In the two dimensional problem, each customer has the same unit demand. The paper gives a quasi-polynomial time approximation scheme and an asymptotic polynomial time approximation scheme for the two dimensional and one dimensional problems under the Euclidean setting, respectively. With reasonable vehicle speed requirements, our algorithms could generate the solutions whose the total route length is \((1 + O(\varepsilon ))\) times of that of the optimum solutions.