标号法(label-setting algorithm)求解带时间窗的最短路问题

写在前面

哈罗大家好~！

想必大家在刚开始学习运筹学模型时，会觉得有些茫然不知所措吧？比如一大堆神奇的名词，各种各样的约束。。。反正我一开始是很懵的状态。

那么我们这次带来一个比较基础的带时间窗的最短路问题（Shortest Path Problem with Time Windows，简称SPPTW），使用一个基础的精确算法，即label-setting算法，来求解它。由于参考文献年代比较久远，这种方法现在已经有了很大的优化。当然，只有先从基础开始，一步步攀登才能不断解决更困难的问题。（说白了就是小编也还不会辣么难的问题啦）

话不多说，开始这篇文章吧！

目录

一. SPPTW简介

二. Label-setting算法简介

三. 占优剪枝：dominate

四. 标记处理的顺序：字典排序

五. 算法流程与例子

六. C++源代码分享

1

SPPTW简介

先来简单介绍要处理的问题。

最短路问题（Shortest Path Problem，简称SPP）：

在一个图中，每条边都有与它相关的数字，我们将这样的数字称为权。对下图G=（N，A）而言，每条边都只有一个权表示花费（cost）（可以理解为该边的长度）。给定起点p，求出p到达其余各点花费最小的路径。

例如上面这张图。每条边上都有一个权用来表示花费。传统的最短路问题要求我们求出起点（例如v_0）到其余各点的最小成本的路径。比如v_0到v_4的最短路径是v_0→v_2→v_3→v_4，其总花费是19；而v_0→v_4这条路径，总花费为30，因此不是v_0到v_4的最短路径。

注意，在经典的最短路问题中，边上的权重一般为正值。

在SPPTW中：

图中每条边有两个权重，其中一个表示消耗的时间（duration），一个表示听过该边的花费（cost）。每个结点i都有一个时间窗[a_i，b_i]，路径访问该节点时需要满足时间窗约束，即：

如果到达i点的时间早于时间窗开启的时间a_i，则需要等待至时间窗开启再进入；若到达的时间超过时间关闭的时间b_i，则无法访问该结点。

（图中d_ij表示时间，c_ij表示花费，[xx， yy]表示时间窗。具体定义见下文）

在此基础上寻找起点p（图中点v_1）到其余各点总花费最小的路径，就是我们要解决的问题。

在图中我们可以看到v_1→v_4的cost权值为负。本文的算法不但能解决花费为正值的情况，还能解决花费为负的情况。只需要保证时间消耗为正。

在此基础上建立问题的模型:

路径X_1^0可以用下图表示：

传统的最短路问题建模可以直接去掉部分定义，不再赘述。下面我们先来看一下处理传统最短路问题的标号法。

2

Label-setting算法简介

标号算法(Labeling algorithms)是解决最短路径问题的一种重要方法，也是绝大多数最短路径算法的核心部分。

按照不同的标识结点处理策略，标号算法又可分为标号设定(Label Setting，简称LS)和标号改正(Label Correcting，简称LC)两大体系。

有关最短路径问题的两个经典算法，Dijkstra算法和Bellman-Ford算法，分别属于LS和LC。

LS算法通过迭代过程对label进行逐步修正，每次迭代均选择候选结点集中标号最小者退出候选结点集，并将该结点标号从临时标号转变久为永久标号。这是一种基于贪心策略的最短路径算法，每一次转化为永久标号的label都代表到当前结点的最短路径，考虑的是“当前最优”。

LC算法在每次迭代时并不一定将任何结点标号从临时标号转变为永久标号，只是对临时标号进行一次修正，所有结点标号仍然为临时标号；只有在所有迭代终止时，所有结点标号同时转变为永久标号。LC算法考虑的是“最终最优”，最短路径需要等待多次迭代直到整个算法运行结束才能被确定。

我们主要介绍LS算法。这里介绍解决不带时间窗约束的最短路问题的Dijkstra算法。该算法中，对于节点i，其label是(C[i], p[i])，其中C[i]表示从起点到节点i的最短距离，p[i]记录在d[i]距离下，从起点到节点i的路径中，节点i的前一个节点编号。s_0表示起点。c_ij表示通过边（i,j）的距离。执行流程如下：

Step0：初始化。令S为空，S*=N，C[s_0]=0，p[s_0]=-1；对N中的顶点i(i≠s_0)令初始距离标号C[j]=∞。

Step1：边界判断。如果S=N，则C[j]为最短路径长度，其最短路径可以通过p[j]所记录的信息反向追踪获得。结束。否则继续step2。

