METHOD AND APPARATUS FOR GENERATING A DRIVING ROUTE BASED ON ORIGIN-DESTINATION RELATIONSHIP

Abstract

A method and system for generating an efficient driving route for a transportation vehicle providing a personal mobility service is disclosed. A transportation vehicle may be a car, truck, bicycle, motorcycle, or the like that transport a payload. A payload may be a person or a product being transported by the vehicle. The personal mobility service broadly refers a service that enables users to plan and book a transportation service at a convenient location and time. A plurality of transportation requests each comprising an origin and a destination is received from the users, a driving route creation device generates an efficient route that visits all destinations of the plurality of transportation requests, and the route may be presented to the users.

Claims

1. A method for generating a driving route for a vehicle providing a mobility service comprising: receiving geolocation data associated with a plurality of nodes in a first group and a plurality of nodes in a second group, wherein each node in said first group forms a pair with a node in said second group; selecting a first node from a first candidate node group based on a current location of said vehicle; selecting a second node from a second candidate node group based on a location of said first node; selecting a third node from a third candidate node group based on said location of said first node and a location of said second node; and generating a driving route in an order of said first node, said second node, and said third node.

2. The method of claim 1: wherein said first candidate node group is said first group; wherein said second candidate node group is generated by selecting at least one unselected node of said first group; and wherein said third candidate node group is generated by selecting a node paired with said first node and a node paired with said second node.

3. The method of claim 1: wherein said first candidate node group is said first group; wherein said second candidate node group is generated by selecting at least one unselected node of said first group and a node paired with said first node; and wherein said third candidate node group is generated by selecting (1) at least one unselected node of said first group, a node paired with said first node, and a node paired with said second node when said second node is selected from said first group, or (2) at least one unselected node of said first group when said second node is selected from said second group;

4. The method of claim 1: wherein said first candidate node group is generated by: assigning a weight w.sub.0 to each node in said first group and w.sub.0+1 to each node in said second group; and selecting at least one node whose weight is w.sub.0.

5. The method of claim 4: wherein said second candidate node group is generated by: updating said weight of each node in said first group to w.sub.0+1 except for said first node, and said weight of each node in said second group to w.sub.0+2 except for a node paired with said first node; and selecting at least one node whose weight is w.sub.0+1.

6. The method of claim 5: wherein said third candidate node group is generated by: when said second node is selected from said second group, selecting at least one node whose weight is w.sub.0+1; and when said second node is selected from said first group, updating said weight of each node in said first group to w.sub.0+2 except for said first node and said second node, said weight of at least one node in said second group to w.sub.0+3 except for two nodes paired with said first node and said second node, wherein weights of said two nodes are updated to w.sub.0+2, and selecting at least one node whose weight is w.sub.0+2.

7. The method of claim 1 comprising: recreating said driving route when at least one node is inserted to said first group and said second group.

8. A method for generating a driving route for a vehicle providing a mobility service using clustering comprising: receiving geolocation data associated with a plurality of nodes in a first group and a plurality of nodes in a second group, wherein each node in said first group forms a pair with a node in said second group; determining a plurality of middle points based said plurality of nodes in said first group and said plurality of nodes in said second group; creating at least one cluster using a clustering algorithm based on said plurality of middle points; determining a sequence for said at least one cluster based on proximity of said at least one cluster to a location of said vehicle; determining an entrance node and an exit node for each of the said at least one cluster; and generating a driving route based on said sequence and said entrance and exit node.

9. The method of claim 8: wherein said sequence includes a first cluster and a last cluster, wherein said first cluster is visited by said vehicle first and said last cluster is visited by said vehicle last; wherein a first cluster entrance node is determined based on proximity of said vehicle to at least one first group node of said first cluster, and a last cluster exit node is determined based on proximity of said vehicle to at least one second group node of said last cluster; wherein said entrance node and said exit node for two consecutive clusters in said sequence except for said first cluster entrance node and said last cluster exit node are determined based on proximity from at least one second group node of a cluster to at least one first group node of a next cluster; and wherein said generating of said driving route includes visiting said entrance node of said first cluster first and said exit node of said last cluster last.

10. A system for generating a driving route for a vehicle providing a mobility service comprising a processor and memory including computer program commands, said memory and program commands configured to, with said processor, enable said system to at least: receive geolocation data associated with a plurality of nodes in a first group and a plurality of nodes in a second group, wherein each node in said first group forms a pair with each node in said second group; select a first node from a first candidate node group based on a current location of said vehicle; select a second node from a second candidate node group based on a location of said first node; select a third node from a third candidate node group based on said location of said first node and a location of said second node; and generate a driving route in an order of said first node, said second node, and said third node.

