CN111998865B - 一种用于路径确定的系统和方法 - Google Patents

Abstract

本申请实施例公开了一种用于路径确定的方法和系统。该方法包括：串联多个节点以生成多个第一候选路径；基于多个节点中任意两个节点之间的地理距离确定多个第一候选路径中每个的地理长度；从多个第一候选路径中确定参考路径；基于参考路径中相邻节点之间的导航长度确定参考路径的导航长度；基于所述多个第一候选路径中每一个的地理长度，从多个第一候选路径中确定出一个或多个第二候选路径；确定一个或多个第二候选路径中每一个的导航长度；基于一个或多个第二候选路径中每一个的导航长度、速度限制和/或实时因素，确定一个或多个第二候选路径中每一个的行驶时间；基于行驶时间从一个或多个第二候选路径中确定目标路径。

Description

一种用于路径确定的系统和方法

分案说明

本申请是针对申请日为2018年6月7日，申请号为201880038648.4，发明名称为一种用于路径确定的系统和方法的中国申请，提出的分案申请。

技术领域

本申请涉及在线到离线服务平台领域，特别涉及一种用于路径确定的系统和方法。

背景技术

随着互联网技术的发展，在线到离线服务，如在线出租车服务和送货服务，在人们的日常生活中发挥着越来越重要的作用。在预定的拼车服务的情况下，司机从自己的起点出发，需要经过每个乘客的起点和终点，并最终到达最后一个乘客的终点。这是典型的车辆路线规划(VRP)问题，需要考虑接乘顺序以实现最短行驶距离。在解决这个问题的过程中，经常需要频繁地请求导航距离计算服务来计算行进路径中任意两点之间的距离。这些资源很有价值，在某些情况下也很昂贵。因此，希望开发有效的系统和方法以提高服务器对服务请求的响应速度并节省计算资源。

发明内容

根据本申请实施例的一个方面，提供了一种用于路径确定方法，该方法包括：串联多个节点以生成多个第一候选路径，其中所述多个节点是基于一个或多个请求确定的，并且所述多个第一候选路径满足与该多个节点相关的第一条件；基于多个节点中的任意两个节点之间的地理距离确定多个第一候选路径中的每一个的地理长度；从多个第一候选路径中确定参考路径，其中，所述参考路径的地理长度在多个第一候选路径中最短；基于所述参考路径中相邻节点之间的导航长度确定所述参考路径的导航长度；基于所述多个第一候选路径中的每一个的地理长度，从所述多个第一候选路径中确定出一个或多个第二候选路径，其中所述第二候选路径的地理长度短于所述参考路径的导航长度；确定一个或多个第二候选路径中的每一个的导航长度；基于所述一个或多个第二候选路径中的每一个的导航长度、速度限制和/或实时因素，确定一个或多个第二候选路径中每一个的行驶时间；基于所述行驶时间从一个或多个第二候选路径中确定目标路径。

在一些实施例中，所述目标路径的行驶时间是所述一个或多个第二候选路径中最短的。

在一些实施例中，所述实时因素包括交通状况、天气状况和道路工程安排中的一种或多种的组合。

根据本申请实施例的一个方面，提供了一种用于路径确定的系统，其特征在于，所述系统包括第一候选路径生成模块、所述长度计算模块、所述第二候选路径确定模块和目标路径确定模块；其中：所述第一候选路径生成模块，用于串联所述多个节点以生成多个第一候选路径，其中所述多个第一候选路径满足与所述多个节点相关的第一条件；所述长度计算模块，用于基于多个节点中的任意两个节点之间的地理距离确定多个第一候选路径中的每一个的地理长度；所述第二候选路径确定模块，用于：从多个第一候选路径中确定参考路径，其中，所述参考路径的地理长度在多个第一候选路径中最短；基于所述参考路径中相邻节点之间的导航长度确定所述参考路径的导航长度；基于所述多个第一候选路径中的每一个的地理长度，从所述多个第一候选路径中确定出一个或多个第二候选路径，其中所述第二候选路径的地理长度短于所述参考路径的导航长度；所述长度计算模块，用于确定一个或多个第二候选路径中的每一个的导航长度；所述目标路径确定模块，用于基于所述一个或多个第二候选路径中的每一个的导航长度、速度限制和/或实时因素，确定一个或多个第二候选路径中每一个的行驶时间；以及基于所述行驶时间从一个或多个第二候选路径中确定目标路径。

根据本申请实施例的一个方面，提供了一种路径确定装置，其特征在于，所述装置包括至少一个处理器和至少一个存储设备，所述存储设备用于存储指令，当所述至少一个处理器执行所述指令时，实现如本申请任一实施例所述的方法。

根据本申请实施例的一个方面，提供了一种计算机可读存储介质，所述存储介质存储计算机指令，当计算机读取所述存储介质中的所述计算机指令后，所述计算机执行如本申请任一实施例所述的方法。

根据本申请实施例的一个方面，提供了一种系统。所述系统可以包括至少一个存储一组指令的非暂时性计算机可读存储介质；至少一个处理器，与所述至少一个非暂时性计算机可读存储介质通信。当执行所述指令时，所述至少一个处理器可以使系统串联多个节点以生成多个第一候选路径。所述多个节点可以是基于一个或多个请求来确定的，并且所述多个第一候选路径可以满足与所述多个节点相关的第一条件。所述至少一个处理器还可以使系统基于所述多个第一候选路径中的每一个的地理长度，从多个第一候选路径中确定出一个或多个第二候选路径。所述至少一个处理器还可以使系统确定每一个第二候选路径的导航长度。所述至少一个处理器还可以使系统基于导航长度从一个或多个第二候选路径中确定出目标路径。目标路径的导航长度是一个或多个第二候选路径中最短的。

在一些实施例中，为了生成一个或多个第二候选路径，所述至少一个处理器还可以使系统从多个第一候选路径中确定参考路径。参考路径的地理长度在多个第一候选路径中最短的。所述至少一个处理器还可以使系统基于参考路径中相邻节点之间的导航长度确定参考路径的导航长度。所述至少一个处理器还可以使系统确定一个或多个第二候选路径。第二候选路径的地理长度短于参考路径的导航长度。

在一些实施例中，每个请求包括起始节点和目的地节点，并且第一条件是第一候选路径中的起始节点的优先级高于第一候选路径中的目的地节点的优先级。

在一些实施例中，为了生成多个第一候选路径，所述至少一个处理器还可以使系统基于多个节点确定初始回路。初始回路可以是具有第一节点序列的欧拉回路。所述至少一个处理器还可以使系统基于第一节点序列和与多个节点相关的第一条件确定多个第二节点序列。所述至少一个处理器还可以使系统基于多个第二节点序列确定多个第一候选路径。

在一些实施例中，所述欧拉回路可以是基于Christofides算法确定的。

在一些实施例中，所述多个第二节点序列可以是基于2-opt算法确定的。

在一些实施例中，为了从所述多个第一候选路径中确定出一个或多个第二候选路径，所述至少一个处理器还可以使系统确定参考路径的地理长度与每一个第一候选路径的地理长度之间的多个第一差值。所述至少一个处理器还可以使系统基于参考路径的导航长度与参考路径的地理长度之间的差值来确定第一参数。如果第一候选路径对应的第一差值小于第一参数，则所述至少一个处理器还可以使系统将该第一候选路径分配为第二候选路径。

在一些实施例中，每个第二候选路径可以包括一个或多个区段。每个区段可以连接第二候选路径中的两个相邻节点。为了确定参考路径的导航长度，所述至少一个处理器还可以使系统获得包括参考路径的多个区段的参考区段集。所述至少一个处理器还可以使系统确定参考区段集中每个区段的导航长度，以确定参考路径的导航长度。

