Online Traveling Salesman Problem With Deadlines

Based on the customer waiting psychology in the door-to-door service of fast food delivery,postman’s package collection and taxi service,this paper studies the online traveling salesman problem with deadlines.Depending on the salesman’s service objectives,whether the objective is to minimize cost,maximize profit or the combination of cost minimization and profit maximization,this research work has four maining research bodies:1.Online nomadic traveling salesman problem with advanced information.Focusing on the situation that the salesman does not have to travel back to origin after service,this paper introduces the advanced infromation into the online nomadic traveling salesman problem,aims at minimizing the service cost,and performs competitive analysis for the problem.Specifically,this research gives the lower bound throught the construction of a special graph,designs ENO-dd algorithms when the graph is a line and analyzes its competitive ratio,and proposes greedy algorithm when the graph is a general one and gives its competitive ratio.The comparison suggests positive ralation between online server’s performance and advanced information.Besides,the amount of advanced information also implies the online-ness of the the problem.2.Online traveling salesman problem with deadline and service flexibility.Based on the customer waiting psychology and customer satisfaction,the deadline is introduced into online traveling salesman problem with service flexibility.If the salesman does not serve a request before its deadline,a penalty would be generated.The penalty is usually in the form of reputation damage or the increase of service fees.Such penalty enters the online service cost,and the server’s objective is to minimize the service cost.Thought the analysis of this problem on general graph,no online algorithms with constant competitive ratios are found.So the research restricts the graph and mainly considers the line segment.When the graph is a line segment,this resarch work analyzes the lower bound,gives Conjecture algorithm and its competitive ratio.3.Online traveling salesman problem with deadlines and advanced information.Focusing on the customer waiting psychology and service booking in reality,this paper introduces deadline into online traveling salesman problem with advanced information,where the objective of the server is to serve requests before their deadlines as many as possible.However,no online algorithms with constant competitive ratios are found on general metric space,then the paper considers two cases for the metric space to be line segment and unifor metric space.For the line segment,lower bounds,Replan algorithmm and its competitive ratios are given.For the uniform metric space,lower bound,greedy algorithm and its competitve ratio are given.The comparison suggests that besides the advanced information,the structure of the graph also affects the performance of online algorithms.4.Online prize-collecting traveling salesman problem with deadlines.The single service objective is seldom the case in reality,most of the service staff and companies would try to maximize profit and minize cost at the same time.Taking into the consideration of customer waiting psychology,this paper introduces deadlines into online prize-collecting traveling salesman problem.The analysis of the porblem on general graph gives no online algorithms with constant competitive ratios,so restricted metric spaces are considered.For the line segment,lower bound,CMC algorithm and its competitive ratio are given.For the unifrom metric space,lower bound,CGA algorithm,and its competitive ratio are given.The research results of this papar has twofold implications.O n one hand,they can provide guidence for fast food delivery,postman’s package collection and taxi service to improve efficiency and customer satisfaction.On the other hand,this research considers multiple objectives for the online traveling salesman with deadlines,and the research sults can enrich the study of online traveling salesman problem.