CRP

Carnival Route Programming - 游乐园路径规划

问题描述

游乐园每天会开放多个游玩项目，每个项目的开放时间段和游玩所需时间（包括排队等待的时间）都不同。设游客游玩 $n$ 个项目，每个项目的游玩所需时间为 $N_{p_i}$ ，开放开始时间为 $S_{p_i}$ ，开放结束时间为 $E_{p_i}$ ，从项目 $p_i$ 移动到项目 $p_j$ 的路程所需时间为 $T_{p_ip_j}$ ，其中 $p_i,p_j\in[1,2,\ldots,n]$ 为游玩项目， $p_i=p_j=0$ 为游乐园大门。要求规划一个项目游玩顺序，使得游客在规定开放时间段游玩所有项目，并且总游玩时间最短。即求下列问题：

$\begin{aligned}G(x) &=g_1(x)+g_2(x)&&\ldots\ldots(1)\\g_{1}(x) &=\sum_{j=1}^nT_{p_{j-1}p_{j}} &&\ldots\ldots(2)\\ g_{2}(x) &=\sum_{j=1}^n\max (S_{p_{j}}-A_{p_{j}},0)&&\ldots\ldots(3)\end{aligned}$

其中 $x$ 为一个从游乐园大门开始的项目序列 $x=(p_0,p_1,\ldots,p_n)$ ， $A_{p_j}$ 为游客真实到达项目 $p_j$ 的时间。 $(2)$ 式表示在项目序列 $x$ 下路程所需的总时间， $(3)$ 式表示在项目序列 $x$ 下的总等待时间 $^1$ ， $(1)$ 式为路程和等待的总时间。由于游玩所需的时间固定不变，所以在这个问题中只需要考虑最小化 $(1)$ 式即可，目标函数如下：

$\begin{aligned}&\min G(x)&&&&&&\ldots\ldots(4)\end{aligned}$

注1：这里的等待时间并非排队等待时间，而是指游客到达了项目位置，而项目还没到开放开始时间，从而产生的等待时间。

问题分解

该问题可以看作一个基础问题附加上一定约束条件。其中基础问题为在完全图中给定一个起点，求一条最短通路，约束条件即为访问点的时间必须在规定范围之内。首先对于基础问题的求解十分简单，可以使用贪心算法每次向离当前点最近的点前进（先不急反驳）。该过程可以使用伪码描述如算法1所示。

算法1：使用贪心算法求解基础问题 

输入：T (每条道路所需的时间)
	 N (游玩项目总数)
输出：X (最优游玩序列)

U ← {1,...,n}
X ← ∅
i ← 0
for 1 to N do
    for j in U do
        m ← min(T[i][j],T[i][m])
    end for
    X ← X ∪ m
    i ← m
end for
return X

基础问题得到了最快的路径，它并不一定能满足时间段要求。但给出了一个启示，即每次寻找的点应为满足时间段要求的最近点。由于满足时间段要求是根据每次选择动态变化的，没有办法一开始就知道选择这个点是否可行，此时我们可以用到回溯算法。核心思想为每次选择的时候将临近点按照 $(1)$ 式规定的总时间逆序排序，首先选择最近的点开始下一次选择，直到发生时间冲突，回溯到上一次选择中，选择次近的点继续选择，一直循环直到找到一条满足时间段要求的通路，该过程可使用如算法2描述的伪代码实现。

算法2：使用回溯算法求解带时间段条件的路径规划问题

输入：T (每条道路所需的时间)
	 N (游玩项目总数)
输出：X (最优游玩序列)

 1: U ← {1,...,n}
 2: i ← 0
 3: A[i] ← 0
 4: X ← reverse(recall(i,U))
 5: return X

算法3：recall 使用回溯算法求解带时间段条件的路径规划问题中的递归函数

输入：i (当前访问的项目下标)
	 U (未访问序列)
输出：c (是否发生冲突)
     X (当前递归排序完毕的项目序列)

c ← False
X ← ∅
if is_conflict then
    return True,∅
U ← time_sort(U)
for j in U do
    A[j] ← compute_arrive_time(i,j)
    U ← U - j
    c,X ← recall(j,U)
    if not c then
        break
    end if
    U ← U + j
end for
if c then
    return True,∅
end if
X ← X ∪ i
return Flase,X

经计算，时间复杂度最好为 $O(n^3)$ ，最差为 $O(n^{n+2})$ ，平均为 $O(n^{\frac{n}{2} + 2})$ 。

优化

回溯算法解决该问题有两个很大的缺点，其一是每次都要从整个未访问的点中求解，其中很多点是明显不能优先访问的，其二是冲突的反应太慢，直到剩下的所有点都不能走的时候才发现冲突，此时可能需要回溯很多次才能找到错误的根源。因此，提出一个按优先级排序的快冲突响应算法（PSFCR）。

PSFCR算法核心思路是在每次递归计算前建立节点之间的支配关系，将非支配的点参与计算。此处的支配关系 $a$ 支配 $b$ 表示，如果 $b$ 在 $a$ 之前访问， $a$ 就无法满足时间段要求。而且在计算支配关系的时候，若发现 $a$ 和 $b$ 互相支配，则证明当前选择的节点无论怎么继续走都会发生冲突，即找到了一种可以只需要试探一次就能发现冲突的快冲突响应方法，PSFCR算法可以使用伪码描述为算法4。

