限制信息条件下基于时间窗的占线装-卸货问题及其竞争分析

提出并研究限制信息条件下基于时间窗的占线装一卸货问题。客户在提出服务请求时只指定需要承运的货物的装载地，而没有提供目的地信息，服务车只有在到达装载地之后才知道目的地的具体位置，如现实中的出租车调度和电梯调度等问题。就两种度量空间对限制信息条件下带时间窗的占线装一卸货问题进行了分析，分别给出了两种竞争策略及其竞争比结果，并得到了针对该问题的任何确定型算法的竞争比下界。

Online Pickup-and-Delivery Problem and Competitive Analysis with Time-Windows under a Restricted Information

In this paper the first results on the Online Pickup and Delivery with Time-Windows under a Restricted Information Model are presented. One server is required to transports a specified amount of goods for requests from the sources to the destinations. At the release time of one request, only the information on the source is presented. The server does not have the information on the destination until it reaches the .source of the request. These models, e.g. the taxi problem, or elevator problem. We study the problem in the uniform metric space and K-constrained metric space. We perform competitive analysis of two deterministic strategies in the two types of metric spaces. The competitive ratios of the strategies are obtained. We also prove a lower bound on the competitive ratio of any deterministic algorithm for this problem in the two kinds of the metric space.