一种动态目标遍历访问序列规划方法与系统

摘要

一种动态目标遍历访问序列规划方法与系统，给定每个目标的初始位置、终端位置以及每个目标在规划时间段内的移动路径；通过离散时间轴将移动目标访问序列规划问题转化成一个间断移动目标访问序列规划问题并构建该问题模型；采用动态目标序列规划蚁群算法求解间断移动目标访问序列规划问题模型，获得间断移动目标访问序列规划问题的最优目标访问次序；将目标访问次序固定，从而把原移动目标访问序列规划问题转化成次序固定访问时间规划问题，构建并求解该问题模型，获得每个目标的最优访问时间，最终获得原移动目标访问序列规划问题的最优解。本发明有效提高了移动目标访问序列规划问题的优化效率和优化成功率。

说明书

技术领域

本发明主要涉及到动态目标访问序列规划技术领域，特指一种动态目标遍历访问序列规划方法与系统。

背景技术

旅行商问题(Traveling Salesman Problem，TSP)作为典型的访问序列规划问题，已被广泛研究。这类问题要求规划者寻找一条最短的路径，使得旅行商从某个城市出发，不遗漏也不重复地访问完所有给定的城市并最终回到出发的城市。经典的TSP问题为静态目标访问序列规划问题，城市的位置始终保持不变，因而经典TSP问题是纯组合优化问题。作为经典TSP问题的一个变种，动态TSP问题是指城市位置会随时间不断变化的问题，是一类移动目标访问序列规划问题。这类问题除了要考虑城市的访问序列变量，还要考虑每个城市的访问时间变量，因而动态TSP问题是混合整数优化问题。

图1和图2展示了静态目标序列和移动目标序列的区别。图1为一条静态目标访问序列，图2为一条移动目标访问序列，其中，A

目前普遍采用混合编码遗传算法求解动态TSP问题。混合编码遗传算法可以实现整数变量(访问次序)和实数变量(访问时间)同时寻优，但实际优化效率较低，优化结果往往不好，有必要开发一种新的移动目标序列规划方法以满足动态TSP问题及其类似衍生问题的优化需求。

发明内容

针对现有技术存在的优化效率低、优化结果差等缺陷，本发明提供一种动态目标遍历访问序列规划方法与系统。该方法通过时间轴离散策略首先将原混合整数优化问题转化成一个纯组合优化问题和一个纯实数优化问题，然后采用分步规划的方法分阶段确定移动目标的访问次序和访问时间。该方法可明显提高移动目标访问序列规划问题的优化效率。

具体地，本发明的技术方案是：

一种动态目标遍历访问序列规划方法，包括以下步骤：

S1：给定移动目标访问序列规划问题中每个目标的初始位置、终端位置以及每个目标在规划时间段内的移动路径。其中规划时间段ΔT为移动目标访问序列规划问题的总时间跨度。

S2：通过离散时间轴将移动目标访问序列规划问题转化成一个间断移动目标访问序列规划问题，并构建间断移动目标访问序列规划问题模型。

S3：采用动态目标序列规划蚁群算法求解间断移动目标访问序列规划问题模型，获得间断移动目标访问序列规划问题的最优目标访问次序。

S4：将S3获得的最优目标访问次序固定，从而把原移动目标访问序列规划问题转化成次序固定访问时间规划问题，并构建次序固定访问时间规划问题模型。

S5：采用优化算法求解次序固定访问时间规划问题模型，获得每个目标的最优访问时间，最终获得原移动目标访问序列规划问题的最优解。

优选地，本发明S2中将每个目标在规划时间段ΔT内的移动路径进行等时间间距离散，得到每个目标在ΔT时间段内的一系列离散的位置点，原移动目标访问序列规划问题被转化成一个间断移动目标访问序列规划问题，规划时间段ΔT被均分的段数p定义为原移动目标访问序列规划问题的时间离散度。

优选地，本发明S2中所构建的间断移动目标访问序列规划问题模型的设计变量为：

X

其中，N为目标的个数；S

间断移动目标访问序列规划问题模型的约束条件有：

第一类约束为访问次序变量取值的唯一性：

上式表示访问次序的取值范围为1到N之间的正整数，且任意两个目标的访问次序的取值不相同，S

第二类约束为旅行商到达后一个目标的时刻不能小于前一个目标的出发时刻：

T

第三类约束为Δt

其中，n

间断移动目标访问序列规划问题的优化目标为最小化相邻两个访问目标之间的距离和，目标函数如下：

其中，

优选地，本发明S3中动态目标序列规划蚁群算法的流程如下：

S301：初始化蚂蚁群体数量N

S302：初始化信息素链表。