算法4：PSFCR 按优先级排序的快冲突响应算法

输入：T (每条道路所需的时间)
	 N (游玩项目总数)
输出：X (最优游玩序列)

 1: U ← {1,...,n}
 2: i ← 0
 3: A[i] ← 0
 4: c,F ← non_domination_sort(i,U)
 5: if c then
 6:     return ∅
 4: X ← reverse(PSFCR_recall(i,U,F))
 5: return X

算法5：non_domination_sort 非支配排序算法

输入：i (当前访问的项目下标)
	 U (未访问序列)
输出：c (是否发生冲突)
     F (非支配的项目序列)
 
F ← ∅
d ← {0,...,0}
for i in range(0,len(U))
    for j in range(i+1,len(U))
        if i ≺ j then // means i dominate j
            d[i]++
        elseif j ≺ i then
	        d[j]++
        end if
        if i ≺ j and j ≺ i then
            return True,∅
        end if
	end for
end for
for i in U
    if d[i]=0 then
	    F ← F ∪ i
F ← time_sort(F)
return False,F

算法6：PSFCR_recall PSFCR中的递归函数

输入：i (当前访问的项目下标)
	 U (未访问序列)
	 F (非支配的项目序列)
输出：c (是否发生冲突)
     X (当前递归排序完毕的项目序列)

c ← False
X ← ∅
if F=∅ and U≠∅ then
    return True,∅
for j in U do
    A[j] ← compute_arrive_time(i,j)
    c,F ← non_domination_sort(i,U)
    if c then
       continue
    end if
    U ← U - j
    c,X ← PSFCR_recall(j,U,F)
    if not c then
        break
    end if
    U ← U + j
end for
if c then
    return True,∅
end if
X ← X ∪ i
return Flase,X

经计算，时间复杂度最好为 $O(n^3)$ ，最差为 $O(n^3)$ ，平均为 $O(n^3)$ 。

进一步优化

这里要推翻一下最开始的假设了。细心的朋友可能会发现我之前根本是在胡说八道，没错，基础问题用贪心算法求出来的解并不是最优解，只是一个比较好的可行解而已。具体如下图所示。

贪心失败

这个问题主要出在区域选择上，贪心算法有可能会先走到一个游玩项目比较偏远的区域，导致回到其他区域时花费异常大的时间。如果还要按照之前的方法，就需要穷举出所有的可行解。当然因为需要所有可行解，那么每个节点的排序操作就可以省略了，经计算无PSFCR时间复杂度为 $O(n^n)$ ，有PSFCR时间复杂度为 $O(n^3l)$ ，其中 $n$ 为结点个数， $l$ 为可行解数目。当 $l<(n-2)!$ 时，有PSFCR的方法更优。即，可行解越少（约束越强）PSFCR算法越好。

这样确实可以求出最优解，但是在可行解偏多的情况下速度很不理想。由于其本身是一个NP问题，故应该找到一个符合时间约束的较优解即可。使用贪心算法的PSFCR就给出了一个较优解，再次基础之上，添加区域选择算法（AS），使算法获得更为优秀的可行解。要进行区域选择，首先要进行区域划分。

区域划分

假设线段 $AB$ 长度等于线段 $AC$ 长度， $\angle A$ 小于60°时， $CB<AB=AC$ ，而 $\angle A$ 大于60°时， $CB>AB=AC$ 。故使用60°作为一个分界值。假设当前所在点为点 $A$ ，任意点 $X\in\{A_1\}$ 与 $Y\in \{A_2\}$ ，使得 $\angle XAY > 60°$ ，即 $\frac{XA\cdot YA}{\lvert XA\rvert\lvert YA\rvert}<\cos 60°=\frac{1}{2}$ ，则 $A_1$ 与 $A_2$ 属于不同的区域，反之属于相同区域。

60°区域划分

区域选择

如果还是需要求出最优解，在划分区域后，可以将PSFCR的支配解按照区域分成一个二维数组。一个区域间算出可行解后，即可跳过整个区间，到下一个区间进行搜索。此时PSFCR-AS的时间复杂度为 $O(n^3a)$ ，其中 $a$ 为总区域数，并有 $a<<l$ 。由此可见区域划分极大提升了算法效率。

但由于该算法用于一个即时交互系统，只需要求出一个较优解即可。为了使得时间复杂度变为 $O(n^3)$ ，就需要人为决定区域之间的访问顺序。目前可以根据平均距离或最远距离来判断访问顺序。为了减少回头路的长度，应该优先选择距离较近的区域访问。但平均距离和最远距离都只能解决部分情况，依概率，平均距离可以解决的情况更多。故我们选择先访问平均距离最短的区域。该算法只能求出较优解，伪码如下。

[PSFCR-AS/AD伪码]

CRP

Carnival Route Programming - 游乐园路径规划

CRP

问题描述

问题分解

优化

进一步优化

区域划分

区域选择

CATALOG

FEATURED TAGS

FRIENDS