在一些实施例中，为了确定一个或多个第二候选路径中的每一个的导航长度，所述至少一个处理器还可以使系统确定参考路径和第二候选路径之间的一个或多个不同区段。所述至少一个处理器还可以使系统将一个或多个不同的区段添加到参考区段集中。所述至少一个处理器还可以使系统基于参考区段集确定第二候选路径的导航长度。

在一些实施例中，如果第二候选路径中某区段的节点序列与参考路径的任意一个区段的节点序列相反，并且该区段的导航长度与地理长度之间的差值不超过阈值，则第二候选路径中的该区段不是不同的区段。

根据本申请实施例的另一个方面，计算机实现的方法包括由至少一个处理器执行的一个或多个以下操作。该方法包括串联多个节点以生成多个第一候选路径。所述多个节点可以是基于一个或多个请求确定的，并且所述多个第一候选路径可以满足与该多个节点相关的第一条件。该方法还包括基于多个节点中的任意两个节点之间的地理距离确定多个第一候选路径中的每一个的地理长度。该方法还包括基于所述多个第一候选路径中的每一个的地理长度，从所述多个第一候选路径中确定出一个或多个第二候选路径。该方法还包括确定一个或多个第二候选路径中的每一个的导航长度。该方法还包括基于导航长度从一个或多个第二候选路径中确定目标路径，其中目标路径的导航长度是该一个或多个第二候选路径中最短的。

根据本申请实施例的另一个方面，一种非暂时性机器可读存储介质存储指令，当所述指令被系统的所述至少一个处理器执行时会使得系统执行一种方法。该方法包括串联多个节点以生成多个第一候选路径。该多个节点可以是基于所述一个或多个请求确定的，并且该多个第一候选路径可以满足与所述多个节点相关的第一条件。该方法还包括基于多个节点中的任意两个节点之间的地理距离确定多个第一候选路径中的每一个的地理长度。该方法还包括基于所述多个第一候选路径中的每一个的地理长度，从该多个第一候选路径中确定一个或多个第二候选路径。该方法还包括确定一个或多个第二候选路径中的每一个的导航长度。该方法还包括基于导航长度从该一个或多个第二候选路径中确定目标路径。目标路径的导航长度是一个或多个第二候选路径中最短的。

附图说明

本申请将以示例性实施例的方式进一步说明，这些示例性实施例将通过附图进行详细描述。这些实施例是非限制性的，在这些实施例中，相同的编号表示相同的结构，其中：

图1是根据本申请一些实施例所示的用于路径确定的示例性的在线到离线服务系统的示意图；

图2是根据本申请一些实施例所示的一种示例性计算设备的硬件和软件组件的示意图；

图3是根据本申请一些实施例所示的可以在其上实现使用终端的示例性移动设备的示例性硬件和/或软件组件的示意图；

图4是根据本申请一些实施例所示的一种示例性处理引擎的模块图；

图5是根据本申请一些实施例所示的用于确定目标路径的示例性过程的流程图；

图6是根据本申请的一些实施例所示的用于确定多个第一候选路径的示例性过程的流程图；

图7是根据本申请的一些实施例所示的用于确定第二候选路径的示例性过程的流程图；

图8是根据本申请的一些实施例所示的用于确定参考路径的导航长度的示例性过程的流程图；

图9是根据本申请的一些实施例所示的用于确定一个或多个第二候选路径中的每一个的导航长度的示例性过程的流程图。

具体实施方式

呈现以下描述是为了使得本领域普通技术人员能够制造和使用本申请，并且在特定应用及其要求的背景下提供以下描述。对于本领域技术人员来说，对所公开的实施例的各种修改是显而易见的，并且在不脱离本申请的精神和范围的情况下，可以将这里定义的一般原理应用于其他实施例和应用。因此，本申请不限于所示的实施例，而是与权利要求一致的最宽范围。

这里使用的术语仅用于描述特定的示例实施例，而不是限制性的。如这里所使用的，除非上下文另有明确说明，单数形式“一”，“一个”和“该”也可以包括复数形式。需要进一步理解的是，当在本说明书中使用术语“包括”与“包含”时，可表明指定所述特征、整数、步骤、操作、元素和/或组件的存在，但不排除一个或多个其他特征、整数、步骤、操作、元素、组件和/或组的存在或添加。

本申请的所有功能和特征、结构的相关元件的操作和功能以及部件的组合和制造经济性，在参考以下附图描述时可以变得更加明显，所有这些描述构成本申请的一部分。然而，应该清楚地理解，附图仅用于说明和描述的目的，并不旨在限制本申请的保护范围。应当理解，附图未按比例绘制。

本申请中使用了流程图来说明根据本申请的一些实施例的系统所执行的操作。应该理解的是，流程图的操作可以不按顺序执行。相反，操作可以倒序或同时执行。此外，可以向流程图添加一个或多个其他操作，或从流程图中移除一个或多个操作。

此外，尽管本申请中的系统和方法主要是描述关于分配相应运输服务的请求，但是应该理解的是，本申请不旨在限制性。本申请的系统或方法可以应用于任何其他类型的在线到离线服务。例如，本申请的系统或方法可以应用于不同环境的运输系统，包括陆地，海洋，航空航天等，或其任何组合。运输系统的交通工具可包括出租车、私家车、公共汽车、火车、高速列车、高铁、地铁、船只、飞机、飞船、热气球、无人驾驶车辆等，或其任何组合。运输系统还包括用于管理和/或分配的任何运输系统，例如，用于发送和/或接收快递的系统。本申请的系统或方法的应用可以在用户设备上实现，并且包括网页、浏览器的插件、客户端终端、自定义系统、内部分析系统、人工智能机器人或类似、以及其任何组合。

本申请中的术语“乘客”、“请求者”、“服务请求者”和“客户”可互换使用，以指代可以请求或订购服务的个人、实体或工具。此外，本申请中的术语“司机”、“提供者”和“服务提供者”可互换使用，以指代可以提供服务或促进提供服务的个人、实体或工具。

本申请中的术语“服务请求”、“请求服务”、“请求”和“订单”可互换使用，以指代可由乘客、服务请求者、客户、司机、提供者、服务提供者或其任何组合发起的请求。服务请求可以由乘客、服务请求者、客户、司机、提供者或服务提供者中的任何一个接受。服务请求可能是收费的或免费的。

本申请中的术语“服务提供者终端”和“司机终端”可互换使用，以指代由服务提供者用于提供服务或促进提供服务的移动终端。本申请中的术语“服务请求者终端”和“乘客终端”可互换使用，以指代由服务请求者用来请求或订购服务的移动终端。

本申请中使用的定位技术可基于全球定位系统(GPS)、全球导航卫星系统(GLONASS)、北斗卫星导航系统(COMPASS)、伽利略卫星定位系统、准天顶卫星系统(QZSS)、无线保真(Wi-Fi)定位技术等，或以上任何组合。一个或多个上述定位系统可以在本申请中互换使用。

本申请的一方面涉及用于确定在线到离线服务的目标路径的系统和方法。该系统可以基于一个或多个请求获得多个节点。该系统可以串联多个节点以生成多个第一候选路径。多个第一候选路径满足与多个节点相关的第一条件。该系统可以基于多个节点中的任何两个节点之间的地理距离来确定多个第一候选路径中的每一个的地理长度。该系统可以从多个第一候选路径中确定出参考路径。参考路径的地理长度可能是多个第一候选路径中最短的。该系统可以基于参考路径中的相邻节点之间的导航长度来确定参考路径的导航长度。该系统可以从多个第一候选路径中确定出一个或多个第二候选路径。第二候选路径的地理长度短于参考路径的导航长度。该系统可以确定一个或多个第二候选路径中的每一个的导航长度。该系统可以基于所述导航长度从一个或多个第二候选路径中确定出目标路径。目标路径的导航长度可能是一个或多个第二候选路径中最短的。