信息素链表呈矩阵形式，信息素链表中的元素表示某个目标被选为当前目标前往下一个目标的偏好程度，信息素链表中所有的元素都初始化为一个相同的值。

S303：蚂蚁m完成一个解构造，生成一个可行解。

蚂蚁m的解构造过程是：蚂蚁m首先从所有需要访问的目标候选集中随机选择一个作为初始目标，然后根据如下规则确定当前目标的出发时刻T

其中，R是0到1之间的一个随机数；q

P

若当前目标为C

其中，τ

P

其中，τ

S304：用S303构造生成的可行解局部更新信息素链表。

每只蚂蚁完成一个解构造所形成的访问序列都会作用于信息素链表的局部更新，若某只蚂蚁在T

τ

式中ξ为0到1之间的信息素局部更新衰减系数。

S305：不断重复S303和S304直到所有蚂蚁都完成解构造和信息素链表局部更新。

S306：用S305中生成的最好解全局更新信息素链表。

在305中每只蚂蚁构造的解都是可行解，最好解是从每一代的所有可行解中筛选出的目标函数值最优的那个解。目标函数值通过计算旅行商访问所有目标的路径之和得出，目标函数值最优的那个解即旅行商访问所有目标的路径之和最短的那个解。

具体地，更新方式如下：

式中，B

S307：不断重复S303～S306直至达到最大进化代数G

进一步地，本发明S4中次序固定访问时间规划问题模型的设计变量X

X

次序固定访问时间规划问题模型的约束条件是：旅行商到达后一个目标的时刻不能小于前一个目标的出发时刻。

次序固定访问时间规划问题模型的优化目标为最小化相邻两个访问目标之间的距离和。

进一步地，本发明S5中采用差分进化算法求解次序固定访问时间规划问题模型。

本发明还提供了一种动态目标遍历访问序列规划系统，包括存储器和处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现以下步骤：

S1：给定移动目标访问序列规划问题中每个目标的初始位置、终端位置以及每个目标在ΔT时间段内的移动路径，其中ΔT为移动目标访问序列规划问题的总时间跨度为ΔT。

S2：通过离散时间轴将移动目标访问序列规划问题转化成一个间断移动目标访问序列规划问题，并构建间断移动目标访问序列规划问题模型。

S3：采用动态目标序列规划蚁群算法求解间断移动目标访问序列规划问题模型，获得间断移动目标访问序列规划问题的最优目标访问次序。

S4：将S3获得的最优目标访问次序固定，从而把原移动目标访问序列规划问题转化成次序固定访问时间规划问题，并构建次序固定访问时间规划问题模型。

S5：采用优化算法求解次序固定访问时间规划问题模型，获得每个目标的最优访问时间，最终获得原移动目标访问序列规划问题的最优解。

一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现以下步骤：

S1：给定移动目标访问序列规划问题中每个目标的初始位置、终端位置以及每个目标在ΔT时间段内的移动路径，其中ΔT为移动目标访问序列规划问题的总时间跨度为ΔT。

S2：通过离散时间轴将移动目标访问序列规划问题转化成一个间断移动目标访问序列规划问题，并构建间断移动目标访问序列规划问题模型。

S3：采用动态目标序列规划蚁群算法求解间断移动目标访问序列规划问题模型，获得间断移动目标访问序列规划问题的最优目标访问次序。

S4：将S3获得的最优目标访问次序固定，从而把原移动目标访问序列规划问题转化成次序固定访问时间规划问题，并构建次序固定访问时间规划问题模型。

S5：采用优化算法求解次序固定访问时间规划问题模型，获得每个目标的最优访问时间，最终获得原移动目标访问序列规划问题的最优解。

传统的以混合整数遗传算法为代表的移动目标序列规划方法在求解移动目标访问序列规划问题时对整数变量(访问次序)和实数变量(访问时间)同时进行优化。由于染色体或粒子的整数片段和实数片段在交叉变异操作时具有独立性，传统方法的优化效率较低，很难获得高质量的解。

本发明提供的动态目标遍历访问序列规划方法和系统，采用时间轴离散和分步优化的策略求解移动目标访问序列规划问题。第一步通过时间轴离散先将移动目标访问序列规划问题转化成间断移动目标访问序列规划问题，最优访问次序通过求解间断移动目标访问序列规划问题获得。基于第一步确定的访问次序，第二步再将原来的移动目标访问序列规划问题转化成次序固定访问时间规划问题，然后只优化连续变量，最优的访问时间通过求解次序固定访问时间规划问题获得。本发明克服了传统移动目标序列规划方法的不足，可有效提高移动目标访问序列规划问题的优化成功率。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图示出的结构获得其他的附图。

