基于预知信息和实时服务选择的在线TSP问题

Translated title of the contribution: The online traveling salesman problem with real-time rejection options and advanced information

廉文琪*, 徐寅峰

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)

4 Citations (Scopus)

Abstract

现实生活中,提供外送服务的快餐店为了降低成本、提高效率,在接到顾客的订餐信息时,可能会因为距离等因素拒绝一些顾客的送餐要求,而拒绝顾客需求会带来一定的惩罚 (如丧失部分客户)。针对快餐店选择性提供送餐服务,同时送餐点信息被提前获知但是不能马上被服务的情形,提出了基于预知信息和实时服务选择的在线旅行商问题 (traveling salesman problem, TSP)。针对需求点在正半轴和直线上的情 形分析了问题的下界,并设计了相应的算法,同时分析了每个算法的竞争性能。结果表明,算法的竞争性能会随着预知信息的增加而得到改善。

Due to the fact that, some fast food restaurants which provide take away service may refuse some delivery orders when they receive requests from customers so as to improve efficiency and cut cost. This results in some forms of penalty, like reputation damage, etc. To achieve the goal of minimizing the whole time of serving plus the total penalties of all rejected requests, we propose the real-time version of online travelling salesman problem (OL-TSP) with rejection options and advanced information. We proposed lower bounds and algorithms on the non-negative real line and the real line. These conclusions are more general than the results in the real-time version of online TSP with rejection options.
Translated title of the contributionThe online traveling salesman problem with real-time rejection options and advanced information
Original languageChinese (Simplified)
Pages (from-to)86-93
Number of pages8
Journal系统工程理论与实践
Volume36
Issue number1
Publication statusPublished - Jan 2016
Externally publishedYes

Bibliographical note

基金资助 : 国家自然科学基金(61221063, 71071123); 教育部长江学者和创新团队发展计划(IRT 1173)

Keywords

  • 旅行商问题
  • 预知信息
  • 实时服务选择
  • 在线算法
  • traveling salesman problem
  • advanced information
  • real-time rejection options
  • online algorithm

Fingerprint Dive into the research topics of 'The online traveling salesman problem with real-time rejection options and advanced information'. Together they form a unique fingerprint.

  • Cite this