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

摘要

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