应该注意的是，在线到离线服务，例如在线出租车，是一种仅在后互联网时代扎根的新形式的服务。它为用户和服务提供者提供技术解决方案，这些解决方案只能在后互联网时代被提出。在互联网时代之前，当用户在街道上叫出租车时，出租车请求和接收仅在乘客和看到乘客的一个出租车司机之间发生。如果乘客通过电话呼叫出租车，则服务请求和服务提供者的接收可能仅在乘客和服务提供者(例如，出租车公司或代理商)之间发生。然而，在线出租车允许请求服务的用户预订服务并自动将预订服务请求分发给距离用户较远的大量个人服务提供者(例如，出租车司机)。它还允许多个服务提供者同时并实时地响应服务请求。因此，通过因特网，在线到离线服务系统可以为在传统前互联网时代的传输服务系统中可能永远不会遇到的用户和服务提供者提供更有效的交易平台。分配预约订单可以有效地为服务请求者和服务提供者提供服务。

图1是根据本申请的一些实施例所示的示例性在线到离线服务系统100的示意图。例如，在线到离线服务系统100可以是用于运输服务的在线到离线服务平台。在线到离线服务系统100包括服务器110、网络120、服务请求者终端130、服务提供者终端140、车辆150、存储设备160和导航系统170。

在线到离线服务系统100可以提供多种服务。示例性服务包括出租车服务、司机服务、快车服务、拼车服务、公共汽车服务、司机租用服务和班车服务。在一些实施例中，在线到离线服务可以是任何在线服务，诸如订餐、购物等服务，或其任何组合。

在一些实施例中，服务器110可以是独立服务器或服务器组。该服务器组可以是集中式的或分布式的(例如，服务器110可以是分布式系统)。在一些实施例中，服务器110可以是本地的或远程的。例如，服务器110可以通过网络120访问存储在服务请求者终端130、服务提供者终端140和/或存储设备160中的信息和/或数据。作为另一示例，服务器110可以直接连接到服务请求者终端130、服务提供者终端140和/或存储设备160以访问存储的信息和/或数据。在一些实施例中，服务器110可以在云平台上执行。仅作为示例，云平台可包括私有云、公共云、混合云、社区云、分布式云、内部云、多云等，或其任何组合。在一些实施例中，服务器110可以在具有一个或多个组件的计算设备上执行，例如本申请中图2所示的计算设备200。

在一些实施例中，服务器110可以包括处理引擎112。处理引擎112可以处理与服务请求有关的信息和/或数据，以执行本申请中描述的一个或多个功能。例如，处理引擎112可以确定从服务请求者终端130接收的服务请求的目标路径。在一些实施例中，处理引擎112可包括一个或多个处理引擎(例如单核处理引擎或多核处理器)。仅作为示例，处理引擎112可以包括中央处理器(CPU)、专用集成电路(ASIC)、专用指令处理器(ASIP)、图形处理单元(GPU)、物理处理单元(PPU)、数字信号处理器(DSP)、现场可编程门阵列(FPGA)、可编程逻辑电路(PLD)、控制器、微控制器单元、精简指令集计算机(RISC)、微处理器等或以上任意任何组合。

网络120可以促进信息和/或数据的交换。在一些实施例中，在线到离线服务系统100中的一个或多个组件(例如：服务器110、服务请求者终端130、服务提供者终端140、车辆150、存储设备160和导航系统170)可以通过网络120将信息和/或数据发送到在线到离线服务系统100的其他组件。例如，服务器110可以通过网络120从服务请求者终端130接收服务请求。在一些实施例中，网络120可以是任何类型的有线或无线网络，或其组合。仅作为示例，网络120可包括缆线网络、有线网络、光纤网络、电信网络、内联网、因特网、局域网(LAN)、广域网(WAN)、无线局域网(WLAN)、城域网(MAN)、公共电话交换网(PSTN)、蓝牙网络、ZigBee网络、近场通信(NFC)网络或类似，以及其任何组合。在一些实施例中，网络120可以包括一个或多个网络接入点。例如，网络120可以包括有线或无线网络接入点，例如基站和/或互联网交换点120-1、120-2......，通过这些接入点，在线到离线服务系统100的一个或多个组件可以连接到网络120以交换数据和/或信息。

在一些实施例中，乘客可以是服务请求者终端130的所有者。在一些实施例中，服务请求者终端130的所有者可以是除乘客之外的其他人。例如，服务请求者终端130的所有者A可以使用服务请求者终端130来发送针对乘客B的服务请求或者从服务器110接收服务确认和/或信息或指令。在一些实施例中，服务提供者可以是服务提供者终端140的用户。在一些实施例中，服务提供者终端140的用户可以是除服务提供者之外的其他人。例如，服务提供者终端140的用户C可以使用服务提供者终端140来接收对服务提供者D的服务请求，和/或来自服务器110的信息或指令。在一些实施例中，“乘客”和“乘客终端”可以互换使用，并且“服务提供者”和“服务提供者终端”可以互换使用。在一些实施例中，服务提供者终端可以与一个或多个服务提供者(例如，夜班服务提供者或日班服务提供者)相关联。

在一些实施例中，服务请求者终端130可包括移动设备130-1、平板电脑130-2、膝上型电脑130-3、机动车内建装置130-4等，或其任何组合。在一些实施例中，移动设备130-1可包括智能家居设备、可穿戴设备、智能移动设备、虚拟现实设备、增强实境设备等，或其任何组合。在一些实施例中，智能家居设备可包括智能照明设备、智能电器的控制设备、智能监控设备、智能电视、智能摄像机、对讲机等，或其任意组合。在一些实施例中，可穿戴设备可包括智能手环、智能鞋袜、智能眼镜、智能头盔、智能手表、智能服装、智能背包、智能配件等，或其任何组合。在一些实施例中，智能移动设备可包括智能手机、个人数字助理(PDA)、游戏设备、导航设备、销售终端(POS)设备等，或其任何组合。在一些实施例中，虚拟现实设备和/或增强现实设备可包括虚拟现实头盔、虚拟现实眼镜、虚拟现实补丁、增强现实头盔、增强现实眼镜、增强现实补丁等，或其任何组合。例如，虚拟现实设备和/或增强现实设备可包括Google^TM Glass、Oculus Rift、HoloLens、Gear VR等。在一些实施例中，机动车内建装置130-4可包括车载电脑、车载电视等。在一些实施例中，服务请求者终端130可以是具有定位功能的设备，用于确定乘客和/或服务请求者终端130的位置。

服务提供者终端140可包括多个服务提供者终端140-1、140-2、...、140-n。在一些实施例中，服务提供者终端140可以与服务请求者终端130类似或相同。在一些实施例中，可以定制服务提供者终端140以实现所述在线到离线服务。在一些实施例中，服务提供者终端140可以是具有定位技术的设备，用于确定服务提供者、服务提供者终端140和/或与服务提供者终端140相关联的车辆150的位置。在一些实施例中，服务请求者终端130和/或服务提供者终端140可以与另一个定位设备通信以确定乘客、服务请求者终端130、服务提供者和/或服务提供者终端140的位置。在一些实施例中，服务请求者终端130和/或服务提供者终端140可定期将定位信息发送到服务器110。在一些实施例中，服务提供者终端140还可以定期将可用性状态发送到服务器110。可用性状态可以指示与服务提供者终端140相关联的车辆150是否可用于携带乘客。例如，服务请求者终端130和/或服务提供者终端140可以每30分钟将定位信息和可用性状态发送到服务器110。作为另一示例，服务请求者终端130和/或服务提供者终端140可以在每次用户登录到与在线到离线服务相关联的移动应用程序时，将定位信息和可用性状态发送到服务器110。

在一些实施例中，服务提供者终端140可以对应于一个或多个车辆150。车辆150可以携带乘客并前往目的地。车辆150可包括多个车辆150-1、150-2、......、150-n。一种车辆可以对应于一种类型的服务(例如，出租车服务、司机服务、快车服务、拼车服务、公共汽车服务、司机租用服务或班车服务)。

