---

一、标签算法介绍

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

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

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

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

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

本博客实现的是标签校正算法。

---

二、SPPRC 问题

带资源约束的最短路径问题 (shortest path problem with resource constraints，SPPRC) 是一个众所周知的NP-Hard问题。除了作为网络 问题直接应用外，SPPRC还用作列生成解决方案方法的基础，用于解决车辆路径规划问题和人员排班问题等。
考虑一个有向图 G = ( N , A ) , N = { v 1 , v 2 , … , v i , … , v n } G=(N, A), N=\left\{v_1, v_2, \ldots, v_i, \ldots, v_n\right\} G=(N,A),N={v1​,v2​,…,vi​,…,vn​} 表示节点的集合，并且 A = { ( i , j ) ∣ v i ∈ N , v j ∈ N , i ≠ j } A=\left\{(i, j) \mid v_i \in N, v_j \in N, i \neq j\right\} A={(i,j)∣vi​∈N,vj​∈N,i=j} 表示弧的 集合。对于每一段弧 $(\mathrm{i},\mathrm{j})\in \mathrm{A}$ 都有一个非负的权重(vrptw问题中可能为负，需要作特殊处理)， ${\mathrm{c}}_{\mathrm{ij}}$ 和 ${\mathrm{t}}_{\mathrm{ij}}$ ，表示通过这段弧的成本和资源消 耗。

SPPRC问题包括找到从起始节点 ${\mathrm{v}}_{\mathrm{s}}\in \mathrm{N}$ 到结束节点 ${\mathrm{v}}_{\mathrm{t}}\in \mathrm{N}$ 的一条路径 $P$ ，使该路径的总成本最小化，但不超过最大资源消耗 $T$ 。 即使只存在一种资源，SPPRC也是一个NP-Hard。

---

三、ESPPRC 问题

带资源约束的基本最短路径问题(Elementary shortest path problem with resource constraints)，以下简称ESPPRC。

从名字上看，SPPRC是把"elementary"约束给松弛了的。Elementary意为：每一个点只能被访问一次。松弛了一个约束，大体上会使得原问题简单一些。

---

四、Python 实现标签算法求解 ESPPRC 问题

4.1 Solomn 数据集

Solomn 数据集下载地址

4.2 完整代码

4.2.1 Functions.py

# -*- coding: utf-8 -*-#
# Author: WSKH
# Blog: wskh0929.blog.csdn.net
# Time: 2023/2/9 13:04
# Description:
import math
import re
import numpy as np
from matplotlib import pyplot as plt


class Data:
    customerNum = 0
    nodeNum = 0
    vehicleNum = 0
    capacity = 0
    corX = []
    corY = []
    demand = []
    serviceTime = []
    readyTime = []
    dueTime = []
    distanceMatrix = [[]]


def readData(path, customerNum):
    data = Data()
    data.customerNum = customerNum
    if customerNum is not None:
        data.nodeNum = customerNum + 2
    with open(path, 'r') as f:
        lines = f.readlines()
        count = 0
        for line in lines:
            count += 1
            if count == 5:
                line = line[:-1]
                s = re.split(r" +", line)
                data.vehicleNum = int(s[1])
                data.capacity = float(s[2])
            elif count >= 10 and (customerNum is None or count <= 10 + customerNum):
                line = line[:-1]
                s = re.split(r" +", line)
                data.corX.append(float(s[2]))
                data.corY.append(float(s[3]))
                data.demand.append(float(s[4]))
                data.readyTime.append(float(s[5]))
                data.dueTime.append(float(s[6]))
                data.serviceTime.append(float(s[7]))
    data.nodeNum = len(data.corX)
    data.customerNum = data.nodeNum - 1
    # 计算距离矩阵
    data.distanceMatrix = np.zeros((data.nodeNum, data.nodeNum))
    for i in range(data.nodeNum):
        for j in range(i + 1, data.nodeNum):
            distance = math.sqrt((data.corX[i] - data.corX[j]) ** 2 + (data.corY[i] - data.corY[j]) ** 2)
            data.distanceMatrix[i][j] = data.distanceMatrix[j][i] = distance
    return data


def calc_path_distance(path, data):
    dis = 0
    for i in range(len(path) - 1):
        dis += data.distanceMatrix[path[i]][path[i + 1]]
    return dis


def calc_path_load(path, data):
    load = 0
    for i in range(len(path)):
        load += data.demand[path[i]]
    return load


def check_time_window(path, data):
    cur_time = 0
    for i in range(len(path) - 1):
        cur_time += data.distanceMatrix[path[i]][path[i + 1]]
        if cur_time < data.readyTime[path[i + 1]] or cur_time > data.dueTime[path[i + 1]]:
            return False
    return True