11. The system of claim 10: wherein said first candidate node group is said first group; wherein said second candidate node group is generated by selecting at least one unselected node of said first group; and wherein said third candidate node group is generated by selecting a node paired with said first node and a node paired with said second node.

12. The system of claim 10: wherein said first candidate node group is said first group; wherein said second candidate node group is generated by selecting at least one unselected node of said first group and a node paired with said first node; and wherein said third candidate node group is generated by selecting (1) at least one unselected node of said first group, a node paired with said first node, and a node paired with said second node when said second node is selected from said first group, or (2) at least one unselected node of said first group when said second node is selected from said second group;

13. The system of claim 10: wherein said first candidate node group is generated by: assigning a weight w.sub.0 to each node in said first group and w.sub.0+1 to each node in said second group; and selecting at least one node whose weight is w.sub.0.

14. The system of claim 13: wherein said second candidate node group is generated by: updating said weight of each node in said first group to w.sub.0+1 except for said first node, and said weight of each node in said second group to w.sub.0+2 except for a node paired with said first node; and selecting at least one node whose weight is w.sub.0+1.

15. The system of claim 14: wherein said third candidate node group is generated by: when said second node is selected from said second group, selecting at least one node whose weight is w.sub.0+1; and when said second node is selected from said first group, updating said weight of each node in said first group to w.sub.0+2 except for said first node and said second node, said weight of at least one node in said second group to w.sub.0+3 except for two nodes paired with said first node and said second node, wherein weights of said two nodes are updated to w.sub.0+2, and selecting at least one node whose weight is w.sub.0+2.

16. The system of claim 10 comprising: recreating said driving route when at least one node is inserted to said first group and said second group.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0013] The figures herein depict exemplary embodiments of the present disclosure, and are provided to facilitate understanding of the present disclosure without limiting the scope or applicability of the present disclosure.

[0014] Furthermore, connecting lines or connectors shown in various figures merely represent exemplary functional relationships and/or physical or logical pairings between components. In an actual apparatus, connections between components may be established by various physical connectors, circuitry connectors, or alternative means of connecting functional components.

[0015] FIG. 1 illustrates an exemplary system architecture comprising a user device, a driver device and a driving route creation device for implementing various embodiments of the present invention;

[0016] FIG. 2a and FIG. 2b show a user device capable of transmitting and receiving data in accordance with certain embodiments of the present invention;

[0017] FIG. 3 illustrates travelling salesman problem in accordance with certain embodiments of the present invention;

[0018] FIG. 4 illustrates a driving route generated for a vehicle providing a personal mobility service in accordance with certain embodiments of the present invention;

[0019] FIG. 5 illustrates a driving route generated for a vehicle providing a personal mobility service using a weight value in accordance with certain embodiments of the present invention;

[0020] FIG. 6 illustrates a driving route generated for a vehicle providing a personal mobility service using clustering in accordance with certain embodiments of the present invention;

[0021] FIG. 7 is a block diagram of a driving route creation device in accordance with certain embodiments of the present invention;

[0022] FIG. 8 is a flowchart illustrating a method for generating a driving route in accordance with certain embodiments of the present invention; and

[0023] FIG. 9 is a flowchart illustrating a strategy of selecting a next node to visit in accordance with certain embodiments of the present invention.

DETAILED DESCRIPTION

Overview

[0024] This disclosure relates to a method and system for generating an efficient driving route for a transportation vehicle providing a personal mobility service. A transportation vehicle (or simply a vehicle) may be a car, truck, bicycle, motorcycle, or the like that transport a payload. A payload may be a person or a product (e.g., food) being transported by the vehicle. The personal mobility service broadly refers to a service and associated resources that, through a data communication network, enable users to plan and book a transportation service at a convenient location and time. A plurality of transportation requests each comprising an origin and a destination is received from the users, a driving route is generated that visits all destinations of the plurality of transportation requests, and the driving route may be presented to the users. The driving route presented in this application can be applied to a wide range of personal mobility services, including car sharing, mobility-on-demand, demand responsive transport, mobility management, intermodal passenger transport, or delivery. In addition, a Traveling Salesman Problem (TSP) algorithm, such as such as Dijkstra algorithm, A* algorithm, or a bidirectional algorithm, may be used to select a node from available nodes for the method described below.

System Components and Data Flow

[0025] Embodiments of the invention may be implemented within an exemplary system architecture such as that depicted in FIG. 1.