图1是静态目标访问序列示意图；

图2是移动目标访问序列示意图；

图3是一实施例的流程图；

图4是一实施例中时间轴离散的移动目标访问序列示意图；

图5是表征静态序列目标之间信息素浓度的信息素链表示意图；

图6是表征动态序列目标之间信息素浓度的信息素链表示意图；

图7是优选实施例中15个城市在60min内的移动轨迹图；

图8为优选实施例中巡游者的最优移动路径图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明的一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

实施例1：

如图3所示，本实施例提供的动态目标遍历访问序列规划方法，包含以下几个步骤：

S1：给定移动目标访问序列规划问题中每个目标的初始位置、终端位置以及每个目标在规划时间段ΔT内的移动路径。

S2：通过离散时间轴将移动目标访问序列规划问题转化成一个间断移动目标访问序列规划问题，并构建间断移动目标访问序列规划问题模型。

原移动目标访问序列规划问题可描述为如下形式：

移动目标访问序列规划问题的设计变量为：

X

其中，N为目标的个数；S

移动目标访问序列规划问题的约束条件有：

(1)需要考虑的第一类约束为访问次序变量取值的唯一性：

式(2)表示访问次序的取值范围为1到N之间的正整数，且任意两个目标的访问次序的取值不相同，S

(2)需要考虑的第二类约束为旅行商到达后一个目标的时刻不能小于前一个目标的出发时刻：

T

移动目标访问序列规划问题的优化目标为最小化相邻两个访问目标之间的距离和，目标函数如下：

其中，

将每个目标在规划时间段ΔT内的移动路径进行等时间间距离散，得到每个目标在ΔT时间段内的一系列离散的位置点，原移动目标访问序列规划问题被转化成一个间断移动目标访问序列规划问题，规划时间段ΔT被均分的段数p定义为原移动目标访问序列规划问题的时间离散度，每个目标的离散位置点数目等于时间离散度加1。

图3给出了一个时间离散度为9的间断移动目标访问序列示意图。其中，A

间断移动目标访问序列规划问题模型的设计变量X

X

间断移动目标访问序列规划问题模型的约束条件除了式(2)和式(3)外，还包括Δt

其中，n

间断移动目标访问序列规划问题模型的目标函数J

明显地，经时间轴离散后的间断移动目标访问序列规划问题从原来的混合整数优化问题变成了一个纯组合优化问题。

S3：设计用于求解间断移动目标访问序列规划问题模型的动态目标序列规划蚁群算法。

动态目标序列规划蚁群算法的工作流程如下：

S301：初始化蚂蚁群体数量N

S302：初始化信息素链表；

信息素链表的定义在蚁群算法的设计中至关重要。在序列规划问题中，信息素链表中的元素表示某个目标被选为当前目标前往下一个目标的偏好程度。信息素浓度越高，被选为下一个目标的概率就越高。对于静态目标访问序列规划问题，目标位置不会随着时间的变化而变化，某个目标被选为下一个目标的偏好程度只需要用一个信息素浓度值来表示即可。因此，信息素链表呈现为矩阵形式，只需要用一个n×n的矩阵就可以表征所有n个访问目标被选为下一个目标的偏好程度。如图4所示，τ

但是，对于移动目标访问序列规划问题，目标位置会随着时间的变化而变化，若只用一个信息素浓度值来表示两个移动目标之间的关系，则会出现“刻舟求剑”的现象，因为一个信息素浓度值只能表示某一时刻的状态，并不能覆盖整个时间段的情况。

为了更好地表征两个移动目标在整个时间段内的情况，信息素矩阵中目标C

信息素链表中所有的元素都初始化为一个相同的值τ

S303：蚂蚁m完成一个解构造，生成一个可行解。

动态序列规划蚁群算法的解构造方法设计如下。

蚂蚁m的解构造过程是：蚂蚁m首先从所有需要访问的目标候选集中随机选择一个作为初始目标，然后根据如下规则确定当前目标的出发时刻T

其中，R是0到1之间的一个随机数；q

其中，τ

P

其中，τ

S304：用S303构造生成的可行解局部更新信息素链表；

每只蚂蚁完成一个解构造所形成的访问序列都会作用于信息素链表的局部更新，若某只蚂蚁在T

τ

式中，ξ为0到1之间的信息素局部更新衰减系数。

S305：不断重复S303和S304直到所有蚂蚁都完成解构造和信息素链表局部更新；

S306：用S305中生成的最好解全局更新信息素链表；其中最好解即当前代所有可行解中筛选出的目标函数值最优的那个解，目标函数值最优的那个解即旅行商访问所有目标的路径之和最短的那个解。