存储设备160可以存储数据和/或指令。在一些实施例中，存储设备160可以存储从服务请求者终端130和/或服务提供者终端140获得的数据。在一些实施例中，存储设备160可以存储服务器110可以执行或使用的数据和/或指令，以执行本申请中描述的示例性方法。在一些实施例中，存储设备160可包括大容量存储器、可移动存储器、易失性读写存储器、只读存储器(ROM)等，或其任何组合。示例性大容量存储器可包括磁盘、光盘、固态驱动器等。示例性可移动存储器可包括闪存驱动器、软盘、光盘、存储卡、zip磁盘、磁带等。示例性易失性读写存储器可包括随机存取存储器(RAM)。示例性随机存取存储器(RAM)可包括动态随机存取存储器(DRAM)、双倍数据速率同步动态随机存储器(DDR SDRAM)、静态随机存取存储器(SRAM)、晶闸管随机存取存储器(T-RAM)和零电容随机存取存储器(Z-RAM)等。示例性只读存储器(ROM)可包括光罩式只读存储器(MROM)、可编程只读存储器(PROM)、可擦除可编程只读存储器(EPROM)、电子式可擦除可编程只读存储器(EEPROM)、光盘只读存储器(CD-ROM)和数字通用磁盘ROM等。在一些实施例中，存储设备160可以在云平台上实现。仅作为示例，云平台可包括私有云、公共云、混合云、社区云、分布式云、内部云、多云等，或其任何组合。

在一些实施例中，存储设备160可以连接到网络120以与在线到离线服务系统100(例如，服务器110、服务请求者终端130或服务提供者终端140)的一个或多个组件通信。在线到离线服务系统100的一个或多个组件可以经由网络120访问存储在存储设备160中的数据或指令。在一些实施例中，存储设备160可以直接与在线到离线服务系统100(例如，服务器110、服务请求者终端130、服务提供者终端140)的一个或多个组件连接或通信。在一些实施例中，存储设备160可以是服务器110的一部分。

导航系统170可以确定与所述物体相关联的信息，例如，服务请求者终端130、服务提供者终端140、车辆150等中的一个或多个。在一些实施例中，导航系统170可以是全球定位系统(GPS)、全球导航卫星系统(GLONASS)、罗盘导航系统(COMPASS)、北斗导航卫星系统、伽利略定位系统、准天顶卫星系统(QZSS)等。该信息可包括该物体的位置、高度、速度或加速度，或当前时间。导航系统170可包括一个或多个卫星，例如，卫星170-1、卫星170-2和卫星170-3。卫星170-1至170-3可以独立地或共同地确定上述信息。卫星导航系统170可通过无线连接将上述信息发送到网络120、服务请求者终端130、服务提供者终端140或车辆150。

在一些实施例中，在线到离线服务系统100的一个或多个组件(例如，服务器110、服务请求者终端130、服务提供者终端140)可具有访问存储设备160的权限。在一些实施例中，当满足一个或多个条件时，在线到离线服务系统100的一个或多个组件可以读取和/或修改与乘客、服务提供者和/或公众有关的信息。例如，服务器110可以在服务完成之后读取和/或修改一个或多个乘客的信息。作为另一示例，服务器110可在服务完成之后读取和/或修改一个或多个服务提供者的信息。

在一些实施例中，可以通过请求服务来发起在线到离线服务系统100的一个或多个组件的信息交换。该服务请求的对象可以是任何产品。在一些实施例中，产品可包括食品、药品、商品、化学产品、电器、衣服、汽车、房屋、奢侈品等或其任何组合。在一些其他实施例中，产品可以包括服务产品、金融产品、知识产品、互联网产品等或其任何组合。互联网产品可包括单独的主机产品、网络产品、移动互联网产品、商业主机产品、嵌入式产品等或其任何组合。移动互联网产品可以用在移动终端的软件、程序、系统等中，或者它们的任何组合中。移动终端可包括平板电脑、笔记本电脑、移动电话、个人数字助理(PDA)、智能手表、销售终端(POS)设备、车载电脑、车载电视、可穿戴设备等等，或其任何组合。例如，该产品可以是在计算机或移动电话上使用的任何软件和/或应用程序。该软件和/或应用可涉及社交、购物、运输、娱乐、学习、投资等或其任何组合。在一些实施例中，与运输有关的软件和/或应用程序可包括旅行软件和/或应用程序、交通工具调度软件和/或应用程序、地图软件和/或应用程序等。在交通工具调度软件和/或应用中，交通工具可包括马、马车、人力车(例如，独轮车、自行车、三轮车等)、汽车(例如，出租车、公共汽车、私家车等)、火车、地铁、船舶、飞机(例如飞机、直升机、航天飞机、火箭、热气球等)等，或其任何组合。

本领域普通技术人员将理解的是，当在线到离线服务系统100的元件(或组件)执行时，该元件可以通过电信号和/或电磁信号执行。例如，当服务请求者终端130向服务器110发送服务请求时，服务请求者终端130的处理器可以生成编码该请求的电信号。然后，服务请求者终端130的处理器可以将电信号发送到输出端口。如果服务请求者终端130经由有线网络与服务器110通信，则输出端口可物理性地连接到电缆，电缆还可以将电信号发送到服务器110的输入端口。如果服务请求者终端130经由无线网络与服务器110通信，则服务请求者终端130的输出端口可以是一个或多个天线，该电线将电信号转换为电磁信号。类似地，服务提供者终端130可以经由电信号或电磁信号从服务器110接收指令和/或服务请求。在诸如服务请求者终端130、服务提供者终端140和/或服务器110的电子设备内，当其处理器处理指令时，如发出指令和/或执行动作时，指令和/或动作是通过电信号进行的。例如，当处理器从存储介质检索或保存数据时，它可以将电信号发送到存储介质的读/写设备，该读/写设备可以在存储介质中读取或写入结构化数据。结构化数据可以通过电子设备的总线以电信号的形式发送到处理器。这里，电信号可以指一个电信号，一系列电信号和/或多个离散电信号。

图2是根据本申请的一些实施例所示的计算设备200的示例性硬件和软件组件的示意图，服务器110、服务请求者终端130和/或服务提供者终端140可以在该组件上执行。例如，处理引擎112可以在计算设备200上执行，并且被配置为执行本申请中披露的处理引擎112的功能。

在一些实施例中，计算设备200可以是专用计算机。计算设备200可用于实现本申请的在线到离线系统。计算设备200可以执行文中所述的在线到离线服务的任何组件。在图1-2中，出于方便目的仅示出了一个这样的计算机设备。在提交本申请时，本领域普通技术人员将理解，与在本申请中描述的在线到离线服务有关的计算机功能可以在多个类似平台上以分布式方式实现，以分配处理负载。

例如，计算设备200可包括连接到与其连接的网络的COM端口250，以促进数据通信。计算设备200还可包括以一个或多个处理器的形式呈现的中央处理单元(CPU或处理器)220，用于执行程序指令。示例性计算机平台可包括内部通信总线210、程序存储器和不同形式的数据存储器，例如硬盘270、只读存储器(ROM)230或随机存取存储器(RAM)240，用于由计算机处理和/或传输的各种数据文件。示例性计算机平台还可包括存储在ROM 230、RAM240和/或由CPU/处理器220执行的其他类型的非暂时性存储介质中的程序指令。本申请的方法和/或过程可以用程序指令来实现。计算设备200还可包括输入/输出组件260，该组件支持计算机与计算机中其他组件(例如用户界面元件280)之间的输入/输出。计算设备200还可通过网络通信接收编程和数据。

仅为了说明，在计算设备200中仅描述了一个CPU/处理器220。然而，应当注意的是本申请中的计算设备200还可以包括多个CPU/处理器，因此本申请中描述的由一个CPU/处理器220执行的处理操作和/或方法步骤，也可以由多个CPU/处理器联合或单独执行。例如，如果在本申请中，计算设备200的CPU/处理器220执行步骤A和步骤B，则应该理解，步骤A和步骤B也可以由计算设备200的两个不同的CPU/处理器联合或分开执行。(例如，第一处理器执行步骤A，第二处理器执行步骤B，或者第一和第二处理器共同执行步骤A和B)。