[0026] In one embodiment, a user device 1000 may include, but not limited to, a smart phone, a tablet, a personal computer, a cell phone, a personal digital assistant (PDA), a laptop computer, a media player, a micro server, a navigation device, a household appliance, a mobile device equipped with a digital camera, or a wearable device, such as a smart watch, smart glasses, or a smart ring, capable of performing data processing and communication. The user device 1000 may include a passenger device or a driver device. The user device 1000 may be used to request transporting any type of payload including one or more person or product.

[0027] A driving route creation device 2000 may be implemented using one or more computers capable of providing program commands, files, contents, and/or services through a data communication network.

[0028] The driving route creation device 2000 may provide a driving route to the user device 1000 by determining the order of the locations to visit based on the geolocation data (Global Positioning System (GPS), cellular signals, Wi-Fi, or the like) of a plurality of payloads.

[0029] The user device 1000 may be coupled to (and communicate with) the driving route creation device 2000 though the data communication network 3000. An application program for a user may be installed in the user device 1000. The application program is capable of sending and receiving data to/from the driving route creation device 2000 over a data communication network 3000. Each user device 1000 may include at least one graphical display and user interface allowing the passenger or the driver to view and interact with applications and other programs of the user device 1000.

[0030] The data communication network 3000 may provide a communicative interface between the user device 1000 and the driving route creation device 2000, and may comprise any public or private network, such as a local area network (LAN), wireless local area network (WLAN), wide area network (WAN), virtual private network (VPN), cellular network (implementing GSM, CDMA, 3G, 4G, LTE, 5G, etc.), Wi-Fi, Wi-Fi Direct, Bluetooth, infrared data association (IrDA), near field communication (NFC), Intranet, Intranet, or any other network architecture or system that facilitates communications in a network environment. Regardless of the type of network standard employed, the data communication network 3000 is capable of providing a reliable data communication for the user device 1000 connected to the driving route creation device 2000.

[0031] Although various embodiments may include any number of user devices, the exemplary system in FIG. 1 depicts only one user device 1000 connected with the driving route creation device 2000 for purposes of explanation.

[0032] FIG. 2a and FIG. 2b show a user device capable of transmitting and receiving data in accordance with certain embodiments of the present invention. User device in FIG. 2a and FIG. 2b are the same user device 1000 as described in FIG. 1. Therefore, detailed descriptions thereof are omitted to avoid duplication.

[0033] Referring to FIG. 2a, a first user device 1001 may receive an origin and a destination entered by a first user. For example, the first user may enter B as an origin and C as a destination.

[0034] The first user device 1001 may send a first trip data comprising the origin and the destination to the driving route creation device 2000. The origin and destination of the user refer to a pick-up and drop-off location of a payload (e.g., a passenger or product). The first trip data may further include, but not limited to, the time the origin and destination are entered by the first user, name of the origin, latitude and longitude of the origin, name of a destination, latitude and longitude of the destination, or the like.

[0035] The driving route creation device 2000 may generate a first driving route based on the first trip data received from the first user device 1001. The driving route may be turn-by-turn directions on a map but other driving directions may be used (e.g., audio directions). The driving route creation device 2000 may transmit the first driving route to the user device 1001. The user device 1001 displays the first driving route on the screen.

[0036] The first driving route displayed on the screen of the user device 1001 may be created from the trip data of the user as well as a location of the vehicle. For example, the driving route creation device 2000 may generate the first driving route from node A to node B, wherein node A is an initial node of the vehicle and node B is an origin input by the user. The initial node of the vehicle may be the location of the vehicle when the driving route creation device 2000 receives the first trip data from the first user device 1001 or when the origin and destination is entered into the first user device 1001.

[0037] For the sake of convenience, a straight line is used to indicate the trip from node A to node B and from node B to node C in FIG. 2a. However, an actual driving route between the two nodes may be generated along the roads that is to be traveled by the vehicle.

[0038] The driving route creation device 2000 may calculate a first estimated departure time and a first estimated arrival time for the first driving route. The first estimated departure time is the time measured for the vehicle to arrive at node B from node A, and the first estimated arrival time is the time measured for the vehicle to arrive at node C from node B. The driving route creation device 2000 may calculate those times in view of the actual distance of the first driving route, traffic condition (e.g., congestion), and/or optional parameters (e.g., shortest distance, shortest travel time, etc.). The driving route creation device 2000 may send the first estimated times to the user device 1001.

