Method and system for recommending one or more vehicles for one or more requestors

Patent metadata

Field	Value
Publication number	US-2016307287-A1
Application number	US-201514687035-A
Country	US
Kind code	A1
Filing date	Apr 15, 2015
Priority date	Apr 15, 2015
Publication date	Oct 20, 2016
Grant date	—

Abstract

The disclosed embodiments illustrate methods and systems for recommending one or more vehicles, commuting on a predefined route, for one or more requestors. The method includes determining a first additional distance traversable by each vehicle apart from the predefined route to accommodate each requestor. Further, a graph comprising a first set of nodes representing the one or more requestors, and a second set of nodes representing the one or more vehicles, is generated. Thereafter, a mapping between the first set of nodes and the second set of nodes is determined based on the first additional distance. The mapping corresponds to an allocation of a requestor to a vehicle such that an additional distance traversable by the vehicle is less than an additional distance traversable by remaining vehicles apart from the predefined route. Thereafter, the one or more vehicles are recommended for the one or more requestors based on the mapping.

First claim

What is claimed is:

1 . A method for recommending one or more vehicles, commuting on a predefined route, for one or more requestors, the method comprising:
determining, by one or more processors, for each of said one or more requestors, a first additional distance that each of said one or more vehicles has to traverse apart from said predefined route to accommodate said one or more requestors; generating, by said one or more processors, a graph comprising a first set of nodes and a second set of nodes, wherein said first set of nodes corresponds to said one or more requestors and said second set of nodes corresponds to said one or more vehicles; determining, by said one or more processors, a mapping between said first set of nodes and said second set of nodes based on at least said first additional distance, wherein said mapping corresponds to an allocation of a requestor, from said one or more requestors, to a vehicle, from said one or more vehicles, such that an additional distance traversable by said vehicle apart from said predefined route is less than an additional distance traversable by each of remaining of said one or more vehicles apart from said predefined route, for accommodating said requestor; and recommending, by said one or more processors, said one or more vehicles for said one or more requestors on a computing device based on said mapping.

2 . The method of claim 1 , wherein said graph corresponds to a flow network such that each of said first set of nodes is connected with a source node, each of said second set of nodes is connected with a sink node, each of said first set of nodes is connected with each of said second set of nodes, and each edge in said graph has an associated cost and an associated flow value, wherein said first additional distance corresponds to a cost of an edge between each of said first set of nodes and each of said second set of node.

3 . The method of claim 2 , wherein said mapping is determined by utilizing a minimum cost maximum flow technique on said flow network based on said additional distance.

4 . The method of claim 1 , wherein when a capacity of said one or more vehicles is fixed, said graph further comprises a third set of nodes, wherein each of said third set of nodes comprises a combination of one or more nodes from said first set of nodes.

5 . The method of claim 4 further comprises determining, by said one or more processors, for each permutation of said one or more nodes in each of said third set of nodes, a second additional distance that each of said one or more vehicles has to traverse apart from said predefined route to accommodate respective requestors corresponding to said permutation of said one or more nodes.

6 . The method of claim 5 , wherein said mapping is based on said second additional distance.

7 . The method of claim 1 , wherein when a capacity of said one or more vehicles is variable, a first requestor, from said one or more requestors, who is allocated to a vehicle, is removed from said first set of nodes, and a first vehicle, from said one or more vehicles, which does not have vacancy, is removed from said second set of nodes.

8 . The method of claim 7 further comprising generating, by said one or more processors, a second graph comprising said modified first set of nodes and said modified second set of nodes.

9 . The method of claim 1 further comprising adding, by said one or more processors, a vehicle with said predefined route to said one or more vehicles, based on a number of vacancies in said one or more vehicles and a number of said one or more requestors.

10 . The method of claim 1 , wherein said predefined route is determined by utilizing an integer linear programming technique.

11 . The method of claim 1 further comprising removing, by said one or more processors, a vehicle from said one or more vehicles, based on a number of vacancies in said one or more vehicles, a number of said one or more requestors, and a capacity of said vehicle.

12 . The method of claim 11 , wherein a set of requestors allocated to said removed vehicle is added to said one or more requestors, for allocation to remaining of said one or more vehicles.

13 . The method of claim 1 further comprising sending, by a transceiver, a notification to a computing device of each of said one or more requestors, wherein said notification includes said recommendation of said one or more vehicles for said one or more requestors.

14 . The method of claim 1 further comprising sending, by a transceiver, a notification to a computing device associated with each of said one or more vehicles, wherein said notification includes said recommendation of said one or more requestors for said one or more vehicles.

15 . A system for recommending one or more vehicles, commuting on a predefined route, for one or more requestors, the system comprising:
one or more processors configured to: determine for each of said one or more requestors, a first additional distance that each of said one or more vehicles has to traverse apart from said predefined route to accommodate said one or more requestors; generate a graph comprising a first set of nodes and a second set of nodes, wherein said first set of nodes corresponds to said one or more requestors and said second set of nodes corresponds to said one or more vehicles; determine a mapping between said first set of nodes and said second set of nodes based on at least said first additional distance, wherein said mapping corresponds to an allocation of a requestor, from said one or more requestors, to a vehicle, from said one or more vehicles, such that an additional distance traversable by said vehicle apart from said predefined route is less than an additional distance traversable by each of remaining of said one or more vehicles apart from said predefined route, for accommodating said requestor; and recommend said one or more vehicles for said one or more requestors on a computing device based on said mapping.

16 . The system of claim 15 , wherein when a capacity of said one or more vehicles is fixed, said graph further comprises a third set of nodes, wherein each of said third set of nodes comprises a combination of one or more nodes from said first set of nodes.

17 . The system of claim 16 , wherein said one or more processors are further configured to determine, for each permutation of said one or more nodes in each of said third set of nodes, a second additional distance that each of said one or more vehicles has to traverse from said predefined route to accommodate respective requestors corresponding to said permutation of said one or more nodes.

18 . The system of claim 17 , wherein said mapping is based on said second additional distance.

19 . The system of claim 15 , wherein when a capacity of said one or more vehicles is variable, a first requestor, from said one or more requestors, who is allocated to a vehicle, is removed from said first set of nodes, and a first vehicle, from said one or more vehicles, which does not have vacancy, is removed from said second set of nodes.

20 . The system of claim 19 , wherein said one or more processors are further configured to generate a second graph comprising said modified first set of nodes and said modified second set of nodes.

21 . A computer program product for use with a computer, the computer program product comprising a non-transitory computer readable medium, wherein the non-transitory computer readable medium stores a computer pro

Assignees

• Xerox Corp

Inventors

• JAT Sharmistha
• Mukherjee Koyel
• Edakunni Narayanan Unny
• Manohar Pallavi

Classifications

• G01C21/34

  Route searching; Route guidance · CPC title

• G06Q50/30 Primary

  Physics · mapped topic

• G06Q30/0631

  Recommending goods or services · CPC title

• G06Q50/40 Primary

  Business processes related to the transportation industry (shipping G06Q10/083) · CPC title

• G01C21/3453

  Special cost functions, i.e. other than distance or default speed limit of road segments · CPC title