Online traveling salesman problem with deadlines and service flexibility

详细信息    查看全文

• 作者：Xingang Wen ; Yinfeng Xu ; Huili Zhang
• 关键词：Online algorithms ; Traveling salesman problem ; Deadlines ; Service flexibility
• 刊名：Journal of Combinatorial Optimization
• 出版年：2015
• 出版时间：October 2015
• 年：2015
• 卷：30
• 期：3
• 页码：545-562
• 全文大小：768 KB
• 参考文献：Ausiello G, Feuerstein E, Leonardi S, Stougie L, Talamo M (2001) Algorithms for the on-line travelling salesman. Algorithmica 29(4):560-81MathSciNet CrossRef MATH
  Ausiello G, Demange M, Laura L, Paschos V (2004) Algorithms for the on-line quota traveling salesman problem. Inf Process Lett 92(2):89-4MathSciNet CrossRef MATH
  Ausiello G, Bonifaci V, Laura L (2008) The online prize-collecting traveling salesman problem. Inf Process Lett 107(6):199-04MathSciNet CrossRef MATH
  Blom M, Krumke SO, De Paepe WE, Stougie L (2001) The online TSP against fair adversaries. INFORMS J Comput 13(2):138-48MathSciNet CrossRef MATH
  Gutiérrez S, Krumke S, Megow N, Vredeveld T (2006) How to whack moles. Theor Comput Sci 361(2-):329-41CrossRef MATH
  Jaillet P, Lu X (2011) Online traveling salesman problems with service flexibility. Networks 58(2):137-46MathSciNet MATH
  Jaillet P, Wagner M (2006) Online routing problems: value of advanced information as improved competitive ratios. Transp Sci 40(2):200-10CrossRef
  Jaillet P, Wagner M (2008) Generalized online routing new competitive ratios, resource augmentation, and asymptotic analyses. Oper Res 3:745-57MathSciNet CrossRef
  Karlin A, Manasse M, Rudolph L, Sleator D (1988) Competitive snoopy caching. Algorithmica 3(1):79-19MathSciNet CrossRef MATH
  Katz K, Larson B, Larson R (2003) Prescription for the waiting-in-line blues entertain, enlighten, and engage. Oper Manag Crit Perspect Bus Manag 2:160
  Lipmann M (2003) On-line routing. PhD Thesis, Technische Universiteit Eindhoven
  Portougal V, Trietsch D (2001) Stochastic scheduling with optimal customer service. J Oper Res Soc 52(2):226-33CrossRef MATH
  Sleator D, Tarjan R (1985) Amortized efficiency of list update and paging rules. Commun ACM 28(2):202-08MathSciNet CrossRef
  Wen X, Xu Y, Zhang H (2012) Online traveling salesman problem with deadline and advanced information. Comput Ind Eng 63(4):1048-053CrossRef
  
• 作者单位：Xingang Wen (1) (2)
  Yinfeng Xu (1) (3)
  Huili Zhang (1) (3)
  
  1. School of Management, Xi’an Jiaotong University, Xi’an?, 710049, China
  2. Tilburg CentER, Tilburg University, P.O. Box 90153, 5000 LE?, Tilburg, The Netherlands
  3. State Key Lab for Manufacturing Systems Engineering, Xi’an?, 710049, China
  
• 刊物类别：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

文摘

Considering the customer psychology while waiting to be served, we introduce a more reasonable form of deadlines into online traveling salesman problem (OL-TSP) with service flexibility. The salesman can choose whether to serve or not when a new request arrives. By rejecting the request or missing its deadline, penalties will be generated. The goal is to minimize server’s costs (travel makespan plus the penalties of missed requests). We show that no deterministic or randomized online algorithms can achieve constant competitive ratio for OL-TSP with deadlines and service flexibility on general metric space. While on constrained metric space (such as truncated line segment), we present lower bound, give an algorithm, and analyze the competitive ratio. Keywords Online algorithms Traveling salesman problem Deadlines Service flexibility