[0039] The driving route creation device 2000 may create a second driving route based on a second trip data entered by a second user. Referring to FIG. 2b, the second user may enter D as an origin and E as a destination. The second user device 1002 may send the second trip data comprising the origin D and destination E to the driving route creation device 2000. For purposes of explanation, it is assumed that the driving route creation device 2000 receives the second trip data from the second user device after receiving the first trip data from the first user device 1001. The driving route creation device 2000 may create the second driving route as well as estimated times based on the second trip data received from the second user device using the same method for creating the first driving route. For example, the driving route creation device 2000 may calculate a second estimated departure time and a second estimated arrival time for the second trip. The second estimated departure time is the time measured for the vehicle to arrive at D from C, and the second estimated arrival time is the time measured for the vehicle to arrive at D from E. The driving route in FIG. 2b visits nodes in order of A-B-C-D-E. However, a route may be created by determining the order using Nearest Insertion, Cheapest Insertion, Farthest Insertion, Random Insertion, or Evolutionary algorithm.

[0040] In addition, the driving route creation device 2000 may create a third driving route by combining the second driving route to the first driving route. For example, after receiving the second trip data from the second user device, the driving route creation device 2000 may calculate the driving route from the end of the first trip (from C) to the beginning of the second trip (to D), and add the second route (from D to E) to the first route (from B to C). The third driving route may comprise an entire trip from A to B, B to C, C to D, and D to E.

[0041] Meanwhile, the driving route creation device 2000 may additionally acquire traffic conditions and road quality of the area where each node (origin or destination) in a trip is located. The acquired location data and additional information (e.g., traffic condition) may be used for implementing various embodiments of the present invention. For example, the driving route creation device 2000 may create a fastest route or a shortest route in consideration of the situation where the vehicle is hard to move from one location to another location due to a traffic jam or poor road quality.

[0042] The road quality may be classified based on certain attributes. In an exemplary embodiment, the attributes may be, without limitation, type of road, volume of traffic, width of road, and length of road. Based on the attributes, a road may be classified from class 1 to class 9, wherein class 1 is the highest quality and class 9 is the lowest quality. Driving connectivity between the roads with the same level of quality may be guaranteed.

[0043] FIG. 3 illustrates travelling salesman problem. The traveling salesman problem (TSP) is a problem in combinatorial optimization. TSP is to find a minimal cost tour visiting all nodes in any order. Referring to FIG. 3, the driving route device 2000 may acquire location information of multiple nodes (A1˜A6) in map 300. The location information may include, but not limited to, longitude and latitude of each node. The driving route device 2000 may generate a driving route that visits all nodes for the vehicle 300 based on the algorithms designed for TSP. The generated driving route may be a path with the shortest distance or fastest travel time.

Creating Driving Route Based on Origin-Destination Relationship

[0044] A driver receives a plurality of transportation requests comprising an origin and a destination in a personal mobility service environment. The origin included in the transportation request is paired with the destination, and there is a plurality of origin-destination pairs on a route that the driver needs to travel. In generating a driving route for transporting multiple passengers (or products) departing at different locations, for example, the order and location of origins and destinations need to be considered.

[0045] FIG. 4 illustrates a driving route generated for a vehicle providing a personal mobility service in accordance with certain embodiments of the present invention.

[0046] In this exemplary embodiment, a driver is allowed to pick up another passenger while transporting a passenger. For example, referring to FIG. 4(a), (1) if O.sub.1 and D.sub.1 are an origin and a destination, respectively, for passenger A, and (2) if O.sub.2 and D.sub.2 are an origin and a destination, respectively, for passenger B, then a vehicle 401 with passenger A already on board is allowed to move to D.sub.1 or O.sub.2 because D.sub.1 is the destination of the passenger A and O.sub.2 is the origin of passenger B. Meanwhile, the vehicle 401 is not allowed to move to D.sub.2 since that is the destination of passenger B. In other words, a passenger B pick-up must precede a passenger B drop-off.

[0047] The driving route creation device 2000 may acquire location data of a plurality of nodes on a map. The plurality of nodes may be classified into either a first group or a second group. Without limiting the types of nodes that can be included, the first group may include origins and the second group may include destinations.

[0048] Referring to FIG. 4(a), O.sub.1, O.sub.2, and O.sub.3 (origins) may be included in the first group, and D.sub.1, D.sub.2, and D.sub.3 (destinations) may be included in the second group. In addition, a pair may be formed between a node in the first group and a node in the second group. For example, O.sub.1 and D.sub.1, O.sub.2 and D.sub.2, O.sub.3 and D.sub.3, may form three pairs. In other words, the pair refers to an origin and a destination of a trip of a passenger.

[0049] The driving route creation device 2000 may select a first node from the first group based on the current location of the vehicle 401. Referring to FIG. 4(b) the driving route creation device 2000 may select O.sub.1 as the first node because O.sub.1 is the closest node from the vehicle 401 among O.sub.1, O.sub.2 and O.sub.3.

