CN114424027A

CN114424027A - System and method for route mapping with familiar routes

Info

Publication number: CN114424027A
Application number: CN202080065149.1A
Authority: CN
Inventors: 张安; 文森特·范; 杰里米·古德西特; 奥斯丁·沃尔特斯; 马克·沃森
Original assignee: Capital One Services LLC
Current assignee: Capital One Services LLC
Priority date: 2019-07-16
Filing date: 2020-07-13
Publication date: 2022-04-29
Also published as: WO2021011446A1; CA3143972A1; US10794715B1; US20210088344A1; US11692835B2; EP3999809A1

Abstract

Systems and methods for route mapping with familiar routes include balancing an optimal route from a standard navigation system that minimizes time and distance with mapping components that suggest familiar routes based on a user's route history. New routes including one or more familiar routes may be suggested to the user when they are not too far detoured or take too long compared to the optimal route, and when they may be more preferred or comfortable.

Description

System and method for route mapping with familiar routes

Technical Field

The present disclosure relates generally to route mapping or route planning, and more particularly, to systems and methods for route mapping with familiar routes.

Background

Currently, route drawing, planning, or navigation systems provide optimal routes based on minimizing time or distance. These so-called optimal routes are sometimes difficult and confusing for the user to follow. Inconvenient routes, while optimal in terms of time or distance, may involve trails or many turns. The so-called optimal route may cause unnecessary trouble. They even add time when the user must spend additional time understanding and following the instructions. They may even increase the distance when it takes too long to change track, or somehow misses a turn and has to be recalculated. Inconvenient routes can be particularly difficult for young drivers, inexperienced drivers, elderly drivers, or disabled drivers.

There is a need for an alternative to the traditional so-called optimal route, which finds an easier, more pleasant and more comfortable route. Such routes are familiar routes that the user has previously traveled, and the user has local knowledge and personal preferences about the optimal route. When a user is familiar with a route, they can travel the familiar route in about the same amount of time without the problems or obstacles they may face on an unfamiliar route, even if the route is five minutes or slightly longer than the so-called optimal route.

Disclosure of Invention

The disclosed subject matter relates to systems and methods for route mapping with familiar routes that meet these needs.

One embodiment of the present disclosure may be a route drawing system including a server and a navigation application. The server may include a processor in data communication with the memory. The navigation application may be stored in memory. The navigation application may include a route recorder and a drawing component.

The route recorder, when executed by the processor, may collect route history data associated with the user. Route history data may include origin information, destination information, and location information about one or more routes traversed by the user. The route recorder may store route history data in a route history database.

The rendering component, when executed by the processor, may receive an origin selection and a destination selection from a user. The mapping component can generate an optimal route from the origin selection to the destination selection. The mapping component may select a familiar route from the route history data based on the optimal route, wherein the familiar route has a familiar origin and a familiar destination. The drawing component can generate an origin route selected from a familiar origin to an origin. The mapping component may generate a destination route selected from a familiar destination to a destination. The mapping component may generate a new route from the origin selection to the destination selection, wherein the new route includes the origin route, the familiar route, and the destination route. The mapping component may generate comparison information between the new route and the optimal route. The mapping component may communicate the optimal route, the new route, and the comparison information for display on a user device associated with the user.

The comparison information may include a comparison of the estimated travel time for the optimal route and the estimated travel time for the new route. The comparison information may include a notification to the user if the estimated travel time for the new route exceeds the estimated travel time for the optimal route by a predetermined threshold. The comparison information may include a comparison of the estimated travel distance for the optimal route and the estimated travel distance for the new route. The comparison information may include a notification to the user if the estimated distance traveled for the new route exceeds the estimated distance traveled for the optimal route by a predetermined threshold.

The familiar route may include a first familiar route segment and a second familiar route segment.

The drawing component can generate a first connection route, a second connection route, and a third connection route. The first connection route connects the first learned route segment to the second connection route. The second connection route connects the first connection route to the third connection route. The third connection route connects the second connection route to the second learned route segment. The new route may include a first familiar route segment to a first connected route to a second connected route to a third connected route to a second familiar route segment.

The route recorder may store location information and time information at a plurality of points along one or more routes in the route history data. The route recorder may generate weights for one or more routes in the route history data. The weight may represent a travel cost derived from the location information and the time information. The rendering component may minimize driving costs.

One embodiment of the present disclosure may be a route drawing method. Route history data associated with the user may be collected. Route history data may include origin information, destination information, and location information about one or more routes traversed by the user. Route history data may be stored in a route history database. An origination selection and a destination selection may be received from a user. An optimal route from the origin selection to the destination selection may be generated. A familiar route may be selected from the route history data based on the optimal route. Familiar routes have familiar origins and familiar destinations. An origin route may be generated that is selected from a familiar origin to an origin. A destination route selected from a familiar destination to a destination may be generated. A new route may be generated from the origination selection to the destination selection. The new route may include an origin route, a familiar route, and a destination route. Comparison information between the new route and the optimal route may be generated. The comparison information may include an estimated travel time difference between the optimal route and the new route, and an estimated travel distance difference between the optimal route and the new route. The optimal route may be communicated for display on a user device associated with the user. When the estimated travel time difference does not exceed the travel time threshold and/or the estimated travel distance difference does not exceed the travel distance threshold, transmitting the new route and the comparison information for display on the user device.

