一种解决漫游取送位置和时间窗的有容量约束车辆路径问题的深度强化学习方法

1.本发明专利涉及一种车辆路径规划方法，在城市物流取配领域具有重要的应用前景。


背景技术：

2.随着我国经济由高速发展向高质量发展的转变，优化车辆路径也成为提高物流行业效率和推动可持续发展的重要手段之一。车辆路径问题(vehicle routing problem，vrp)作为运筹学、计算机科学及图论等多个学科的主要研究方向，不仅是优化城配物流运输效率的重要依据，更是实现节能减排的重点问题。而在传统的有容量约束的车辆路径问题中，规定车辆都是以满足客户的需求为目标，从网点装载货物给不同的客户分配相同种类的货物。但在实际城市物流配送过程中，物流的运输都是以完成所有订单为目标。由于不同货主提供的货物种类可能存在差异，车辆必须确保将来自同一货主的货物分配给对应的客户，以避免混淆或错误交付。为了最大程度地减少成本并提高配送效率，车辆运输过程中不仅要考虑满足客户需求，还需要优化整个运输过程，并适应不同货主和客户位置的变化。同时，现实中货主和客户的位置、订单数量等都处于频繁变化之中，这增加了运输路线规划的难度和复杂性。因此，提出了一种深度强化学习方法来解决具有漫游取送位置和时间窗的有容量约束车辆路径问题(capacitated vehicle routing problem with roaming pickup and delivery locations and time windows,cvrprpdltw)，使车辆能对每个货主或客户服务时间点上不断地进行决策，以更好的解决实际城配物流问题。
3.由于cvrprpdltw的复杂性，目前还没有切实可行的解决方案，而且传统解决方案中的蚁群、粒子群等启发式算法无法在该问题的大规模实例上快速求出可行解来满足车辆路径实时决策的需要。本发明设计了一种深度强化学习方法，即动态漫游位置的深度强化学习方法(dynamic roaming position deep reinforcement learning method,drpdrl),它是一种考虑多维度特性的transformer架构。首先设计了一种具有表征cvrprpdltw中不同信息的encoder-decoder架构，通过三个编码器层处理具有不同维度的信息，解码器层融合这些信息来进行路线构建，以增强drpdrl拟合不同场景的能力，用以自动选择订单。然后，提出在强化学习训练过程中全部使用动态的信息嵌入编解码器框架，这种策略能够更好的感知环境的动态变化，使车辆能够更好地处理订单。最后，按照均匀分布对订单进行了采样，学习到的策略能够为车辆选择取配订单找到更高质量的解决方案。验结果表明，本发明能够更好的解决cvrprpdltw，解决方案质量优于最先进的drl方法和大多数传统启发式方法，并可以在极短的时间内产生解决方案。为求解cvrprpdltw问题提供了一种新的有效算法。


技术实现要素：