[0050] In an exemplary embodiment, the vehicle 401 departed from an origin may visit a destination paired with the origin. More specifically, given that O.sub.1 is selected as the first node, the driving route creation device 2000 may select D.sub.1, among D.sub.1, D.sub.2, and D.sub.3, as a second node, then may generate the driving route that starts from the first node O.sub.1 and ends in the second node D.sub.1 as shown in FIG. 4(c).

[0051] In another embodiment, the vehicle 401 departed from a first origin may visit a second origin before the vehicle 401 reaches a destination paired with the first origin. More specifically, the driving route creation device 2000 may select a second node from at least one unselected node in the first group based on the current location of the vehicle 401. For example, referring to FIG. 4(d), given that O.sub.1 is selected as the first node, the driving route creation device 2000 may select O.sub.2, between O.sub.2 and O.sub.3, as the second node because O.sub.2 is the closest node from O.sub.1.

[0052] After the second node is determined, the driving route creation device 2000 may select a third node based on the location of the second node and the location of the first node. In this case, the third node is selected from a node (from the second group) that is paired with the first node and a node that is paired with the second node. For example, referring to FIG. 4(e), given that D.sub.1 is paired with O.sub.1(O.sub.1 being the first node), and D.sub.2 is paired with O.sub.2 (O.sub.2 being the second node), the driving route creation device 2000 may select D.sub.1 between D.sub.1 and D.sub.2 as the third node because the distance between D.sub.1 and O.sub.2 is closer than the distance between D.sub.2 and O.sub.2.

[0053] Then, the driving route creation device 2000 may generate a driving route in the order of the first node, the second node, and the third node for the vehicle 401.

[0054] In another embodiment, the vehicle 401 departed from a first origin may visit either a second origin or a destination paired with the first origin. In other words, given that a first node is selected, the driving route creation device 2000 may select a second node from (1) at least one unselected node of the first group or (2) a destination node paired with the first node, which is a node in the second group, based on the current location of the first node.

[0055] If the second node is selected from the first group, the driving route creation device 2000 may select a third node from (1) at least one unselected node of the first group, (2) a node paired with the first node, or (3) a node paired with the second node.

[0056] For example, given that O.sub.2 (first group node) is selected as the second node, the third node may be select from O.sub.3 (unselected first group node), D.sub.1 (node paired with O.sub.1), and D.sub.2 (node paired with O.sub.2). The driving route creation device 2000 may select D.sub.1 as the third node because D.sub.1 is the closest node from O.sub.2.

[0057] If the second node is selected from the second group, the driving route creation device 2000 may first determine at least one unselected node in the first group, and select the closest node from the second node as a third node. For example, referring to FIG. 4(f), given that O.sub.1 is selected as the first node and D.sub.1 is selected as the second node, the driving route creation device 2000 may select the third node from either O.sub.2 or O.sub.3 (unselected node in the first group) based on the distance between D.sub.1 and O.sub.2 and D.sub.1 and O.sub.3.

[0058] Then, the driving route creation device 2000 may generate a driving route in the order of the first node, the second node, and the third node for the vehicle.

[0059] The driving route creation device 2000 may create a new driving route using the method described above when a new pair of nodes has been added. The new driving route is created using the new pair of nodes as well as all existing nodes.

Creating Driving Route Using Weight Value

[0060] FIG. 5 illustrates a driving route generated for a vehicle providing a personal mobility service using a weight value of each node in accordance with certain embodiments of the present invention.

[0061] Referring to FIG. 5, the driving route creation device 2000 may acquire location data of a plurality of nodes on the map 500. Each node in the plurality of nodes may be an element of either a first group and a second group. The first group may include but not limited to origin nodes, and the second group may include but not limited to destination nodes.

[0062] Referring to FIG. 5(a), origin nodes O.sub.1, O.sub.2, and O.sub.3 are in a first group, destination nodes D.sub.1, D.sub.2, and D.sub.3 are in a second group. Each node in the first group may form a pair with each node in the second group. For example, O.sub.1 and D.sub.1, O.sub.2 and D.sub.2, and O.sub.3 and D.sub.3, may form pairs.

[0063] Referring to FIG. 5(b), the driving route creation device 2000 may assign an initial weight w.sub.0 to the nodes in the first group, and w.sub.0+1 to the nodes in the second group. For example, the driving route creation device 2000 assigns (w.sub.0)=1 to O.sub.1, O.sub.2, and O.sub.3, and (w.sub.0+1)=2 to D.sub.1, D.sub.2, and D.sub.3.