The route mapping method may include receiving a travel time threshold and/or a travel distance threshold from a user. The route mapping method may include determining a travel time threshold and/or a travel distance threshold from route history data. The familiar route may include a first familiar route segment and a second familiar route segment. The route drawing method may include generating a first connection route, a second connection route, and a third connection route, wherein the first connection route connects the first familiar route segment to the second connection route, the second connection route connects the first connection route to the third connection route, and the third connection route connects the second connection route to the second familiar route segment. The new route may include a first familiar route segment to a first connected route to a second connected route to a third connected route to a second familiar route segment. The route drawing method may include generating a modified origin route and a modified destination route, wherein the modified origin route connects the origin selection to the first familiar route and the modified destination route connects the second familiar route to the destination selection, and the new route includes the modified origin route and the modified destination route.

One embodiment of the present disclosure may be a route drawing application. The route mapping application may include a route recorder, a route history database, a mapping component, and a communications component. The route recorder may collect route history data associated with the user. Route history data may include origin information, destination information, and location information about one or more routes traversed by the user. The route history database may store route history data collected by the route recorder.

The drawing component can receive an origin selection and a destination selection from a user. The mapping component can generate an optimal route from the origin selection to the destination selection. The mapping component may select a familiar route from the route history data based on the optimal route, wherein the familiar route has a familiar origin and a familiar destination. The drawing component can generate an origin route selected from a familiar origin to an origin. The mapping component may generate a destination route selected from a familiar destination to a destination. The mapping component may generate a new route from the origin selection to the destination selection, wherein the new route includes the origin route, the familiar route, and the destination route. The mapping component may generate comparison information between the new route and the optimal route. The mapping component may communicate the optimal route, the new route, and the comparison information for display on a user device associated with the user. The familiar route may include a first familiar route and a second familiar route.

The drawing component can generate a first connection route, a second connection route, and a third connection route. The first connection route connects the first familiar route to the second connection route. The second connection route connects the first connection route to the third connection route. The third connection route connects the second connection route to the second familiar route. The new route may include a first familiar route to a first connecting route to a second connecting route to a third connecting route to a second familiar route.

The mapping component may generate a modified origin route and a modified destination route. The modified origin route connects the origin selection to the first familiar route, and the modified destination route connects the second familiar route to the destination selection. The new route includes a modified origin route and a modified destination route.

The comparison information may include a comparison of the estimated travel distance for the optimal route and the estimated travel distance for the new route.

The comparison information may include a notification to the user if the estimated distance traveled for the new route exceeds the estimated distance traveled for the optimal route by a predetermined threshold.

These and other features, aspects, and advantages of the disclosed subject matter are explained in more detail with reference to specific example embodiments that are illustrated in the following description, appended claims, and accompanying drawings, in which like elements are referred to with like reference numerals.

Drawings

FIG. 1 is a diagram of a route drawing system, according to an example embodiment.

FIG. 2 is a diagram of a route mapping system, according to an example embodiment.

FIG. 3 is a flow chart of a route drawing method according to an example embodiment.

FIG. 4 is a map according to an example embodiment.

Detailed Description

The following description of embodiments provides non-limiting representative examples of reference numbers that particularly describe features and teachings of various aspects of the present invention. The described embodiments should be considered to be capable of being implemented separately from or in combination with other embodiments from the description of the embodiments. Those of ordinary skill in the art, with access to the description of the embodiments, will be able to learn and understand the various described aspects of the present invention. The description of the embodiments should facilitate an understanding of the invention to the extent that other embodiments not specifically contemplated, but within the knowledge of one of ordinary skill in the art having read the description of the embodiments, will be understood to be consistent with the application of the present invention.

Fig. 1 is a schematic diagram of a route drawing system 100, according to an example embodiment. Route mapping system 100 may include a user device 102 connected by a network 104 to a server 106.

The user device 102 may be a network-enabled cmputer. As referred to herein, a network-enabled computer may include, but is not limited to, for example, any computer device or communication device, including, for example, a server, a network appliance, a Personal Computer (PC), a workstation, a mobile device, a telephone, a handheld PC, a Personal Digital Assistant (PDA), a thin client, a thick client, an internet browser, or other device. One or more network-enabled computers may execute one or more software applications to enable, for example, network communications. The mobile device may include: from

The iPhone, iPod, iPad or any other mobile device running the iOS operating system of Apple; running Google

Any device that operates a system, including, for example, Google's wearable device, Google glasses (Google Glass); running Microsoft

Any device that moves an operating system; and/or any other smart phone or any wearable mobile device.

The network 104 may be one or more of a wireless network, a wired network, or any combination of wireless and wired networks. For example, the network 104 may include one or more of the following: fiber optic networks, passive optical networks, cable networks, internet networks, satellite networks, wireless LANs, global system for mobile communications (GSM), Personal Communication Services (PCS), Personal Area Networks (PANs), D-AMPS, Wi-Fi, fixed wireless data, IEEE 802.11b, 802.15.1, 802.11n, and 802.11g, or any other wired or wireless network for transmitting and receiving data signals.