只有到目前为止的最好解才会用于信息素链表的全局更新，更新方式如下：

式中，B

S307：不断重复S303～S306直至达到最大进化代数G

S4：导入S1中每个目标的位置参数并采用S3中设计的动态目标序列规划蚁群算法获得间断移动目标访问序列规划问题模型的最优目标访问次序。

S5：将S4获得的最优目标访问次序固定，从而把移动目标访问序列规划问题转化成次序固定访问时间规划问题。

次序固定访问时间规划问题模型的设计变量X

X

式(11)中变量的含义与式(1)相同。

次序固定访问时间规划问题模型的约束条件为：旅行商到达后一个目标的时刻不能小于前一个目标的出发时刻。该问题只需要考虑如式(3)的访问时间先后约束。

次序固定访问时间规划问题模型的优化目标为最小化相邻两个访问目标之间的距离和，目标函数与式(4)相同。

S6：采用差分进化算法求解次序固定访问时间规划问题模型，获得每个目标的最优访问时间，最终获得原移动目标访问序列规划问题的最优解。

至此，基于时间轴离散和分步优化策略规划移动目标访问序列的过程全部完成。

实施例2：

采用实施例1中提供的动态目标遍历访问序列规划方法，本实施例以一个平面移动城市巡游序列规划问题为例进行说明。

S1：给定每个被访问目标的初始位置、终端位置以及每个目标在ΔT时间段内的移动路径。

本算例的时间段ΔT取为0～60min，移动城市数目为15，其中1号城市固定为初始出发城市。15个移动城市在初始0min和终端60min的位置坐标如表1所示。每个城市都从其初始位置沿直线移动到终端位置，移动速度恒定。移动轨迹如图6所示。其中三角形所在位置是各城市初始位置，圆形所在位置是终端位置。巡游者从当前城市到下一个城市也是按直线移动，移动速度不受限制。

表1初始时刻和终端时刻15个城市的位置坐标

S2：通过离散时间轴将原移动目标访问序列规划问题转化成一个间断移动目标访问序列规划问题。

将上述移动城市巡游序列规划问题的时间轴进行离散，离散度为20，也即在原来的移动轨迹上每3min取一个点，巡游者只能在这些时间点上从某个城市出发或到达某个城市。

S3：设计用于求解间断移动目标访问序列规划问题的动态目标序列规划蚁群算法。

按照实施例1中S301～S307设计动态目标序列规划蚁群算法。其中S301中用于本实施例的算法参数设置如表2所示。

表2动态序列规划蚁群算法参数设置

S4：导入S1中每个目标的位置参数并采用S3中设计的动态目标序列规划蚁群算法获得间断移动目标访问序列规划问题的最优目标访问次序；

采用动态目标序列规划蚁群算法获得间断移动目标访问序列规划问题的访问次序为(1,12,2,9,10,6,7,5,15,13,8,4,3,14,11)，经验证该访问次序为本实施例的最优访问次序。

S5：将S4获得的目标访问次序固定，从而把原移动目标访问序列规划问题转化成次序固定访问时间规划问题。

S6：采用差分进化算法求解次序固定访问时间规划问题，获得每个目标的最优访问时间，最终获得原移动目标访问序列规划问题的最优解。

采用差分进化算法求解获得的各城市的访问时间如表3所示。巡游者访问这15个移动城市的最优巡游路径如图7所示。从表3和图7中可以看出，巡游者并没有一开始就从1号城市出发，而是随1号城市一起移动了8.7208min后才离开前往12号城市。除了在9号、10号、13号和14号城市上有停留外，在其它城市都未作停留。在53.3254min时到达最后一个城市(11号城市)，完成了所有城市的巡游。

表3最优解各城市的出发时刻和到达时刻

为了对比本发明设计的方法和传统方法(即混合整数遗传算法)在求解移动目标序列规划问题上的表现，基于本实施例，我们分别做了20组独立的测试。20次独立测试的统计结果如表4所示。从表中的结果可以看出，本发明设计的方法获得的结果要比混合整数遗传算法的结果好得多。在20次独立测试中，混合整数遗传算法只有一次获得了最优序列，而且该次运行目标函数只优化到了865.57，并未完全收敛到最优值865.11，而本发明设计的方法有16次获得了最优序列，且均收敛到了最优值865.11。这说明本发明设计的方法在优化收敛性和稳定性方面都明显好于传统的混合整数遗传算法。

表4本发明方法与混合整数遗传算法独立运行20次统计结果对比

以上所述实施例仅表达了本申请某种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本申请构思的前提下，还可以做出若干变形和改进，这些都属于本申请的保护范围。因此，本申请专利的保护范围应以所附权利要求为准。