[0064] The driving route creation device 2000 may select a first node from the nodes whose weight is 1 based on the current location of the vehicle 401. For example, among O.sub.1, O.sub.2, and O.sub.3, the driving route creation device may select O.sub.1, which is the closest origin node from the vehicle 401, as the first node.

[0065] After selecting the first node, the driving route creation device 2000 may update the weight of the nodes in the first group to w.sub.0+1 except for the first node, and the weight of the nodes in the second group to w.sub.0+2 except for the node paired with the first node. Referring to FIG. 5(c), the driving route creation device 2000 updates the weights of O.sub.2 and O.sub.3 to 2, and the weight of D.sub.2 and D.sub.3 to 3. The weight of D.sub.1 that is paired with O.sub.1 has not changed. Then, the driving route creation device 2000 may select a second node from the nodes whose weight is w.sub.0+1 based on the location of the first node. The second node may be a first group node or a second group node. For example, in FIG. 5(c), the driving route creation device 2000 may select either O.sub.2, O.sub.3, or D.sub.1, whose weight is 2, as the second node.

[0066] In an embodiment, when the second node is selected from the second group, the driving route creation device 2000 may select a third node from the nodes whose weight is w.sub.0+1. Referring to FIG. 5(d), when D.sub.1 is selected as the second node, the driving route creation device 2000 may select O.sub.2 between O.sub.2 or O.sub.3 as the third node because the distance between D.sub.1 and O.sub.2 is closer than the distance between D.sub.1 and O.sub.3.

[0067] In another embodiment, when the second node is selected from the first group, the driving route creation device 2000 may update the weight of the nodes in the first group to w.sub.0+2 except for the first node and the second node. The driving route creation device 2000 may further update the weight of the nodes (in the second group) paired with the first node and the third node to w.sub.0+2, and the weight of the remaining nodes in the second group to w.sub.0+3. Then, the driving route creation device 2000 may select a second node from the nodes whose weight is w.sub.0+2 based on the location of the third node. Referring to FIG. 5(e), when O.sub.2 is selected as the second node, the driving route creation device 2000 may update the weight of O.sub.3 to 3 because O.sub.3 is the remaining node in the first group after the first node O.sub.1 and the second node O.sub.2 are selected. The driving route creation device 2000 may further update the weight of D.sub.1 (paired with O.sub.1) and D.sub.2 (paired with O.sub.2) to 3, and weight of D.sub.3 to 4. After updating the weights, the driving route creation device 2000 may select D.sub.1, among D.sub.1, D.sub.2, or O.sub.3, as the third node whose weight is 3.

[0068] Finally, the driving route creation device 2000 may generate a driving route in the order of the first node, the second node, and the third node for the vehicle 401.

Creating Driving Route Using Clustering

[0069] FIG. 6 illustrates a driving route generated using clustering in accordance with certain embodiments of the present invention.

[0070] Referring to FIG. 6, the driving route creation device 2000 may acquire location data of a plurality of nodes on a map. Origin nodes O.sub.1, O.sub.2, O.sub.3, O.sub.4, O.sub.5, and O.sub.6 may be included in a first group, and destination nodes D.sub.1, D.sub.2, D.sub.3, D.sub.4, D.sub.5, and D.sub.6 may be included in a second group. A pair between an origin node and a destination node may be formed. In other words, each node in the first group forms a pair with each node in the second group. For example, O.sub.1 and D.sub.1, O.sub.2 and D.sub.2, O.sub.3 and D.sub.3, O.sub.4 and D.sub.4, O.sub.5 and D.sub.5, and O.sub.6 and D.sub.6 form six pairs.

[0071] In addition, the driving route creation device 2000 may create at least one cluster for the pairs using a clustering algorithm, such as k-means++. A middle point between an origin and a destination may be chosen as a location of each pair and used as a data point in calculating a centroid or a center of each cluster. For example, when six middle points of O.sub.1-D.sub.1, O.sub.2-D.sub.2, O.sub.3-D.sub.3, O.sub.4-D.sub.4, O.sub.5-D.sub.5, and O.sub.6-D.sub.6 pairs are fed into the clustering algorithm with k=2, three pairs O.sub.1-D.sub.1, O.sub.2-D.sub.2, O.sub.3-D.sub.3 may be clustered into the cluster 610, and another three pairs O.sub.4-D.sub.4, O.sub.5-D.sub.5, O.sub.6-D.sub.6 may be clustered into the cluster 620.