Additionally, the network 104 may include, but is not limited to: telephone lines, fiber optics, IEEE ethernet 902.3, a Wide Area Network (WAN), a Local Area Network (LAN), or a global network such as the internet. Additionally, the network 104 may support an internet network, a wireless communication network, a cellular network, and the like, or any combination thereof. The network 104 may further include one network or any number of the example types of networks described above, operating as standalone networks or cooperating with each other. Network 104 may utilize one or more protocols of one or more network elements to which they are communicatively coupled. Network 104 may translate to one or more protocols of the network device or from other protocols to one or more protocols of the network device. Although network 104 is depicted as a single network, it should be understood that network 104 may include multiple interconnected networks, such as, for example, the Internet, a service provider's network, a cable television network, a corporate network, and a home network, in accordance with one or more embodiments.

The server 106 may be a network-enabled computer that includes a memory 108. Memory 108 may include Random Access Memory (RAM), dynamic RAM (dram), static RAM (sram), Read Only Memory (ROM), or any other type of internal, external, primary/secondary memory or storage device, such as a Hard Disk Drive (HDD), Compact Disk (CD), or Universal Serial Bus (USB) flash drive, or a database. The memory 108 may include a route history database 116. The memory 108 may store software for execution by a processor in the server 106.

The memory 108 may include a navigation application 110, a route recorder 112, and a drawing component 114. Given an origin address and a destination address, the navigation application 110 may generate one or more optimal routes. The navigation application 110 may be any application that provides navigation directions in real time, such as

Apple

Or Google

The navigation application 110, route recorder 112, and mapping component 114 may use a Global Positioning System (GPS) radio navigation system.

The Global Positioning System (GPS) is a global radio navigation system consisting of a constellation of 24 satellites and their ground stations. The global positioning system is mainly subsidized and controlled by the united states department of defense (DOD). The system was originally designed for the operation of the U.S. military. Today, however, there are many civilian users of GPS worldwide as well. Civilian users are allowed to use standard location services without any kind of charging or restriction.

The route recorder 112 may be any kind of GPS tracking system. GPS tracking may be any system or method of determining the position and/or motion of an object. The GPS tracking system may be placed, for example, in a vehicle, on a cell phone, or on a specific GPS device, which may be a fixed or portable unit. GPS systems and methods can provide accurate location information. GPS tracking can track the movement of vehicles or people. So, for example, GPS tracking systems may be used by companies to monitor the route and progress of delivery trucks, by parents to check the location of their children, or to monitor high value assets in transit.

The GPS tracking system may use a Global Navigation Satellite System (GNSS) network. GNSS may incorporate a series of satellites that use microwave signals that are transmitted to GPS devices to provide information about location, vehicle speed, time, and direction. Therefore, the GPS tracking system can potentially give both real-time and historical navigation data about any kind of trip.

The GPS may provide special satellite signals that are processed by the receiver. These GPS receivers are not only able to track accurate position, but also to calculate speed and time. With the help of four GPS satellite signals, the position can even be calculated in a three-dimensional view. The spatial portion of the GPS may include 27 earth orbiting GPS satellites. There may be 24 satellites in operation and 3 additional satellites (to prevent one of them from malfunctioning) that orbit the earth once every 12 hours and transmit radio signals from space that are received by a GPS receiver.

The control of the positioning system may include different tracking stations located around the globe. These monitoring stations can help track signals from GPS satellites that continue to orbit the earth. Spacecraft transmit microwave carrier signals. Users of the global positioning system have GPS receivers that can convert these satellite signals so that the GPS receivers can estimate actual position, velocity, and time.

The operation of the system is based on a simple mathematical principle called trilateration. Trilateration is divided into two categories: 2-D trilateration and 3-D trilateration. In order to perform simple mathematical calculations, the GPS receiver must know two things. First, it must know that the location of the site is to be tracked by at least three satellites above the site. Second, it must know the distance between the site and each of those space vehicles. The device has multiple receivers that simultaneously acquire signals from several GPS satellites. These radio waves are electromagnetic energy that propagates at the speed of light.

The GPS tracking system may operate in various ways. From a commercial perspective, GPS devices are commonly used to record the position of a vehicle as it travels. Some systems may store data in the GPS tracking system itself (referred to as passive tracking), while some systems periodically send information to a central database or system via a modem or bi-directional GPS within the GPS system device (referred to as active tracking).

A passive GPS tracking system may monitor locations and store trip data thereof based on certain types of events. So, for example, a passive GPS system may record data such as where the device has traveled over the past 12 hours. The data stored on such GPS tracking systems is typically stored in internal memory or memory cards and can later be downloaded to a computer for analysis. In some cases, the data may be automatically transmitted at a predetermined location/time for wireless download, or may be requested at a specific location during the trip.

Active GPS tracking systems are also referred to as real-time systems because the method can automatically send information on the GPS system to a central tracking portal or system in real-time as it occurs. Such a system is often a better choice for business purposes such as fleet tracking or monitoring of people such as children or elderly people, as it allows caregivers to know exactly where lovers are, if they are on time, and if they are in what should be during a trip. This is also an effective way to monitor the behavior of employees in performing work and to simplify the internal processes and procedures for a fleet of freight vehicles.

Route recorder 112 collects historical data about the user, such as daily home-to-work, home-to-shopping routes, based on the location of user device 102 and/or GPS searches. Route recorder 112 may store the information in route history database 116. Route history database 116 may be any organized collection of data accessible on server 106 and may be any type of database, such as a relational database management system (RDBMS) using Structured Query Language (SQL). Route history database 116 may be stored in memory 108 or in a separate memory or storage device accessible to server 106.

The navigation application 110 may be any application that provides navigation directions in real time, such as

Apple

Or Google