def plot_path(title, path, data):
    plt.xlabel("x")
    plt.ylabel("y")
    plt.title(title)
    plt.scatter(data.corX[0], data.corY[0], c='red', alpha=1, marker='v', linewidths=3, label='org')  # 起点
    plt.scatter(data.corX[1:-1], data.corY[1:-1], c='black', alpha=1, marker='o', linewidths=3,
                label='mid')  # 中间站点
    plt.scatter(data.corX[-1], data.corY[-1], c='blue', alpha=1, marker='s', linewidths=3,
                label='des')  # 终点
    for i in range(len(path) - 1):
        a = int(path[i])
        b = int(path[i + 1])
        x = [data.corX[a], data.corX[b]]
        y = [data.corY[a], data.corY[b]]
        plt.plot(x, y, 'k', linewidth=1)
    plt.grid(False)
    plt.legend(loc='best')
    plt.show()

4.2.2 LabelAlgo.py

注意：is_dominate函数我没有写，我一开始也想了一个优超准则的，但是经过实验会导致求出来的解不一定是最优的，所以我注释掉了，如果你知道优超准则怎么写，欢迎在评论区留言！（正确的优超准则可以在确保结果的最优性的同时，减少不必要的搜索，提高求解效率。当然不写优超准则也没事，只是求解效率会相对低一些）

# -*- coding: utf-8 -*-#
# Author: WSKH
# Blog: wskh0929.blog.csdn.net
# Time: 2023/2/9 13:02
# Description:

wei = 15