[0072] The driving route creation device 2000 may generate a driving route that visits all nodes of the at least one cluster. First, the driving route creation device 2000 may determine a sequence of clusters to visit based on proximity of the vehicle 601 to the centroid of each cluster. In other words, a cluster close to the vehicle 601 is visited before another cluster far from the vehicle 601. For example, the vehicle 601 in FIG. 6 may first visit the cluster 610 and then visit the cluster 620 because the distance between the vehicle 601 and a centroid C1 is shorter than the distance between the vehicle 601 and a centroid C2. An estimated time of arrival (ETA) may also be used instead of distance in determining the sequence.

[0073] Next, the driving route creation device 2000 may determine an entrance node and an exit node of each cluster. Except for the entrance node of a first cluster and the exit node of a last cluster, the entrance node and the exit node of consecutive clusters are determined by measuring the proximity between destination nodes of one cluster and origin nodes of another cluster in the sequence.

[0074] In an exemplary embodiment, the entrance node of the first cluster is determined by selecting an origin node of the first cluster that is closest from a vehicle's current location. For example, referring to FIG. 6, given that the cluster 610 is the first cluster, O.sub.1 may be selected, among origin nodes O.sub.1, O.sub.2, and O.sub.3 in the cluster 610, as the entrance node of the cluster 610. The exit node of the last cluster is determined by selecting a destination node of the last cluster that is farthest from the vehicle's current location. For example, given that the cluster 620 is the last cluster, D.sub.6 may be selected, among destination nodes D.sub.4, D.sub.5, and D.sub.6, as the exit node of the cluster 620.

[0075] After the entrance node of the first cluster and the exit node of the last cluster are determined, the destination node and the origin node having the shortest distance between them may be selected for the entrance and exit node for each of the at least one cluster. For example, the driving route creation device 2000 may measure the distance between D.sub.1, D.sub.2, and D.sub.3 of the cluster 610 and O.sub.4, O.sub.5, and O.sub.6 of the cluster 620, and select D.sub.2 as the exit node of cluster 610 and O.sub.6 as the entrance node of cluster 620 after comparing all possible combinations between D.sub.1, D.sub.2, and D.sub.3 in the cluster 610 and O.sub.4, O.sub.5, and O.sub.6 in the cluster 620.

[0076] Finally, the driving route creation device 2000 may determine the order of nodes to visit in each cluster using the methods explained with reference to FIGS. 4-5.

[0077] FIG. 7 is a block diagram of a driving route creation device in accordance with certain embodiments of the present invention. In general, the term server may refer to any computing device including, desktop, laptop, mobile phone, server, distributed system, wearable device, cloud-based processing device, or combination thereof adapted to perform the functions described herein. As will be understood from this figure, in one exemplary embodiment, the driving route creation device 2000 may include a communication interface 710, a processor 720, and a database (DB) 730. It is to be noted that only the components associated with the exemplary embodiments of the present disclosure are depicted in the figure. Additional components that work together to perform functions described herein may be apparent to those skilled in the art.

[0078] The communication interface 710 may include one or more components enabling the driving route creation device 2000 to communicate with the user device 1000 of FIG. 1 using any type of digital network technology, such as a local area network (LAN), wireless local area network (WLAN), wide area network (WAN), virtual private network (VPN), cellular network (implementing GSM, CDMA, 3G, 4G, LTE, 5G, etc.), Intranet, Internet, or any suitable combination thereof.

[0079] The DB 730 may store any suitable data or information processed by the driving route creation device 2000, including user information, driving route information, payment information, and instructions to achieve the operations detailed in this specification. The DB 730 may comprise any form of non-volatile or volatile memory including, without limitation, random access memory (RAM), read-only memory (ROM), EEPROM (electrically erasable programmable read-only memory), magnetic media (e.g., one or more disk or tape drives), CD-ROM, Blue-ray, or any other optical media, solid state memory (e.g., flash memory), removable media, or any other suitable local or remote memory component or components.

[0080] The processor 720 may manage the overall control of the driving route creation device 2000. In one example, the processor 720 may be configured to control one or more functions of one or more elements of the user interface (not shown), display interface (not shown), communication interface 710, and DB 730 through computer program instructions stored on DB 730. In addition, the processor 720 may control at least one operation detailed in FIGS. 1-6. In another example, the processor 720 may be implemented with ASICs (application specific integrated circuits), DSPs (digital signal processors), DSPDs (digital signal processing devices), PLDs (programmable logic devices), FPGAs (field programmable gate arrays), controllers, micro-controllers, microprocessors, or any suitable combination thereof.

