具有时间窗的局内开放式车辆调度的竞争分析

Competitive analysis concerning open on-line TSPTW

基于k-卡车问题和局内运输问题,提出了具有时间窗的局内开放式车辆调度问题.该问题的优化目标为:在服务需求的发布为局内方式的条件下,如何最小化完成整个服务需求序列的时间跨度.建立了该问题的数学模型并对有关的概念和参数进行了定义和说明.研究了当车辆数为1时该问题的竞争分析的有关结果:给出并证明了对于该问题的竞争策略的竞争比下限;针对该局内问题,设计了两种不同的竞争策略,得到了相应的竞争比,并进行了理论证明.

Based on the k-truck problem and on-line transportation problem, the open on-line truck scheduling problem with time-window（TSPTW） is originally proposed. The goal of the optimization of the TSFFW is to minimize the span time for finishing the whole request sequence under the condition that all requests are revealed with an on-hne fashion. A relevant model is established and some concepts are defined. Furthermore, the case which has only one vehicle is studied and some relative results are obtained： the lower bound of competitive ratio is given and proved; two different competitive strategies are designed and the relevant competitive ratios are obtained and proved.