Given an origin address and a destination address, the navigation application 110 may generate one or more optimal routes. The mapping component 114 may select one or more familiar routes that are close to, but different from, the optimal route generated by the navigation application 110. The mapping component 114 may then add any transition segments as needed to incorporate the familiar route into the new route. A new route from a given origin and destination may combine a partially familiar route with a partially optimal route. If the total time of the new route is greater than a threshold (e.g., 5-10 minutes for short distances, or 15-30 minutes for long distances), the drawing component 114 can notify the user whether to select the option.

The user device 102 may include a navigation app that interacts with a navigation application 110 on the server 106. For example, the user device 102 may be a device that includes a GPS navigation software app

A smart phone inside, and the server 106 may be

And (4) a server.

Providing turn-by-turn) Navigation information and travel time and route details submitted by the user, while location related information is downloaded over the mobile phone network.

Map data, travel time and traffic information are collected from a user and transmitted to

And (4) a server.

The user may report traffic accidents, traffic jams, speeds and police traps, and may update roads, landmarks, house numbers, etc. from the online map editor.

Anonymous information, including the user's speed and location, is sent back to its database to improve overall service. Based on the information collected in the collection of information,

route and real-time traffic updates may be provided.

The server uses a routing algorithm to determine the best path for a given route at a particular time.

Although on a smart phone

apps may have routing algorithms but not connect to

The server otherwise does not use the algorithm. When a user requests a route calculation, it is common to

The server sends the request.

The server calculates the optimal route and transmits it back to the smartphone to be displayed. The user may make various routing requests such as fastest or shortest route, whether toll roads are allowed or avoided, whether dirt roads are allowed, whether arterial roads are avoided. The shortest route may refer to a distance. The fastest route may determine that a freeway is better than a town road.

The server stores information such as the average speed of the link between the user's current location and the destination.

The server may determine which of the road lists to take to minimize the total travel time. Although each request can be processed in real time, it is possible to do so

The server may cache some requested routes or primary locations. In this way it is possible to provide a solution,

the server may have learned the optimal route from B to C and when the user requests a route from A to C, once

The server checks that there is no better route that bypasses B completely, it can only calculate the optimal route from a to B.

At the user equipment 102 is

Smartphone for app and server 105 is

In the example of a server, the route recorder 112 and the drawing component 114 mayAdopt by

The shortest or fastest route generated by the server is used as input and a new route, including familiar routes, is suggested based on the familiar routes stored in the route history database 116. Familiar routes and route history may include data from users proposing to drive through in parallel

Information of previous route requests on the app.

Fig. 2 is a schematic diagram of a route drawing system 200, according to an example embodiment. Route mapping system 200 includes a user device 202. The user device 202 may be a network-enabled computer having a memory 208, a navigation application 210, a route recorder 212, and a drawing component 214. The route drawing system may be a Personal Navigation Device (PND), such as

PND、

PND、

PND or

And (4) PND. The route drawing system may be a car navigation system that is part of the car controls or a third party accessory. The route mapping system may be a truck GPS system, such as

A truck GPS navigator, a TomTom Trucker GOS navigation device, or a TruckWay GPS-Pro series. The route mapping system 200 may provide routes for any kind of transportation, such as cars, buses, trains, trucks, mobile workers, pedestrians, cyclists, motorcycles, sales personnel, product delivery service, freight carriers, buses, and the like,Shipping services, service calls, pick-up and delivery, vehicles, dealers, logistics companies, area sales, technicians, buses, or passenger carriers.

The navigation application 110 may run on the route mapping system 200 to provide one or more optimal routes in response to a request to navigate from a starting point to an ending point with selectable intermediate points. The navigation application 210 may be an app installed on the user device 202 or a website of a browser installed on the user device 202.

The navigation application 210 may use any optimization algorithm to find the optimal route or routes. The optimal route may be a solution to a shortest path problem, such as the shortest path between points a and B. Many different shortest path algorithms can be used to find the optimal route under different circumstances. The shortest path algorithm operates on a graph consisting of vertices and edges connecting them. For example, a map may be represented by a graphical data structure stored in memory and used by a navigation application. The graphics may be directional, undirected, weighted, and the like. For some graph types, these differences may determine which algorithm performs better than another algorithm.

For example, the shortest path algorithm is Dijkstra's algorithm. Dijkstra's algorithm is distinctive in that it can find the shortest path from one node to all other nodes within the same graph data structure. This means that Dijkstra's algorithm does not just find the shortest path from the starting node to another particular node, but rather strives to find the shortest path to each reachable node — provided that the graph does not change. The algorithm runs until all reachable nodes have been visited. Therefore, you would only need to run the Dijkstra algorithm once, saving the results for reuse, and not need to run the algorithm again, unless the graphical data structure changes in some way. In case of a change in the graph, you would need to rerun the graph to ensure you have the latest shortest path to your data structure. For example, if you intend to go from a to B in the shortest way possible, but know that some roads are heavily congested, engineering, and the like, when Dijkstra is used, the algorithm will find the shortest path while avoiding any edges of greater weight, finding the shortest path for you.