4.深度强化学习在解决车辆路径问题方面虽然已经越来越有效地生成更高质量的
方案来，但现有的大多数基于深度强化学习的解决方案只专注于处理典型的vrp问题，即车辆从网点出发，不断选择下一个要访问的客户节点，直到满足所有客户的需求，最终形成车辆的完整路线。因此，这些工作的关键是选择下一个要访问的节点。然而，在实际的城配物流中，物流车辆是从订单角度出发，每一步选择下一个要处理的订单，并动态的根据时间来确定即将要访问节点的位置。显然，考虑到以下问题，这些工作在应用于解决更实际的cvrprpdltw时效果要差得多：(1)车辆无法根据客户需求判断当前车上是否有相应货物，并且车辆对具有移动性的节点位置不够敏感，无法实时决策要访问下一个节点的位置；(2)传统的模拟退火、蚁群等启发式算法无法在该问题的大规模实例上快速求出可行解来满足车辆路径实时决策的需要。
5.为了解决上述问题，本发明设计了一种动态漫游位置的深度强化学习方法。本发明主要包括五个部分：(1)对cvrprpdltw的混合整数规划公式进行问题建模。(2)马尔可夫决策过程建模。(3)构建drpdrl框架(4)构建基于actor-critic的强化学习训练算法(5)对模型的有效性进行实验验证。
6.下面分别介绍以上五部分的内容：
7.1、对cvrprpdltw的混合整数规划公式进行问题建模。根据问题实例进行问题定义，定义cvrprpdltw的决策变量和目标函数。
8.2、马尔可夫决策过程建模。在cvrprpdltw中车辆从网点出发分步取送货的过程也可以看作是一个顺序决策问题，本发明中将这样的路线构建过程建模为马尔可夫决策过程。
9.3、构建drpdrl框架。首先经过三个编码器分别将问题实例的原始特征进行处理。然后通过解码器融合三个并行编码器的输出，以选择最优动作概率的订单。这种方案能够使策略网络更全局地感知环境的变化。
10.4、构建actor-critic的强化学习训练算法。本发明中采用actor-critic(ac)算法训练用于订单选择的策略网络参数及评价其好坏的价值网络参数。
11.5、对模型的有效性进行实验验证。通过实验证明，本发明的整体性能优于大多数传统启发式方法，与先进的深度强化学习方法相比，实现了最佳的整体性能。更重要的是，与许多经典启发式方法不同，本发明可以随问题规模的增加很好地扩展，并且它不需要优先计算距离矩阵，尤其是在节点位置可以动态变化的车辆路径问题中。
12.本发明为实现上述目的所采取的详细实施步骤如下：
13.步骤1：对cvrprpdltw的混合整数规划公式进行问题建模。本发明定义所有节点的集合为x＝(d，h，c)。d是网点，h是货主，c是客户。在个节点集合x＝(x1，x2，...，xn)，其中xi∈r8定义为其中分别表示节点对应两个位置的坐标及其开始和结束时间，第一个位置的开始和结束时间分别为第二个位置的开始和结束时间分别为车辆的最大载重为v＝{(q)}，需要完成的订单数量为n。每个订单表示orderi：(xu，xv，wi)，每个订单有不同的id，表示第i个订单，货主xu给客户xv配送货物体积wi。定义决策变量如下：
14.15.其中，y
ij
是一个二元变量，车辆从xi直接行驶到xj，则等于1，否则等于0。令d(xi，xj)为xi和xj之间的欧氏距离。令t
ij
为车辆从节点xi行驶到节点xj的时间。令ti为连续变量，表示车辆离开位置xi的时间。令li为连续变量，表示车辆离开位置xi后负载。令m为一个足够大的值，用于确保取货和交货的两个约束中只有一个有效。为了简化，假设所有车辆都具有相同的速度s，可以很容易地将其扩展为采用不同的值。然后，cvrprpdltw的目标函数可以表示为：
[0016][0017]
步骤2：马尔可夫决策过程建模。在cvrprpdltw中车辆从网点出发分步取送货的过程也可以看作是一个顺序决策问题。因此，本发明将这样的路线构建过程建模为马尔可夫决策过程(markov decision process，mdp)，由四元组m＝{s，a，τ，r}表示，s表示状态空间，a为动作空间，τ为状态转移规则，r为奖励函数。mdp的元素，即状态空间、动作空间、转换规则和奖励函数定义如下：
[0018]
步骤2.1：状态。在本发明的mdp中，每个状态s
t
＝(d
t
，l
t
，z
t
)∈s由三部分组成。第一部分是当前车辆位置距未完成订单相应点的距离，表示为其中和分别表示车辆在步骤t时距订单i相应节点的两个位置的距离。第二部分是未完成订单的装卸载量l
t
，表示为其中是表示在步骤t时订单i需要装载或者卸载的重量。第三部分是所有订单的状态z
t
，表示为其中是表示在步骤t时订单i的状态(订单有三种状态待运状态等于0、在运状态等于1、完成状态等于2)。
[0019]
步骤2.2：动作。在本发明中的动作定义为选择要访问的订单。具体来说，在a
t
∈a处的动作表示为即车辆要完成订单i的取货或者送货服务。
[0020]
步骤2.3：状态转移规则。转换规则v将根据在处执行的动作将前一个状态s
t
转换到下一个状态s
t+1
，即s
t+1
＝(o
t+1
)＝τ(o
t
)。当前车辆位置距未完成订单相应点的距离d
t
中的元素更新如下：
[0021][0022][0023]
其中xi是车辆当前位置。未完成订单的装卸载量l
t
中元素更新如下：
[0024][0025]
订单的状态z
t
更新如下：
[0026][0027]
步骤2.4：奖励。对于cvrprpdltw，为了最小化车辆完成所有订单的时间，奖励定义为该值的负值，那么每步奖励及最终的奖励可以定义为：
[0028]
r(s
t+1
|s
t
)＝t
ij
+waitj[0029][0030]
其中，t
ij
为车辆从节点xi行驶到节点xj的时间，waitj表示如果在点j处车辆需要等待，则加上等待时间。
[0031]
步骤3：构建drpdrl框架。本发明专注于学习一种新颖的基于注意力的深度神经网络，其中策略网络能够在每个决策步骤中实现订单的选择，价值网络能够帮助策略网络进行策略更新。如图2所示，策略网络和价值网络由编码器解码器和解码器组成。在第一步(t＝0)时，编码器对给定输入数据的本身执行一次计算，其输出可在后续步骤(t＞0)中重复用于路线构建。为了解决这个实例，通过三个编码器处理原始特征以获得更好的表示，策略网络从所有未完成的订单中选择一个订单进行处理。价值网络会判断在当前状态下选择当前订单是否是好的。所选订单构成该步骤的动作，进一步用于更新状态。重复此过程，直到完成所有订单。
[0032]
为了解决cvrprpdltw，本发明提出了一个transformer风格的模型作为策略网络和价值网络，其设计如图3所示。基于未完成的订单在每一步都有机会被选择的规定，策略网络能够根据cvrprpdltw的特点在更合理和更广阔的行动空间中进行搜索。此外，本发明将丰富的状态信息输入到编码器，其提取的特征来丰富解码器的上下文信息。这样做，以便让智能体做出更有效地决策。
[0033]
步骤3.1：通过三个编码器分别将问题实例的原始特征(即当前车辆位置距未完成订单相应点的距离、未完成订单的装卸载量和所有订单的状态)进行处理。首先将输入数据归一化，可访问点为[0，0.5]，不可访问点为1，然后线性投影到维数dim＝128的高维空间中，表示如下：
[0034]
hdi＝w
uv
concat(ui，vi)，hli＝w
l
li，hzi＝wzzi[0035]
其中hdi，hli，hzi分别表示订单i的节点位置与车辆位置的距离、订单i的装卸载量和订单i状态的原始高维映射，w
uv
，w
l
，wz为可训练参数。随后每个增强的节点嵌入都通过一个自编码器子层，每一个子层都有一个多头注意力(mha)和前馈(ff)组成。
[0036]
mha子层使用多头自注意力网络来处理节点嵌入。第一个编码器的mha子层用来处理hdi，输出后使用跳跃连接和批量归一化层，表示如下：
[0037][0038]
第二个和第三个编码器的mha子层分别处理hli和hzi，表示如下：
[0039][0040][0041]
mha输出被馈送到具有tanh激活函数的ff子层。第一个编码器的ff子层用来处理，这里也使用了跳跃连接和批量归一化层，表示如下：
[0042][0043]
第二个和第三个编码器的ff子层分别处理hli和hzi，表示如下：
[0044][0045][0046]
mha子层使用多头自注意力网络来处理节点嵌入，规定dimk＝32，y＝8是
attention中的head数。mha子层首先计算每个头部的注意力值，然后连接所有这些头部。以当前车辆位置距未完成订单相应点的距离的节点嵌入为例，将这些步骤展示如下：
[0047][0048]
mha(hd)＝concat(z
l，1
，z
l，2
，...，z
l，y
)
[0049]
其中是可训练参数，并且在不同的注意力层之间是独立的。此外，ff子层表示具有256维隐藏层并使用tanh激活的全连接层，表示如下：
[0050][0051]
其中w
f1
，w
f2
，b
f1
，b
f2
是可训练参数。最后，将编码器的最终输出即定义为问题实例的节点嵌入，它将作为解码器的输入。
[0052]
步骤3.2：通过三个并行编码器的输出分别作为解码器attention中的query、key和value向量，具体步骤如下式所示：
[0053][0054][0055]
其中是可训练参数。然后解码器通过6个注意力层进一步转换，并连接所有这些头部，表示如下：
[0056]
mha(h
d+1
，h
l+1
，h
z+1
)＝concat(z
c，1
，z
c，2
，...，z
c，y
)
[0057]
之后，第l个mha子层的输出被馈送到具有tanh激活函数的第l个ff子层，以获得下一个更新嵌入h
z+2
，总结如下：
[0058][0059][0060]
最后，将用参数w1和b1进行线性投影，价值网络根据此结果来判断选取当前动作的好坏，线性投影如下所示：
[0061][0062]
策略网络会使用softmax函数进一步处理以计算概率向量，如下所示：
[0063]
p
t
＝softmax(hz)
[0064]
其中p
t
∈rm及其元素表示在时间步t选择订单zi的概率。策略网络可以根据向量p
t
采样来选择订单。
[0065]
步骤4：构建基于actor-critic的强化学习训练算法。drpdrl的训练使用actor-critic算法，训练用于订单选择的策略网络参数及评价其好坏的价值网络参数。策略网络π
θ
，在每个解码步骤生成订单的概率向量，根据该概率选择一个订单作为动作，价值网络v
ω
，与策略网络具有相似的结构，该网络生成的值是对策略网络选取的动作进行评价。
[0066]
每次迭代中，为每个问题实例构建路线，策略网络每步选择一个要处理的订单a
i，j
～π
θ
(a
i，j
|s
i，j
)，随后获取每一步解决方案的奖励r
i，j
并更新到下一个状态s
i+1，j
，选择完所有订单后为每一步计算时序差分残差，其用于指导策略梯度进行学习，如下所示：
[0067]
δ
i，j
＝r
i，j
+γv
ω
(s
i+1，j
)-v
ω
(s
i，j
)
[0068]
然后通过均方误差损失函数更新价值网络参数ω，从而改善策略，提高行为质量。并通过策略梯度学习更新策略网络的参数θ，使其更好地估计状态值函数，从而提高预测的准确程度，如下所示：
[0069][0070][0071]
不断重复上述步骤直到达到停止条件或满足收敛条件，最终得到最短的车辆总行程时间。
[0072]
本发明提出了一种解决漫游取送位置和时间窗的有容量约束车辆路径问题的深度强化学习方法，该方法是一种考虑多维度特性的transformer架构。首先，通过三个编码器层处理具有不同维度的信息，解码器层融合这些信息来进行路线构建，以增强drpdrl拟合不同场景的能力，用以自动选择订单。然后，提出在强化学习训练过程中全部使用动态的信息嵌入编解码器框架，这种策略能够更好的感知环境的动态变化，使车辆能够更好地处理订单。最后，按照均匀分布对订单进行了采样，学习到的策略能够为车辆选择取配订单找到更高质量的解决方案。实验结果表明，与现有方法相比，本发明能够更好的解决cvrprpdltw。对于所研究的案例，与模拟退火、蚁群等传统的启发式算法相比，可以在极短的时间内产生解决方案。在相当的计算时间下，比其他深度强化学习方法获得了更好的解决方案质量。
附图说明
[0073]
图1是本发明中车辆从网点出发，在货主所在地提货，并在客户所在地交货的过程示意图
[0074]
图2是本发明中网络框架示意图
[0075]
图3是本发明中网络架构示意图
[0076]
图4是本发明中drpdrl方法与aco的收敛曲线图
[0077]
图5是本发明中在rpdt-30、rpdt-45、rpdt-60和rpdt-75数据集上的训练拟合曲线图
[0078]
图6是本发明中隐藏状态维度对rpdt-30、rpdt-45、rpdt-60和rpdt-75数据集的影响曲线图
[0079]
图7是本发明中解码器数量对rpdt-30、rpdt-45、rpdt-60和rpdt-75数据集的影响曲线图
具体实施方式
[0080]
下面结合附图和实施例对本发明进一步说明。
[0081]
本发明针对具有漫游取送位置和时间窗的有容量约束车辆路径问题建立了具有马尔可夫的深度强化学习仿真环境，设计了一种动态漫游位置的深度强化学习方法，该方法是一种考虑多维度特性的transformer架构，来学习路径构建解决方案。
[0082]
步骤1：设在一个cvrprpdltw中，有1个网点、10个货主、30个客户和30的订单，由于除网点外一个节点有两个不同的位置，所以一共有121个坐标。首先随机生成实例，交付中
心的坐标为(59，28)，10个货主的20个坐标为(76，25)、(27，56)、(27，17)、(10，52)、(53，68)、(26，66)、(58，56)、(57，72)、(21，59)、(43，74)、(45，26)、(29，47)、(12，36)、(79，57)、(27，34)、(69，33)、(67，57)、(42，50)、(73，31)、(31，14)，30个客户的60个坐标为(14，32)、(61，16)、(41，57)、(12，44)、(55，48)、(20，78)、(72，49)、(44，72)、(78，40)、(46，21)、(39，30)、(12，34)、(21，40)、(42，79)、(48，57)、(32，64)、(49，37)、(16，22)、(20，10)、(68，53)、(23，47)、(40，12)、(63，35)、(22，62)、(69，46)、(41，52)、(10，25)、(71，45)、(58，17)、(69，74)、(12，37)、(25，70)、(42，21)、(69，52)、(50，56)、(40，16)、(44，42)、(78，28)、(44，62)、(32，44)、(42，56)、(43，65)、(31，55)、(36，26)、(61，60)、(66，33)、(38，33)、(67，63)、(59，29)、(79，72)、(50，31)、(35，46)、(68，54)、(39，27)、(26，61)、(52，23)、(37，59)、(48，35)、(33，72)、(68，46)。其中每相邻的两个坐标代表一个节点，相邻坐标第一个坐标的时间窗为[0，12)，第二个坐标的时间窗为[12，20)。30个订单的取货节点、送货节点和货物量分别为(6，24，5)、(1，40，2)、(4，34，3)、(4，17，3)、(8，27，1)、(10，16，2)、(4，26，2)、(6，19，2)、(3，37，2)、(5，23，4)、(8，33，4)、(7，13，3)、(9，22，4)、(9，39，1)、(2，32，4)、(7，15，5)、(8，21，2)、(8，31，3)、(9，20，5)、(02，12，4)、(6，11，5)、(10，18，5)、(9，25，5)、(10，38，4)、(5，36，5)、(4，30，5)、(1，28，5)、(4，35，1)、(6，14，5)、(1，29，4)。车的核载量为20，车速为20.0km/h。本发明中定义的决策变量如下：
[0083][0084]
据此，在满足约束的条件下，cvrprpdltw的目标函数为：
[0085][0086]
步骤2：在本发明中将cvrprpdltw中的路线建设过程建模为马尔可夫决策过程，由四元组m＝{s，a，τ，r}表示，s表示状态空间，a为动作空间，τ为状态转移规则，r为奖励函数。
[0087]
(1)设此时选择解码的订单为第1个订单，如果此时第一个订单的状态为在运状态，那么下一时刻的车辆应该去节点24送货，当前车辆位置距未完成订单相应点的距离为节点24的对应位置到下一个订单需要取货或送货节点位置的距离。当前车辆位置距未完成订单相应点的距离d
t
中的元素更新如下：
[0088][0089][0090]
(2)同理，如果此时选择解码的订单为第1个订单，且此时第一个订单的状态为在运状态，那么下一时刻的车辆应该去节点24送货。那么下一时刻的车辆剩余核载量为此时车辆的剩余核载量减去第1个订单的货物量。下一时刻未完成订单的装卸载量l
t
中元素更新如下：
[0091][0092]
(3)如果完成第1个订单的送货任务，那么第一个订单处理结束。订单的状态z
t
更
新如下：
[0093][0094]
步骤3：为了解决cvrprpdltw，本发明提出了一个transformer风格的模型作为策略网络和价值网络.如图2所示，策略网络和价值网络由编码器解码器和解码器组成，通过三个编码器处理原始特征以获得更好的表示，策略网络从所有未完成的订单中选择一个订单进行处理。价值网络会判断在当前状态下选择当前订单是否是好的。
[0095]
本发明中的单步编解码过程如图3所示，三个编码器分别将三个问题实例的原始特征进行处理，最终会输出三个相应的特征嵌入。假设有30个订单，在给定当前状态的情况下，通过编码器处理当前车辆位置距未完成订单相应点的距离、未完成订单的装卸载量和所有订单的状态这三个特征，计算相应的特征嵌入。三个并行编码器的输出分别作为解码器attention中的query、key和value向量，通过一个多头注意力层和一个前馈全连接后，再经过一个masked softmax层抽取订单的动作概率(例如p
t
＝0.68)，其中根据掩码规则求订单的概率，如果掩码值为0取对数为负无穷，代表不可访问，如果掩码则值为1取对数后为0，代表可访问。在本例中选择了订单1，并将更新的状态传递到s
t+1
。重复进行上述步骤，直到所有的订单都已处理完成时结束。
[0096]
步骤4：本发明中drpdrl的训练使用actor-critic算法，训练用于订单选择的策略网络参数及评价其好坏的价值网络参数。在处理完步骤1的实例后，首先策略网络求一次，然后价值网络再求一次。在策略网络中，车辆的路径为0、6.0、6.0、6.0、8.0、8.0、21.0、5.0、23.0、9.0、39.0、14.0、4.0、4.0、4.0、30.0、4.0、3.1、34.1、37.1、8.1、27.0、11.0、2.0、2.0、12.0、9.0、22.0、9.0、25.0、32.1、10.1、33.1、1.1、9.1、17.1、35.0、19.0、16.0、5.0、36.0、8.0、31.0、4.0、26.0、28.1、1.1、10.1、18.1、6.0、20.0、24.0、10.0、38.0、29.0、1.0、7.1、40.1、13.1、7.1、15.0，其中小数点后为0代表当前节点的第一个位置，小数点后为1代表当前节点的第二个位置，此路径的最优总时间为75.94h，等待时间为10.12h，总路径长度为1316.49。在价值网络中，对每一步动作生成一个值来评价动作的好坏即会有60个评价值，策略网络会据此进行策略更新。
[0097]
本发明中总结了采用的解决cvrprpdltw的训练算法，其中策略网络π
θ
，在每个解码步骤生成订单的概率向量，根据该概率选择一个订单作为动作，价值网络vw，与策略网络具有相似的结构，该网络生成的值是对策略网络选取的动作进行评价。具体来说，在每次迭代中，为每个问题实例构建路线，并根据这个解计算奖励，然后计算均方误差损失函数，并更新策略网络的参数和价值网络参数。每个回合的实例被训练使用完以后，重新抽样新的评估实例以防止过拟合。通过更新这两个网络，策略π
θ
被训练为寻找更高质量的解决方案。
[0098]
设货主、客户节点的位置坐标及订单都是随机生成的，实验运行了20个回合，在每个回合中处理14000批次，每次评估批处理大小为10，每个批次有30个实例，使用adam优化器以恒定学习率训练网络，其中策略网路学习率为0.0001，价值网络学习率为0.001。为适配不同的规模，训练了30、45、60、75、90、105和120个订单的cvrprpdltw。在训练中，所有的实例都是随机生成的，生成的实例均按照均匀分布随机采样，其中客户节点坐标和交付中心坐标在区域[10，80]
×
[10，80]中采样。
[0099]
在验证中，以sa、aco、pg以及ppo算法为求解基准，分别验证了drpdrl模型在不同
规模实例上的表现，给出了具有代表性的基准方案aco算法的验证样例及分析，通过消融实验和参数实验验证了所提出方法的有效性。最终结果表明drpdrl方法优于最先进的深度强化学习算法和大多数的传统启发式方法。