[0081] FIG. 8 is a flowchart illustrating a method for generating a driving route in accordance with certain embodiments of the present invention. Because the process described in FIG. 8 is associated with the embodiments of the present disclosure described above, the methods, processes, and techniques described with reference to FIGS. 1-6 may be applied herein.

[0082] At step 810, the processor 720 acquires location data of a plurality of nodes in a first group and a plurality of nodes in a second group. The first group includes, without limitation, origin nodes, and the second group includes, without limitation, destination nodes. The location data may include at least longitude and latitude of each node.

[0083] At step 820, the processor 720 may select a first node from the first group based on the current location of a vehicle.

[0084] At step 830, the processor 720 may select a second node based on a location of the first node, wherein the second node is selected from at least one unselected node in the first group or a node paired with the first node.

[0085] At step 840, the processor 720 may determine if the second node is selected from the first group.

[0086] If the second node is selected from the first group, step 850 may be executed.

[0087] At step 850, the processor 720 may select a third node based on a location of the second node, wherein the second node is selected from at least one unselected node in the first group, a node paired with the first node, or a node paired with the second node.

[0088] If the second node is selected from the second group, step 860 may be executed.

[0089] At step 860, the processor 720 may select a third node based on the location of the second node from at least one unselected node of the first group.

[0090] At step 870, the processor 720 may generate a driving route in the order of the first node, the second node, and the third node.

[0091] FIG. 9 is a flowchart illustrating a strategy of selecting a next node to visit in accordance with certain embodiments of the present invention. Because the process described in FIG. 9 is associated with the embodiments of the present disclosure described above, the methods, processes, and techniques described with reference to FIGS. 1-8 may be applied herein.

[0092] At step 910, processor 720 may acquire location data of a plurality of nodes in a first group and a plurality of nodes in a second group.

[0093] At step 920, processor 720 may select a next node to visit from at least one unselected node in the first group or at least one destination node paired with at least one selected node based on at least one location of the at least one selected node.

[0094] The present invention is designed in such a way that a second group node (destination node) is not selected until a first group node (origin node) paired with the second group node is selected, and a node that is already selected or included in a driving route is not selected again.

[0095] For example, referring to FIG. 4, assume that origin nodes O.sub.1, O.sub.2 and O.sub.3 are in a first group, destination nodes D.sub.1, D.sub.2, and D.sub.3 are in a second group, and O.sub.1 and D.sub.1, O.sub.2 and D.sub.2, and O.sub.3 and D.sub.3 form pairs. If O.sub.1 was previously selected, O.sub.2 is currently selected, and all other nodes are not yet selected, then the processor 720 may select a next node from D.sub.1 that is paired with O.sub.1, D.sub.2 that is paired with O.sub.2, or an unselected first group.

[0096] In another example, when D.sub.1 is currently selected, which implies that D.sub.1's pair O.sub.1 is already selected, based on the design principal of the node selection process described above, the processor 720 may select an unselected node O.sub.2 or O.sub.3 in the first group as the next node to visit.

[0097] At step 930, processor 720 may generate a drive route in order of node selection. For example, if the order of node selection is O.sub.1, D.sub.1, and O.sub.2, processor 720 may generate a driving route in such a way that the vehicle 401 visits nodes in the order of O.sub.1, D.sub.1, and O.sub.2,

[0098] Various embodiments of the present invention can be implemented as a computer program. The computer program may be a software program specifically developed for the present invention or built from publicly available software programs. In addition, the computer program may be implemented in any programming language, such as machine language or a high-level programming language. The programming language may be a compiled or interpreted programming language.

[0099] The present invention includes a computer program product which is a storage medium having instructions stored thereon which when executed cause a computer to perform any of the processes of the present invention. The storage medium may be, for example, but not limited to, an electronic, magnetic, optical, or any suitable combination thereof.

[0100] The computer program product may be delivered via physical data storage media to end customer, or downloaded from an online application store (e.g., Google Play Store) or directly from another user's device. In case of online distribution, at least one part of a computer program may be cached in a server of a manufacturer, server of the application store, or a hosting server.

[0101] Various steps of the method in various embodiments in the present invention may be carried out without a particular order, unless the context clearly indicates otherwise. Examples used in embodiments of the present invention are not to be construed as a limitation on other ways of making the present invention. Also, any person with ordinary skill in the art may implement the present invention by removing or changing some modules if necessary, and it will be apparent that the scope of the present invention should be determined in accordance with the claims herewith.

[0102] While the invention has been shown and described with respect to the embodiments, the present invention is not limited thereto, it will be understood by those skilled in the art that various changes and modifications may be made without departing from the scope of the invention as defined in the following claims