本申请涉及智能交通技术领域，特别是涉及一种巡逻路线确定方法、装置、计算机可读存储介质和计算机设备。
背景技术：
智能交通是业界关注的焦点的之一。在智能交通领域的智能巡逻应用中，现有技术中提供的巡逻方法通常是控制巡逻车从某一个区域连接口出发开始巡逻，直到每一个区域被巡逻到为止，这样可以保证巡逻车将所有区域巡逻完。
然而，在实际应用中，若直接按照上述巡逻方法进行巡逻，在巡逻过程中很有可能存在多次重复巡逻的区域，从而巡逻车的巡逻路径将会大量增加，巡逻路径的增加必然会造成成本的增加。
因此，如何保证巡逻车在巡逻完所有区域的前提下实现最短路径巡逻是智能巡逻面临的关键问题。
技术实现要素：
基于此，有必要针对如何保证巡逻车在巡逻完所有区域条件下实现最短路径巡逻的技术问题，提供一种优化的巡逻路线确定方法、装置、可读存储介质和计算机设备。
一种巡逻路线确定方法，所述方法包括：
获取待巡逻区域中的各子区域连接口之间的指向信息；
当根据所述各子区域连接口之间的指向信息确定所述待巡逻区域满足预设欧拉区域判断条件时，选取所述待巡逻区域中一个子区域连接口作为起始子区域连接口；
从所述起始子区域连接口开始依次确定下一子区域连接口，直至终点子区域连接口，获得各子区域连接口的排序信息；其中，非终点的各所述子区域连接口被经过的次数等于各所述子区域连接口所指向的子区域连接口的数量；
根据所述各子区域连接口的排序信息生成所述待巡逻区域的巡逻路线。
一种巡逻路线确定装置，所述装置包括：
指向信息获取模块，用于获取待巡逻区域中的各子区域连接口之间的指向信息
起始子区域连接口选取模块，用于当根据所述各子区域连接口之间的指向信息确定所述待巡逻区域满足预设欧拉区域判断条件时，选取所述待巡逻区域中一个子区域连接口作为起始子区域连接口；
排序信息确定模块，用于根据所述指向信息从所述起始子区域连接口开始依次确定下一子区域连接口，直至终点子区域连接口，获得各子区域连接口的排序信息；其中，非终点的各所述子区域连接口被经过的次数等于各所述子区域连接口所指向的子区域连接口的数量；
巡逻路线生成模块，用于根据所述各子区域连接口的排序信息生成所述待巡逻区域的巡逻路线。
一种计算机可读存储介质，存储有计算机程序，所述计算机程序被处理器执行时，使得所述处理器执行上述巡逻路线确定方法的步骤。
一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，所述计算机程序被所述处理器执行时，使得所述处理器执行上述巡逻路线确定方法的步骤。
上述巡逻路线确定方法、装置、可读存储介质和计算机设备，在对待巡逻区域进行巡逻之前，获取待巡逻区域中各子区域连接口之间的指向信息，当根据各子区域连接口的指向信息确定待巡逻区域满足预设的欧拉区域判断条件时，从待巡逻区域中选取起始子区域连接口，以该起始子区域连接口的指向信息依次确定下一子区域连接口，获得各子区域连接口的排序信息，其中保证各子区域连接口为非终点时，被经过的次数等于各子区域连接口指向的区域连接口的数量，进而根据排序信息生成巡逻路线。由于在根据各子区域连接口的指向信息确定待巡逻区域满足欧拉区域的判断条件，表示该待巡逻区域是可以以最短路径完成巡逻的，因此依次选取子区域连接口，并使其中非终点的子区域连接口被经过的次数等于其所指向的子区域连接口数量，如此获得排序信息生成的巡逻路线可以保证该待巡逻区域以最短路径实现巡逻。
附图说明
图1为一个实施例中巡逻路线确定方法的应用环境图；
图2为一个实施例中巡逻路线确定方法的流程示意图；
图3为一个具体实施例中子区域连接口之间的指向信息的示意图；
图4为一个具体实施例中欧拉回路区域的示意图；
图5为另一个实施例中巡逻路线确定方法的流程示意图；
图6为一个实施例中将待巡逻区域划分成至少两个均满足预设欧拉区域判断条件的待巡逻子区域的流程示意图；
图7为一个具体实施例中巡逻路线确定方法的流程示意图；
图8为一个具体实施例中巡逻路线确定方法的应用场景示意图；
图9为一个实施例中巡逻路线确定装置的结构框图；
图10为一个实施例中计算机设备的结构框图。
具体实施方式
为了使本申请的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本申请进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本申请，并不用于限定本申请。
图1为一个实施例中巡逻路线确定方法的应用环境图。请参照图1，在一些实施例中，该巡逻路线确定方法终端110和服务器120。终端110和服务器120通过网络连接。服务器120中的计算模块通过终端110获取待巡逻区域中各子区域连接口之间的指向信息，当根据各子区域连接口的指向信息确定待巡逻区域满足预设的欧拉区域判断条件时，从待巡逻区域中选取起始子区域连接口，以该起始子区域连接口的指向信息依次确定下一子区域连接口，获得各子区域连接口的排序信息，其中保证各子区域连接口为非终点时，被经过的次数等于各子区域连接口指向的区域连接口的数量，进而根据排序信息生成巡逻路线。进一步地，服务器120可以将巡逻路线发送至终端110，以实现根据终端110接收到的巡逻路线进行巡逻。其中，终端110具体可以是安装在用于巡逻的车辆上的车载终端。服务器120可以用独立的服务器或者是多个服务器组成的服务器集群来实现，在一些实施例中，服务器120以云服务器的方式实现。
如图2所示，在一个实施例中，提供了一种巡逻路线确定方法。本实施例主要以该方法应用于上述图1中的服务器120来举例说明。参照图2，该巡逻路线确定方法具体包括步骤s210至步骤s240。
步骤s210，获取待巡逻区域中的各子区域连接口之间的指向信息。
其中，待巡逻区域是指需要巡逻的区域；本实施例中，待巡逻区域包括多个子区域，各子区域之间的连接部分在本实施例中记为子区域连接口，两两子区域连接口之间的连接存在方向，在本实施例中记为子区域连接口之间的指向信息，如两个子区域连接口a和b，a和b之间的指向信息可能是a指向b，也可有可能是b指向a，或者也可以是a可以指向b，b也可以指向a；获取各子区域连接口之间的方向信息即获取待巡逻区域中每一子区域连接口与其它子区域连接口之间的指向信息，具体地，是指获取每一子区域连接口跟与其关联的子区域连接口(包括各子区域连接口所指向的子区域连接口和指向各区域连接口的子区域连接口)之间的指向信息。
在一个实施例中，待巡逻区域中的子区域为待巡逻的道路，子区域连接口为道路之间的连接口，在本实施例中，待巡逻区域中的区域子连接口之间的指向信息表示的是道路的方向，如道路连接口a指向道路连接口b，表示的是道路连接口a与道路连接口b之间的道路方向是由a向b的；进一步地，在一个实施例中，如果道路按照交通规定是单向行驶，那么该道路两端的道路连接口之间的指向信息为单向的；如果道路按照交通规定是双向行驶，那么该道路两端的道路连接口之间的指向信息为双向的。如图3所示为一个具体实施例中子区域连接口之间的指向信息的示意图；图3所示的子区域连接口中，由于两条道路均为单向行驶的，车辆在其中任意一条道路的各不同车道之间是可以变道的，而在两条不同向的道路之间是无法变道的，因此在本实施例中可以将两条不同向的道路记为两个子区域，而每一条道路中同向的不同车道记为同一子区域，每个子区域包括两个子区域连接口。可以理解地，在其它实施例中，待巡逻区域也可以是其它区域，如有必要，将待巡逻区域中根据一定预设规则划分为多个子区域，将子区域之间的连接位置即对应其中的子区域连接口。
在一个实施例中，从云端或者其他渠道获取待巡逻区域的各子区域连接口之间的指向信息。
步骤s220，当根据各子区域连接口之间的指向信息确定待巡逻区域满足预设欧拉区域判断条件时，选取待巡逻区域中一个子区域连接口作为起始子区域连接口。
如果图g中的一个路径包括每个边恰好一次，则该路径称为欧拉路径；其中欧拉路径包括两种情形：欧拉通路和欧拉回路；在本实施例中如果待巡逻区域中的每一个子区域在均被巡逻到的同时保证每一个子区域仅被巡逻一次，那么可以判定该待巡逻区域满足预设欧拉区域判断条件。其中，如果每一个子区域在均被巡逻到的同时保证每一个子区域仅被巡逻一次，在巡逻结束时用于巡逻的车辆没有回到巡逻起始点，那么该待巡逻区域可以称为欧拉通路区域；如果每一个子区域在均被巡逻到的同时保证每一个子区域仅被巡逻一次，且用于巡逻的车辆在巡逻结束时回到了巡逻起始点，那么可以将该待巡逻区域记为欧拉回路区域。如图4所示为一个具体实施例中欧拉回路区域的示意图，图示实施例中由子区域连接口①到子区域连接口②再到子区域连接口③，回到子区域连接口①，且三个子区域均仅被巡逻一次；因此可以将这一区域称为欧拉回路区域,；其中，箭头的方向表示该子区域的两个子区域连接口之间的指向性。
其中，起始子区域连接口是指对待巡逻区域巡逻开始的位置，在一个实施例中，待巡逻区域从哪里开始巡逻可能是已经被设置好的，本实施例中可以获取预设起始位置，确定为起始子区域连接口。其中，预设欧拉区域判断条件是根据实际情况预先设置的。
步骤s230，根据指向信息从起始子区域连接口开始依次确定下一子区域连接口，直至终点子区域连接口，获得各子区域连接口的排序信息；其中，非终点的各子区域连接口被经过的次数等于各子区域连接口所指向的子区域连接口的数量。
其中，当前在某一子区域连接口时，根据该子区域连接口的指向信息确定下一子区域连接口包括：在该子区域连接口所指向的子区域连接口中选取一个作为下一子区域连接口，该下一子区域连接口需满足上述条件。
在确定需满足最短路径的巡逻路线时，可以依次确定巡逻的子区域连接口的顺序，本实施例中首先选定一个子区域连接口作为起始巡逻点，记为起始子区域连接口；根据该起始子区域连接口的指向信息来确定第二个需要巡逻的子区域连接口，然后根据第二个子区域连接口的指向信息确定第三个需要巡逻的子区域连接口，直至待巡逻区域中的最后一个子区域连接口。其中在本实施例中，选取非终点的子区域连接口(包括起始子区域连接口以及终点之前的所有子区域连接)时，需要满足当前子区域连接口被经过的次数等于各子区域连接口的指出子区域连接口数量的条件；也就是说如果选取的任意一个非终点子区域连接口x时，如果会使得该子区域连接口x及其后的任一子区域连接口被经过的次数大于其子区域连接口的指出子区域连接口数量时，那么该非终点子区域连接口x不能在这一顺序位置被选取。进一步地，判断当前子区域连接口被经过的次数是否等于各子区域连接口的指出子区域连接口数量的条件，可以采用例如枚举法等方法实现。
在另一实施例中，起始子区域连接口和/或终点子区域连接口均可以被指定，可以理解地，在本实施例中，在确定巡逻路线时需以已预先确定的子区域连接口来确定巡逻路线。在实际情况中，有时对于待巡逻区域有需要指定巡逻车的起点和/或终点，因此在确定巡逻路线时根据已指定的起点和/或终点确定。
步骤s240，根据各子区域连接口的排序信息生成待巡逻区域的巡逻路线。
在步骤s220和步骤s230中已经选定了待巡逻区域的各个子区域连接口被经过的顺序，根据该顺序即可得到巡逻路线；进一步地，当按照该巡逻路线巡逻该待巡逻区域时，可以保证其中的任意一个子区域被巡逻到、且仅被巡逻一次，实现最短路径巡逻。
上述巡逻路线确定方法，在对待巡逻区域进行巡逻之前，获取待巡逻区域中各子区域连接口之间的指向信息，当根据各子区域连接口的指向信息确定待巡逻区域满足预设的欧拉区域判断条件时，从待巡逻区域中选取起始子区域连接口，以该起始子区域连接口的指向信息依次确定下一子区域连接口，获得各子区域连接口的排序信息，其中保证各子区域连接口为非终点时，被经过的次数等于各子区域连接口指向的区域连接口的数量，进而根据排序信息生成巡逻路线。由于在根据各子区域连接口的指向信息确定待巡逻区域满足欧拉区域的判断条件，表示该待巡逻区域是可以以最短路径完成巡逻的，因此依次选取子区域连接口，并使其中非终点的子区域连接口被经过的次数等于其所指向的子区域连接口数量，如此获得排序信息生成的巡逻路线可以保证该待巡逻区域以最短路径实现巡逻。
进一步地，在一个实施例中，上述巡逻路线确定方法还包括步骤：根据指向信息，确定各子区域连接口所指出的指出子区域连接口数量以及指入各子区域连接口的指入子区域连接口数量，其中，在确定各子区域连接口的指出子区域连接口数量和指入子区域连接口数量时，子区域连接口不被重复计入。
其中，子区域连接口指出的区域连接口也就是该子区域连接口所指向的子区域连接口，指入子区域连接口的区域连接口也就是指向该子区域连接口的子区域连接口，例如子区域连接口a指向子区域连接口包括b、c和d，指向该子区域连接口a的子区域连接口包括e和f，则a的指出子区域连接口数量为3，a的指入子区域连接口数量为2。在一个实施例中，子区域连接口a所指向的子区域连接口也可能包括子区域连接口a本身，在实际情况中以道路连接口为例，可能存在以道路连接口开始并以该道路连接口结束的环形道路，此时称道路连接口指向该道路连接口本身。
每一子区域连接口的指出子区域连接口数量和指入子区域连接口数量中子区域连接口不重复，表示的是在对子区域连接口a的指出子区域连接口和指入子区域连接口进行计数时，如果子区域连接口b已经被计入子区域连接口a的指出子区域连接口数量中，那么将不会再被计入子区域连接口a的指入子区域连接口数量中；也即是说，当两个子区域连接口之间的指向信息为双向指向时，在确定其中一个子区域连接口的指出子区域连接口数量和指入子区域连接口数量时，另一子区域连接口仅会被计入一次。进一步地，每一子区域连接口的指出子区域连接口数量和指入子区域连接口数量中子区域连接口不重复这一条件，仅在一次确定各子区域连接口的指出子区域连接口数量和指入子区域连接口数量时体现；例如，假设子区域连接口a指向子区域连接口包括b、c和d，指向该子区域连接口a的子区域连接口包括d、e和f，则a的指出子区域连接口数量和指入子区域连接口数量可能包括两种情况：第一种，a的指出子区域连接口数量为3(b、c和d)，a的指入子区域连接口数量为2(e和f)；第二种，a的指出子区域连接口数量为2(b和c)，a的指入子区域连接口的数量为3(d、e和f)。
进一步地，在本实施例中，根据各子区域连接口之间的指向信息确定待巡逻区域满足预设欧拉区域判断条件包括：根据各子区域连接口的指出子区域连接口数量和指入子区域连接口数量确定待巡逻区域满足预设欧拉区域判断条件。
在本实施例中，根据各子区域连接口的指出子区域连接口数量和指入子区域连接口数量来判断待巡逻区域是否符合预设欧拉区域的判断条件；在其中一个实施例中，当各子区域连接口的指出子区域连接口数量和指入子区域连接口数量均相等，或者，当待巡逻区域中除去两个子区域连接口以外的所有子区域连接口的指出子区域连接口数量和指入子区域连接口数量均相等、且该两个子区域连接口各自的指出子区域连接口数量和指入子区域连接口数量的数值的差值均满足预设差值条件时，判定待巡逻区域满足预设欧拉区域判断条件。
其中，根据各子区域连接口的指出子区域连接口数量和指入子区域连接口数量确定待巡逻区域满足预设欧拉区域判断条件时，需分别确定各子区域连接口的指出子区域连接口数量和指入区域连接口数量是否满足条件，具体需要分别判断各子区域连接口的指出子区域连接口数量和指入子区域连接口数量是否相等或者差值满足预设差值条件。
在一个实施例中，当待巡逻区域中任意一个子区域连接口均满足指出子区域连接口数量和指入子区域连接口数量相等时，判定待巡逻区域满足预设欧拉区域判断条件；进一步地，本实施例中巡逻区域为欧拉回路区域。
在另一个实施例中，当待巡逻区域中除去两个子区域连接口以外的所有子区域连接口的指出子区域连接口数量和指入子区域连接口数量均相等，且该两个子区域连接口的所述指出子区域连接口数量和指入子区域连接口数量的数值差值满足预设差值条件时；即，当且仅当待巡逻区域中有两个子区域连接口的指出子区域连接口数量和指入子区域连接口数量的差值满足预设差值条件，而其余所有的子区域连接口的指出子区域连接口数量和指入子区域连接口数量相等时，同样判定待巡逻区域满足预设欧拉区域判断条件；进一步地，本实施例中待巡逻区域不是欧拉回路区域但是欧拉通路区域。
在一个具体实施例中，其中的预设差值条件为不满足相等的两个子区域连接口，其中一个子区域连接口的指出子区域连接口数量比指入子区域连接口数量多1，而另一个子区域连接口的指入子区域连接口数量比指出子区域连接口数量多1。
需要说明的是，由于在确定各子区域连接口的指出子区域连接口数量和指入子区域连接口数量时，为了满足子区域连接口不重复计入的条件，各子区域连接口的指出子区域连接口数量和指入子区域连接口数量可能存在不同情形，在根据各子区域连接口的指出子区域连接口数量和指入子区域连接口数量判断待巡逻区域是否满足预设欧拉区域判断条件时，需对于其中的每一种情形分别进行判断。进一步地，在确定待巡逻区域满足预设欧拉区域的条件时，即表示待巡逻区域是存在至少一条巡逻路线可以在完成巡逻的同时实现最短路径巡逻。
进一步地，上述实施例中对于一个待巡逻区域在最理想的情况下仅确定一条巡逻路线，即仅通过一台巡逻车辆对该待巡逻区域进行巡逻。实际情况中，可能对于待巡逻区域安排了多台巡逻车辆进行巡逻可以提高效率，因此需要对待巡逻区域进行子区域的划分，划分子区域的最大数量受到总的最大巡逻次数限制，具体划分方法可以参考下面的实施例。
在一个实施例中，如图5所示，上述巡逻路线确定方法还包括步骤s510和步骤s520。
步骤s510，当根据各子区域连接口之间的指向信息确定待巡逻区域不满足预设欧拉区域判断条件时，将待巡逻区域划分成至少两个均满足预设欧拉区域判断条件的待巡逻子区域。
在上面的实施例中已经详细介绍了当待巡逻区域满足预设欧拉区域判断条件的情形，但是在实际情况中，待巡逻区域可能不满足预设欧拉区域判断条件，则可以采用本实施例中的方法实现巡逻路线的确定。
具体在待巡逻区域不满足预设欧拉判断条件时，将待巡逻区域划分为多个待巡逻子区域，需要说明的是，这里划分得到的每一个待巡逻子区域中仍可以包括多个子区域。在一个实施例中，在划分待巡逻子区域时，需要考虑到实际情况中可以允许巡逻的最大巡逻次数，如果对于运行巡逻的最大巡逻次数有限制时，划分的待巡逻子区域的个数应当小于或者等于最大巡逻次数。其中，最大巡逻次数可以根据是情况进行确定，如当前仅有一台巡逻车，受到巡逻车的能量等限制，巡逻车存在最大使用次数，此时该最大使用次数即为最大巡逻次数；又如当前有一定数量的巡逻车可以用于巡逻，而受到每一巡逻车的最大使用次数，或者预设的最高巡逻时间的限制时，可以根据上述现实条件确定最大巡逻次数。
在一个实施例中，如图6所示，将待巡逻区域划分成至少两个均满足预设欧拉区域判断条件的待巡逻子区域包括：
步骤s610，将待巡逻区域划分成两个或两个以上模拟待巡逻子区域。
其中，划分模拟待巡逻子区域的数目可以根据实际情况进行设置，在一个实施例中，模拟待巡逻子区域的数目小于预设最大巡逻次数；当对于巡逻待巡逻区域预先设置了最大巡逻次数，则划分得到的模拟待巡逻子区域不得超过这一预设最大巡逻次数。其中，预设最大巡逻次数根据实际情况进行设置。
步骤s620，当根据各模拟待巡逻子区域中的各子区域连接口的指向信息，确定各模拟待巡逻子区域均满足预设欧拉区域判断条件时，将模拟待巡逻子区域确定为所述待巡逻子区域。
进一步地，根据各模拟待巡逻子区域中的各子区域连接口的指向信息，确定各模拟待巡逻子区域是否满足预设欧拉区域判断条件具体包括：根据各模拟待巡逻子区域中各子区域连接口的指出子区域连接口数量和指入子区域连接口数量确定各模拟待巡逻子区域是否满足预设欧拉区域判断条件。具体判断方法可以与上述实施例中对待巡逻区域进行判断的方式相同，在此不再赘述。
步骤s630，当根据各模拟待巡逻子区域中的各子区域连接口的指向信息，确定存在不满足预设欧拉区域判断条件的模拟待巡逻子区域时，返回将待巡逻区域划分成两个或两个以上模拟待巡逻子区域的步骤。
若能将待巡逻区域划分成多个均满足预设欧拉区域判断条件的模拟待巡逻子区域，则将模拟待巡逻子区域作为待巡逻子区域；若此次划分的模拟待巡逻子区域中存在不满足预设欧拉区域判断条件的模拟待巡逻子区域时，可以返回重新划分模拟待巡逻子区域。
在存在多台巡逻车用于巡逻的一个实施例中，上述方法还包括：获取巡逻车的数目，以及各巡逻车的最大使用次数，确定最大巡逻次数。进一步地，在本实施例中如需将待巡逻区域划分为多个待巡逻子区域时，需满足待巡逻子区域的数量不超过最大巡逻次数的条件。
步骤s520，分别确定各待巡逻子区域对应的巡逻子路线。
进一步地，将待巡逻区域划分成多个均满足预设欧拉区域判断条件的待巡逻子区域之后，对各待巡逻子区域分别确定巡逻子路线；进一步地，可以通过多台巡逻车分别按照各巡逻子路线巡逻，或者通过一台巡逻车按照各巡逻子路线分多次完成各待巡逻子区域的巡逻，仍然可以保证巡逻路线能使总的巡逻路径最短。其中，确定各待巡逻子区域的巡逻子路线的方式，与如图2所示的实施例中确定待巡逻区域的方式相同，确定的各巡逻子路线需使各待巡逻子区域中的各个子区域被巡逻到、且仅被巡逻一次。
在另一个实施例中，请继续参照图5，上述巡逻路线确定方法还包括步骤s530和步骤s540。
步骤s530，当无法将待巡逻区域划分成均满足预设欧拉区域判断条件的待巡逻子区域时，将待巡逻区域划分为满足预设欧拉区域判断条件的第一类待巡逻子区域和不满足预设欧拉区域判断条件的第二类待巡逻子区域，使第一类待巡逻子区域的数量最大化。
在上一实施例中如果可以将待巡逻区域刚好划分为多个均满足预设欧拉区域判断条件的待巡逻子区域，而当无论如何划分均无法使待巡逻区域划分获得的待巡逻子区域均满足预设欧拉区域判断条件时，即表示待巡逻区域无法满足各子区域被巡逻到且仅被巡逻一次，此时需确定一种巡逻路线尽量使巡逻该待巡逻区域时巡逻车的巡逻路线最短。在本实施例中，当待巡逻区域无法满足条件时，将其划分为满足预设欧拉区域判断条件的第一类待巡逻子区域和不满足预设欧拉区域判断条件的第二类待巡逻子区域，可以理解地，这里的第二类待巡逻子区域的数目大于或者等于1，进一步地，由于需要尽量使待巡逻区域在巡逻时巡逻路线最短，因此在将待巡逻区域划分成第一类待巡逻子区域和第二类待巡逻子区域时，使第一类待巡逻子区域的数量最大化；具体保证第一类待巡逻子区域的数量最大化可以通过例如枚举法等任意一种方式实现。
步骤s540，分别确定各第一类待巡逻子区域对应的第一巡逻子路线；第一巡逻子路线中非终点的各子区域连接口被经过的次数等于各子区域连接口的指出子区域连接口数量；分别确定各第二类待巡逻子区域中使第二类待巡逻子区域满足最短巡逻路径的第二巡逻子路线。
在将待巡逻区域划分为第一类待巡逻子区域和第二类待巡逻子区域之后，分别对各待巡逻子区域进行巡逻子路线的确定；其中对于满足预设欧拉判断条件的第一类待巡逻子区域，对应的巡逻子路线的确定可以参照上述实施例中描述的方法进行确定，需要保证第一类待巡逻子区域对应的第一巡逻子路线使第一类待巡逻子区域中的各子区域被巡逻且仅被巡逻一次；对于不满足预设欧拉区域判断条件的第二类待巡逻子区域对应的巡逻子路线的确定，尽量使对应的第二类待巡逻子区域的巡逻路线最短；其中，保证第二类待巡逻子区域满足最短巡逻路径的方法可以是任意一种；如此获得的各第一类待巡逻子区域对应的巡逻子路线和各第二类待巡逻子区域对应的巡逻子路线，可以使待巡逻区域在巡逻时总的巡逻路径仍保持在最小。
上述实施例中，当待巡逻区域不满足预设欧拉区域判断条件时，对待巡逻区域按照一定的限制进行划分获得待巡逻子区域，分别确定各待巡逻子区域对应的巡逻子路线，如此可仍可以保证待巡逻区域在巡逻时总的巡逻路线最短。
进一步地，在一个实施例中，上述方法还包括：控制巡逻车按照巡逻路线进行巡逻。当在按照上述方法确定待巡逻区域的巡逻路线之后，按照巡逻路线巡逻待巡逻区域，可以保证巡逻车的巡逻路径最小，具体可以是控制智能巡逻车按照巡逻路线进行巡逻。
在一个具体实施例中，以上述巡逻路线确定方法应用于巡逻道路为例，本实施例中待巡逻区域中包括多条道路，子区域连接口为道路连接口，将同向道路的不同车道设定为同一子区域，两个路口之间的不同向道路设定为不同子区域。如图7所示本实施例中的巡逻路线确定方法包括以下步骤。
从云端或者其他渠道获取待巡逻区域中各子区域连接口的数量，记为n，并分别用v1，v2，...，vn表示。
针对子区域连接口v1，v2，...，vn，从云端或者其他渠道获取分别指向各子区域连接口v1，v2，...，vn的子区域连接口(包括该子区域连接口本身)的数量，分别记为i1，i2，...，in。
针对子区域连接口v1，v2，...，vn，从云端或者其他渠道获取子区域连接口v1，v2，...，vn分别指向的子区域连接口的(包括该子区域连接口本身)的数量，分别记为j1，j2，...，jn；
其中，对于子区域两端的区域连接口a和b，如果在巡逻该区域时既可以从子区域连接口a开始巡逻到子区域连接口b终止，也可以从子区域连接口b开始巡逻到子区域连接口a终止，那么既可以认为“子区域连接口a指向子区域连接口b，也可以认为子区域连接口b指向子区域连接口a”；本实施例中，在子区域连接口a的一次计数情形中，该子区域连接口b在in和jn中仅记一次。
针对任意的子区域连接口vk，k∈{1，2，...，n}vk，k∈{1，2，...，n}：
①如果指向它的子区域连接口(包括子区域连接口本身)的数量等于它指向的子区域连接口的数量(条件一)，判定待巡逻区域是欧拉回路区域(当然也是欧拉通路区域)；
②如果并不是所有的子区域连接口都满足条件一，但是当且仅当有两个子区域连接口(记它们分别为vp，vq，p，q∈{1，2，...，n})不满足条件一时，那么判断指向它们各自的子区域连接口的数量是否比它们各自指向的子区域连接口的数量多1或者少1，如果是，判定待巡逻区域是欧拉通路区域；当满足①或者②时，待巡逻区域均可判定为满足预设欧拉区域判断条件；
③如果①与②都不成立，判定待巡逻区域不是欧拉巡逻区域。此时可以通过以下方法对待巡逻区域进行划分之后再确定巡逻路线。
将该待巡逻区域划分成数量不超过最大巡逻次数的两个或者两个以上待巡逻子区域，然后判断每一个待巡逻子区域是否是欧拉区域，如果是，分别确定各待巡逻子区域对应的巡逻子路线，让巡逻车按照巡逻子路线在每一个子区域进行巡逻；这样也能在保证智能巡逻车在巡逻完所有区域的同时最小化巡逻路径。如果无法使得待巡逻区域的每一个子区域都是欧拉区域，在对其进行区域划分的时候应最大化其子区域是欧拉区域的待巡逻子区域数量(可以采用枚举法即可)；进一步分别确定各待巡逻子区域对应的巡逻子路线，其中满足欧拉区域的待巡逻子区域(上述第一类待巡逻子区域)对应的巡逻子路线使该待巡逻子区域中的各子区域被巡逻且仅被巡逻一次，而其中不满足欧拉区域的待巡逻子区域(上述第二类待巡逻子区域)对应的巡逻子路线应使该待巡逻子区域巡逻的路径最短。其中，最大巡逻次数的确定方式：假设一共有n辆巡逻车，分别编号为1,2,…,n，每一辆巡逻车的最大可重复巡逻次数记为r1,r2,…,rn，最大巡逻次数为r1 r2 … rn。进一步地，其中每一辆巡逻车的最大可重复巡逻次数可以是根据巡逻车的剩余能量、使用寿命等情况确定。
进一步地，在一个具体实施例中，如图8所示，为将上述方法应用于道路巡逻时的应用场景示意图，其中车辆可以是巡逻车辆或者普通车辆，车辆中包含路测感知单元，在云平台中部署了计算模块，路测感知单元与云平台之间通过网络连接；其中，云平台中的计算模块可以采用python(一种跨平台的计算机程序设计语言。是一种面向对象的动态类型语言)编写，它通过路测感知单元等获取待巡逻区域的子区域连接口之间的指向信息。进一步地，车辆中还可以采用车载单元，若车辆中安装有车载单元，云平台可以从智能巡逻车或者其他车辆获取待巡逻区域的信息；需要说明的是，如果车辆中安装有车载单元，那么路测感知单元与车载单元一一配对的。云平台的计算模块根据获取的待巡逻区域的各子区域连接口之间的指向信息判断待巡逻区域是否为欧拉区域，或者是否可以划分为多个欧拉区域的待巡逻子区域，并确定使巡逻待巡逻区域的巡逻路径最短的巡逻路线；进一步地，可以将巡逻路线返回至车辆中的路测感知单元或者车载单元。
由于欧拉区域中的每一个子区域都可被智能巡逻车巡逻到且每一个子区域都仅被巡逻一次，所以巡逻车在巡逻欧拉巡逻区域时总可在巡逻完所有区域的同时实现最短路径巡逻；而上述巡逻路线确定方法中，优先确定待巡逻区域是否为欧拉区域，若是则确定实现最短巡逻路线的巡逻路线；若待巡逻区域不是欧拉区域，则通过对其进行划分，并取最合适的划分方法，分别确定划分得到的待巡逻子区域对应的巡逻子路线，通过各待巡逻子区域对应的巡逻子路线巡逻也可以尽量使巡逻路径最短。
图2为一个实施例中巡逻路线确定方法的流程示意图。应该理解的是，虽然图2的流程图中的各个步骤按照箭头的指示依次显示，但是这些步骤并不是必然按照箭头指示的顺序依次执行。除非本文中有明确的说明，这些步骤的执行并没有严格的顺序限制，这些步骤可以以其它的顺序执行。而且，图2中的至少一部分步骤可以包括多个子步骤或者多个阶段，这些子步骤或者阶段并不必然是在同一时刻执行完成，而是可以在不同的时刻执行，这些子步骤或者阶段的执行顺序也不必然是依次进行，而是可以与其它步骤或者其它步骤的子步骤或者阶段的至少一部分轮流或者交替地执行。
在本申请的一个实施例中，还提供一种巡逻路线确定装置，如图9所示，该装置包括：指向信息获取模块910、起始子区域连接口选取模块920、排序信息确定模块930和巡逻路线生成模块940。其中：
指向信息获取模块910，用于获取待巡逻区域中的各子区域连接口之间的指向信息；
起始子区域连接口选取模块920，用于当根据各子区域连接口之间的指向信息确定待巡逻区域满足预设欧拉区域判断条件时，选取待巡逻区域中一个子区域连接口作为起始子区域连接口；
排序信息确定模块930，用于根据指向信息从起始子区域连接口开始依次确定下一子区域连接口，直至终点子区域连接口，获得各子区域连接口的排序信息；其中，非终点的各子区域连接口被经过的次数等于各子区域连接口所指向的子区域连接口的数量；
巡逻路线生成模块940，用于根据各子区域连接口的排序信息生成待巡逻区域的巡逻路线。
上述巡逻路线确定装置，在对待巡逻区域进行巡逻之前，获取待巡逻区域中各子区域连接口之间的指向信息，当根据各子区域连接口的指向信息确定待巡逻区域满足预设的欧拉区域判断条件时，从待巡逻区域中选取起始子区域连接口，以该起始子区域连接口的指向信息依次确定下一子区域连接口，获得各子区域连接口的排序信息，其中保证各子区域连接口为非终点时，被经过的次数等于各子区域连接口指向的区域连接口的数量，进而根据排序信息生成巡逻路线。由于在根据各子区域连接口的指向信息确定待巡逻区域满足欧拉区域的判断条件，表示该待巡逻区域是可以以最短路径完成巡逻的，因此依次选取子区域连接口，并使其中非终点的子区域连接口被经过的次数等于其所指向的子区域连接口数量，如此获得排序信息生成的巡逻路线可以保证该待巡逻区域以最短路径实现巡逻。
在一个实施例中，上述巡逻路线确定装置中还包括待巡逻子区域划分模块，用于当根据各子区域连接口之间的指向信息确定待巡逻区域不满足预设欧拉区域判断条件时，将待巡逻区域划分成至少两个均满足预设欧拉区域判断条件的待巡逻子区域；本实施例中的巡逻路线生成模块，还用于分别确定各所述待巡逻子区域对应的巡逻子路线。
在一个实施例中，上述巡逻路线确定装置中的待巡逻子区域划分模块具体用于将所述待巡逻区域划分成两个或两个以上模拟待巡逻子区域；当根据各模拟待巡逻子区域中的各子区域连接口的指向信息，确定各模拟待巡逻子区域均满足预设欧拉区域判断条件时，将模拟待巡逻子区域确定为待巡逻子区域；当根据各模拟待巡逻子区域中的各子区域连接口的指向信息，确定存在不满足预设欧拉区域判断条件的模拟待巡逻子区域时，返回将所述待巡逻区域划分成两个或两个以上模拟待巡逻子区域的步骤。
在一个实施例中，上述巡逻路线确定装置中的待巡逻子区域划分模块，还用于当无法将待巡逻区域划分成均满足预设欧拉区域判断条件的待巡逻子区域时，将待巡逻区域划分为满足预设欧拉区域判断条件的第一类待巡逻子区域和不满足预设欧拉区域判断条件的第二类待巡逻子区域，使第一类待巡逻子区域的数量最大化；在本实施例中的巡逻路线生成模块，还用于分别确定各第一类待巡逻子区域对应的第一巡逻子路线；第一巡逻子路线中非终点的各子区域连接口被经过的次数等于各子区域连接口的指出子区域连接口数量；以及分别确定各第二类待巡逻子区域中使第二类待巡逻子区域满足最短巡逻路径的第二巡逻子路线。
在一个实施例中，待巡逻子区域的数目小于预设最大巡逻次数。
在一个实施例中，上述装置还包括：子区域连接口数量确定模块，用于根据指向信息，确定各子区域连接口所指出的指出子区域连接口数量以及指入各子区域连接口的指入子区域连接口数量，在确定各子区域连接口的指出子区域连接口数量和指入子区域连接口数量时，子区域连接口不被重复计入；在本实施例中，根据各子区域连接口的指出子区域连接口数量和指入子区域连接口数量确定待巡逻区域满足预设欧拉区域判断条件。
在一个实施例中，当各子区域连接口的指出子区域连接口数量和指入子区域连接口数量均相等，或者，当待巡逻区域中除去两个子区域连接口以外的所有子区域连接口的指出子区域连接口数量和指入子区域连接口数量均相等、且两个子区域连接口各自的指出子区域连接口数量和指入子区域连接口数量的数值的差值均满足预设差值条件时，判定待巡逻区域满足预设欧拉区域判断条件。
图10示出了一个实施例中计算机设备的内部结构图。该计算机设备具体可以是图1中的服务器120。如图10所示，该计算机设备包括该计算机设备包括通过系统总线连接的处理器、存储器、网络接口、输入装置和显示屏。其中，存储器包括非易失性存储介质和内存储器。该计算机设备的非易失性存储介质存储有操作系统，还可存储有计算机程序，该计算机程序被处理器执行时，可使得处理器实现巡逻路线确定方法。该内存储器中也可储存有计算机程序，该计算机程序被处理器执行时，可使得处理器执行巡逻路线确定方法。计算机设备的显示屏可以是液晶显示屏或者电子墨水显示屏，计算机设备的输入装置可以是显示屏上覆盖的触摸层，也可以是计算机设备外壳上设置的按键、轨迹球或触控板，还可以是外接的键盘、触控板或鼠标等。
本领域技术人员可以理解，图10中示出的结构，仅仅是与本申请方案相关的部分结构的框图，并不构成对本申请方案所应用于其上的计算机设备的限定，具体的计算机设备可以包括比图中所示更多或更少的部件，或者组合某些部件，或者具有不同的部件布置。
在一个实施例中，本申请提供的巡逻路线确定装置可以实现为一种计算机程序的形式，计算机程序可在如图10所示的计算机设备上运行。计算机设备的存储器中可存储组成该巡逻路线确定装置的各个程序模块，比如，图9所示的指向信息获取模块、起始子区域连接口选取模块、排序信息确定模块和巡逻路线生成模块。各个程序模块构成的计算机程序使得处理器执行本说明书中描述的本申请各个实施例的巡逻路线确定方法中的步骤。
例如，图10所示的计算机设备可以通过如图9所示的巡逻路线确定装置中的指向信息获取模块获取待巡逻区域中的各子区域连接口之间的指向信息。计算机设备可通过指向信息获取模块获取待巡逻区域中的各子区域连接口之间的指向信息。计算机设备可通过起始子区域连接口选取模块当根据各子区域连接口之间的指向信息确定待巡逻区域满足预设欧拉区域判断条件时，选取待巡逻区域中一个子区域连接口作为起始子区域连接口。计算机设备可通过排序信息确定模块根据指向信息从起始子区域连接口开始依次确定下一子区域连接口，直至终点子区域连接口，获得各子区域连接口的排序信息；其中，非终点的各子区域连接口被经过的次数等于各子区域连接口所指向的子区域连接口的数量。计算机设备可通过巡逻路线生成模块根据各子区域连接口的排序信息生成待巡逻区域的巡逻路线。
在一个实施例中，提供了一种计算机设备，包括存储器和处理器，存储器存储有计算机程序，计算机程序被处理器执行时，使得处理器执行上述巡逻路线确定方法的步骤。此处巡逻路线确定方法的步骤可以是上述各个实施例的巡逻路线确定方法中的步骤。
在一个实施例中，提供了一种计算机可读存储介质，存储有计算机程序，计算机程序被处理器执行时，使得处理器执行上述巡逻路线确定方法的步骤。此处巡逻路线确定方法的步骤可以是上述各个实施例的巡逻路线确定方法中的步骤。
本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于一非易失性计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，本申请所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。非易失性存储器可包括只读存储器(rom)、可编程rom(prom)、电可编程rom(eprom)、电可擦除可编程rom(eeprom)或闪存。易失性存储器可包括随机存取存储器(ram)或者外部高速缓冲存储器。作为说明而非局限，ram以多种形式可得，诸如静态ram(sram)、动态ram(dram)、同步dram(sdram)、双数据率sdram(ddrsdram)、增强型sdram(esdram)、同步链路(synchlink)dram(sldram)、存储器总线(rambus)直接ram(rdram)、直接存储器总线动态ram(drdram)、以及存储器总线动态ram(rdram)等。
以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。
以上所述实施例仅表达了本申请的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对本申请专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本申请构思的前提下，还可以做出若干变形和改进，这些都属于本申请的保护范围。因此，本申请专利的保护范围应以所附权利要求为准。
1.一种巡逻路线确定方法，包括：
获取待巡逻区域中的各子区域连接口之间的指向信息；
当根据所述各子区域连接口之间的指向信息确定所述待巡逻区域满足预设欧拉区域判断条件时，选取所述待巡逻区域中一个子区域连接口作为起始子区域连接口；
根据所述指向信息从所述起始子区域连接口开始依次确定下一子区域连接口，直至终点子区域连接口，获得各子区域连接口的排序信息；其中，非终点的各所述子区域连接口被经过的次数等于各所述子区域连接口所指向的子区域连接口的数量；
根据所述各子区域连接口的排序信息生成所述待巡逻区域的巡逻路线。
2.根据权利要求1所述的方法，其特征在于，所述方法还包括：
当根据所述各子区域连接口之间的指向信息确定所述待巡逻区域不满足预设欧拉区域判断条件时，将所述待巡逻区域划分成至少两个均满足预设欧拉区域判断条件的待巡逻子区域；
分别确定各所述待巡逻子区域对应的巡逻子路线。
3.根据权利要求2所述的方法，其特征在于，所述将所述待巡逻区域划分成至少两个均满足预设欧拉区域判断条件的待巡逻子区域包括：
将所述待巡逻区域划分成两个或两个以上模拟待巡逻子区域；
当根据各所述模拟待巡逻子区域中的各子区域连接口的指向信息，确定各所述模拟待巡逻子区域均满足预设欧拉区域判断条件时，将所述模拟待巡逻子区域确定为所述待巡逻子区域；
当根据各所述模拟待巡逻子区域中的各子区域连接口的指向信息，确定存在不满足预设欧拉区域判断条件的模拟待巡逻子区域时，返回所述将所述待巡逻区域划分成两个或两个以上模拟待巡逻子区域的步骤。
4.根据权利要求2所述的方法，其特征在于，所述方法还包括：
当无法将待巡逻区域划分成均满足预设欧拉区域判断条件的待巡逻子区域时，将所述待巡逻区域划分为满足预设欧拉区域判断条件的第一类待巡逻子区域和不满足预设欧拉区域判断条件的第二类待巡逻子区域，使所述第一类待巡逻子区域的数量最大化；
分别确定各所述第一类待巡逻子区域对应的第一巡逻子路线；所述第一巡逻子路线中非终点的各所述子区域连接口被经过的次数等于各所述子区域连接口的指出子区域连接口数量；
分别确定各所述第二类待巡逻子区域中使所述第二类待巡逻子区域满足最短巡逻路径的第二巡逻子路线。
5.根据权利要求2所述的方法，其特征在于，所述待巡逻子区域的数目小于预设最大巡逻次数。
6.根据权利要求1所述的方法，其特征在于，所述方法还包括：
根据所述指向信息，确定各子区域连接口所指出的指出子区域连接口数量以及指入所述各子区域连接口的指入子区域连接口数量，在确定所述各子区域连接口的所述指出子区域连接口数量和所述指入子区域连接口数量时，子区域连接口不被重复计入；
根据所述各子区域连接口之间的指向信息确定所述待巡逻区域满足预设欧拉区域判断条件包括：
根据所述各子区域连接口的指出子区域连接口数量和指入子区域连接口数量确定所述待巡逻区域满足预设欧拉区域判断条件。
7.根据权利要求6所述的方法，其特征在于，当所述各子区域连接口的指出子区域连接口数量和指入子区域连接口数量均相等，或者，当所述待巡逻区域中除去两个子区域连接口以外的所有子区域连接口的指出子区域连接口数量和指入子区域连接口数量均相等、且所述两个子区域连接口各自的所述指出子区域连接口数量和指入子区域连接口数量的数值的差值均满足预设差值条件时，判定所述待巡逻区域满足预设欧拉区域判断条件。
8.一种巡逻路线确定装置，其特征在于，所述装置包括：
指向信息获取模块，用于获取待巡逻区域中的各子区域连接口之间的指向信息；
起始子区域连接口选取模块，用于当根据所述各子区域连接口之间的指向信息确定所述待巡逻区域满足预设欧拉区域判断条件时，选取所述待巡逻区域中一个子区域连接口作为起始子区域连接口；
排序信息确定模块，用于根据所述指向信息从所述起始子区域连接口开始依次确定下一子区域连接口，直至终点子区域连接口，获得各子区域连接口的排序信息；其中，非终点的各所述子区域连接口被经过的次数等于各所述子区域连接口所指向的子区域连接口的数量；
巡逻路线生成模块，用于根据所述各子区域连接口的排序信息生成所述待巡逻区域的巡逻路线。
9.一种计算机可读存储介质，存储有计算机程序，所述计算机程序被处理器执行时，使得所述处理器执行如权利要求1至7中任一项所述方法的步骤。
10.一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，所述计算机程序被所述处理器执行时，使得所述处理器执行如权利要求1至7中任一项所述方法的步骤。
技术总结