图3是根据本申请的一些实施例所示的示例性移动设备300的示例性硬件和/或软件组件的示意图，使用终端可以在该组件上被执行。如图3所示，所述移动设备300可包括通信平台310、显示器单元320、图形处理单元(GPU)330、中央处理单元(CPU)340、输入/输出单元350、内存360和存储器390。在一些实施例中，任何其他合适的组件，包括但不限于系统总线或控制器(未示出)，也可以包括在移动设备300中。在一些实施例中，移动操作系统370(例如iOS^TM、Android^TM、Windows Phone^TM等)和一个或多个应用程序380可以从存储器390加载到内存360中，以便于由CPU340执行。应用程序380可包括浏览器或任何其他合适的移动应用程序，用于从处理引擎112接收和呈现与图像处理或其他信息相关的信息。用户与信息流的交互可以通过输入/输出单元350实现，该交互可通过网络120提供给处理引擎112和/或在线到离线服务系统100的其他组件。

为了实现本申请中描述的各种模块、单元及其功能，计算机硬件平台可以用作本申请描述的一个或多个元件的硬件平台。具有用户界面元件的计算机可用于实现个人计算机(PC)或任何其他类型的工作站或终端设备。如果适当编程，计算机也可以充当服务器。

图4是根据本申请的一些实施例所示的示例性处理引擎的模块图。处理引擎112可包括获取模块410、第一候选路径生成模块420、第二候选路径确定模块430、目标路径确定模块440和长度计算模块450。每个模块可以是设计用于执行某些动作的硬件电路，例如，根据存储在一个或多个存储介质中的一组指令，和/或硬件电路和一个或多个存储介质的任何组合。

获取模块410可被配置用来获得一个或多个请求。在一些实施例中，可以从一个或多个终端130中发送一个或多个请求。在一些实施例中，该一个或多个请求可以是在线到离线服务请求。以车辆在线到离线请求为例，一个或多个请求可以由一个或多个服务请求者(例如，乘客)通过一个或多个终端130发送。一个或多个请求中的每一个都包括服务请求者的信息，诸如起始位置、目的地位置、出发时间等。获取模块410还可被配置用于获得服务提供者的信息，例如起始位置、目的地位置、车辆类型、服务状态等。一个或多个起始位置，以及一个或多个目的地位置可以作为多个节点。起始位置可指代起始节点，目的地位置可以指代目的地节点。例如，服务请求者(例如，乘客)通过服务请求者终端130和服务器110可以向服务提供者终端140发送服务请求命令。服务请求订单涉及起始位置和目的地位置。起始位置可对应于起始节点，目的地位置可对应于目的地节点。在一些实施例中，一个或多个请求中的每一个请求可包括起始节点、目的地节点和一个或多个中间节点。服务请求者或服务提供者可选择或设置一个或多个中间节点。例如，服务提供者(例如，司机)可以将加油站设置为中间节点。在一些实施例中，该多个节点可包括服务提供者(例如，司机)的起始位置和目的地位置。在一些实施例中，服务提供者不具有特定目的地，行程的最终目的地是最后一个乘客的目的地。

第一候选路径生成模块420可被配置为用于生成多个第一候选路径。第一候选路径生成模块420可被配置为基于多个节点确定初始回路。在一些实施例中，初始回路可以是具有第一节点序列的欧拉回路。第一候选路径生成模块420可以基于第一节点序列和与多个节点相关的第一条件来确定多个第二节点序列。第一候选路径生成模块420可以基于多个第二节点序列确定多个第一候选路径。

第二候选路径确定模块430可被配置为用于从多个第一候选路径中确定出一个或多个第二候选路径。第二候选路径确定模块430可以从多个第一候选路径中确定出参考路径。第二候选路径确定模块430可以基于参考路径中的相邻节点之间的导航长度来确定参考路径的导航长度。第二候选路径确定模块430可以确定出一个或多个第二候选路径。第二候选路径的地理长度可能短于参考路径的导航长度。

目标路径确定模块440可被配置为将具有最短导航长度的第二候选路径指定为目标路径。在一些实施例中，目标路径确定模块440可基于一个或多个第二候选路径中的每一个的导航长度来确定目标路径。例如，目标路径的导航长度可能是一个或多个第二候选路径中最短的。在一些实施例中，目标路径确定模块440可以在考虑导航长度、速度限制和/或诸如交通状况、天气状况和道路工程安排等实时因素的前提下，基于行程时间确定目标路径。在一些实施例中，参考路径可以是目标路径，因为参考路径的导航长度可能是一个或多个第二候选路径中最短的。

长度计算模块450可被配置为用于计算多个节点中任何两个节点之间的长度。长度可包括球形长度、直线长度、导航长度等。在一些实施例中，长度计算模块450可以基于多个节点中任意两个节点之间的地理长度来确定多个第一候选路径中的每一个的地理长度。地理长度可以指两个节点之间的空间距离。在一些实施例中，长度计算模块450可基于参考路径中的相邻节点之间的导航长度来确定参考路径的导航长度。在一些实施例中，长度计算模块450可以确定一个或多个第二候选路径中的每一个的导航长度。

应当注意的是，提供以上关于处理引擎112的描述是出于说明的目的，并不旨在限制本申请的范围。对于本领域普通技术人员，在不违背本申请的原理的情况下，可以对上述方法和系统的应用的形式和细节进行各种修改和改变。然而，该类变化和修改也落入本申请的范围内。在一些实施例中，处理引擎112可包括一个或多个其他模块。例如，处理引擎112可包括存储模块，用于存储由处理引擎112中的模块生成的数据。在一些实施例中，任何两个模块可以组合为单个模块，并且任何一个模块可划分为两个或更多单元。

图5是根据本申请的一些实施例所示的用于确定目标路径的示例性过程的流程图。在一些实施例中，该确定目标路径的过程500可以由在线到离线服务系统100执行。例如，该确定目标路径的过程500可以被实现为存储在存储设备160中的一组指令(例如，应用程序)。在一些实施例中，处理引擎112可执行该组指令，并且可因此被指示在该在线到离线服务平台中执行该过程500。该平台可以是基于因特网的平台，其通过因特网连接服务提供者和请求者。

在步骤510中，处理引擎112(例如，获取模块410)可基于一个或多个请求获得多个节点。在被处理之后，该一个或多个请求可以对应于在线到离线服务订单(例如，拼车服务订单)。例如，拼车订单可包括来自服务请求者A的关于车辆的请求A1和来自服务请求者B的针对同一车辆的请求B1。该一个或多个请求中的每一个可包括起始位置和目的地位置。在一些实施例中，该请求的起始位置或目的地位置可称为节点。起始位置可指代起始节点，并且目的地位置可以指代目的地节点。例如，服务请求者(例如，乘客)可以通过服务请求者终端130和服务器110向服务提供者终端140发送请求。该请求可包括起始位置和目的地位置。起始位置可以对应于起始节点，目的地位置可对应于目的地节点。在一些实施例中，该一个或多个请求中的每一个可包括起始节点、目的地节点和一个或多个中间节点。该一个或多个中间节点可以由服务请求者或服务提供者选择或设置为经过的节点。例如，请求A1可包括起始节点和目的地节点，并且服务请求者A可以确定中间节点，该中间节点表明服务请求者A在从起始节点到目的地节点的行程期间想要通过该中间节点。

作为另一示例，处理引擎112(例如，获取模块410)可接收多个服务请求，例如接收包括第一服务请求者的第一服务请求和第二服务请求者的第二服务请求。第一服务请求订单可包括与第一节点相对应的第一服务请求的起始位置，以及与第二节点相对应的第一服务请求的目的地位置。第二服务请求订单可包括与第三节点相对应的第二服务请求的起始位置，以及与第四节点相对应的第二服务请求的目的地位置。此外，处理引擎112可获得六个节点，包括第一节点、第二节点、第三节点、第四节点、对应于服务提供者的起始位置的第五节点(例如，司机)、以及对应于服务提供者的目的地位置的第六节点。