Step2：更新标记。从S*中找到总花费最小的结点i，把它从S*中删除，加入S。对于所有从i出发的可到达的后继点j，若C[j]>C[i]+c_ij，则令C[j]=C[i]+c_ij，p[j]=i。转step1。

该算法的主要计算量在于step2循环。它包括两个过程：寻找结点的过程(从S*中找到花费最小的结点i)和总花费更新的过程(更新与结点i相邻的结点的花费)。

然而，简单的Dijkstra算法无法处理时间窗约束，也无法处理负权边：在不断循环的过程中，实际上有一些边被我们忽视了，及时它的权值为负，能够优化花费，我们也不会去管。

下面我们将提出LS算法的改进版，既能处理时间窗约束，又能满足负权边。

3

占优剪枝：dominate

在了解了解决最短路问题的LS算法后，我们再回到时间窗约束下的最短问题。因为加上了时间这一权重，我们的标记不能再像上一部分那样只记录一个变量cost。我们为每一条路径到达的每一个点时的状态分别制作一个label,为(T, C)，记录这条路径到达该点时消耗的总时间、总花费。

根据定义，我们可以给出标记的处理方法：

当然可以用穷举直接用类似Dijkstra的方法解决问题。但我们希望找出一种有效的剪枝手段以避免穷举带来的高时间复杂度。值得庆幸的是，对于寻找起点到每个点的最短路径而言，并不是所有标记都是有效的。我们通过举例来说明：

dominate rule 能让我们筛选掉无效标记。

我们可以用一个函数来直观表示这种关系：

很显然，在图中，如果两点间斜率k>=0，终点is dominated。（如X_i^1 dominateX_i^5）因为两个标记所代表的两条路径都将到达同一个点，而斜率终点的那条路径时间和cost都更高，当然更差了。而k=0时，我们在图中画了几条直线。每条直线都由一个点（代表一个标记）引出，下一个点结束。这代表，在这条直线对应的时间内，该标记的花费为最小花费。其他情况，并不能判断哪条路径更优。

我们通过一个函数EFF（）来筛选。在第一部分LS的介绍中我们提到了永久标记的概念，意思是对永久标记我们已确保其有效，在之后的拓展过程中其标记值将不再改变。我们给出拓展结点j对应的永久标记的方法。

定义：

Q_j为结点j的永久标记的集合。（Q_j中所有标记中的最小花费即为p到j的最短路径）

通过以下方式拓展Q_j：

这里的拓展其实暗示了Q_j中必须要存在所有可能dominate新label的所有label。如何保证这一点呢？我们在下一节中给出解决方法。

4

标记处理的顺序：字典排序

在LS处理标记的过程中，我们是按结点顺序拓展标记的，所以对于一个结点的多个标记我们需要依照一个顺序进行处理。这个顺序最好能在拓展过程中揪出所有无效点，即一边拓展一边进行EFF查找。

在函数图像中我们用斜率k来表示统治关系，容易想到从左到右判断k，找出所有的k>=0的线段。转化过来，就是按照先比较T再比较C的顺序进行排序。因此，我们在存储标记的时候也考虑按先判断T再判断C的顺序存储，处理时从小到大处理。这就是所谓的字典排序。显然，这是一种全排序，满足我们的需求。

我们有以下三个命题：

字典序是为了配合dominate的判断而生的。这些都是类似剪枝的操作，以避免穷举。加了这两个操作以后，你在枚举的过程中，就会发现很多不可行的路径，一旦不可行，立马停止该路径的扩展。

我们将所有标记分为三个部分：

Q为永久标记的集合

P为已处理标记的集合。

T为未处理标记的集合。

我们按照字典序对所有标记进行排序处理，可以保证所有T中的标记无法dominate P中的标记。因为每一条边的时间d_ij都为正值，因此被拓展出的新标记必定排列在原标记后，无法再dominate原标记。dominate关系有传递性，依照归纳法可得，T中的标记无法对任意中的P标记进行dominate处理。

我们还可以利用P、Q、T的定义给出一个关系式：

在算法中我们可以利用这个式子来计算T。

5

算法流程与例子

A simple example：

6

代码分享

下面提供C++代码。栗子用的是上面的简单栗子，命名按照上述定义。理解了算法的流程后，代码本身并不难。这里的代码重点在配合讲解，作为一个参考，所以没有选择复杂的数据结构和语法技巧，有需要的朋友可以自己作为练习自己尝试。

//SPPTW GLSA 
//By ZLL_HUST

#include <iostream>
#include <vector>
using namespace std;

class label  //标记类，存放该路径当前所在的结点，总时间，总花费 
{
  public:
    int node;
    int time;
       int cost;
      label(){node=-1,time=-1,cost=-1;};
};