For example, the shortest path algorithm is the Bellman-Ford algorithm. Similar to the Dijkstra algorithm, the Bellman-Ford algorithm strives to find the shortest path between a given node and all other nodes in the graph. Although it is slower than the Dijkstra algorithm, the generality of Bellman-Ford remedies its shortcomings. Unlike the Dijkstra algorithm, Bellman-Ford can handle graphs in which some edge weights are negative. If there is a negative loop in the graph where the sum of the edges is negative, then there is no shortest or most economical path. This means that the algorithm is unable to find the correct route because of the termination of the negative loop. Bellman-Ford is able to detect negative cycles and report their presence.

For example, the shortest path algorithm is the Floyd-Warshall algorithm. Floyd-Warshall is distinguished in that, unlike Dijkstra's algorithm and Bellman-Ford's algorithm, it is not a single-origin algorithm. Meaning that it computes the shortest distance between each pair of nodes in the graph, rather than just from a single node. It works on the principle of breaking a major problem into smaller ones and then combining the answers to solve the major shortest path problem. Floyd-Warshall is very efficient when it comes to generating routes for multi-stop trips, since it computes the shortest path between all relevant nodes. For this reason, many route planning software will make use of this algorithm, as it will provide you with an optimal route from any given location. Thus, regardless of where you are, Floyd-Warshall will determine the fastest way to reach any other node on the graph.

For example, the shortest path algorithm is the Johnson algorithm. The Johnson algorithm works best for sparse graphs (graphs with few edges) because its run time depends on the number of edges. Therefore, the smaller the number of sides, the faster the route will be generated. The Johnson algorithm differs from other algorithms in that it relies on two other algorithms to determine the shortest path. First, it uses Bellman-Ford to detect negative cycles and eliminate any negative edges. Then, in the case of the new graph, it relies on Dijkstra's algorithm to compute the shortest path in the input original graph.

The route recorder 212 may include any GPS tracking application. The route recorder 212 collects historical data from a GPS tracking application, a vehicle or other navigation system, and/or any tracked location over time. For example, route recorder 212 may collect data about daily travel routes from your home to your workplace and back, commuter shops, restaurants, social events, vacations, or the like. For example, route recorder 212 can collect data from users over time and store route information that can be used by mapping component 214 to generate recommended routes, including familiar routes. Route data may be collected directly or indirectly from the user. For example, the user may manually enter routes, provide feedback on routes, or indicate preferences for certain routes. For example, data may be collected from the navigation application 210, such as searches, origin and destination entries, frequency of navigation or travel routes, and so forth.

The mapping component 214 may create a list of familiar routes from the data recorded by the route recorder 212 that are in the vicinity of the optimal route from the navigation application 210. The mapping component 214 may project one or more familiar routes to one or more optimal routes and concatenate route segments together to form a new route for a given origin and destination. The mapping component 214 may calculate a total distance for the new route and/or a total time for the new route. The rendering component 214 can select an optimization criterion such as total distance or total time and solve the optimization problem using any optimization algorithm, such as a Greedy algorithm. The greedy algorithm uses a problem solving heuristic that makes a locally optimal selection at each stage, with the goal of finding a global optimum. The rendering component 214 can use any optimization algorithm, such as a cultural genetic (memetic) algorithm, differential evolution, evolutionary algorithm, dynamic relaxation, genetic algorithm, hill climbing, Nelder-Mead simplex heuristic, particle swarm optimization, and the like. The mapping component 214 may determine a new route based on a familiar route or a combination of familiar routes merged together.

Fig. 3 is a flow diagram of a route drawing method 300 according to an example embodiment. The route drawing method 300 begins at 302. At block 304, a route history source is identified. Route history data may be collected from vehicle sensor data, smart phones, personal navigation devices, road sensors, networked automobiles, navigation systems, and other sources. Route history data may be collected for automobiles, hiking, riding, golf, aviation, buses, trains, trucks, and the like. A user interface, such as an Application Programming Interface (API), may be provided to identify the route history source. The user interface may enable a user to identify the source and, if necessary, provide access to information that may be retrieved and stored. For example, a user may open an app on their smartphone and configure route history source settings to allow route drawing method 300 to use data from Android

Or Apple

Navigation system and Apple

Google

And/or

The information of (1).

At block 306, route history data is stored in a route history database. Route history data may include location information, start points, end points, map information, user identification, speed information, frequency information, travel dates, travel times, travel distances, traffic conditions, weather, and the like. Route history data may include any information available from the identified route history source, such as from

The previously traveled route. Route history data may be selected, aggregated, and/or combined from a plurality of identified route history sources. For example, historical data may be collected over time from a user's regular travel patterns, daily living from home to work, or weekly trips to a store or social event. Once a sufficient amount of route history data is collected, familiar routes may be revealed and recommendations for new routes using familiar routes may be improved over time.

At block 308, a route request is received. For example, a user may connect a mobile device to their vehicle using a USB cable. User selection of Android

Navigation app on, and select

The user then speaks "OK Google" or selects a microphone. The user can tell Android Auto where they want to go, such as "take me home bar," navigate to san francisco union square, "" navigate to work site, "and" drive to landscape city # 1600 opentheater park road. The user can then confirm the location and follow the guidance to the destination. Such a route request may include location information for the current location and the destination location, as well as information about the optimal route. This route request location information may be stored and used as input for the route drawing method 300 to find new routes, including familiar routes, to suggest to the user.

At block 310, one or more optimal routes are generated. For example, an optimal route from a starting point to a destination may be generated by a personal navigation system to minimize time and distance. For example, in response to a request to a smartphone

a route request of the app is made,

