在线叫车问题中最小化最大流时间的研究

### 在线叫车问题中最小化最大流时间的研究 在在线算法领域，在线叫车问题（Online Dial - a - Ride Problem）的最大流时间最小化是一个重要的研究方向。下面将详细探讨相关的算法和理论。 #### 1. 定理 1 相关内容 为了证明相关结论，我们从时间 0 开始构建请求序列。具体步骤如下： 1. 对手在每个时间单位发出一个针对边 $e_3$ 的请求，方向交替进行，直到在线服务器首次位于节点 1 或 2 为止，设这个时间为 $t \in N$。 2. 在时间 0 时，公平的对手可以将其服务器移动到第一个发出请求的源节点（节点 1 或 2），并在时间 1 到达，此时有两个针对边 $e_3$ 的待处理请求。 3. 对手继续在每个时间单位处理一个针对边 $e_3$ 的请求，直到时间 $t$。 当算法在时间 $t$ 到达节点 1 或 2 时，必然有 $t \geq 1$，并且在此期间针对边 $e_3$ 有 $t + 1$ 个未处理的请求堆积。因此，对于某个 $t \geq 1$，属性 $P_{t + 1}$ 在时间 $t$ 成立，从而完成了定理的证明。 这种构造方法对于对手的更强限制同样有效。上述使用的对手甚至在某种意义上是非滥用的，即除了处理请求外，它只移动到未处理请求的源节点。此外，定理 1 对于容量更大但有限的服务器（容量 $K > 1$）也成立，只需将序列中的每个请求重复 $K$ 次。 #### 2. 针对公平对手的 Fmax - OlTsp 问题 考虑 Fmax - OlDarp 的一个特殊情况，即每次行程的源点和终点重合，也就是 Fmax - OlTsp 问题。与之前的问题不同，在这个问题中，如果所有请求指定访问的是同一个节点，服务器可以同时处理无限数量的请求。 在具有至少两个点的均匀度量空间中，标准的无限制对手可以构造出序列，使得其最大流时间为零，而任何确定性的在线算法对于某些请求都有正的流时间。因此，不存在严格竞争的算法。但如果允许一个加法常数 $b = n$（$n$ 为空间中的节点数），则可以得到一个平凡的 1 - 竞争算法。 下面我们考虑针对公平对手的 Fmax - OlTsp 问题。 ##### 2.1 先来先服务（fcfs）算法的竞争力 定理 2 表明，先来先服务（fcfs）算法，即总是优先处理最旧的未处理请求，在均匀度量空间上针对公平对手的 Fmax - OlTsp 问题中是严格 2 - 竞争的。 在证明定理 2 之前，需要先建立一个基本引理。 **引理 1**：给定一个序列 $\sigma = r_1, \ldots, r_m$，设 $\sigma_i$ 表示包含 $\sigma$ 的前 $i$ 个请求的子序列，即 $\sigma_i = r_1, \ldots, r_i$。对于任何 $i \in \{1, \ldots, m\}$，有 $opt(\sigma_i) \leq opt(\sigma)$，其中 $opt$ 指的是公平对手。 对于标准对手，这个结论是显然的，适用于 $\sigma$ 的任何子序列。但对于公平对手，需要更谨慎。从序列中移除某个请求实际上可能导致公平对手的最大流时间增加，因为该请求可能会扩大对手允许移动的空间。不过，移除请求只会影响后续请求的流时间，所以从序列中移除尾部不会增加公平对手对前面请求的流时间。 接下来证明 fcfs 算法的竞争力，其证明基于以下两个思路： 1. 为了在保持最优最大流时间稳定的情况下增加 fcfs 的流时间，对手必须在在线服务器离开某个节点 $v$ 后不久发出针对该节点的第二个请求。离线服务器需要在此期间能够处理其他请求，并在第二次请求该节点时到达。这样，针对节点 $v$ 的第二个请求会使在线服务器再次移动到该节点，而离线服务器可以同时处理两个请求。 2. 如果 $F^*$ 表示最优离线算法在给定序列上的最大流时间，那么最优离线算法必须在时间窗口 $[t_i, t_i + F^*]$ 内处理请求 $r_i$。因此，一旦 fcfs 落后 $F^*$ 个时间单位，即存在某个节点 $w$ 的未处理请求比 $F^*$ 个时间单位更旧，最优离线服务器必须在在线服务器之前处理该请求，从而不能再利用针对节点 $w$ 的另一个请求来进一步增加 fcfs 的流时间，同时保持最优流时间稳定。 为了进行正式证明，引入一些额外的符号。如果 fcfs 同时处理针对节点 $v$ 的较旧请求 $r_j$ 和请求 $r_i$，则称 fcfs 免费处理请求 $r_i$。用 $F_{fcfs}(r_i)$ 表示 fcfs 调度中请求 $r_i$ 的流时间。由于对手是公平的，对于任何有意义的请求序列，$F^*$ 必须大于 0。 假设该结论不成立，即 fcfs 不是 2 - 竞争的。那么存在一个请求序列，使得 fcfs 的最大流时间是最优算法最大流时间的两倍以上。在所有具有此属性的请求序列中，设 $\sigma = r_1, \ldots, r_m$ 是请求数量最少的序列，我们称这个序列 $\sigma$ 为最短反例。 **引理 2**：fcfs 在最短反例 $\sigma$ 中不会免费处理任何请求。 如果存在一个请求 $r \in \sigma$ 被 fcfs 免费处理，那么 $\tilde{\sigma} := \sigma \setminus \{r\}$ 是一个更短的序列，在该序列上 fcfs 的流时间与在 $\sigma$ 上相同。由于 $r$ 被免费处理，必然存在针对同一节点的更旧请求。因此，$r$ 不会为对手开辟新的空间，也不能用于在后续请求上获得更小的流时间。所以，从 $\sigma$ 中移除 $r$ 不会使公平对手的最大流时间变大，这与 $\sigma$ 是最短反例的定义矛盾。 **引理 3**：设 $F^*$ 表示最优算法在最短反例 $\sigma$ 上的最大流时间。只有最后一个请求 $r_m$ 被 fcfs 以超过 $2F^*$ 的流时间处理。 如果 fcfs 以超过 $2F^*$ 的流时间处理了某个 $l < m$ 的请求 $r_l$，那么它在截断序列 $\sigma_l = r_1, \ldots, r_l$ 上的最大流时间也会超过 $2F^*$。根据引理 1，最优算法在 $\sigma_l$ 上的最大流时间最