Browse Prior Art Database

Taxi sharing optimisation Disclosure Number: IPCOM000246493D
Publication Date: 2016-Jun-13
Document File: 2 page(s) / 42K

Publishing Venue

The Prior Art Database


The system described uses constraints dynamically to inform path-finding algorithms, allowing the organisation of people, (even those with different start points and end destinations) into cabs that satisfy their needs while splitting the cost fairly between all passengers. This can be used in an integrated transportation system.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 54% of the total text.

Page 01 of 2

Taxi sharing optimisation

This system describes a method for fairly splitting taxi fairs. Existing solutions split the fair retrospectively while this system uses user input to inform its pathfinding, making it more proactive in finding a fairly costed route.

    As an on demand service, taxis can play an important role in smarter transportation. Their convenience comes at a price, but the cost can be substantially reduced by sharing with other people. Sharing also makes the use of taxi more environmentally friendly. Methods of organising group taxi bookings between strangers have to solve two problems in such a way that all users are satisfied; i) getting each user from their start point to their end destination as quickly as possible, and ii) minimising and fairly splitting the bill between all passengers. There are no current solutions that solve this problem for a range of different start points and destinations. This system provides a solution that considers multiple constraints or factors, including time and cost, to split passengers into cabs and calculate the optimal route for each cab.

    Multiple people enter their destination and constraints (eg time and price restrictions) into a database. The system uses weighted travelling salesman algorithms to work out the optimal way of splitting the people into cabs and the optimal routes that satisfy all of their constraints. The weighting on the travelling salesman algorithm can also account for potential delays by factoring in traffic reports, so that the price quoted is reasonable for both parties and can be paid in advance.

    The following steps should allow this solution to be implemented:
1 - Decide which area is to be covered.
2 - Decide how much each road in that area should cost to traverse. Work out how much time each road should take. These provide two weightings for our travelling salesman algorithms.

3 - Collect data from users as to where they wish to travel to and from, and

what their time and cost constraints are. (More data cold be collected to allow for other constraints, eg same-sex cabs, which could then be implemented in the next


whose constraints are causing the most problems that no solution with their

constraints is available and give them the option of relaxing their constraints, or

    4 - For each possible combination of users for which the total number is less than or equal to the number of spaces in a taxi, carry out two constrained travelling salesman algorithms, one with the time constraints, the other with the price constraints.

    This is the inventive step; instead of simply accepting the cost once a solution is found and retroactively trying to split it, we are actively using the dynamic

cost to help c...