the server may access the navigation data and run a program to determine one or more optimal routes and send the shortest path or fastest route results back to the user's smartphone for display. The route drawing system may receive the secondary route

An optimal route is generated and the optimal route is used as a starting point to find a new route including a familiar route.

At block 312, it is determined whether there are any familiar routes in the route history near the optimal route. For example, the route drawing system may have already been started from

Location information of a departure place and a destination for a route request and information on an optimal route are received. The route mapping system may run an optimization program on the server to determine whether any familiar routes that are close to, but different from, the optimal route are stored in the route history database. As will be described in more detail for both cases in fig. 4, the optimization procedure may include choosing a familiar route, projecting a location, and minimizing the gap. The optimization program may store location information for the origin and destination of the requested route and information about the optimal route in a data structure representing the graph, such that the optimization program may operate on a graphical representation consisting of vertices and edges or points and segments to find a new route using a familiar route. A greedy algorithm with weights may be used to favor frequently used routes as familiar route indicators to find familiar routes in the route history that are close to the optimal route but different from the optimal route. Route drawing systems using familiar routes may use a greedy algorithm or any other optimization algorithm.

If a familiar route is found, at block 314, a familiar origin and a familiar destination for the familiar route are identified. For example, a single familiar route may cover most of the distance between a given origin and destination, but the origin and destination of the familiar route may need to be linked to the given origin and destination to provide a complete new route. For example, a route mapping system using familiar routes may find a suitable familiar route in a route history database, including location information for the origin and destination of the familiar route. The route mapping system may find the familiar route by running a mapping component on a server.

At block 316, an optimization algorithm is performed to find a new route that maximizes familiarity. For example, the route mapping system may include a server running a mapping component that includes an optimizer for finding new routes using familiar routes. The optimization program may use a greedy algorithm. A greedy algorithm may be used with the optimization criteria selected to maximize familiarity. For example, the frequency with which a route has been traveled may be used as an indicator of familiarity. For example, new routes may include familiar routes as long as they do not detour too far and do not waste too much time. For example, a new route may include many familiar routes linked together, but not too many, particularly if the new route is ultimately too complex or takes too long to find. The mapping component may take these factors into account by calculating a threshold for deciding when a new route using a familiar route will be a good idea.

At block 318, the optimal route and the new route are suggested to the user. For example, the optimal route determined by the personal navigation system may be displayed with new routes that include familiar routes and that do not take too far around the route and do not take too much additional time.

At block 320, if there is no suitable familiar route in the route history, the optimal route is simply suggested to the user. At block 322, the user selects one of the suggested routes, and at block 324, the user begins navigation of the selected route. The route drawing method ends at 326.

Fig. 4 is a map 400 according to an example embodiment. The map 400 shows a route from point a to point B. The map 400 illustrates how a route mapping method may use familiar routes for some examples to build a new route. In this example, map 400 shows from point A to point BThe three possible optimal routes are indicated by the line segments marked green on the graph. The map 400 shows the green optimal route from left to right through the top, middle and bottom of the graph. For example, the user may have entered the location of point a as a departure location and the location of point B as a destination into a personal navigation system that generated three optimal routes from a to B. The route drawing method may generate, for example, three familiar routes consisting of blue and red line segments A 'B' (blue), A₁I₁(Red) and J₁B₁(red) indication. For example, the route mapping method may have searched the route history in order to get a familiar route that is close to the green optimal route, and found a single blue familiar route that routes most of a to B and two red familiar routes that may be combined into most of a to B routes. In a first example, a simple new route indicated by the line segment AA' B may be generated by a route drawing method. In a second example, the new route AA is combined₁I₁I₂J₂J₁B₁B may be generated by a route drawing method.

In the first example shown in the map 400, a simple new route indicated by the line segment AA' B may be generated by a route drawing method. The simple new route AA' B starts at point a (origin selection) and ends at point B (destination selection). The simple new route includes blue segment a 'B' (familiar route segment). The familiar route indicated by the blue line segment a 'B' is linked to the origin selection a and the destination selection B by adding a broken line segment AA '(origin route) and a broken line segment B' B (destination route).

In a second example shown in map 400, a new route AA is combined₁I₁I₂J₂J₁B₁B may be generated by a route drawing method. Combined route AA₁I₁I₂J₂J₁B₁B starts at point a and ends at point B and includes two familiar routes, indicated by red line segments in the figure at the lower left portion of the figure and from the middle of the figure to the upper right portion of the figure. Combined route AA₁I₁I₂J₂J₁B₁B includes a red line segment A indicating a first familiar line₁I₁And a red line segment J indicating a second familiar line₁B₁. Three connecting lines bridging the pitch are used to connect the first (A) of red₁I₁) And second (J)₁B₁) The familiar routes are joined to form the novel route AA₁I₁I₂J₂J₁B₁B. These three connecting routes connect the two familiar routes to a part of one of the green optimal routes to form a new route AA₁I₁I₂J₂J₁B₁B. First connecting route I₁I₂Shown as a dashed line in the figure, and the first familiar line a₁I₁(Red) line segment I connected to the optimal route₂J₂(green) the optimal route is lowest or lowest on the graph. Second connection route I₂J₂(Green) first familiar route A₁I₁(Red) to the third connection route J₂J₁(dotted line). Third connecting line J₂J₁(dotted line) segment I of the optimal route₂J₂(Green) to a second familiar route segment J₁B₁(red). In this way, two familiar routes are combined with a portion of the optimal route to create a sequence. Then, by adding the dotted line segment AA₁(modified origin route) and dashed line segment B₁B (modified destination route) links the start and end points of this sequence of two familiar routes and a part of the optimal route to origin selection a and destination selection B.