class Label:
    path = []
    travel_time = 0
    distance = 0
    load = 0

    def __init__(self, node_num):
        self.node_num = node_num
        l = (node_num // wei) + 1
        self.node_set = [0 for _ in range(l)]

    def append(self, node):
        i = node // wei
        j = node % wei
        self.node_set[i] = self.node_set[i] | (1 << j)
        self.path.append(node)

    def have_node(self, node):
        i = node // wei
        j = node % wei
        return self.node_set[i] & (1 << j) != 0


def copy_label(label):
    c_label = Label(label.node_num)
    c_label.path = label.path.copy()
    c_label.travel_time = label.travel_time
    c_label.distance = label.distance
    c_label.load = label.load
    c_label.node_set = label.node_set.copy()
    return c_label


def is_dominate(Q, extended_label, t, load, d):
    # for label in Q:
    #     if label.path[-1] == extended_label.path[
    #         -1] and label.travel_time < t and label.distance < d and label.load < load:
    #         b = True
    #         for i in range(len(label.node_set)):
    #             if label.node_set[i] | extended_label.node_set[i] != extended_label.node_set[i]:
    #                 # 说明 label.path 不是 extended_path 的子集
    #                 b = False
    #                 break
    #         if b is True:
    #             # 说明 label.path 是 extended_path 的子集，extended_path 要被 dominate
    #             return True
    return False


# labeling algorithm
def Labeling_SPPRC(data, org, des):
    # initial opt_labels
    opt_labels = []
    # initial Q
    Q = []
    # create initial label
    label = Label(data.nodeNum)
    label.append(org)
    Q.append(label)
    # start search
    while len(Q) > 0:
        current_label = Q.pop()
        # print(current_label.path)
        if current_label.path[-1] == des:
            if len(opt_labels) == 0:
                opt_labels = [current_label]
            else:
                if abs(opt_labels[0].distance - current_label.distance) < 0.000001:
                    opt_labels.append(current_label)
                elif opt_labels[0].distance > current_label.distance:
                    opt_labels = [current_label]
            continue
        # extend the current label
        last_node = current_label.path[-1]
        for next_node in range(data.nodeNum):
            # current_label.have_node(next_node) is False
            # next_node not in current_label.path
            if next_node not in current_label.path:
                extended_label = copy_label(current_label)
                # check the feasibility
                arrive_time = current_label.travel_time + data.distanceMatrix[last_node][next_node]
                load = extended_label.load + data.demand[next_node]
                if load <= data.capacity and data.readyTime[next_node] <= arrive_time <= data.dueTime[next_node]:
                    # dominate rule
                    extended_label.append(next_node)
                    d = extended_label.distance + data.distanceMatrix[last_node][next_node]
                    dominate = is_dominate(Q, extended_label, arrive_time, load, d)
                    if dominate is False:
                        extended_label.travel_time = arrive_time
                        extended_label.distance = d
                        extended_label.load = load
                        Q.append(extended_label)
                    else:
                        # print(extended_label.path)
                        pass
    # return
    return opt_labels

4.2.3 Main.py

# -*- coding: utf-8 -*-#
# Author: WSKH
# Blog: wskh0929.blog.csdn.net
# Time: 2023/2/9 13:03
# Description:
import time

from Functions import *
from LabelAlgo import *

if __name__ == '__main__':
    # 哪个数据集
    data_type = "c101"
    # 数据集路径
    data_path = f'../../data/solomn_data/{data_type}.txt'
    # 顾客个数设置（从上往下读取完 customerNum 个顾客为止，例如c101文件中有100个顾客点，
    # 但是跑100个顾客点太耗时了，设置这个数是为了只选取一部分顾客点进行计算，用来快速测试算法）
    # 如果想用完整的顾客点进行计算，设置为None即可
    customerNum = 20
    # 读取数据
    data = readData(data_path, customerNum)
    # 指定起点和终点
    org = 0
    des = data.nodeNum - 1
    # 输出相关数据
    print("-" * 20, "Problem Information", '-' * 20)
    print(f'Data Type: {data_type}')
    print(f'Node Num: {data.nodeNum}')
    print(f'Customer Num: {data.customerNum}')
    print(f'Vehicle Num: {data.vehicleNum}')
    print(f'Vehicle Capacity: {data.capacity}')
    # 开始求解
    start_time = time.time()
    opt_labels = Labeling_SPPRC(data, org, des)
    print("-" * 20, "Solved Completely", '-' * 20)
    if len(opt_labels) > 0:
        print(f"Solve Time: {time.time() - start_time} s")
        for i in range(len(opt_labels)):
            print(
                f'Optimal Solution {i + 1} : {opt_labels[i].path} , load: {opt_labels[i].load} , distance: {opt_labels[i].distance} , check_time_window: {check_time_window(opt_labels[i].path, data)}')
            plot_path(f'Optimal Solution {i + 1}', opt_labels[i].path, data)
    else:
        print("There is no solution to this question")

4.3 结果展示

4.3.1 测试案例：c101.txt

设置 customerNum = 20

-------------------- Problem Information --------------------
Data Type: c101
Node Num: 21
Customer Num: 20
Vehicle Num: 25
Vehicle Capacity: 200.0
-------------------- Solved Completely --------------------
Solve Time: 0.0 s
Optimal Solution 1 : [0, 20] , load: 10.0 , distance: 10.0 , check_time_window: True

设置 customerNum = 35

-------------------- Problem Information --------------------
Data Type: c101
Node Num: 36
Customer Num: 35
Vehicle Num: 25
Vehicle Capacity: 200.0
-------------------- Solved Completely --------------------
Solve Time: 0.06851029396057129 s
Optimal Solution 1 : [0, 20, 5, 32, 3, 33, 7, 25, 18, 27, 35] , load: 200.0 , distance: 289.7898204179148 , check_time_window: True

设置 customerNum = 55

-------------------- Problem Information --------------------
Data Type: c101
Node Num: 56
Customer Num: 55
Vehicle Num: 25
Vehicle Capacity: 200.0
-------------------- Solved Completely --------------------
Solve Time: 28.623275756835938 s
Optimal Solution 1 : [0, 5, 32, 55] , load: 50.0 , distance: 96.34850796740938 , check_time_window: True

4.3.2 测试案例：r101.txt

设置 customerNum = 55

-------------------- Problem Information --------------------
Data Type: r101
Node Num: 56
Customer Num: 55
Vehicle Num: 25
Vehicle Capacity: 200.0
-------------------- Solved Completely --------------------
Solve Time: 0.0375361442565918 s
Optimal Solution 1 : [0, 14, 2, 44, 16, 55] , load: 66.0 , distance: 136.55961482272318 , check_time_window: True

设置 customerNum = 75

-------------------- Problem Information --------------------
Data Type: r101
Node Num: 76
Customer Num: 75
Vehicle Num: 25
Vehicle Capacity: 200.0
-------------------- Solved Completely --------------------
Solve Time: 0.47461438179016113 s
Optimal Solution 1 : [0, 14, 21, 75] , load: 49.0 , distance: 73.48725559064414 , check_time_window: True

设置 customerNum = 85

-------------------- Problem Information --------------------
Data Type: r101
Node Num: 86
Customer Num: 85
Vehicle Num: 25
Vehicle Capacity: 200.0
-------------------- Solved Completely --------------------
Solve Time: 1.7239580154418945 s
Optimal Solution 1 : [0, 63, 69, 85] , load: 57.0 , distance: 91.74424577496413 , check_time_window: True

设置 customerNum = 100

-------------------- Problem Information --------------------
Data Type: r101
Node Num: 101
Customer Num: 100
Vehicle Num: 25
Vehicle Capacity: 200.0
-------------------- Solved Completely --------------------
Solve Time: 32.46246600151062 s
Optimal Solution 1 : [0, 92, 27, 28, 69, 30, 79, 97, 74, 100] , load: 121.0 , distance: 185.00120247142092 , check_time_window: True