技术特征：
1.一种解决漫游取送位置和时间窗的有容量约束车辆路径问题的深度强化学习方法，其特征在于包括下述步骤：定义：cvrprpdltw全称为capacitated vehicle routing problem with roaming pickup and delivery locations and time windows，即具有漫游取送位置和时间窗的有容量约束车辆路径问题，是本发明设计的新问题，drpdrl全称为dynamic roaming position deep reinforcement learning method，即动态漫游位置的深度强化学习方法，本发设计了一种考虑多维度特性的transformer架构，来增强深度强化学习拟合不同场景的能力，在这种架构中，通过三个编码器层处理具有不同维度的信息，解码器层融合这些信息来进行路线构建，以自动选择订单来学习构建解决方案，这种方法能够大规模实例上快速求出可行解来满足车辆路径实时决策的需要；步骤1：对cvrprpdltw的混合整数规划公式进行问题建模；本发明定义所有节点的集合为x＝(d，h，c)，d是网点，h是货主，c是客户，在个节点集合x＝(x1，x2，...，x
n
)，其中x
i
∈r8定义为其中分别表示节点对应两个位置的坐标及其开始和结束时间，第一个位置的开始和结束时间分别为第二个位置的开始和结束时间分别为车辆的最大载重为v＝{(q)}，需要完成的订单数量为n，每个订单表示order
i
：(x
u
，x
v
，w
i
),每个订单有不同的id，表示第i个订单，货主x
u
给客户x
v
配送货物体积w
i
，定义决策变量如下：其中，y
ij
是一个二元变量，车辆从x
i
直接行驶到x
j
，则等于1，否则等于0，令d(x
i
，x
j
)为x
i
和x
j
之间的欧氏距离，令t
ij
为车辆从节点x
i
行驶到节点x
j
的时间，令t
i
为连续变量，表示车辆离开位置x
i
的时间，令l
i
为连续变量，表示车辆离开位置x
i
后负载，令m为一个足够大的值，用于确保取货和交货的两个约束中只有一个有效，为了简化，假设所有车辆都具有相同的速度s，可以很容易地将其扩展为采用不同的值，然后，cvrprpdltw的目标函数可以表示为：步骤2：马尔可夫决策过程建模；在cvrprpdltw中车辆从网点出发分步取送货的过程也可以看作是一个顺序决策问题，因此，本发明将这样的路线构建过程建模为马尔可夫决策过程(markov decision process，mdp)，由四元组表示，s表示状态空间，a为动作空间，为状态转移规则，r为奖励函数，mdp的元素，即状态空间、动作空间、转换规则和奖励函数定义如下：步骤2.1：状态；在本发明的mdp中，每个状态s
t
＝(d
t
，l
t
，z
t
)∈s由三部分组成，第一部分是当前车辆位置距未完成订单相应点的距离，表示为其中和分别表示车辆在步骤t时距订单i相应节点的两个位置的距离，第二部分是未完成订单的装卸载量l
t
，表示为其中是表示在步骤t时订单i需要装载或者卸载的重量，第三部分
是所有订单的状态z
t
，表示为其中是表示在步骤t时订单i的状态(订单有三种状态待运状态等于0、在运状态等于1、完成状态等于2)；步骤2.2：动作；在本发明中的动作定义为选择要访问的订单，具体来说，在a
t
∈a处的动作表示为即车辆要完成订单i的取货或者送货服务；步骤2.3：状态转移规则；转换规则将根据在处执行的动作将前一个状态s
t
转换到下一个状态s
t+1
，即当前车辆位置距未完成订单相应点的距离d
t
中的元素更新如下：中的元素更新如下：其中x
i
是车辆当前位置，未完成订单的装卸载量l
t
中元素更新如下：订单的状态z
t
更新如下：步骤2.4：奖励；对于cvrprpdltw，为了最小化车辆完成所有订单的时间，奖励定义为该值的负值，那么每步奖励及最终的奖励可以定义为：r(s
t+1
|s
t
)＝t
ij
+wait
j
其中，t
ij
为车辆从节点x
i
行驶到节点x
j
的时间，wait
j
表示如果在点j处车辆需要等待，则加上等待时间；步骤3：构建drpdrl框架；本发明专注于学习一种新颖的基于注意力的深度神经网络，其中策略网络能够在每个决策步骤中实现订单的选择，价值网络能够帮助策略网络进行策略更新，如图2所示，策略网络和价值网络由编码器解码器和解码器组成，在第一步(t＝0)时，编码器对给定输入数据的本身执行一次计算，其输出可在后续步骤(t>0)中重复用于路线构建，为了解决这个实例，通过三个编码器处理原始特征以获得更好的表示，策略网络从所有未完成的订单中选择一个订单进行处理，价值网络会判断在当前状态下选择当前订单是否是好的，所选订单构成该步骤的动作，进一步用于更新状态，重复此过程，直到完成所有订单；为了解决cvrprpdltw，本发明提出了一个transformer风格的模型作为策略网络和价值网络，其设计如图3所示，基于未完成的订单在每一步都有机会被选择的规定，策略网络能够根据cvrprpdltw的特点在更合理和更广阔的行动空间中进行搜索，此外，本发明将丰富的状态信息输入到编码器，其提取的特征来丰富解码器的上下文信息，这样做，以便让智
能体做出更有效地决策；步骤3.1：通过三个编码器分别将问题实例的原始特征(即当前车辆位置距未完成订单相应点的距离、未完成订单的装卸载量和所有订单的状态)进行处理，首先将输入数据归一化，可访问点为[0，0.5]，不可访问点为1，然后线性投影到维数dim＝128的高维空间中，表示如下：hd
i
＝w
uv
concat(u
i
，v
i
)，hl
i
＝w
l
l
i
，hz
i
＝w
z
z
i
其中hd
i
，hl
i
，hz
i
分别表示订单i的节点位置与车辆位置的距离、订单i的装卸载量和订单i状态的原始高维映射，w
uv
，w
l
，w
z
为可训练参数，随后每个增强的节点嵌入都通过一个自编码器子层，每一个子层都有一个多头注意力(mha)和前馈(ff)组成；mha子层使用多头自注意力网络来处理节点嵌入，第一个编码器的mha子层用来处理hd
i
，输出后使用跳跃连接和批量归一化层，表示如下：第二个和第三个编码器的mha子层分别处理hl
i
和hz
i
，表示如下：，表示如下：mha输出被馈送到具有tanh激活函数的ff子层，第一个编码器的ff子层用来处理，这里也使用了跳跃连接和批量归一化层，表示如下：第二个和第三个编码器的ff子层分别处理hl
i
和hz
i
，表示如下：，表示如下：mha子层使用多头自注意力网络来处理节点嵌入，规定dim
k
＝32，y＝8是attention中的head数，mha子层首先计算每个头部的注意力值，然后连接所有这些头部，以当前车辆位置距未完成订单相应点的距离的节点嵌入为例，将这些步骤展示如下：mha(hd)＝concat(z
l，1
，z
l，2
，...，z
l，y
)其中是可训练参数，并且在不同的注意力层之间是独立的，此外，ff子层表示具有256维隐藏层并使用tanh激活的全连接层，表示如下：其中w
f1
，w
f2
，b
f1
，b
f2
是可训练参数，最后，将编码器的最终输出即定义为问题实例的节点嵌入，它将作为解码器的输入；步骤3.2：通过三个并行编码器的输出分别作为解码器attention中的query、key和value向量，具体步骤如下式所示：
其中是可训练参数，然后解码器通过6个注意力层进一步转换，并连接所有这些头部，表示如下：mha(h
d+1
，h
l+1
，h
z+1
)＝concat(z
c，1
，z
c，2
，...，z
c，y
)之后，第1个mha子层的输出被馈送到具有tanh激活函数的第1个ff子层，以获得下一个更新嵌入h
z+2
，总结如下：，总结如下：最后，将用参数w1和b1进行线性投影，价值网络根据此结果来判断选取当前动作的好坏，线性投影如下所示：策略网络会使用softmax函数进一步处理以计算概率向量，如下所示：p
t
＝softmax(h
z
)其中p
t
∈r
m
及其元素表示在时间步t选择订单z
i
的概率，策略网络可以根据向量p
t
采样来选择订单；步骤4：构建基于actor-critic的强化学习训练算法；drpdrl的训练使用actor-critic算法，训练用于订单选择的策略网络参数及评价其好坏的价值网络参数，策略网络π
θ
，在每个解码步骤生成订单的概率向量，根据该概率选择一个订单作为动作，价值网络v
ω
，与策略网络具有相似的结构，该网络生成的值是对策略网络选取的动作进行评价；每次迭代中，为每个问题实例构建路线，策略网络每步选择一个要处理的订单a
i，j
～π
θ
(a
i，j
|s
i，j
)，随后获取每一步解决方案的奖励r
i，j
并更新到下一个状态s
i+1，j
，选择完所有订单后为每一步计算时序差分残差，其用于指导策略梯度进行学习，如下所示：δ
i，j
＝r
i，j
+γv
ω
(s
i+1，j
)-v
ω
(s
i，j
)然后通过均方误差损失函数更新价值网络参数ω，从而改善策略，提高行为质量，并通过策略梯度学习更新策略网络的参数θ，使其更好地估计状态值函数，从而提高预测的准确程度，如下所示：程度，如下所示：不断重复上述步骤直到达到停止条件或满足收敛条件，最终得到最短的车辆总行程时间。

技术总结
本发明提供了一种用深度强化学习解决漫游取送位置和时间窗的有容量约束车辆路径问题的方法。该方法是一种考虑多维度特性的Transformer架构。具体来说，模型通过三个编码器层处理具有不同维度的信息，解码器层融合这些信息来进行路线构建，它通过自动选择订单来学习构建解决方案，与此同时，该方法考虑了车辆的等待时间，旨在最小化车队中车辆的最长或总行程时间。实验结果表明，该方法在总体解决质量方面优于最先进的深度强化学习方法和大多数传统启发式方法，并且具有更短的计算时间。本方法通过优化路线和避免不必要的出行等方式，降低行驶里程和成本、减少燃料消耗、碳排放和运营成本，同时促进可持续发展，提高环保意识和经济效益。意识和经济效益。意识和经济效益。


技术研发人员：田冉 孙志慧 吴佳蕊 芦鑫 王进世 常龙龙
受保护的技术使用者：西北师范大学
技术研发日：2023.07.13
技术公布日：2023/10/6