The map 400 illustrates how the route mapping method may find a new route using a familiar route that is close to the optimal route. In a first example, a simple new route comprises one familiar route that runs almost all the way from a to B, and line segments are added at the start and end points. In a second example, two familiar routes are combined with a portion of an optimal route, and line segments are added at the start and end points to form a combined new route.

Route drawing methods may solve an optimization problem in which familiar routes are projected to an optimal route and combined in a manner that minimizes the gap between the familiar routes and the optimal route. For example, if you plan a trip that takes three hours, the route drawing method may allow the gap to be around half an hour. As long as the total combined familiar route, using, for example, a greedy algorithm, is within the allowed gap compared to the optimal route, the route drawing method will suggest the total combined familiar route. The route mapping method may solve the optimization problem and minimize the gap to within a threshold of time and/or distance to determine the recommended route. The optimal route shown in green on the map 400 may be from a navigation system (such as Google)

Or Apple

) And the suggested route will take into account the comfort of the user by merging familiar routes from the route history.

The route drawing method may project the familiar route to the optimal route and then solve the optimization problem. The proxels are determined as part of a route drawing method. For example, the projection points on the map 400 are A ', B', A₁、I₁、I₂、J₂、J₁And B₁. The route drawing method may select the best location to project the familiar route to the optimal route. In other words, the familiar route is projected for an optimal route, and any spacing is minimized.

The route drawing method may use some optimization algorithm to project points onto the map 400. For example, a route drawing method may project a departure point a to a ', then use a familiar route (blue) from a' to B ', and find an optimal point to project B' back to a destination B. In this case, a simple new route is from a to a 'and from a' to B 'and from B' to B.

The route drawing method may combine shorter familiar routes, such as red line segments on the map 400. In this case, it is preferable that the air conditioner,the route drawing method may find more projection points to string or join them together to form a new route to suggest to the user. The route drawing method may project a to a₁Then use the slave A₁To I₁The red color of (1) is familiar with the route. Then, adding I₁Projection returns to I₂And binding slave I₂To J₂Is part of the green optimal route. Then, from J₂As seen, the optimal point projected back to the familiar route is J₁. Then, use the slave J₁To B₁Familiar with the route. Point B₁Projected back to destination B.

The new routes are comfortable routes known to the user, but they may not go directly to the origin and destination. The user may wish to make a little yield in terms of distance to travel a more comfortable route, provided that the yield in terms of time, distance, complexity, or other considerations is not too great. The route drawing method takes this into account by using a threshold for suggesting a new route using a familiar route. The threshold may be balanced between an optimal route and a comfortable or familiar route. The threshold may be determined by a distance deviation from the fastest route. For example, the distance deviation from the fastest route may be set to no more than a 50% increase in time to reach the destination relative to the determined fastest route.

The route mapping method may calculate a total distance and/or a total time or other metric for the potential proposed new route to determine whether the threshold is met.

Comfort may be roughly estimated using weights in the objective function, where the weights represent the frequency of familiar routes in history. For example, the route mapping method may use two terms in the objective function to minimize the gap between the new route and the optimal route. The first term may be the total amount of time for the new route and the second term may be comfort or weight.

In the present description, numerous specific details have been set forth. However, it is understood that embodiments of the disclosed technology may be practiced without these specific details. In other instances, well-known methods, structures and techniques have not been shown in detail in order not to obscure an understanding of this description. References to "some examples," "other examples," "one example," "an example," "various examples," "one embodiment," "an embodiment," "some embodiments," "example embodiments," "various embodiments," "one embodiment," "an embodiment," "example embodiments," "various embodiments," "some embodiments," etc., indicate that the embodiment of the disclosed technology so described may include a particular feature, structure, or characteristic, but not every embodiment necessarily includes the particular feature, structure, or characteristic. Moreover, repeated usage of the phrases "in one example," "in one embodiment," or "in an embodiment" does not necessarily refer to the same example, embodiment, or embodiment, although it may.

As used herein, unless otherwise specified the use of the ordinal adjectives "first", "second", "third", etc., to describe a common object, merely indicate that different instances of like objects are being referred to, and are not intended to imply that the objects so described must be in a given sequence, either temporally, spatially, in ranking, or in any other manner.

While certain embodiments of the disclosed technology have been described in connection with what is presently considered to be the most practical and various embodiments, it is to be understood that the disclosed technology is not limited to the disclosed embodiments, but, on the contrary, is intended to cover various modifications and equivalent arrangements included within the scope of the appended claims. Although specific terms are employed herein, they are used in a generic and descriptive sense only and not for purposes of limitation.

This written description uses examples to disclose certain embodiments of the disclosed technology, including the best mode, and also to enable any person skilled in the art to practice certain embodiments of the disclosed technology, including making and using any devices or systems and performing any incorporated methods. The patentable scope of certain embodiments of the disclosed technology is defined in the claims, and may include other examples that occur to those skilled in the art. Such other examples are intended to be within the scope of the claims if they have structural elements that do not differ from the literal language of the claims, or if they include equivalent structural elements with insubstantial differences from the literal languages of the claims.

Claims

1. A route drawing system comprising:

a server comprising a processor in data communication with a memory; and

a navigation application stored in the memory, the navigation application including a route recorder and a drawing component,

wherein the route recorder, when executed by the processor, is configured to:

collecting route history data associated with a user, the route history data including origin information, destination information, and location information regarding one or more routes taken by the user; and is

Storing the route history data in a route history database; and is

Wherein the rendering component, when executed by the processor, is configured to:

receiving an origin selection and a destination selection from the user;

generating an optimal route from the origin selection to the destination selection;

selecting a familiar route from the route history data based on the optimal route, the familiar route having a familiar origin and a familiar destination;

generating an origin route selected from the familiar origin to the origin;

generating a destination route selected from the familiar destination to the destination;

generating a new route from the origin selection to the destination selection, the new route including the origin route, the familiar route, and the destination route;

generating comparison information between the new route and the optimal route; and is

Transmitting the optimal route, the new route, and the comparison information for display on a user device associated with the user.

2. The route mapping system of claim 1, wherein the comparison information includes a comparison of an estimated travel time for the optimal route and an estimated travel time for the new route.

3. The route mapping system of claim 2, wherein the comparison information includes a notification to the user if the estimated travel time for the new route exceeds the estimated travel time for the optimal route by a predetermined threshold.

4. The route mapping system of claim 1, wherein the comparison information includes a comparison of an estimated travel distance for the optimal route and an estimated travel distance for the new route.

5. The route mapping system of claim 4, wherein the comparison information includes a notification to the user if the estimated distance traveled for the new route exceeds the estimated distance traveled for the optimal route by a predetermined threshold.

6. The route drawing system of claim 1, wherein the familiar route comprises a first familiar route segment and a second familiar route segment.

7. The route drawing system of claim 6, wherein the drawing component is further configured to:

generating a first connection route, a second connection route, and a third connection route, wherein:

the first connection route connecting the first familiar route segment to the second connection route,

the second connection route connecting the first connection route to the third connection route,

the third connection route connects the second connection route to the second learned route segment, and

the new route includes the first familiar route segment to the first connected route to the second connected route to the third connected route to the second familiar route segment.

8. The route drawing system of claim 1, wherein the route recorder is further configured to:

storing location information and time information at a plurality of points along one or more routes in the route history data; and is

Generating weights for one or more routes in the route history data, the weights representing travel costs derived from location information and time information;

wherein the rendering component is further configured to minimize the travel cost.

9. A route drawing method, comprising:

collecting route history data associated with a user, the route history data including origin information, destination information, and location information regarding one or more routes taken by the user;

storing the route history data in a route history database;

receiving an origin selection and a destination selection from the user;

generating an origin route selected from the familiar origin to the origin;

generating comparison information between the new route and the optimal route, the comparison information including an estimated travel time difference between the optimal route and the new route and an estimated travel distance difference between the optimal route and the new route;

transmitting the optimal route for display on a user device associated with the user;

transmitting the new route and the comparison information for display on the user device when the estimated travel time difference does not exceed a travel time threshold and/or the estimated travel distance difference does not exceed a travel distance threshold.

10. The route drawing method according to claim 9, further comprising:

receiving the travel time threshold and/or the travel distance threshold from the user.

11. The route drawing method according to claim 9, further comprising:

determining the travel time threshold and/or the travel distance threshold from route history data.

12. The route drawing method according to claim 9, wherein the familiar route includes a first familiar route segment and a second familiar route segment.

13. The route drawing method according to claim 12, further comprising:

generating a first connection route, a second connection route and a third connection route,

wherein the first connection route connects the first familiar route segment to the second connection route, the second connection route connects the first connection route to the third connection route, and the third connection route connects the second connection route to the second familiar route segment,

wherein the new route includes the first familiar route segment to the first connecting route to the second connecting route to the third connecting route to the second familiar route segment.

14. The route drawing method according to claim 13, further comprising:

a modified origin route and a modified destination route are generated,

wherein the modified origin route connects the origin selection to the first familiar route and the modified destination route connects the second familiar route to the destination selection,

wherein the new route includes the modified origin route and the modified destination route.

15. A computer-readable non-transitory medium storing a routing application including instructions for execution by a processor, the instructions comprising the steps of:

storing the route history data collected by the route recorder;

receiving an origin selection and a destination selection from the user;

generating an origin route selected from the familiar origin to the origin;

generating a new route from the origin selection to the destination selection, the new route including the origin route, the familiar route, and the destination route; and is

16. The computer-readable non-transitory medium of claim 15, wherein the familiar route comprises a first familiar route and a second familiar route.

17. The computer-readable non-transitory medium of claim 16, further comprising:

wherein the first connection route connects the first familiar route to the second connection route, the second connection route connects the first connection route to the third connection route, and the third connection route connects the second connection route to the second familiar route,

wherein the new route comprises the first familiar route to the first connection route to the second connection route to the third connection route to the second familiar route.

18. The computer-readable non-transitory medium of claim 17, further comprising:

a modified origin route and a modified destination route are generated,

19. The computer-readable non-transitory medium of claim 17, wherein the comparison information includes a comparison of an estimated distance traveled for the optimal route and an estimated distance traveled for the new route.

20. The computer-readable non-transitory medium of claim 17, wherein the comparison information includes a notification to the user if the estimated distance traveled for the new route exceeds the estimated distance traveled for the optimal route by a predetermined threshold.