Method and apparatus for generating a driving route based on origin-destination relationship
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.
1 . A method for generating a driving route for a navigation device of a vehicle providing a mobility service comprising:
providing a first application for installation on said navigation device of said vehicle, wherein said first application is configured to determine a current location of said vehicle using a Global Positioning System (GPS);
providing a second application for said installation on a mobile device of at least one user, wherein said second application is configured to transmit geolocation data;
receiving, by a route creation device, said geolocation data associated with a plurality of nodes in a first group and a plurality of nodes in a second group from said mobile device and said current location from said navigation device over a data communication network, wherein each node in said first group forms a pair with a node in said second group;
creating, by said route creation device, at least one cluster using a clustering algorithm based on a plurality of middle points based on said plurality of nodes in said first group and said plurality of nodes in said second group;
determining, by said route creation device, a visiting sequence of said at least one cluster based on said current location of said vehicle and a centroid of each of said at least one cluster;
selecting, by said route creation device, a first node from a first candidate node group included in a cluster determined to be visited first among said at least one cluster, based on said current location of said vehicle;
selecting, by said route creation device, a second node from a second candidate node group based on a location of said first node;
selecting, by said route creation device, a third node from a third candidate node group based on said location of said first node and a location of said second node;
generating, by said route creation device, a driving route in an order of said first node, said second node, and said third node; and
restricting, by said route creation device, a movement of said vehicle based on said generated driving route to enforce a pickup and drop-off order constraint,
wherein a plurality of nodes in said first candidate node group are included in said cluster determined to be visited first;
transmitting, by said route creation device, said driving route comprising travel time information over said data communication network to said navigation device, causing said first application to display said driving route on said navigation device,
wherein a travel time to said first node is determined from said current location, and travel times among said first, second, and third nodes are determined based on road quality information in a database of said route creation device,
wherein the determining of visiting sequence comprises:
determining, by said route creation device, based on said current location of said vehicle, an entrance node of a cluster determined to be visited first and an exit node of a cluster determined to be visited last among said at least one cluster;
calculating, by said route creation device, distances for all combinations between at least one node of said second group included in a previously visited cluster among said at least one cluster and at least one node of said first group included in a next cluster to be visited among said at least one cluster; and
determining, by said route creation device, among said all combinations, a node of said first group of said previously visited cluster included in a combination having a shortest distance as the exit node of said previously visited cluster, and determining a node of said second group of said next cluster to be visited in said combination having a shortest distance as the entrance node of said next cluster to be visited.
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 0 to each node in said first group and w 0 +1 to each node in said second group; and
selecting at least one node whose weight is w 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 0 +1 except for said first node, and said weight of each node in said second group to w 0 +2 except for a node paired with said first node; and
selecting at least one node whose weight is w 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 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 0 +2 except for said first node and said second node, said weight of at least one node in said second group to w 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 0 +2, and selecting at least one node whose weight is w 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 . The method of claim 1 comprising:
creating a preliminary route for each of said at least one cluster by determining an entrance node and an exit node for each of said at least one cluster; and
said driving route is generated by using said preliminary route for each of said at least one cluster.
9 . A system for generating a driving route for a vehicle providing a mobility service comprising:
a navigation device configured to determine a current location of said vehicle using a Global Positioning System (GPS) through a first application installed on said navigation device of said vehicle,
a mobile device configured to transmit geolocation data through a second application installed on a mobile device of at least one user, and
a route creation device comprising a processor and memory including computer program commands, said memory and program commands configured to, with said processor, enable said route creation device 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 from said mobile device and said current location from said navigation device over a data communication network, wherein each node in said first group forms a pair with each node in said second group;
create at least one cluster using a clustering algorithm based on a plurality of middle points based on said plurality of nodes in said first group and said plurality of nodes in said second group;
determine a visiting sequence of said at least one cluster based on said current location of said vehicle and a centroid of each of said at least one cluster;
select a first node from a first candidate node group included in a cluster determined to be visited first among said at least one cluster based on said 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, and
restrict a movement of said vehicle based on said generated driving route to enforce a pickup and drop-off order constraint,
wherein a plurality of nodes in said first candidate node group are included in said cluster determined to be visited first,
transmit said driving route comprising travel time information over said data communication network to said navigation device, causing said first application to display said driving route on said navigation device,
wherein a travel time to said first node is determined from said current location, and travel times among said first, second, and third nodes are determined based on road quality information in a database of said route creation device,
wherein said route creation device is further configured to determine the visiting sequence by;
determining, based on said current location of said vehicle, an entrar >of a cluster determined to be visited first and an exit node of a cluster determined to be visited last among said at least one cluster;
calculating distances for all combinations between at least one node of said second group included in a previously visited cluster among said at least one cluster and at least one node of said first group included in a next cluster to be visited among said at least one cluster, and
determining, among said all combinations, a node of said first group of said previously visited cluster included in a combination having a shortest distance as the exit node of said previously visited cluster, and determining a node of said second group of said next cluster to be visited in said combination having a shortest distance as the entrance node of said next cluster to be visited.
10 . The system of claim 9 :
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.
11 . The system of claim 9 :
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.
12 . The system of claim 9 :
wherein said first candidate node group is generated by:
assigning a weight wo to each node in said first group and w 0 +1 to each node in said second group; and
selecting at least one node whose weight is w 0 .
13 . The system of claim 12 :
wherein said second candidate node group is generated by:
updating said weight of each node in said first group to w 0 +1 except for said first node, and said weight of each node in said second group to w 0 +2 except for a node paired with said first node; and
selecting at least one node whose weight is w 0 +1.
14 . The system of claim 13 :
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 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 0 +2 except for said first node and said second node, said weight of at least one node in said second group to w 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 0 +2, and selecting at least one node whose weight is w 0 +2.
15 . The system of claim 9 comprising:
recreating said driving route when at least one node is inserted to said first group and said second group.
16 . The system of claim 9 , comprising:
wherein said route creation device is configured to generate said driving route using a preliminary route for each of said at least one cluster.