在步骤520中，处理引擎112(例如，第一候选路径生成模块420)可串联多个节点以生成多个第一候选路径。例如，来自服务请求者A的请求A1可包括起始节点A'和目的地节点B'。来自服务请求者B的请求B1可以包括起始节点C'和目的地节点D'。处理引擎112可以将节点A'、节点B'、节点C'和节点D'串联在节点序列中，例如ABCD，表示车辆将以节点A'、节点B'、节点C'和节点D'的顺序进行，以生成第一候选路径。具体地，该多个第一候选路径可以满足与多个节点相关的第一条件。在第一候选路径中的服务请求的起始节点的优先级(优先级指的是路径中的队列位置)高于第一候选路径中的目的地节点的优先级。例如，根据该第一条件，在第一候选路径中，节点B'不会出现在节点A'之前，节点D'不会出现在节点C'之前。在一些实施例中，节点A'可以出现在节点C'之前或之后，节点B'可以出现在节点D'之前或之后。在图6中提供了关于生成多个第一候选路径的详细描述。

在步骤530中，处理引擎112(例如，长度计算模块450)可基于多个节点中任何两个节点之间的地理长度来确定多个第一候选路径中的每一个的地理长度。地理长度可以指两个节点之间的空间距离。两个节点之间的地理长度可以是由两个节点形成的线段的长度。在一些实施例中，考虑到地球具有球形形状，两个节点之间的地理长度可以是由地球上的两个节点形成的弧的长度。路径的地理长度(例如，第一候选路径)是该路径的多个节点的序列中的任何两个相邻节点之间的地理长度的总和。例如，使用步骤520中描述的示例，第一候选路径A'B'C'D'的地理长度可以指节点A'和B'、节点B'和C'、节点C'和D'的地理长度之和。又例如，处理引擎112(例如，长度计算模块450)可使用与两个节点相关的包括经纬度等的GPS数据来确定两个节点之间的地理长度。因此，在某些实施例中，确定地理长度不需要获得节点之间的导航信息。在一些实施例中，处理引擎112(例如，长度计算模块450)可以确定多个第一候选路径中的每一个的地理长度。

在步骤540中，处理引擎112(例如，第一候选路径生成模块420)可以从多个第一候选路径中确定出参考路径。在一些实施例中，参考路径是在多个第一候选路径中地理长度最短的第一候选路径。

在步骤550中，处理引擎112(例如，长度计算模块450)可基于参考路径中的相邻节点之间的导航长度来确定参考路径的导航长度。两个节点之间的导航长度可以被称为车辆驾驶时经过的长度。在一些实施例中，导航长度是从基于已建道路(链路)的路径中导出的。例如，处理引擎112可以确定参考路径中相邻节点之间的多个导航长度。参考路径可依次包括第一节点、第二节点、第三节点和第四节点。处理引擎112可以确定第一节点和第二节点之间的第一导航长度、第二节点和第三节点之间的第二导航长度、以及第三节点和第四节点之间的第三导航长度。此外，处理引擎112可通过计算第一导航长度、第二导航长度和第三导航长度的总和来确定参考路径的导航长度。关于确定参考路径的导航长度的详细内容可以参考图8及其相关描述。

在步骤560中，处理引擎112(例如，第二候选路径生成模块420)可从多个第一候选路径中确定出一个或多个第二候选路径。在一些实施例中，一个或多个第二候选路径中的每一个的地理长度可短于参考路径的导航长度。关于生成多个第一候选路径的详细内容可以参考图6及其相关描述。在一些实施例中，参考路径是第二候选路径之一。在一些实施例中，参考路径是唯一的第二候选路径，因为没有其他第一候选路径的地理长度比参考路径的导航长度更短。

在步骤570中，处理引擎112(例如，长度计算模块450)可确定一个或多个第二候选路径中的每一个的导航长度。以第二候选路径为例，确定第二候选路径的导航长度的方法可与步骤550中描述的确定参考路径的导航长度的方法相同。

步骤540-570提供了确定第二候选路径的示例，目标路径可以从该第二候选路径中选出。然而，应该注意的是，存在部分基于每一个第一候选路径的地理长度来确定第二候选路径的其他实施例。例如，在确定每个第一候选路径的地理长度之后，处理引擎112可选择固定数量(例如，1、2、3、5或10)的具有最短地理长度的第一候选路径作为第二候选路径。作为另一示例，处理引擎112可首先选择具有最短地理长度的第一候选路径作为参考路径，然后再选择出任何一个地理长度与参考路径有差值的第一候选路径，将其与参考路径进行比较，若差距小于预定阈值，则可以将该第一候选路径作为第二候选路径。

在步骤580中，处理引擎112(例如，目标路径确定模块440)可以从一个或多个第二候选路径中确定出目标路径。在一些实施例中，可以基于导航长度确定目标路径。例如，目标路径的导航长度可以是一个或多个第二候选路径中最短的。在一些实施例中，可以在考虑导航长度、速度限制和/或诸如交通状况、天气状况和道路工程安排等实时因素的情况下，基于行驶时间来确定目标路径。在一些实施例中，参考路径可以是目标路径，因为参考路径的导航长度可能是一个或多个第二候选路径中最短的。

应当注意的是，过程500的以上描述是出于说明的目的而提供的，并不旨在限制本申请的范围。对于本领域普通技术人员，在不脱离本申请的原理的情况下，可以对上述方法和系统在应用时的形式和细节进行各种修改和改变。然而，那些变化和修改也落入本申请的范围内。在一些实施例中，可以添加或省略一个或多个步骤。例如，步骤540和550可合并为一个步骤。作为另一示例，步骤560和570可合并为一个步骤。

图6是根据本申请的一些实施例所示的用于确定多个第一候选路径的示例性过程的流程图。在一些实施例中，过程600可以由在线到离线服务系统100执行。例如，过程600可以由存储在存储设备160中的一组指令(例如，应用程序)来实现。在一些实施例中，处理引擎112可以执行该组指令，并且因此可以被用来在该在线到离线服务平台中执行过程600。该平台是基于因特网的平台，其通过因特网连接服务提供者和服务请求者。

在步骤610中，处理引擎112可基于多个节点确定初始回路。在一些实施例中，初始回路是具有第一节点序列的欧拉回路。可以基于Christo fides算法和车辆路线规划(VRP)来确定具有第一节点序列的欧拉回路。欧拉回路是指包括仅经过多边中每个边一次的多个边的路径。例如，服务提供者或车辆可以从节点A'行进，经过节点B'、节点C'、节点D'、节点E'、节点F'、节点G'和节点H'，并返回到节点A'。这些点或节点的序列可称为第一节点序列。例如，用于表示服务提供者的行程的欧拉回路可以由第一节点序列表示(例如，A'B'C'D'E'F'G'H'A')。在一些实施例中，处理引擎112可确定多个节点中的一个或多个欧拉回路。

