[go: up one dir, main page]

CN111222667B - 路线规划方法、装置、设备及存储介质 - Google Patents

路线规划方法、装置、设备及存储介质 Download PDF

Info

Publication number
CN111222667B
CN111222667B CN201811422192.XA CN201811422192A CN111222667B CN 111222667 B CN111222667 B CN 111222667B CN 201811422192 A CN201811422192 A CN 201811422192A CN 111222667 B CN111222667 B CN 111222667B
Authority
CN
China
Prior art keywords
route
scenic spot
scenic
tour
total
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201811422192.XA
Other languages
English (en)
Other versions
CN111222667A (zh
Inventor
才鑫
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
China Mobile Communications Group Co Ltd
China Mobile Group Liaoning Co Ltd
Original Assignee
China Mobile Communications Group Co Ltd
China Mobile Group Liaoning Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by China Mobile Communications Group Co Ltd, China Mobile Group Liaoning Co Ltd filed Critical China Mobile Communications Group Co Ltd
Priority to CN201811422192.XA priority Critical patent/CN111222667B/zh
Publication of CN111222667A publication Critical patent/CN111222667A/zh
Application granted granted Critical
Publication of CN111222667B publication Critical patent/CN111222667B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
    • G06Q10/047—Optimisation of routes or paths, e.g. travelling salesman problem
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q50/00—Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism
    • G06Q50/10—Services
    • G06Q50/14—Travel agencies

Landscapes

  • Business, Economics & Management (AREA)
  • Tourism & Hospitality (AREA)
  • Human Resources & Organizations (AREA)
  • Engineering & Computer Science (AREA)
  • Economics (AREA)
  • Strategic Management (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Marketing (AREA)
  • General Business, Economics & Management (AREA)
  • Physics & Mathematics (AREA)
  • Game Theory and Decision Science (AREA)
  • Quality & Reliability (AREA)
  • Operations Research (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Development Economics (AREA)
  • Health & Medical Sciences (AREA)
  • General Health & Medical Sciences (AREA)
  • Primary Health Care (AREA)
  • Navigation (AREA)

Abstract

本发明实施例公开了一种路线规划方法、装置、设备及存储介质。该方法包括：获得用户的起始点位置、终点位置、游览总时长和用户针对每一景点的偏好程度分值；根据偏好程度分值，从当前路线未涵盖的景点中，确定待插入景点和待插入景点的插入位置；计算将待插入景点插入插入位置后的第一目标路线对应的游览时长；若游览时长不大于游览总时长，则将待插入景点插入插入位置；继续插入景点；若游览时长大于游览总时长，将当前路线确定为规划路线。本发明实施例的路线规划方法、装置、设备及存储介质，根据用户针对景点的偏好程度分值，来进行路线规划，能够使规划出的路线满足用户的偏好要求。

Description

路线规划方法、装置、设备及存储介质
技术领域
本发明涉及计算机技术领域，尤其涉及一种路线规划方法、装置、设备及存储介质。
背景技术
定向问题分为传统定向问题和团队定向问题，是一类特殊的非确定性多项式困难(non-deterministic polynomial-hard，NP-hard)路径优化问题，在物流领域、旅游领域非常常见且同时也具有极大的挑战性。
个性化旅游路线求解优化问题可以模拟为带时间窗的定向问题(OrienteeringProblem with Time Windows，OPTW)。
目前，解决OPTW问题主要采用迭代局部搜索(Iterated Local Search，ILS)算法。但是采用ILS算法在规划路线的过程中，可能会排除用户偏好度较高的地点，使得规划出的路线不能满足用户的偏好要求。
发明内容
本发明实施例提供一种路线规划方法、装置、设备及存储介质，能够使规划出的路线满足用户的偏好要求。
一方面，本发明实施例提供了一种路线规划方法，方法包括：
获得用户的起始点位置、终点位置、游览总时长和用户针对每一景点的偏好程度分值；
根据偏好程度分值，从由起始点位置至终点位置的当前路线未涵盖的景点中，确定待插入景点和待插入景点对于当前路线中的插入位置；
计算将待插入景点插入插入位置后的第一目标路线对应的游览时长；
若游览时长不大于游览总时长，则将待插入景点插入插入位置；
返回根据偏好程度分值，从由起始点位置至终点位置的当前路线未涵盖的景点中，确定待插入景点和待插入景点对于当前路线中的插入位置继续执行；
若游览时长大于游览总时长，将当前路线确定为规划路线。
另一方面，本发明实施例提供了一种路径规划装置，装置包括：
获得模块，用于获得用户的起始点位置、终点位置、游览总时长和用户针对每一景点的偏好程度分值；
第一确定模块，用于根据偏好程度分值，从由起始点位置至终点位置的当前路线未涵盖的景点中，确定待插入景点和待插入景点对于当前路线中的插入位置；
计算模块，用于计算将待插入景点插入插入位置后的第一目标路线对应的游览时长；
插入模块，用于若游览时长不大于游览总时长，则将待插入景点插入插入位置；并触发确定模块；
第二确定模块，用于若游览时长大于游览总时长，将当前路线确定为规划路线。
再一方面，本发明实施例提供一种路线规划设备，设备包括：存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序；
处理器执行计算机程序时实现本发明实施例提供的路线规划方法。
再一方面，本发明实施例提供一种计算机可读存储介质，计算机可读存储介质上存储有计算机程序，计算机程序被处理器执行时实现本发明实施例提供的路线规划方法。
本发明实施例的路线规划方法、装置、设备及存储介质，根据用户针对景点的偏好程度分值，来进行路线规划，能够使规划出的路线满足用户的偏好要求。
附图说明
为了更清楚地说明本发明实施例的技术方案，下面将对本发明实施例中所需要使用的附图作简单地介绍，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1示出了现有技术提供的路线规划的结果示意图；
图2示出了本发明实施例提供的路线规划方法的流程示意图；
图3示出了本发明实施例提供的路线规划方法的场景示意图；
图4示出了本发明实施例提供的路线优化的流程示意图；
图5示出了本发明实施例提供的路线规划的结果示意图；
图6示出了本发明实施例规划出的路线的总时长与现有技术规划出的路线的总时长的对比图；
图7示出了本发明实施例规划出路线的耗时时间和现有技术规划出路线的耗时时间的对比图；
图8示出了本发明实施例提供的路线规划装置的结构示意图；
图9示出了能够实现根据本发明实施例的路线规划方法及装置的计算设备的示例性硬件架构的结构图。
具体实施方式
下面将详细描述本发明的各个方面的特征和示例性实施例，为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细描述。应理解，此处所描述的具体实施例仅被配置为解释本发明，并不被配置为限定本发明。对于本领域技术人员来说，本发明可以在不需要这些具体细节中的一些细节的情况下实施。下面对实施例的描述仅仅是为了通过示出本发明的示例来提供对本发明更好的理解。
需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。
图1示出了现有技术提供的路线规划的结果示意图。图1中共有5个景点，5个景点分别为景点1、景点2、景点3、景点4和景点5。景点5为用户偏好程度较高的景点。由图1所示的路线规划的结果示意图中可以看出，利用现有技术规划出的路线并不包括景点5，使得规划出的路线不能满足用户的偏好要求。其中，图1路线规划的结果为：起始点位置—>景点2—>景点4—>景点1—>终点位置。
为了解决现有技术问题，本发明实施例提供了一种路线规划方法、装置、设备及存储介质，来进行路线规划，使规划出的路线满足用户的偏好要求。下面首先对本发明实施例提供的路线规划方法进行详细说明。
图2示出了本发明实施例提供的路线规划方法的流程示意图。路线规划方法可以包括：
S201：获得用户的起始点位置、终点位置、游览总时长和用户针对每一景点的偏好程度分值。
S202：根据偏好程度分值，从由起始点位置至终点位置的当前路线未涵盖的景点中，确定待插入景点和待插入景点对于当前路线中的插入位置。
S203：计算将待插入景点插入插入位置后的第一目标路线对应的游览时长。
S204：若游览时长不大于游览总时长，则将待插入景点插入插入位置，继续执行S202。
S205：若游览时长大于游览总时长，将当前路线确定为规划路线。
示例性的，下面结合具体的路线规划场景对本发明实施例提供的路线规划方法进行说明。
图3示出了本发明实施例提供的路线规划方法的场景示意图。图3所示的场景中包括10个景点，分别为景点1、景点2、……、景点9和景点10。其中，用户针对景点1、景点2、……、景点9和景点10的偏好程度分别可以为：非常想去、比较想去、比较不想去、比较不想去、一定要去、非常不想去、比较想去、非常想去、比较不想去和比较不想去。
其中，偏好程度与偏好程度分值对应关系如表1所示。
表1
偏好程度 偏好程度分值
非常不想去 1
比较不想去 2
比较想去 3
非常想去 4
一定要去 MAX
在本发明的一个实施例中，偏好程度分值MAX远大于其他偏好程度分值，比如，MAX为10000、1000000或20000等等。
相应的，基于表1，用户针对景点1、景点2、……、景点9和景点10的偏好程度分值分别为：4、3、2、2、MAX、1、3、4、2和2。
在本发明的一个实施例中，若用户针对某一景点未设置偏好程度，则可以将用户针对该景点的偏好程度默认为：比较想去。
假设用户设置的游览总时长为160分钟。
开始的路线为由起始点位置直接到达终点位置，即当前路线为：起始点位置—>终点位置。
假设此时根据偏好程度分值，确定出待插入景点为景点5，可以理解的是，当前的插入位置为起始点位置和终点位置之间。计算将景点5插入到起始点位置和终点位置之间后的第一目标路线：起始点位置—>景点5—>终点位置对应的游览时长，假设计算出的游览时长为100分钟，小于用户设置的游览总时长160分钟，则将景点5插入到起始点位置和终点位置之间，此时当前路线为：起始点位置—>景点5—>终点位置对应的游览时长。
基于当前路线：起始点位置—>景点5—>终点位置，再进行景点的插入操作。
假设根据偏好程度分值，确定出待插入景点为景点1，可以理解的是，当前的插入位置可以为起始点位置和景点5之间，还可以为景点5和终点位置之间。
在本发明的一个实施例中，可以将时间消耗最小的那个位置作为景点的插入的最佳插入位置。
示例性的，假设在未插入景点1前，起始点位置至景点5的时间为25分钟，将景点1插入起始点位置和景点5之间后，起始点位置至景点5的时间为50分钟，则时间消耗为50-25＝25分钟。
假设在未插入景点1前，景点5至终点位置的时间为75分钟，将景点1插入景点5和终点位置之间后，景点5至终点位置的时间为85分钟，则时间消耗为85-75＝10分钟。
则将景点5和终点位置之间确定为景点1的最佳插入位置。
计算将景点1插入到景点5和终点位置之间后的第一目标路线：起始点位置—>景点5—>景点1—>终点位置对应的游览时长，计算出的游览时长为110分钟，小于用户设置的游览总时长160分钟，则将景点1插入到景点5和终点位置之间之间，此时当前路线为：起始点位置—>景点5—>景点1—>终点位置。
后续的插入过程与景点1的插入过程相同，具体可参考景点1的插入过程，本发明实施例在此不对其进行赘述。
在本发明的一个实施例中，根据偏好程度分值，从由起始点位置至终点位置的当前路线未涵盖的景点中，确定待插入景点和待插入景点对于当前路线中的插入位置，可以包括：针对从由起始点位置至终点位置的当前路线未涵盖的景点中的每一景点，计算景点插入当前路线中的相邻两个景点的之间对应的时间消耗；根据时间消耗，确定景点的最小插入成本；将最小插入成本对应的相邻两个景点的之间的位置，作为景点的插入位置；针对每一景点，根据偏好程度分值和最小插入成本，计算景点的插入比率；将最高插入比率对应的景点，作为待插入景点。
假设由起始点位置至终点位置的当前路线为：起始点位置—>景点5—>终点位置。
则分别针对当前路线未涵盖的每一景点：针对景点1、景点2、景点3、景点4、景点6、景点7、景点8、景点9和景点10，计算每一景点插入到当前路线中的起始点位置和景点5之间，以及景点5和终点位置之间的时间消耗。根据时间消耗，确定景点的最小插入成本；将最小插入成本对应的相邻两个景点的之间的位置，作为景点的插入位置。
在本发明的一个实施例中，可以将景点对应的最小时间消耗，作为景点的最小插入成本。
示例性的，还以上述景点1为例进行说明。
景点1插入起始点位置和景点5之间对应的时间消耗为25分钟；景点1插入景点5和终点位置之间对应的时间消耗为10分钟。则最小时间消耗为10分钟，则将10分钟确定为景点1的最小插入成本。
在本发明的一个实施例中，根据时间消耗，确定景点的最小插入成本，可以包括：若景点与相邻两个景点中的前一个景点和/或后一个景点位于同一个景点集群，将最小时间消耗与景点集群对应的景点集群参数值的比值，作为景点的最小插入成本；若景点与前一个景点和后一个景点没有位于同一个景点集群，将最小时间消耗，作为景点的最小插入成本。
在本发明的一个实施例中，可以对景点进行聚类，形成多个景点集群。属于同一景点集群的景点之间的距离相对较近。本发明实施例并不对景点聚类的算法进行限定，任何可用的聚类算法均可应用于本发明实施例中，比如K均值(K-means)算法。
本发明实施例提供的最小插入成本公式如下：
若景点与相邻两个景点中的前一个景点和/或后一个景点位于同一个景点集群，
若景点与前一个景点和后一个景点没有位于同一个景点集群，
shiftClusterp＝shiftp (2)
其中，公式(1)和公式(2)中，shiftClusterp为景点P的最小插入成本，shiftp为景点P的最小时间消耗，ClusterParamterP为景点集群参数。其中，ClusterParamterP大于1。
本发明实施例提供的插入比率公式如下：
其中，ratiop为景点P的插入比率，profitp为用户对于景点P的偏好程度分值，shiftClusterp为景点P的最小插入成本。
通过上述公式(1)、(2)和(3)确定待插入景点以及待插入景点的插入位置。
本发明实施例通过对景点进行聚类，在插入景点时，会优先插入位于同一景点集群内的其他景点，能够减少路线在行程上的时间消耗，同时也能够减少用户在景点集群之间的转移次数。
通常情况下，景点有其各自对应的开放时间和关闭时间，即景点对应的时间窗，比如，对于景点1而言，其开放时间为：上午10:00至下午13:00。因此，在本发明的一个实施例中，本发明实施例提供的路线规划方法还可以包括：针对第一目标路线涵盖的每一景点，根据用户浏览景点的时长和起始时间，确定用户针对景点的游览是否满足景点的开放时间和关闭时间的要求；若针对第一目标路线涵盖的每一景点，均确定出用户针对景点的游览满足景点的开放时间和关闭时间的要求，将待插入景点插入插入位置。
示例性的，假设用户从起始点位置的出发时间为上午9:00。当前路线为：起始点位置—>景点5—>终点位置。待插入景点为景点1，待插入位置为：起始点位置和景点5之间。则第一目标路线为：起始点位置—>景点1—>景点5—>终点位置。
由起始点位置到景点1的时长为25分钟，景点1的游览时长为35分钟。由景点1到景点5的时长为35分钟，景点5的游览时长为20分钟。则用户到达景点1的时间为9:25，预计从景点1出发的时间为10:00，用户到达景点5的时间为10:35，从景点5出发的时间为10:50。
假设景点1和景点5的开放时间均为上午9:00，关闭时间均为下午13:00。
针对景点1确定出用户针对景点1的游览满足景点1的开放时间和关闭时间的要求。
针对景点5确定出用户针对景点5的游览满足景点5的开放时间和关闭时间的要求。
则将景点1插入到起始点位置和景点5之间，当前路线为：起始点位置—>景点1—>景点5—>终点位置。
假设景点1的开放时间为上午9:00，关闭时间为上午9:30。景点5的开放时间为上午9:00，关闭时间为下午13:00。
用户预计从景点1出发的时间10:00已超过景点1的关闭时间，则针对景点1确定出用户针对景点1的游览不满足景点1的开放时间和关闭时间的要求。则不插入景点1。
假设景点1的开放时间为上午9:00，关闭时间为下午13:00。景点5的开放时间为上午8:40，关闭时间为上午9:40。
用户预计从景点5出发的时间9:50已超过景点5的关闭时间，则针对景点5确定出用户针对景点5的游览不满足景点5的开放时间和关闭时间的要求。则不插入景点1。
再示例性的，假设景点1的开放时间为上午9:30，关闭时间为上午12:30。景点5的开放时间为上午9:00，关闭时间为下午13:00。
用户到达景点1的时间9:25，未到达景点1的开放时间。此时，用户可以等待5分钟。用户预计从景点1出发的时间变为10:05。用户到达景点5的时间变为10:40，从景点5出发的时间为10:55。
针对景点1确定出用户针对景点1的游览满足景点1的开放时间和关闭时间的要求。
针对景点5确定出用户针对景点5的游览满足景点5的开放时间和关闭时间的要求。
则将景点1插入到起始点位置和景点5之间，当前路线为：起始点位置—>景点1—>景点5—>终点位置。
也就是说，景点插入的条件为：插入景点后的路线的游览总时长小于用户设置的游览总时长，且插入景点后的路线涵盖的各个景点均满足各自开放时间和关闭时间的要求，即用户需在景点关闭时间之前离开。
在本发明的一个实施例中，本发明实施例提供的路线规划方法还可以包括：对规划出的路线进行优化。具体的优化过程如图4所示。图4示出了本发明实施例提供的路线优化的流程示意图。
S401：将规划路线作为中间规划路线。
S402：比较从中间规划路线涵盖的景点中删除预设数量个景点的次数与预设无改进的最大迭代次数。
S403：若次数等于最大迭代次数，将中间规划路线确定为最终规划路线。
S404：若次数小于最大迭代次数，则从中间规划路线涵盖的景点中删除预设数量个景点，得到第二目标路线，并将次数加1。
S405：根据偏好程度分值，从第二目标路线未涵盖的景点中确定待插入景点和待插入景点对于第二目标路线的插入位置。
S406：计算将待插入景点插入插入位置后的第三目标路线对应的游览时长。
S407：若游览时长不大于游览总时长，则将待插入景点插入插入位置，继续执行S405。
S408：若游览时长大于游览总时长，比较当前路线涵盖的景点的第一总偏好程度分值与中间规划路线涵盖的景点的第二总偏好程度分值。若第一总偏好程度分值不大于第二总偏好程度分值，继续执行S402。
S409：若第一总偏好程度分值大于第二总偏好程度分值，则将当前路线作为中间规划路线，并将次数清零；继续执行S402。
S410：若第一总偏好程度分值等于第二总偏好程度分值，比较当前路线对应的第一游览总时长和中间规划路线对应的第二游览总时长。
S411：若第一游览总时长不大于第二游览总时长，则将当前路线作为中间规划路线，并将次数清零；继续执行S402。
S412：若第一游览总时长大于第二游览总时长，继续执行S402。
在本发明的一个实施例中，从中间规划路线涵盖的景点中删除预设数量个景点，可以从中间规划路线涵盖的景点中删除预设数量个连续的景点。此时，可以指定删除景点的起始景点和数量，从所指定的起始景点连续删除景点。
在本发明的一个实施例中，从中间规划路线涵盖的景点中删除预设数量个景点，可以从起始点位置的第一个景点开始，往后删除连续的M个景点，再从终点位置前的第一个景点开始，往前删除连续的N个景点，使M与N的和等于预设数量。
在本发明的一个实施例中，从中间规划路线涵盖的景点中删除预设数量个景点，还可以每间隔一个景点删除一个景点，若删除的景点数量不足预设数量，则从删除后得到的路线中，再每间隔一个景点删除一个景点，直到删除的景点的总数量到达预设数量。
下面通过具体的示例对路线优化过程进行详细说明。
假设，规划路线为起始点位置—>景点1—>景点5—>终点位置，该规划路线对应的游览时长为155分钟，该规划路线涵盖的景点的总偏好程度分值为10分。预先设定的游览总时长为160分钟。从中间规划路线涵盖的景点中删除预设数量个景点的删除次数初始值为0，预设无改进的最大迭代次数为200。
首先将规划路线：起始点位置—>景点1—>景点5—>终点位置作为中间规划路线。
此时，删除次数0小于最大迭代次数200，则从中间规划路线：起始点位置—>景点1—>景点5—>终点位置中删除景点。将删除次数加1，此时，删除次数＝1。
对删除景点后的路线进行景点插入，其中，景点插入过程与上述景点插入过程基本相同，本发明实施例在此不对其进行赘述。
假设经过景点删除和插入后的当前路线为：起始点位置—>景点1—>景点4—>终点位置，当前路线对应的游览时长为155分钟，涵盖的景点的总偏好程度分值为13分。当前路线涵盖的景点的总偏好程度分值13分大于中间规划路线涵盖的景点的总偏好程度分值10分。则将当前路线：起始点位置—>景点1—>景点4—>终点位置作为中间规划路线，并将删除次数清零。
此时，删除次数0小于最大迭代次数200，则从中间规划路线：起始点位置—>景点1—>景点4—>终点位置中删除景点。将删除次数加1，此时，删除次数＝1。
对删除景点后的路线进行景点插入。假设经过景点删除和插入后的当前路线为：起始点位置—>景点2—>景点3—>终点位置，当前路线对应的游览时长为145分钟，涵盖的景点的总偏好程度分值为13分。当前路线涵盖的景点的总偏好程度分值13分等于中间规划路线涵盖的景点的偏好程度分值13分，但当前路线对应的游览时长145分钟小于中间规划路线对应的游览时长145分钟相等。则将当前路线：起始点位置—>景点2—>景点3—>终点位置作为中间规划路线，并将删除次数清零。
此时，删除次数0小于最大迭代次数200，则从中间规划路线：起始点位置—>景点2—>景点3—>终点位置中删除景点。将删除次数加1，此时，删除次数＝1。
对删除景点后的路线进行景点插入。假设经过景点删除和插入后的当前路线为：起始点位置—>景点1—>景点7—>终点位置，当前路线对应的游览时长为150分钟，涵盖的景点的偏好程度分值为13分。当前路线涵盖的景点的总偏好程度分值13分等于中间规划路线涵盖的景点的偏好程度分值13分，但当前路线对应的游览时长150分钟大于中间规划路线对应的游览时长145分钟相等。。则中间规划路线不变还为：起始点位置—>景点2—>景点3—>终点位置。
此时，删除次数1小于最大迭代次数200，则从中间规划路线：起始点位置—>景点2—>景点3—>终点位置中删除景点。将删除次数加1，此时，删除次数＝2。
对删除景点后的路线进行景点插入。假设经过景点删除和插入后的当前路线为：起始点位置—>景点2—>景点5—>终点位置，当前路线对应的游览时长为145分钟，涵盖的景点的偏好程度分值为12分。当前路线对应的游览时长145分钟等于中间规划路线对应的游览时长145分钟，但当前路线涵盖的景点的偏好程度分值12分小于中间规划路线涵盖的景点的偏好程度分值13分。则中间规划路线不变还为：起始点位置—>景点2—>景点3—>终点位置。
此时，删除次数2小于最大迭代次数200，则从中间规划路线：起始点位置—>景点2—>景点3—>终点位置中删除景点。将删除次数加1，此时，删除次数＝3。对删除景点后的路线进行景点插入。
若删除次数等于最大迭代次数200，则将中间规划路线确定为最终规划路线。
示例性的，假设对于中间规划路线：起始点位置—>景点2—>景点3—>终点位置。删除次数已达200次，可以理解的是，当删除次数达到200次数，每次删除和插入景点后的路线的游览总时长均不小于中间规划路线对应的游览总时长，且每次删除和插入景点后的路线涵盖的景点的总偏好程度分值均不大于中间规划路线涵盖的景点的总偏好程度分值，此时，将中间规划路线：起始点位置—>景点2—>景点3—>终点位置确定为最终规划路线。
在本发明的一个实施例中，在利用上述过程过程优化路线的过程中，可以在每经过1/4的最大迭代次数时，将用于计算景点的最小插入成本的景点集群参数进行减少。示例性的，假设景点集群参数ClusterParamter初始值为1.2。当删除次数＝50时，将景点集群参数ClusterParamter减少0.1，此时，ClusterParamter＝1.1。当删除次数＝100时，将景点集群参数ClusterPa再减少0.1，此时，ClusterParamter＝1。当删除次数＝150时，将景点集群参数ClusterParamter再减少0.1，此时，ClusterParamter＝0.9。
也就是说，优化后的路线需要满足下述条件1或条件2。
条件1：优化后的路线涵盖的景点的总偏好程度分值比优化前的路线涵盖的景点的总偏好程度分值高。
条件2：优化后的路线涵盖的景点的总偏好程度分值与优化前的路线涵盖的景点的总偏好程度分值相等。但优化后的路线对应的总游览时长比优化前的路线对应的总游览时长短。
需要说明的是，条件1和条件2的前提为：优化后的路线对应的总游览时长比用户设置的游览时长短。
图5示出了本发明实施例提供的路线规划的结果示意图。
图6示出了本发明实施例规划出的路线的总时长与现有技术规划出的路线的总时长的对比图。由图6可见，当用户设置的游览总时长较短时，本发明实施例规划出的路线的总时长与现有技术规划出的路线的总时长基本相同。当用户设置的游览总时长较长时，本发明实施例规划出的路线的总时长要比现有技术规划出的路线的总时长短，能够节省用户的游览时间。通常情况下，游览一个景区需要的时长基本在两个半小时以上，更有甚者，有的景区游览需要至少4、5个小时，比如，颐和园和承德避暑山庄等等。
图7示出了本发明实施例规划出路线的耗时时间和现有技术规划出路线的耗时时间的对比图。由图7可以看出，本发明实施例规划出路线的耗时时间与现有技术规划出路线的耗时时间相差约1000毫秒(1秒)，对于用户来说也是可以接受的。
需要说明的是，上述以10个景点为例进行说明，仅为本发明的一具体实例，并不构成对本发明的限定。
本发明实施例的路线规划方法，根据用户针对景点的偏好程度分值，来进行路线规划，能够使规划出的路线满足用户的偏好要求。
与上述的方法实施例相对应，本发明实施例还提供一种路线规划装置。如图8所示，图8示出了本发明实施例提供的路线规划装置的结构示意图。路线规划装置可以包括：
获得模块801，用于获得用户的起始点位置、终点位置、游览总时长和用户针对每一景点的偏好程度分值。
第一确定模块802，用于根据偏好程度分值，从由起始点位置至终点位置的当前路线未涵盖的景点中，确定待插入景点和待插入景点对于当前路线中的插入位置。
计算模块803，用于计算将待插入景点插入插入位置后的第一目标路线对应的游览时长。
插入模块804，用于若游览时长不大于游览总时长，则将待插入景点插入插入位置；并触发第一确定模块802。
第二确定模块805，用于若游览时长大于游览总时长，将当前路线确定为规划路线。
在本发明的一个实施例中，第一确定模块802，包括：
插入位置确定单元，用于针对从由起始点位置至终点位置的当前路线未涵盖的景点中的每一景点，计算景点插入当前路线中的相邻两个景点的之间对应的时间消耗；根据时间消耗，确定景点的最小插入成本；将最小插入成本对应的相邻两个景点的之间的位置，作为景点的插入位置；
待插入景点确定单元，用于针对每一景点，根据偏好程度分值和最小插入成本，计算景点的插入比率；将最高插入比率对应的景点，作为待插入景点。
在本发明的一个实施例中，插入位置确定单元，具体用于：
若景点与相邻两个景点中的前一个景点和/或后一个景点位于同一个景点集群，将最小时间消耗与景点集群对应的景点集群参数值的比值，作为景点的最小插入成本；
若景点与前一个景点和后一个景点没有位于同一个景点集群，将最小时间消耗，作为景点的最小插入成本。
在本发明的一个实施例中，本发明实施例提供的路线规划装置还包括：
第三确定模块，用于针对第一目标路线涵盖的每一景点，根据用户浏览景点的时长和起始时间，确定用户针对景点的游览是否满足景点的开放时间和关闭时间的要求；若针对第一目标路线涵盖的每一景点，均确定出用户针对景点的游览满足景点的开放时间和关闭时间的要求，触发插入模块。
在本发明的一个实施例中，本发明实施例提供的路线规划装置还包括：
路线优化模块，用于将规划路线作为中间规划路线；
比较从中间规划路线涵盖的景点中删除预设数量个景点的次数与预设无改进的最大迭代次数；
若次数等于最大迭代次数，将中间规划路线确定为最终规划路线；
若次数小于最大迭代次数，则从中间规划路线涵盖的景点中删除预设数量个景点，得到第二目标路线，并将次数加1；
根据偏好程度分值，从第二目标路线未涵盖的景点中确定待插入景点和待插入景点对于第二目标路线的插入位置；
计算将待插入景点插入插入位置后的第三目标路线对应的游览时长；
若游览时长不大于游览总时长，则将待插入景点插入插入位置；
返回根据偏好程度分值，从第二目标路线未涵盖的景点中确定待插入景点和待插入景点对于第二目标路线的插入位置继续执行，直至游览时长大于游览总时长；
比较当前路线涵盖的景点的第一总偏好程度分值与中间规划路线涵盖的景点的第二总偏好程度分值；
若第一总偏好程度分值大于第二总偏好程度分值，则将当前路线作为中间规划路线，并将次数清零；返回比较从中间规划路线涵盖的景点中删除预设数量个景点的次数与预设无改进的最大迭代次数线继续执行；
若第一总偏好程度分值等于第二总偏好程度分值，比较当前路线对应的第一游览总时长和中间规划路线对应的第二游览总时长；
若第一游览总时长不大于第二游览总时长，则将当前路线作为中间规划路线，并将次数清零；返回比较从中间规划路线涵盖的景点中删除预设数量个景点的次数与预设无改进的最大迭代次数继续执行；
若第一游览总时长大于第二游览总时长，则返回比较从中间规划路线涵盖的景点中删除预设数量个景点的次数与预设无改进的最大迭代次数继续执行；
若第一总偏好程度分值不大于第二总偏好程度分值，则返回比较从中间规划路线涵盖的景点中删除预设数量个景点的次数与预设无改进的最大迭代次数继续执行。
本发明实施例的路线规划装置，根据用户针对景点的偏好程度分值，来进行路线规划，能够使规划出的路线满足用户的偏好要求。
图9示出了能够实现根据本发明实施例的路线规划方法及装置的计算设备的示例性硬件架构的结构图。如图9所示，计算设备900包括输入设备901、输入接口902、中央处理器903、存储器904、输出接口905、以及输出设备906。其中，输入接口902、中央处理器903、存储器25 904、以及输出接口905通过总线910相互连接，输入设备901和输出设备906分别通过输入接口902和输出接口905与总线910连接，进而与计算设备900的其他组件连接。
具体地，输入设备901接收来自外部的输入信息，并通过输入接口902将输入信息传送到中央处理器903；中央处理器903基于存储器904中存储的计算机可执行指令对输入信息进行处理以生成输出信息，将输出信息临时或者永久地存储在存储器904中，然后通过输出接口905将输出信息传送到输出设备906；输出设备906将输出信息输出到计算设备900的外部供用户使用。
也就是说，图9所示的计算设备也可以被实现为路线规划设备，该路线规划设备可以包括：存储有计算机可执行指令的存储器；以及处理器，该处理器在执行计算机可执行指令时可以实现结合图2和图8描述的路线规划方法和装置。
本发明实施例还提供一种计算机可读存储介质，该计算机可读存储介质上存储有计算机程序指令；该计算机程序指令被处理器执行时实现本发明实施例提供的路线规划方法。
需要明确的是，本发明并不局限于上文所描述并在图中示出的特定配置和处理。为了简明起见，这里省略了对已知方法的详细描述。在上述实施例中，描述和示出了若干具体的步骤作为示例。但是，本发明的方法过程并不限于所描述和示出的具体步骤，本领域的技术人员可以在领会本发明的精神后，作出各种改变、修改和添加，或者改变步骤之间的顺序。
以上所述的结构框图中所示的功能块可以实现为硬件、软件、固件或者它们的组合。当以硬件方式实现时，其可以例如是电子电路、专用集成电路(ASIC)、适当的固件、插件、功能卡等等。当以软件方式实现时，本发明的元素是被用于执行所需任务的程序或者代码段。程序或者代码段可以存储在机器可读介质中，或者通过载波中携带的数据信号在传输介质或者通信链路上传送。“机器可读介质”可以包括能够存储或传输信息的任何介质。机器可读介质的例子包括电子电路、半导体存储器设备、ROM、闪存、可擦除ROM(EROM)、软盘、CD-ROM、光盘、硬盘、光纤介质、射频(RF)链路，等等。代码段可以经由诸如因特网、内联网等的计算机网络被下载。
还需要说明的是，本发明中提及的示例性实施例，基于一系列的步骤或者装置描述一些方法或系统。但是，本发明不局限于上述步骤的顺序，也就是说，可以按照实施例中提及的顺序执行步骤，也可以不同于实施例中的顺序，或者若干步骤同时执行。
以上所述，仅为本发明的具体实施方式，所属领域的技术人员可以清楚地了解到，为了描述的方便和简洁，上述描述的系统、模块和单元的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。应理解，本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到各种等效的修改或替换，这些修改或替换都应涵盖在本发明的保护范围之内。

Claims (8)

1.一种路线规划方法，其特征在于，所述方法包括：
获得用户的起始点位置、终点位置、游览总时长和用户针对每一景点的偏好程度分值；
根据所述偏好程度分值，从由所述起始点位置至所述终点位置的当前路线未涵盖的景点中，确定待插入景点和所述待插入景点对于当前路线中的插入位置；
计算将所述待插入景点插入所述插入位置后的第一目标路线对应的游览时长；
若所述游览时长不大于所述游览总时长，则将所述待插入景点插入所述插入位置；
返回所述根据所述偏好程度分值，从由所述起始点位置至所述终点位置的当前路线未涵盖的景点中，确定待插入景点和所述待插入景点对于当前路线中的插入位置继续执行；
若所述游览时长大于所述游览总时长，将当前路线确定为规划路线；
所述根据所述偏好程度分值，从由所述起始点位置至所述终点位置的当前路线未涵盖的景点中，确定待插入景点和所述待插入景点对于当前路线中的插入位置，包括：
针对所述从由所述起始点位置至所述终点位置的当前路线未涵盖的景点中的每一景点，计算所述景点插入所述当前路线中的相邻两个景点之间对应的时间消耗；根据所述时间消耗，确定所述景点的最小插入成本；将所述最小插入成本对应的相邻两个景点之间的位置，作为所述景点的插入位置；
针对所述每一景点，根据所述偏好程度分值和所述最小插入成本，计算所述景点的插入比率；将最高插入比率对应的景点，作为待插入景点；
所述插入比率按照如下公式表示：
其中，所述ratiop为所述插入比率，profitp为所述偏好程度分值，shiftClusterp为所述最小插入成本；
所述根据所述时间消耗，确定所述景点的最小插入成本，包括：
若所述景点与所述相邻两个景点中的前一个景点和/或后一个景点位于同一个景点集群，将最小时间消耗与所述景点集群对应的景点集群参数值的比值，作为所述景点的最小插入成本；
若所述景点与所述前一个景点和所述后一个景点没有位于同一个景点集群，将所述最小时间消耗，作为所述景点的最小插入成本。
2.根据权利要求1所述的方法，其特征在于，在所述将所述待插入景点插入所述插入位置之前，所述方法还包括：
针对所述第一目标路线涵盖的每一景点，根据用户浏览所述景点的时长和起始时间，确定用户针对所述景点的游览是否满足所述景点的开放时间和关闭时间的要求；若针对所述第一目标路线涵盖的每一景点，均确定出用户针对所述景点的游览满足所述景点的开放时间和关闭时间的要求，则将所述待插入景点插入所述插入位置。
3.根据权利要求1所述的方法，其特征在于，所述方法还包括：
将所述规划路线作为中间规划路线；
比较从所述中间规划路线涵盖的景点中删除预设数量个景点的次数与预设无改进的最大迭代次数；
若所述次数等于所述最大迭代次数，将所述中间规划路线确定为最终规划路线；
若所述次数小于所述最大迭代次数，则从所述中间规划路线涵盖的景点中删除预设数量个景点，得到第二目标路线，并将所述次数加1；
根据所述偏好程度分值，从所述第二目标路线未涵盖的景点中确定待插入景点和所述待插入景点对于所述第二目标路线的插入位置；
计算将所述待插入景点插入所述插入位置后的第三目标路线对应的游览时长；
若所述游览时长不大于所述游览总时长，则将所述待插入景点插入所述插入位置；
返回所述根据所述偏好程度分值，从所述第二目标路线未涵盖的景点中确定待插入景点和所述待插入景点对于所述第二目标路线的插入位置继续执行，直至所述游览时长大于所述游览总时长；
比较当前路线涵盖的景点的第一总偏好程度分值与所述中间规划路线涵盖的景点的第二总偏好程度分值；
若所述第一总偏好程度分值大于所述第二总偏好程度分值，则将当前路线作为所述中间规划路线，并将所述次数清零；返回所述比较从所述中间规划路线涵盖的景点中删除预设数量个景点的次数与预设无改进的最大迭代次数线继续执行；
若所述第一总偏好程度分值等于所述第二总偏好程度分值，比较当前路线对应的第一游览总时长和所述中间规划路线对应的第二游览总时长；
若所述第一游览总时长不大于所述第二游览总时长，则将当前路线作为所述中间规划路线，并将所述次数清零；返回所述比较从所述中间规划路线涵盖的景点中删除预设数量个景点的次数与预设无改进的最大迭代次数继续执行；
若所述第一游览总时长大于所述第二游览总时长，则返回所述比较从所述中间规划路线涵盖的景点中删除预设数量个景点的次数与预设无改进的最大迭代次数继续执行；
若所述第一总偏好程度分值不大于所述第二总偏好程度分值，则返回所述比较从所述中间规划路线涵盖的景点中删除预设数量个景点的次数与预设无改进的最大迭代次数继续执行。
4.一种路径规划装置，其特征在于，所述装置包括：
获得模块，用于获得用户的起始点位置、终点位置、游览总时长和用户针对每一景点的偏好程度分值；
第一确定模块，用于根据所述偏好程度分值，从由所述起始点位置至所述终点位置的当前路线未涵盖的景点中，确定待插入景点和所述待插入景点对于当前路线中的插入位置；
计算模块，用于计算将所述待插入景点插入所述插入位置后的第一目标路线对应的游览时长；
插入模块，用于若所述游览时长不大于所述游览总时长，则将所述待插入景点插入所述插入位置；并触发所述第一确定模块；
第二确定模块，用于若所述游览时长大于所述游览总时长，将当前路线确定为规划路线；
所述第一确定模块，包括：
插入位置确定单元，用于针对所述从由所述起始点位置至所述终点位置的当前路线未涵盖的景点中的每一景点，计算所述景点插入所述当前路线中的相邻两个景点之间对应的时间消耗；根据所述时间消耗，确定所述景点的最小插入成本；将所述最小插入成本对应的相邻两个景点之间的位置，作为所述景点的插入位置；
待插入景点确定单元，用于针对所述每一景点，根据所述偏好程度分值和所述最小插入成本，计算所述景点的插入比率；将最高插入比率对应的景点，作为待插入景点；所述插入比率按照如下公式表示：
其中，所述ratiop为所述插入比率，profitp为所述偏好程度分值，shiftClusterp为所述最小插入成本；
所述插入位置确定单元，具体用于：
若所述景点与所述相邻两个景点中的前一个景点和/或后一个景点位于同一个景点集群，将最小时间消耗与所述景点集群对应的景点集群参数值的比值，作为所述景点的最小插入成本；
若所述景点与所述前一个景点和所述后一个景点没有位于同一个景点集群，将所述最小时间消耗，作为所述景点的最小插入成本。
5.根据权利要求4所述的装置，其特征在于，所述装置还包括：
第三确定模块，用于针对所述第一目标路线涵盖的每一景点，根据用户浏览所述景点的时长和起始时间，确定用户针对所述景点的游览是否满足所述景点的开放时间和关闭时间的要求；若针对所述第一目标路线涵盖的每一景点，均确定出用户针对所述景点的游览满足所述景点的开放时间和关闭时间的要求，触发插入模块。
6.根据权利要求4所述的装置，其特征在于，所述装置还包括：
路线优化模块，用于将所述规划路线作为中间规划路线；
比较从所述中间规划路线涵盖的景点中删除预设数量个景点的次数与预设无改进的最大迭代次数；
若所述次数等于所述最大迭代次数，将所述中间规划路线确定为最终规划路线；
若所述次数小于所述最大迭代次数，则从所述中间规划路线涵盖的景点中删除预设数量个景点，得到第二目标路线，并将所述次数加1；
根据所述偏好程度分值，从所述第二目标路线未涵盖的景点中确定待插入景点和所述待插入景点对于所述第二目标路线的插入位置；
计算将所述待插入景点插入所述插入位置后的第三目标路线对应的游览时长；
若所述游览时长不大于所述游览总时长，则将所述待插入景点插入所述插入位置；
返回所述根据所述偏好程度分值，从所述第二目标路线未涵盖的景点中确定待插入景点和所述待插入景点对于所述第二目标路线的插入位置继续执行，直至所述游览时长大于所述游览总时长；
比较当前路线涵盖的景点的第一总偏好程度分值与所述中间规划路线涵盖的景点的第二总偏好程度分值；
若所述第一总偏好程度分值大于所述第二总偏好程度分值，则将当前路线作为所述中间规划路线，并将所述次数清零；返回所述比较从所述中间规划路线涵盖的景点中删除预设数量个景点的次数与预设无改进的最大迭代次数线继续执行；
若所述第一总偏好程度分值等于所述第二总偏好程度分值，比较当前路线对应的第一游览总时长和所述中间规划路线对应的第二游览总时长；
若所述第一游览总时长不大于所述第二游览总时长，则将当前路线作为所述中间规划路线，并将所述次数清零；返回所述比较从所述中间规划路线涵盖的景点中删除预设数量个景点的次数与预设无改进的最大迭代次数继续执行；
若所述第一游览总时长大于所述第二游览总时长，则返回所述比较从所述中间规划路线涵盖的景点中删除预设数量个景点的次数与预设无改进的最大迭代次数继续执行；
若所述第一总偏好程度分值不大于所述第二总偏好程度分值，则返回所述比较从所述中间规划路线涵盖的景点中删除预设数量个景点的次数与预设无改进的最大迭代次数继续执行。
7.一种路线规划设备，其特征在于，所述设备包括：存储器、处理器及存储在所述存储器上并可在所述处理器上运行的计算机程序；
所述处理器执行所述计算机程序时实现如权利要求1至3任一项所述的路线规划方法。
8.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现如权利要求1至3任一项所述的路线规划方法。
CN201811422192.XA 2018-11-27 2018-11-27 路线规划方法、装置、设备及存储介质 Active CN111222667B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201811422192.XA CN111222667B (zh) 2018-11-27 2018-11-27 路线规划方法、装置、设备及存储介质

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201811422192.XA CN111222667B (zh) 2018-11-27 2018-11-27 路线规划方法、装置、设备及存储介质

Publications (2)

Publication Number Publication Date
CN111222667A CN111222667A (zh) 2020-06-02
CN111222667B true CN111222667B (zh) 2023-09-19

Family

ID=70806264

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201811422192.XA Active CN111222667B (zh) 2018-11-27 2018-11-27 路线规划方法、装置、设备及存储介质

Country Status (1)

Country Link
CN (1) CN111222667B (zh)

Families Citing this family (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112541021B (zh) * 2020-12-10 2024-05-03 北京百度网讯科技有限公司 路线评估方法、风景区游览预估时长计算方法及装置
CN112465176B (zh) * 2020-12-10 2022-05-10 南京领行科技股份有限公司 一种行车路线规划方法及装置
CN113689025B (zh) * 2021-07-08 2023-12-01 湖南中惠旅智能科技有限责任公司 基于电子地图的景区游玩项目规划方法及系统
CN113869558A (zh) * 2021-09-03 2021-12-31 云南腾云信息产业有限公司 路线推荐方法、装置、计算机设备和存储介质
JP2024030810A (ja) * 2022-08-25 2024-03-07 トヨタ自動車株式会社 走行ルート生成装置、走行ルート生成方法、走行ルート生成プログラム
CN116878484A (zh) * 2023-07-11 2023-10-13 深圳特为科创信息技术有限公司 一种基于大数据的路线导航方法及系统

Citations (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1871499A (zh) * 2003-09-30 2006-11-29 株式会社建伍 引导路线搜索装置和引导路线搜索方法
CN101236095A (zh) * 2008-03-06 2008-08-06 倚天资讯股份有限公司 导航系统
TW200936988A (en) * 2008-02-19 2009-09-01 E Ten Information Sys Co Ltd Navigation system, method of automatically planning trip itinerary, computer readable recording media with stored program and computer program product with stored program
CN104036441A (zh) * 2013-03-06 2014-09-10 中兴通讯股份有限公司 一种导游系统及方法
WO2016044855A1 (en) * 2014-09-19 2016-03-24 Arris Enterprises, Inc. Systems and methods for street level routing
CN106447097A (zh) * 2016-09-20 2017-02-22 北京工业大学 一种受限最长频繁路径的查询方法
CN107025495A (zh) * 2015-12-17 2017-08-08 Sap欧洲公司 基于用户选择来降低确定用于装运集装箱的路线的复杂度
CN107704508A (zh) * 2017-08-31 2018-02-16 北京空间飞行器总体设计部 多类型海量空间目标数据的数据融合与数据挖掘方法
CN107748937A (zh) * 2017-11-03 2018-03-02 哈尔滨工业大学 一种基于moead的比例区间偏好引导多目标决策优化方法
CN107832872A (zh) * 2017-10-19 2018-03-23 金华航大北斗应用技术有限公司 用于景区路线的动态规划方法
CN108108847A (zh) * 2017-12-29 2018-06-01 合肥工业大学 一种电商物流最后一公里配送的路径规划方法

Patent Citations (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1871499A (zh) * 2003-09-30 2006-11-29 株式会社建伍 引导路线搜索装置和引导路线搜索方法
TW200936988A (en) * 2008-02-19 2009-09-01 E Ten Information Sys Co Ltd Navigation system, method of automatically planning trip itinerary, computer readable recording media with stored program and computer program product with stored program
CN101236095A (zh) * 2008-03-06 2008-08-06 倚天资讯股份有限公司 导航系统
CN104036441A (zh) * 2013-03-06 2014-09-10 中兴通讯股份有限公司 一种导游系统及方法
WO2016044855A1 (en) * 2014-09-19 2016-03-24 Arris Enterprises, Inc. Systems and methods for street level routing
CN107025495A (zh) * 2015-12-17 2017-08-08 Sap欧洲公司 基于用户选择来降低确定用于装运集装箱的路线的复杂度
CN106447097A (zh) * 2016-09-20 2017-02-22 北京工业大学 一种受限最长频繁路径的查询方法
CN107704508A (zh) * 2017-08-31 2018-02-16 北京空间飞行器总体设计部 多类型海量空间目标数据的数据融合与数据挖掘方法
CN107832872A (zh) * 2017-10-19 2018-03-23 金华航大北斗应用技术有限公司 用于景区路线的动态规划方法
CN107748937A (zh) * 2017-11-03 2018-03-02 哈尔滨工业大学 一种基于moead的比例区间偏好引导多目标决策优化方法
CN108108847A (zh) * 2017-12-29 2018-06-01 合肥工业大学 一种电商物流最后一公里配送的路径规划方法

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
"机场接送服务中基于协作的车次分配与调度方法研究";许争争;《中国博士学位论文全文数据库工程科技Ⅱ辑》;20170315;第C031-13页 *

Also Published As

Publication number Publication date
CN111222667A (zh) 2020-06-02

Similar Documents

Publication Publication Date Title
CN111222667B (zh) 路线规划方法、装置、设备及存储介质
US8681635B2 (en) Computer-implemented systems and methods for planning a route
US9892532B2 (en) Apparatus and method for generating a shortest-path tree in a graph
US10404576B2 (en) Constrained shortest path determination in a network
CN102506849B (zh) 寻找带约束的最短路径的方法
CN107687859A (zh) 基于a星算法的最短寻路方法
TW201700955A (zh) 路徑規劃方法及裝置
CN107196858A (zh) 一种考虑多类型约束的k最短路径求解方法
KR20150145169A (ko) 도로망에 기초하여 도달가능한 지역을 결정하는 방법 및 장치
CN110146072A (zh) 一种路径规划方法、服务器及可读存储介质
US9674083B2 (en) Path calculation order deciding method, program and calculating apparatus
CN114091763B (zh) 路线规划方法、装置、可读介质和电子设备
JP5391322B2 (ja) 経路計算方法、プログラムおよび計算装置
CN113992259B (zh) 一种时隙资源拓展图的构建方法
CN107332770A (zh) 一种必经点路由路径选择方法
CN110247805B (zh) 一种基于k壳分解的识别传播关键节点的方法及装置
CN113347083B (zh) 网络路径确定及切换方法、装置、设备、介质及程序产品
CN113987995A (zh) 一种布线方案确定方法、装置、电子设备及存储介质
CN112807682A (zh) 路径找寻方法、终端及计算机可读存储介质
CN106034266B (zh) 光路由的生成方法及装置
US20130010643A1 (en) Method and apparatus for loop path search in mesh network
CN110278154B (zh) 路由节点位置优化方法、装置和终端设备
JP5506538B2 (ja) 経路計算方法及び装置及びプログラム
CN116679712B (zh) 一种基于广义维诺图的室内环境机器人高效探索决策方法
CN115406459B (zh) 路径确定方法、装置、非易失性存储介质及计算机设备

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant