WO2009053953A1

WO2009053953A1 - A transport management system

Info

Publication number: WO2009053953A1
Application number: PCT/IE2008/000106
Authority: WO
Inventors: Harvey Appelbe
Original assignee: Mapflow Limited
Priority date: 2007-10-22
Filing date: 2008-10-22
Publication date: 2009-04-30

Abstract

A transport management system comprises a database of location and route data for drivers willing to car share, and a processor for managing ride-sharing operations according to said data. The processor maintains in the database data structures defining vehicle stops with directional attributes. During a learning phase the processor determines a vehicle's direction, and associate stops with a vehicle according to matching of the vehicle's direction with the stops' directional attributes. The processor defines a vehicle's route in terms of matched stops. Each stop has a unidirectional attribute, a bi-directional attribute, or an omni-directional attribute. Also, the processor is adapted to define at least some stops with geo-fence attributes, a geo-fence being an area encompassing roads which access the stops, and to perform matching of vehicle position with the stop geo-fence attributes to match stops with a vehicle. The processor performs the position-geo-fence matching to narrow down a vehicle set for vehicle-stop matching using directional attributes. Also, the processor defines as proxy stops road junctions that can be used by a vehicle to turn to an additional stop which is not normally part of a route.

Description

"A Transport Management System"

INTRODUCTION

Field of the Invention

The invention relates to transport management involving ride-sharing services.

Prior Art Discussion

Users of today's transport systems are well aware of situations such as: drivers on their own in cars delayed on roads congested by too many cars going the same way, people waiting for a bus while empty cars pass by on their way to the same destination, taxis pick up just one passenger, leaving other people to wait to get to the same place, and company and station car parks filled with vehicles, many of which came from the same location.

In each of these cases, if drivers could communicate their intention with other passengers in the transport system unnecessary cost and hassle would be avoided, as spare capacity already exists.

A number of transport management systems for 'dynamic ride sharing' exist that exploit communication (Cellular Comms, GPRS, 3G) and location technology (GPS) to broker empty seats between drivers and passengers, creating value from an existing untapped resource. However, a key limitation of these systems is the difficulty drivers face when trying to declare their intended route.

Unless these ride-sharing services know the places that are visited during each driver's route it is impractical to match available capacity with demand. It is not sufficient to merely ask the driver what their intended origin and destination will be. This journey could only be shared with passengers who also wish to travel from this precise origin to this precise destination. The driver might take any number of alternate routes to get there. Many other passengers who could be served by some subset of the route, could not be suggested, unless the route is known.

A known approach to this problem is to equip the vehicle with satellite tracking technology and to 'learn' the routes that are frequented by the driver. Thus, when the driver starts their journey, the subsequent route they will likely take can be judged.

There are a number of problems associated with relying on satellite position information to determine route, principally due to the often ambiguous or absent position information. For example, referring to Fig. 1, we notice that the points to the north wander far from the road lines. A first 'false positive' problem is that ambiguous position data can suggest that a vehicle uses a road segment that the driver does not or cannot visit during their journey. In ride-sharing applications this would lead the service to suggest passengers meet and share vehicles at locations that are not appropriate.

Conventional map matching techniques exist to deduce the roads that were actually used by the vehicle, despite ambiguous or missing position information. However, these techniques require a complete, up-to-date map database and expensive processing power to deduce road usage correctly.

Referring to Fig. 2, another 'false negative' problem relates to the fact that although a driver may not visit a location [stopl] during their normal route [routel], they very easily could by taking a minor detour [Detourl].

Consider that a large proportion of the distance driven, that could be shared, is driven on motorways and other major trunk routes, where it is not safe or appropriate to stop to pick-up passengers. Stops would more conveniently be placed on nearby slip roads and roundabout. If the service relied upon raw satellite position information, albeit map matched, as the vehicles drive on major routes, the stops which are mostly positioned off major routes would not be recorded as being visited. The invention addresses these problems.

SUMMARY OF THE INVENTION

According to the invention, there is provided a transport management system comprising a database of vehicle route data for drivers willing to car share, and a processor for managing ride-sharing operations according to said data, wherein the processor is adapted to: maintain in the database data structures defining vehicle stops with directional attributes, determine a vehicle's direction, and match stops with the vehicle according to matching of the vehicle's direction with the stops' directional attributes, and store the vehicle's route in terms of the matched stops.

In one embodiment, each stop has a unidirectional attribute, a bi-directional attribute, or an omni-directional attribute.

In one embodiment, the processor is adapted to: define at least some stops with geo-fence attributes, a geo-fence being an area encompassing roads which access the stops, and perform matching of vehicle position with the stop geo-fence attributes to match stops with a vehicle.

In another embodiment, the processor is adapted to perform the position-geo-fence matching to narrow down a vehicle set for vehicle-stop matching using directional attributes.

In one embodiment, the processor is adapted to initially determine a road being travelled and to then match the road data with geo-fence data, and to match direction data of the road with the stop directional attributes. In a further embodiment, size of a geo-fence area is determined by distance to a nearest road which does not access the stop.

In one embodiment, the processor is adapted to define as proxy stops road junctions that can be used by a vehicle to turn to a stop which is not part of a route for the vehicle.

In one embodiment, the processor is adapted to perform the vehicle-stop matching in a learning phase to establish routes for vehicles, to store the learned routes, and to use the learned routes during subsequent ride sharing management.

In one embodiment, the processor is adapted to trigger a learning process automatically upon detection of a new route being travelled by a vehicle.

In one embodiment, the processor is adapted to monitor position of a plurality of vehicles at periodic intervals to trigger learning processes automatically upon detection of new routes for vehicle

In one embodiment, the processor is adapted to perform the vehicle stop matching in real time for each vehicle journey.

In one embodiment, the processor is adapted to initially filter down a candidate set of stops for potential matching with a vehicle.

In one embodiment, said filtering comprises monitoring vehicle position in terms of latitude and longitude and associating a series of vehicle positions with roads, and iteratively re-associating vehicle positions with roads according to a fitting algorithm, and using a final position for comparison with stop geo-fence areas.

In another embodiment, the processor is adapted to apply a routing algorithm to eliminate errors and exclude impossible manoeuvres. In one embodiment, the processor is adapted to process geometry, proximity, and shape of the roads to identify likely roads that the vehicle visited, and to apply a confidence factor to each iteration.

hi one embodiment, wherein the processor is adapted to match, in each iteration, vehicle movement vectors with road vectors.

In another aspect, the invention provides a computer storage medium comprising software code for performing operations of the processor of any system defined above when executing on a digital processor.

DETAILED DESCRIPTION OF THE INVENTION

Brief Description of the Drawings

The invention will be more clearly understood from the following description of some embodiments thereof, given by way of example only with reference to the accompanying drawings in which:-

Figs. 1 and 2 are the drawings referred to above in the prior art discussion; and

Figs. 3 to 9 are maps illustrating aspects of the invention.

Description of the Embodiments

A transport management system has a database of routes and a digital processor which performs ride-sharing operations. It stores route data incorporating stop data defining designated appropriate vehicle stops. The processor is programmed to maintain in the database data structures defining vehicle stops with directional attributes. The processor determines a vehicle's direction, and associates stops with a vehicle according to matching of the vehicle's direction with the stops' directional attributes. The processor defines a vehicle's route in terms of matched stops. The route may be learned in a learning phase in which vehicle progress sis monitored. Alternatively, the stops may be dynamically matched with a vehicle in real time. The database records may be in a relation table format, each stop being defined by a set of data including latitude and longitude co-ordinates and the directional attributes, and geo-fence attributes as described in more detail below. Because of simplicity of the stop data structures a variety of known database techniques may be used, all providing the benefit of very fast processor operation because of the simplicity of the database structure, with avoidance of need to process large volumes of geographical map data.

Vehicle stops are defined to maximise the intelligence that is gathered from position data emanating from vehicles. They are placed at locations that are significant for ride sharing. Referring to Fig. 3, in this case, an 'omnidirecitonal stop' [Stop3] is created at a junction where it is convenient for passengers to wait for collection and for passing vehicles, from any direction, to pick passengers up. The fact that a passing vehicle's route [Route3] services this stop [Stop3] is determined by the fact that some road points fall within an area close to the stop [Geofence 3]. The area is defined such that it includes routes that lead to the stop, and excludes nearby routes that do not. Therefore the size of this area is related to the distance to the nearest road that does not visit the stop, and the inaccuracy of GPS.

A stop database structure might include a bi-directional attribute if a single location, perhaps a pick-up location, is served by vehicles travelling on one route, but not served by vehicles travelling on another nearby route. Referring to Fig. 4, the directional stop [Stop 4] is placed at a location, perhaps a shop, which is convenient for vehicles travelling on one route [Route 4b] to pick up passengers. However, vehicles on the nearby motorway [Route 4a] could not service this stop. By including a vector [Vector 4] as a directional attribute, the service can distinguish between routes that service the stop and routes that do not.

Another directional attribute might be used in cases where a single location, perhaps a pick-up location, can safely be served by vehicles travelling on a road in one direction, but cannot be served by vehicles travelling in the opposite direction. Referring to Fig. 5, the stop [Stop5] is placed at a location close to and in the direction of both directions of traffic [Route 5a and Route 5b]. The direction of the vector [Vector 5] indicates which subset of these vehicles the service should recognise as serving the stop.

The processor defines in the database 'proxy stop' structures might be used in cases where a single location, perhaps a pick-up location, is not normally visited by a vehicle, but could conveniently be served. By placing proxy stops at appropriate location such as a junction leading to the actual pick-up location, the service^" can understand which vehicles 'could easily' serve the pick-up. Referring to Fig. 6, consider that the stop [Stop 6] is not served by vehicles on either of the motorway routes [Route 6a or Route 6b]. However, by placing stops [Stop 6a, b, c, d] vehicles travelling on a nearby route, which could be diverted to the stop [Stop 6], can be detected by the service. In this case, the proxy-stop to the South [Stop 6d] would allow the service to detect vehicles travelling North bound [Route 6b] which could be diverted to serve the stop [Stop 6]. The vector [Vector 6d] ensures that South bound vehicles [Route 6a] that could not easily serve the stop [Stop 6] would be excluded.

Numerous other example exist, according to the geography and topology of the local road network, where a combination of omni-directional, bi-directional, uni-directional and proxy stop data structures can be used to enhance the performance of the transport management services.

Since, with this invention, the service can summarise each vehicle's journey as a short list of significant locations only ("stops"), rather than an exhaustive list of all roads and other map data, the data size and processing power required to match passengers to drivers is much less.

The geometric (coordinates) and topological (direction) attributes provided by the use of such stops enables the service to distinguish between vehicles that can conveniently and safely serve a stop and those that cannot or should not.

The placement and association of "proxy" stops at locations that could lead to the stop affords the transport management operations additional intelligence to include vehicles that could easily serve the stop, rather than limiting searches only to vehicles that do already serve the stop.

Within a service area, perhaps an urban district, in which the ride sharing service is operating, stops are created for significant locations, as described above. Based on a map of the road layout, transport routes and local knowledge, the position, nature and orientation of sufficient stops are created. These might include omni-directional stops at rural junctions or bi-directional stops on fly-overs. Directional stops on dual carriageways and proxy stops of slip roads of complex motorway interchanges.

After the database of stops has been developed, the system is invoked to learn a driver's routes in terms of stops which are accessed. This occurs initially and when the driver indicates that she is taking a new route. As the vehicle travels, the processor collects time-ordered position data, in one embodiment derived from satellite navigation systems.

While learning, the service processes the time-ordered position data to detect stops that have been passed. A bounding box for a given stretch of position data is used to automatically retrieve stops. The position data is then used to determine if each stop has been triggered. Firstly, this is determined from the number of time contiguous points that fall close to the stop, i.e. are within the stop geo-fences. Secondly, the vehicle bearing implied by the time-ordered points is compared with the direction of the stop vector.

Only stops where sufficient points falling close to and in the direction of the stop are associated with the vehicle's route. For each stop judged to have been visited, the time that it was visited is derived from the raw position data. Where proxy-stops have been detected, the actual stop is recorded as being 'easily served' by the vehicle. The results are a time-ordered list of significant locations that can be visited by the vehicle on this route. The processor executes a 'map matching' process as a first or preliminary phase to detect which stops have been passed by the driver in a system route-learning phase. There are a number of levels of map matching process, described below.

To detect which stops have been passed, the conventional or simple geometric approach might be to compare the proximity of the coordinate information from the raw GPS position and the coordinate of the stops. If the position falls within a distance of a stop it might be said to have been used. However, due to the inaccuracy of some GPS data, incorrect stops can often be identified. In other cases, where there are inaccuracies or gaps in the GPS data, stops may be missed altogether.

These simple geometric approaches can be further elaborated to take into account other attributes such as the GPS bearing vs. the stop bearing, or the number of GPS points near each stop. This leads to complex queries with poor performance and inherent limitations. It is difficult to identify whether the vehicle visited stops once or twice in this journey, and exclude stops were never actually used but still reported multiple points.

In one embodiment, the processor executes 'map matching¹ processes to deduce stops that are passed. Despite the presence of inaccurate raw GPS data, or missing information, these processes use the spatial and topological relationship between road features to reconstruct vehicle journeys and then determine which stops were passed.

The map matching technique deduces the vehicle journey and identifies the actual route taken by the vehicle. This process tries to return the sequence of roads visited by the vehicle in the correct order, and identifies the time at which they were visited. Impossible manoeuvres are excluded and missing roads are filled in to provide the complete and correct journey.

The 'statistical curve-to-curve' technique utilises the topology of the stop network. The following provides an overview of the process. Stepl: Vehicle Trajectory (Tig. 7)

Once the process has been presented with GPS data that has passed a logical check, i.e. it pertains to a real journey, the suggested trajectory of the vehicle is created. In simple terms, this means "joining the dots". GPS data is ordered and the apparent movement (red line) of the vehicle from one place to the next is calculated. Statistics are generated for each movement, which go to describe the vehicle trajectory for any given period. Rudimentary checks are performed during this process to identify quality issues and exclude illogical vehicle movements. For instance, when the vehicle is perfectly stationary or is travelling at huge speeds or accelerating wildly.

Step 2: Filter (Fig. 81

Once the vehicle trajectory has been created from the raw GPS data, and checked for correctness, the process attempts to identify significant or unique movements. Various rules can be used. In one example, where vehicles are mostly driving in London we have focused on 'straight¹ movements. In other applications, such as motorway driving the angular movement of the vehicle may be more significant.

By identifying significant movements of the vehicle the algorithm can focus its efforts on the parts of the journey that are likely to match the road network and therefore identify the road usage with more confidence. The process of identifying these significant movements also generates metrics which go to qualify the level of confidence that can be placed in the later matches.

Step3: Deduce fFig. 9)

The significant movements that have been identified by the process are then each matched against nearby road vectors. Various approaches can be used to identify and score candidates. In this application the geometry, proximity, and shape of the roads were used to identify likely roads that the vehicle visited. Armed with a set of likely candidate road segments the vehicle may have visited during a journey, the process then attempts to reconstruct the most likely road usage. This process uses the topology in the underlying road network to validate the logic of each combination of candidates. The process iterates through numerous combinations of the candidate road segments until the most likely journey is deduced. The metric 'likely' can be based on many measures. In this application the confidence of each candidate and the correlation with other strong candidates was used to judge the optimal journey. In the unlikely cases where two journey deductions provide the same likelihood of being correct, the shortest distance is chosen.

Step 4: Stop detection

Once the vehicle's route has been determined (above) the process then compares the proximity and directional vector of the route with the stops in the area to determine, with certainty, which stops are accessed by the vehicle.

In other embodiments, the service does not necessarily require a user to indicate ^"that a route should be learned. The service can operate much less deterministically. Using stochastic methods, the service monitors the driver's road usage. If they appear to be driving on a substantially new route, the learning process described above may take place automatically. The learning process does not have to take place in real time or on the device. The raw position data could be distilled and returned to a central server where the same learning process can take place.

The invention is not limited to the embodiments described but may be varied in construction and detail.

Claims

1. A transport management system comprising a database of vehicle route data for drivers willing to car share, and a processor for managing ride-sharing operations according to said data, wherein the processor is adapted to: maintain in the database data structures defining vehicle stops with directional attributes, determine a vehicle's direction, and match stops with the vehicle according to matching of the vehicle's direction with the stops' directional attributes, and store the vehicle's route in terms of the matched stops.

2. A transport management system as claimed in claim 1, wherein each stop has a unidirectional attribute, a bi-directional attribute, or an omni-directional attribute.

3. A transport management system as claimed in either of claims 1 or 2, wherein the processor is adapted to: define at least some stops with geo-fence attributes, a geo-fence being an area encompassing roads which access the stops, and perform matching of vehicle position with the stop geo-fence attributes to match stops with a vehicle.

4. A transport management system as claimed in claim 3, wherein the processor is adapted to perform the position-geo-fence matching to narrow down a vehicle set for vehicle-stop matching using directional attributes.

5. A transport management system as claimed in claim 4, wherein the processor is adapted to initially determine a road being travelled and to then match the road data with geo-fence data, and to match direction data of the road with the stop directional attributes.

6. A transport management system as claimed in any of claims 3 to 5, wherein size of a geo-fence area is determined by distance to a nearest road which does not access the stop.

7. A transport management system as claimed in any preceding claim, wherein the processor is adapted to define as proxy stops road junctions that can be used by a vehicle to turn to a stop which is not part of a route for the vehicle.

8. A transport management system as claimed in any preceding claim, wherein the processor is adapted to perform the vehicle-stop matching in a learning phase to establish routes for vehicles, to store the learned routes, and to use the learned routes during subsequent ride sharing management.

9. A transport management system as claimed in claim 8, wherein the processor is adapted to trigger a learning process automatically upon detection of a new route being travelled by a vehicle.

10. A transport management system as claimed in claim 9, wherein the processor is adapted to monitor position of a plurality of vehicles at periodic intervals to trigger learning processes automatically upon detection of new routes for vehicle

11. A transport management system as claimed in any preceding claim, wherein the processor is adapted to perform the vehicle stop matching in real time for each vehicle j ourney.

12. A transport management system as claimed in any preceding claim, wherein the processor is adapted to initially filter down a candidate set of stops for potential matching with a vehicle.

13. A transport management system as claimed in claim 12, wherein said filtering comprises monitoring vehicle position in terms of latitude and longitude and associating a series of vehicle positions with roads, and iteratively re- associating vehicle positions with roads according to a fitting algorithm, and using a final position for comparison with stop geo-fence areas.

14. A transport management system as claimed in claim 13, wherein the processor is adapted to apply a routing algorithm to eliminate errors and exclude impossible manoeuvres.

15. A transport management system as claimed in claim 14, wherein the processor is adapted to process geometry, proximity, and shape of the roads to identify likely roads that the vehicle visited, and to apply a confidence factor to each iteration.

16. A transport management system as claimed in either of claims 14 or 15, wherein the processor is adapted to match, in each iteration, vehicle movement vectors with road vectors.

17. A computer storage medium comprising software code for performing operations of the processor of a system of any preceding claim when executing on a digital processor.