int const N=4;
int const INF=9999;

vector<vector<label> > Q(N);//将集合Q，P定义为二维向量，存放每一个结点的labels 
vector<vector<label> > P(N);

double cost[N][N];//这里采用简单的二维表来存储数据，不多作展开，可以关注公众号以后的推文 
double time[N][N];
double time_win_a[N]={0,3,4,4};
double time_win_b[N]={0,10,6,10};

//初始化数据 
void init();
//查找字典序最小的label 
label minlex(vector<label> &);
//构造集合T：未处理的labels 
bool buildT(vector<label> &);
//dominance判断，剪枝无效label 
bool EFF(label);
//对label的总处理 
void treatlabel(label);
//GLSA总流程 
void GLSA();

//初始化数据 ，采用推文中所选例子，加入了负权边 
void init()
{
  label X0;
  X0.cost=0;
  X0.time=0;
  X0.node=0;
  vector<label> X;
  X.push_back(X0);
  Q[0]=X; 
  
  for (int i=0;i<N;i++)
      for(int j=0;j<N;j++)
          cost[i][j]=time[i][j]=-INF;
  
  cost[0][1]=2;
  time[0][1]=3;
  
  cost[1][2]=5;
  time[1][2]=2;
  
  cost[0][3]=-7;
  time[0][3]=5;
  
  cost[3][1]=1;
  time[3][1]=1; 
}

//查找字典序最小的label ，优先判断time，其次判断cost 
label minlex(vector<label> &T)
{
  label min;
  min.time=INF;
  for (int i=0;i<T.size();i++)
    if (T[i].time<min.time || (T[i].time==min.time && T[i].cost<min.cost))
      min=T[i];
  return min;
}

//构造集合T：未处理的labels。由于我们往集合Q和P中加入labels是有序的，所以只需要从P.size后面开始加入。
bool buildT(vector<label> &T)
{
  for (int i=0;i<N;i++) 
    for (int j=P[i].size();j<Q[i].size();j++)
       T.push_back(Q[i][j]); 
  if (T.size()==0) 
     return false;//若所有标记都已处理，返回false值，退出程序 
  else 
     return true;
}

//dominance判断，剪枝无效label 
bool EFF(label next)
{
  bool is_dominated=false;
  for (int i=0;i<Q[next.node].size();i++)
    if (next.time>Q[next.node][i].time && next.cost>Q[next.node][i].cost)
        is_dominated=true;
  return !is_dominated;
}

//对label的总处理 
void treatlabel(label FT)
{
  for(int succ=1;succ<N;succ++)
  {
  if (cost[FT.node][succ]!=-INF)//寻找后继结点 
  {
    if ((FT.time+time[FT.node][succ])<=time_win_b[succ])//时间窗约束 
    {
      label next;//更新标记 
      next.time=(FT.time+time[FT.node][succ])>time_win_a[succ]?(FT.time+time[FT.node][succ]):time_win_a[succ];
      next.cost=FT.cost+cost[FT.node][succ];
      next.node=succ;
      //cout<<FT.node <<"'s one successor is"<<succ<<next.cost <<next.time <<endl;
      if (EFF(next))
         Q[next.node].push_back(next);
    }
  }
    }
  P[FT.node].push_back(FT);//FT已处理，加入集合P 
}

//GLSA总流程 
void GLSA()
{
  bool flag=true;
  vector<label> T;
  flag=buildT(T);
  int i=0;
  while(flag)
  {
    label FT=minlex(T);
    treatlabel(FT);
    T.clear();
    flag=buildT(T);
    cout<<"F(T)'s cost is  "<<FT.cost<<"\t"<<"F(T)'s time is  "<<FT.time <<"\t"<<"F(T)'s node is  "<<FT.node <<endl;
  }
  for (int i=1;i<N;i++)//由于加入集合时按照先时间后花费的标准，因此每个结点的最后一个label为最迟、最短路径 
     cout<<"起点1到达点"<<i+1<<"的最短路径花费为"<<Q[i][Q[i].size()-1].cost<<endl; 
}

int main()
{
  init();
  GLSA();
  return 0;
}

本期的文章到这里就差不多该结束啦~

这期的推文是小编在咱们公众号的第一篇正式推文，反复修改了多次。感谢邓发珩学长和秦虎老师对我的支持，提供了很多修改意见！非常感谢！

既然加入了这里，那么小编肯定会继续努力学习，为大家带来更多有趣的文章的~！

咱们下次再见( ^_^ )/~~

参考:

Martin Desrochers, Francois Soumis (1988) A generalized permanent labeling algorithm for the shortest path problem with time windows. INFOR Information Systems and Operational Research. 26(3):191-212.