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

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

The online traveling salesman problem with real-time rejection options and advanced information

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.