在步骤620中，处理引擎112可基于第一节点序列和与多个节点相关的第一条件来确定多个第二节点序列。在一些实施例中，处理引擎112可以基于第一节点序列和与多个节点相关的第一条件，使用2-opt算法来确定多个第二节点序列。例如，步骤610中描述的欧拉回路(例如，A'B'C'D'E'F'G'H'A')可包括第一节点序列，例如A'→B'→C'→D'→E'→F'→G'→H'→A'。通过随机选择两个节点i和k(例如，i＝4即节点D'，k＝7即节点G')，可以通过依次组合初始节点序列中在节点i之前的第一区段来确定第二节点序列(即，A'→B'→C')，通过反转第一节点序列的第二区段而获得的从节点i到节点j的反转节点序列(即，G'→F'→E'→D')，以及节点j之后的初始节点序列的第三区段(即，H'→A')。第二节点序列可以由“A'→B'→C'→G'→F'→E'→D'→H'→A'”表示。同理，处理引擎112可以确定多个第二节点序列。此外，处理引擎112可通过应用与多个节点相关的第一条件来确定多个第二节点序列。例如，如果节点B'是服务请求A1的起始节点、节点D'是服务请求A1的目的地节点、节点E'是服务请求B1的起始节点、节点H'是服务请求B1的目的地节点，若在节点序列中，节点D'出现在节点B'之前或节点H'出现在节点E'之前，那么该节点序列不是第二节点序列。

在步骤630中，处理引擎112可基于多个第二节点序列确定多个第一候选路径。第二节点序列可对应于第一候选路径。例如，第二序列可以由“A'→B'→C'→G'→F'→E'→D'→H'→A'”表示。处理引擎112可以通过串联第二序列“A'→B'→C'→G'→F'→E'→D'→H'→A'”中的多个节点来生成第一候选路径。

图7是根据本申请的一些实施例所示的用于确定第二候选路径的示例性过程的流程图。在一些实施例中，过程700可以由在线到离线服务系统100执行。例如，过程700可以由存储在存储设备160中的一组指令(例如，应用程序)来实现。在一些实施例中，处理引擎112可执行该组指令，并且因此可被指示在该在线到离线服务平台中执行过程700。该平台可以是基于因特网的平台，其通过因特网连接服务提供者和请求者。

在步骤710中，处理引擎112可以确定参考路径的地理长度与每一个第一候选路径的地理长度之间的多个第一差值。参考路径的地理长度可以由Q0表示。多个第一候选路径的地理长度可以由Q1、Q2、...、Qn表示，其中n表示第一候选路径的数量。参考路径的地理长度与每一个第一候选路径的地理长度之间的多个第一差值可以由Q1-Q0、Q2-Q0、......、Qn-Q0表示。在一些实施例中，Q0是Q1-Qn之一。在一些实施例中，地理长度和第一差值的确定不需要访问或利用导航系统。

在步骤720中，处理引擎112可基于参考路径的导航长度与参考路径的地理长度之间的差值来确定第一参数。在一些实施例中，参考路径的导航长度可以由N0表示。参考路径的导航长度与参考路径的地理长度之间的差值可以由N0-Q0表示。此外，处理引擎112可基于参考路径的导航长度与参考路径的地理长度之间的差值来确定第一参数。在一些实施例中，第一参数可等于参考路径的导航长度与参考路径的地理长度之间的差值(即，N0-G0)。在一些实施例中，第一参数可等于参考路径的导航长度与参考路径的地理长度之间的差值的百分比(例如，(N0-G0)*80％)。

在步骤730中，如果第一候选路径对应的第一差值小于第一参数，则处理引擎112可将该第一候选路径分配为第二候选路径。例如，如果第一候选路径对应的第一差值(例如，Q2-Q0)小于第一参数(例如，N0-G0)，则处理引擎112可分配该第一候选路径(即，对应于地理长度Q2的第一候选路径)作为第二候选路径。同理，处理引擎112可以从多个第一候选路径中确定出一个或多个第二候选路径。

图8是根据本申请的一些实施例所示的用于确定参考路径的导航长度的示例性过程的流程图。在一些实施例中，过程800可以由该在线到离线服务系统100执行。例如，过程800可以由存储在存储设备160中的一组指令(例如，应用程序)来实现。在一些实施例中，处理引擎112可执行该组指令并因此可被指示在该在线到离线服务平台上执行过程800。该平台是基于因特网的平台，其通过因特网连接服务提供者和请求者。

参考路径可包括多个区段。每个区段可指参考路径的两个相邻节点的连接。区段可指代两个不同节点之间的连接。在步骤810中，处理引擎112可获得包括参考路径多个区段的参考区段集。例如，参考路径可以由“1→2→3→4”表示，并且参考区段集可包括参考路径的多个区段，例如“1→2”，“2→3”，和“3→4”。从1到4的数字可表示多个节点。

在步骤820中，处理引擎112可以确定参考区段集中的每个区段的导航长度，以确定参考路径的导航长度。例如，参考区段集可包括参考路径的多个区段，例如“1→2”、“2→3”和“3→4”。处理引擎112可以确定区段(“1→2”)的第一导航长度、区段(“2→3”)的第二导航长度和区段(“3→4”)的第三导航长度。此外，处理引擎112通过计算区段(“1→2”)的第一导航长度、区段(“2→3”)的第二导航长度和区段(“3→4”)的第三个导航长度的总和来确定参考路径的导航长度。

图9是根据本申请的一些实施例所示的用于确定一个或多个第二候选路径中的每一个的导航长度的示例性过程的流程图。在一些实施例中，过程900可以由该在线到离线服务系统100执行。例如，过程900可以由存储在存储设备160中的一组指令(例如，应用程序)来实现。在一些实施例中，处理引擎112可执行该组指令，并因此被指示在该在线到离线服务平台中执行过程900。该平台可以是基于因特网的平台，其通过因特网连接服务提供者和请求者。

每个候选路径可包括多个区段。区段指的是两个不同节点之间的连接。在步骤910中，处理引擎112可以确定出参考路径和第二候选路径之间的一个或多个不同区段。例如，参考路径的多个区段可包括“1→2”、“2→3”和“3→4”。候选路径(例如，第一候选路径或第二候选路径)可以由“1→3→2→4”表示，并且候选路径可包括多个区段，例如“1→3”、“3→2”和“2→4”。参考路径和第二候选路径之间的一个或多个不同区段可包括“1→3”、“3→2”和“2→4”。

在步骤920中，处理引擎112可将一个或多个不同区段添加到参考区段集中。例如，参考路径的多个区段可以包括“1→2”，“2→3”和“3→4”。第二候选路径可以由“1→3→2→4”表示，并且该候选路径可包括多个区段，例如“1→3”，“3→2”和“2→4”。参考路径和第二候选路径之间的一个或多个不同区段可以包括“1→3”、“3→2”和“2→4”。处理引擎112可以将一个或多个不同的区段添加到参考区段集中，即参考区段集可包含新的多个区段，包括“1→2”、“2→3”、“3→4”、“1→3”、”3→2“和”2→4“。处理引擎112可以将参考区段集存储到存储设备160中。

在步骤930中，处理引擎112可基于参考区段集确定第二候选路径的导航长度。处理引擎112可以确定第二候选路径的多个区段并从存储设备160中检索第二候选路径的多个区段。例如，对于第二候选路径“1→3→2→4”，处理引擎112可以检索预先存储在存储设备160中的“1→3”、“3→2”和“2→4”。

上文已对基本概念做了描述，显然，对于本领域技术人员来说，上述详细披露仅仅作为示例，而并不构成对本申请的限定。虽然此处并没有明确说明，本领域技术人员可能会对本申请进行各种修改、改进和修正。该类修改、改进和修正在本申请中被建议，所以该类修改、改进、修正仍属于本申请示范实施例的精神和范围。

此外，本申请使用了特定词语来描述本申请的实施例。例如，术语“一个实施例”，“一实施例”和/或“一些实施例”意指与本申请至少一个实施例相关的某一特征、结构或特点。因此，应该强调并注意的是，在本说明书的各个部分中对“实施例”、“一个实施例”或“一替代性实施例”的两次或更多次引用不一定都指代相同的实施例。此外，本申请的一个或多个实施例中的某些特征、结构或特点可以进行适当的组合。

此外，本领域技术人员可以理解，本申请的各方面可以通过若干具有可专利性的种类或情况进行说明和描述，包括任何新的和有用的工序、机器、产品或物质的组合，或对他们的任何新的和有用的改进。相应地，本申请的各方面可以完全由硬件执行、可以完全由软件(包括固件、常驻软件、微码等)执行、也可以由硬件和软件组合执行。以上硬件或软件均可被称为“数据块”、“模块”、“引擎”、“单元”、“组件”或“系统”。此外，本申请的各方面可能表现为位于一个或多个计算机可读介质中的计算机产品，该产品包括计算机可读程序编码。

计算机可读信号介质可包括一个内含有计算机可读程序编码的传播数据信号，例如在基带中或作为载波的一部分。这种传播信号可能采用多种表现形式，包括电磁形式、光形式等，或合适的组合形式。计算机可读信号介质可以是除计算机可读存储介质之外的任何计算机可读介质，该介质可以通过连接至一个指令执行系统、装置或设备以实现通讯、传播或传输供使用的程序。位于计算机可读信号介质上的程序代码可以通过任何合适的介质进行传输，包括无线电、电缆、光纤电缆、RF等，或者任何上述介质的组合。

用于执行本申请各方面的操作的计算机程序代码可以用任意一种或多种编程语言来编写，包括面向对象编程语言如Java、Scala、Smalltalk、Eiffel、JADE、Emerald、C++、C#、VB.NET、Python等，传统的面向过程编程语言如“C”语言、Visual Basic、Fortran 1703、Perl、COBOL 1702、PHP、ABAP，动态编程语言如Python、Ruby和Groovy，或其他编程语言。该程序代码可以完全在用户的计算机上运行，或作为独立的软件包在部分用户的计算机上运行，部分在用户的计算机上运行部分在远程计算机上运行，或完全在远程计算机或服务器上运行。在后一种情况下，远程计算机可以通过任何类型的网络连接到用户的计算机，包括局域网(LAN)或广域网(WAN)，或者可以连接到外部计算机(例如，使用互联网服务提供者通过互联网)或在云计算环境中，或作为服务使用例如软件即服务(SaaS)。

此外，除非权利要求中明确说明，本申请所述处理元素和序列的顺序、数字字母的使用、或其他名称的使用，并非用于限定本申请过程和方法的顺序。尽管上述披露中通过各种示例讨论了一些目前认为有用的实施例，但是应该理解的是，该类细节仅起到说明的目的，附加的权利要求并不仅限于披露的实施例，相反，权利要求旨在覆盖所有符合本申请实施例实质和范围的修正和等价组合。例如，虽然以上所描述的系统组件可以通过硬件设备实现，但是也可以只通过软件的解决方案得以实现，如在现有的服务器或移动设备上安装所描述的系统。

同理，应当注意的是，在对本申请的实施例的前述描述中，出于简化本申请的目的，有时将各种特征归并在单个实施例、附图或对其的描述中，以帮助理解本申请中的一个或多个实施例。然而，这种披露方法并不意味着本申请对象所需要的特征比权利要求中提及的特征多。而是，所要求保护的公开对象的特征可以少于单个前述公开实施例的所有特征。

Claims (14)

1.一种用于路径确定方法，该方法包括：

串联多个节点以生成多个第一候选路径，其中所述多个节点是基于一个或多个请求确定的，并且所述多个第一候选路径满足与该多个节点相关的第一条件；

基于多个节点中的任意两个节点之间的地理距离确定多个第一候选路径中的每一个的地理长度；

从多个第一候选路径中确定参考路径，其中，所述参考路径的地理长度在多个第一候选路径中最短；

基于所述参考路径中相邻节点之间的导航长度确定所述参考路径的导航长度；

基于所述多个第一候选路径中的每一个的地理长度，从所述多个第一候选路径中确定出一个或多个第二候选路径，其中所述第二候选路径的地理长度短于所述参考路径的导航长度；

确定一个或多个第二候选路径中的每一个的导航长度；

基于所述一个或多个第二候选路径中的每一个的导航长度、速度限制和/或实时因素，确定一个或多个第二候选路径中每一个的行驶时间；

基于所述行驶时间从一个或多个第二候选路径中确定目标路径。

2.如权利要求1所述的方法，其中，所述目标路径的行驶时间是所述一个或多个第二候选路径中最短的。

3.如权利要求1所述的方法，其中，所述实时因素包括交通状况、天气状况和道路工程安排中的一种或多种的组合。

4.如权利要求1所述的方法，其中，每个请求包括起始节点和目的地节点，并且第一条件是第一候选路径中的起始节点的优先级高于第一候选路径中的目的地节点的优先级。

5.如权利要求1中任一项所述的方法，其中，为了生成多个第一候选路径，所述方法还包括：

基于多个节点确定初始回路，其中初始回路是具有第一节点序列的欧拉回路；

基于第一节点序列和与多个节点相关的第一条件来确定多个第二节点序列；

基于所述多个第二节点序列确定多个第一候选路径。

6.如权利要求5所述的方法，其中，欧拉回路是基于Christofides算法确定的。

7.如权利要求5或6所述的方法，其中，所述多个第二节点序列是基于2-opt算法确定的。

8.如权利要求1所述的方法，其中，为了从所述多个第一候选路径中确定出一个或多个第二候选路径，所述方法还包括：

确定参考路径的地理长度与多个第一候选路径中的每一个的地理长度之间的多个第一差值；

基于参考路径的导航长度与参考路径的地理长度之间的差值来确定第一参数；

如果第一候选路径对应的第一差值小于第一参数，则将该第一候选路径分配为第二候选路径。

9.如权利要求1或8所述的方法，其中：

每个第二候选路径包括一个或多个区段，每个区段连接第二候选路径中的两个相邻节点，

为了确定参考路径的导航长度，该方法还包括：

获得包括参考路径多个区段的参考区段集，和

确定参考区段集中每个区间的导航长度以确定参考路径的导航长度。

10.如权利要求9所述的方法，其中：

为了确定一个或多个第二候选路径中的每一个的导航长度，该方法还包括：

确定参考路径和第二候选路径之间的一个或多个不同区段；

将该一个或多个不同的区段添加到参考区段集中；和

基于参考区段集确定第二候选路径的导航长度。

11.如权利要求10所述的方法，其中，如果出现以下情况，则第二候选路径的该区段不是不同的区段：

第二候选路径的该区段的节点序列与参考路径的某区段的节点序列相反，并且

该区段的导航长度与地理长度之间的差值不超过阈值。

12.一种用于路径确定的系统，其中，所述系统包括第一候选路径生成模块、长度计算模块、第二候选路径确定模块和目标路径确定模块；其中：

所述第一候选路径生成模块，用于串联多个节点以生成多个第一候选路径，其中所述多个第一候选路径满足与所述多个节点相关的第一条件；

所述长度计算模块，用于基于多个节点中的任意两个节点之间的地理距离确定多个第一候选路径中的每一个的地理长度；

所述第二候选路径确定模块，用于：

从多个第一候选路径中确定参考路径，其中，所述参考路径的地理长度在多个第一候选路径中最短；

基于所述参考路径中相邻节点之间的导航长度确定所述参考路径的导航长度；以及，

基于所述多个第一候选路径中的每一个的地理长度，从所述多个第一候选路径中确定出一个或多个第二候选路径，其中所述第二候选路径的地理长度短于所述参考路径的导航长度；

所述长度计算模块，用于确定一个或多个第二候选路径中的每一个的导航长度；

所述目标路径确定模块，用于基于所述一个或多个第二候选路径中的每一个的导航长度、速度限制和/或实时因素，确定一个或多个第二候选路径中每一个的行驶时间；以及基于所述行驶时间从一个或多个第二候选路径中确定目标路径。

13.一种用于路径确定的装置，其中，所述装置包括至少一个处理器和至少一个存储设备，所述存储设备用于存储指令，当所述至少一个处理器执行所述指令时，实现如权利要求1～11中任一项所述的方法。

14.一种计算机可读存储介质，所述存储介质存储计算机指令，当计算机读取所述存储介质中的所述计算机指令后，所述计算机执行如权利要求1～11中任一项所述的方法。

Images