Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
A METHOD FOR PREDICTING THE PRESENCE OF VEHICLE BELONGING TO A FLEET OF VEHICLES THAT CAN BE USED FOR A FREE-FLOATING RENTAL SERVICE OF THE SAME, IN A NEIGHBORHOOD OF A DESIRED POSITION IN A FUTURE TIME INSTANT
Document Type and Number:
WIPO Patent Application WO/2016/009319
Kind Code:
A1
Abstract:
A method for predicting the presence of a vehicle, belonging to a fleet of vehicles that can be used for a free-floating rental service thereof, in a neighbourhood of a desired position in a future time instant comprising the following steps: geolocation of the free vehicles of the fleet at predetermined time intervals for a predetermined time period; requesting the coordinates of the desired position and of the future time instant; processing by means of an autoregressive model the geolocations to predict the distance from the desired position of the nearest vehicle between the free vehicles in the future time instant.

Inventors:
SAVARESI SERGIO MATTEO (IT)
FORMENTIN SIMONE (IT)
BIANCHESSI ANDREA GIOVANNI (IT)
Application Number:
PCT/IB2015/055277
Publication Date:
January 21, 2016
Filing Date:
July 13, 2015
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
MILANO POLITECNICO (IT)
International Classes:
G06Q30/06; G08G1/01; G08G1/00; G08G1/123
Foreign References:
US20140172727A12014-06-19
JP2008165362A2008-07-17
US20130321178A12013-12-05
JP2006011572A2006-01-12
JP2004178385A2004-06-24
Other References:
None
Attorney, Agent or Firm:
TRENTIN, Michele et al. (Borgo Santa Lucia 31, Vicenza, IT)
Download PDF:
Claims:
CLAIMS

1 . A method for predicting the presence of a vehicle, belonging to a fleet of vehicles that can be used for a free-floating rental service thereof, in a neighborhood of a desired position in a future time instant comprising the following steps:

geolocation of free vehicles of said fleet at predetermined time intervals for a predetermined time period;

requesting the coordinates of said desired position and said future time instant;

calculating the distance from said desired position of the nearest vehicle of said free vehicles in said future time instant by processing with an autoregressive model of said geolocations.

2. Method according to claim 1 , wherein said autoregressive model has the following mathematical formulation:

where:

y(t) is said distance of said nearest free vehicle in said time instant t;

y(t-k) is the distance between the nearest free vehicle and said desired position in said predetermined time intervals of said predetermined time period of said geolocation step;

e(t) is a parameter of error that represents the uncertainty on said autoregressive model;

n is the order of said autoregressive model;

a is a coefficients vector of said autoregressive model.

3. Method according to claim 2, wherein after said geolocation step there is a pre-processing step of said geolocations at least to determine said order of said autoregressive model.

4. Method according to any one of the preceding claims, wherein said processing step of said geolocations comprises the calculation of a vector of distances of the vehicle nearest to said desired position of said free vehicles in said predetermined time intervals of said predetermined time period.

5. Method according to claim 4, wherein said processing step of said geolocations comprises a first calculating operation of a vector of trends tr(t) occurring in said geolocations and to be subtracted from said vector of distances.

6. Method according to claim 5, wherein said processing step of said geolocations comprises a second calculating operation of a vector of periodicities p(t) occurring in said geolocations and to be subtracted from said vector of distances.

7. Method according to claim 6, wherein said processing step of said geolocations comprises a third calculating operation of said coefficients vector a

8. Method according to claim 7, wherein said processing step of said geolocations comprises, after said third operation, a fourth calculating operation of a predictive stochastic vector of distances of said nearest free vehicle in future time instants.

9. Method according to claim 8, wherein said processing step of said geolocations comprises, after said fourth operation, a fifth calculating operation of said vector of predicted distances in said future time instants according to the following formulation:

y(t\t - k) = t\t - k) + p(t) + tr(t)

10. A computer product susceptible to be performed by a computer to implement a method according to one or more of the preceding claims.

Description:
A METHOD FOR PREDICTING THE PRESENCE OF A VEHICLE BELONGING TO A FLEET OF VEHICLES THAT CAN BE USED FOR A FREE-FLOATING RENTAL SERVICE OF THE SAME, IN A NEIGHBOROOD

OF A DESIRED POSITION IN A FUTURE TIME INSTANT

DESCRIPTION

Definitions

In the present text, for free-floating rent it is meant a rental service of vehicles that allows to take and leave a vehicle at any point of the area covered by the service without the need for providing special parking areas.

For free vehicles it is meant vehicles no more used by users who have rented them temporarily.

For geolocation it is meant the detection of the position of a vehicle by means of geographical coordinates adding to such information also the indication of the time instant of the detection thererof.

Field of Application

The present invention is applicable to the field of traffic and transport and it particularly relates to private transport by sharing of vehicles.

More in detail, the present invention refers to the sharing of vehicles between several users with the so-called "free-floating" service.

Background of the Invention

In recent times, the vehicle-sharing has imposed for private transport, generally, but not only, in urban areas, that is the presence of fleets of vehicles available to users that can be rented for limited time periods.

A first type of vehicles rental services provides vehicles that are available in a special parking area where they are taken by users who rent them and where they need to be taken back after use. This service allows the user to book the vehicle in advance, however, it forces him not only to move to the area to take it, but also to take the vehicle back at the same area, thus obliging the user to arrange his own movements to and from the area.

Therefore, point-to-point or station-to-station services are known, that is services for which vehicles are taken from a special parking area and, after use, have to be taken back in one parking area of those belonging to the service thereof. Clearly, this allows the user to choose the departing and destination areas most convenient for his purposes. However, there is still the drawback that these areas generally are not placed in convenient places for the user who therefore has to arrange special movements to go there.

Moreover, vehicles sharing services of "free-floating" type are known, that is they provide vehicles that are arranged substantially scattered in the area covered by the service. Therefore, it is more likely that the way the user has to do to reach the nearest available vehicle is reduced with respect to the previous cases. Furthermore, after use the user may leave the vehicle anywhere inside the service area thus typically zeroing the way the user has to manage independently between the release point of the vehicle and his final destination.

As far as this system has the above mentioned advantages with respect to the above mentioned systems, however, it has the drawback that the known free-floating rental services do not allow to know in advance if a vehicle will be available at the desired time and nearby a desired position wherein the user will provide to be.

Summary of the Invention

Object of the present invention is to at least partially overcome the above mentioned drawbacks, by providing a free-floating rental service to allow the users to know in advance the distance from a desired position of a free vehicle of the fleet in a future time instant.

A further object is that the above mentioned prediction considers any extraordinary events such as atmospheric events or particular seasonal events.

Said objects are achieved by a rental service that uses a method for predicting the presence of a free vehicle, belonging to a fleet of vehicles that can be used for a free-floating rent, in a neighbourhood of a desired position in a future time instant according to the following claims which are considered an integral part of the present description.

In particular, the method of the invention comprises a geolocation step of the free vehicles of the fleet at predetermined time intervals for a predetermined time period. In this way, it is possible to create time series of distances of free vehicles from all positions of the area concerned by the service. In other words, given the location and the time instant of each free vehicle in the concerned area for a predetermined time period, for example one month, it is possible to calculate, for each position of the concerned area, the distance of the nearest free vehicle in time intervals of the predetermined time period.

Then, the same method comprises a requesting step to the user of the coordinates of the position wherein he is when needing a vehicle as well as the time distance at which he desires to use such vehicle.

According to an aspect of the invention, then there is a processing step of the geolocations by an autoregressive model to predict, or estimate, the distance from the above mentioned desired position of the nearest free vehicle in the desired future time instant.

In particular, according to another aspect of the invention the autoregressive model has the following mathematical formulation:

where:

y (t) is the distance from the nearest vehicle at the instant t;

y(t-k) is a vector containing the minimum distances between the free vehicles and the desired position in the predetermined time intervals of the predetermined time period of the geolocation step;

e(t) is the uncertainty about the model and it is typically, but not necessarily, a white process of gaussian distribution;

n is the order of the autoregressive model;

a is a coefficients vector of the autoregressive model.

The predictor y t\t - k) is obtained with the classic and established methods for the autoregressive models. The error of prediction is defined as: ε(ί, σ) = y(t) - y(t\t - k, a)

Advantageously, therefore, the use of an autoregressive model allows to estimate the distance from the desired position within which the nearest free vehicle is at the desired future time instant. This data is obtained by processing, by means of the above mentioned autoregressive model, the geolocation data previously collected and used as a statistical database of the locations of the free vehicles in the area concerned by the service.

Moreover, it is observed that the choice of predicting the distance from the nearest free vehicle instead of other variables is advantageous because it is a continuous variable (and not a discrete one as in other cases such as the prediction of the number of free vehicles within a predetermined distance) that allows the use of the autoregressive model. Furthermore, the choice of this variable does not require the division of the concerned area in zones as it would occur for other variables and, consequently, it does not impose the critical choice of how to divide this space forcing to identify, if possible, the most appropriate grid.

Still advantageously, the above mentioned prediction further allows, if the rental system allows it, to book the vehicle. In any case, the user may know if the estimated distance of the nearest free vehicle is likely to be acceptable or unacceptable, allowing him to plan more certainly his future movements.

Furthermore, the use of autoregressive models is particularly advantageous since these models also provide exogenous inputs, that is the incorporation in the processing of data related to extraordinary events such as rainfalls, frosts, festivities or other, all data that basically alter the statistics of the positions and of the use of the vehicles of the fleet.

Brief description of the drawings

Further features and advantages of the invention will become more evident upon reading the detailed description of some preferred, but not exclusive, embodiments of a method for predicting the presence of a free vehicle, belonging to a fleet of vehicles that can be used for free floating rent, in a neighbourhood of a desired position in a future time instant according to the invention, shown as non limiting example with the help of the annexed drawings wherein:

FIG. 1 is a descriptive block diagram of a method according to the invention;

FIG. 2 represents a detail of FIG. 1 ; FIG. 3 represents an example of time series of the geolocations;

FIG. 4 shows a plant in a schematic view and susceptible to implement a method according to the invention.

Detailed description of some preferred embodiments

With reference to the above mentioned drawings, and in particular to

FIG. 1 , it is described a method for predicting the presence of a vehicle, belonging to a fleet of vehicles that can be used for rent, in a neighbourhood of a desired position in a future time instant.

As said, between the vehicles rental systems the free-floating is known to allow many advantages (previously listed), but according to the prior art it does not allow to predict if nearby a predetermined place in a future time instant there is a vehicle free and available for use.

According to an aspect of the invention, the method for predicting comprises a geolocation step of the free vehicles of the fleet at predetermined time intervals for a predetermined time period. More in detail, in this step all vehicles are examined to know whether they are free or in use. In the first case, a detection of the position in geographic coordinates is performed typically, but not necessarily, by means of GPS systems or the like present inside the vehicles. Such examination is made for a predetermined time period that is typically of a month and at predetermined time intervals that are typically of one hour.

Obviously, such details are not to be considered as limitative for different embodiments of the invention where both the time intervals and the time period of observation are different from the above mentioned. However, from the experimental tests it has been found that such predetermined values allow to obtain a good degree of precision in the subsequent prediction.

Therefore, with the above mentioned geolocation, a database is created regarding the distribution of the free vehicles in the area of interest of the vehicle in a time period sufficient to constitute a valid statistical basis upon which it is possible to base the following processing.

Then, according to another aspect of the invention there is a requesting step to the user about the coordinates of the above mentioned desired position as well as of the time instant of interest, that is of the temporal distance, from the present instant, of the moment wherein the user needs the vehicle.

According to a further aspect of the invention, with the collected data it is possible to perform a further step where the data are processed by means of an autoregressive model in order to predict the distance from the desired position of the nearest free vehicle of the fleet in the desired future time instant.

Firstly, it is observed that the choice of using the distance of the nearest vehicle as a parameter to be predicted is a relevant and advantageous aspect for the present invention. In fact, other parameters are available such as the number of vehicles present within a predetermined distance from the user. These other parameters are undoubtedly related to the same aleatory phenomenon and they may be chosen as variables of interest.

However, there is no doubt that the choice of predicting the distance of the nearest free vehicle brings several advantages. First of all, this parameter represents a continuous variable and not a discrete one as in the case of the example of the number of free vehicles within a predetermined distance. Still advantageously, the chosen parameter does not require the division of the concerned area in zones and, consequently, it does not need the further critical choice of how to divide the area.

Moreover, such choice regarding the parameter to be predicted allows to use as predicting technique an autoregressive model with its advantages. In particular, such models also allow exogenous inputs, that is the incorporation in the processing of data related to extraordinary events such as rainfalls, frosts, festivities or other, all data that basically alter the statistics of the positions and of the use of the vehicles of the fleet.

Therefore, as said, the use of an autoregressive model advantageously allows to estimate such distance. This data is obtained by processing, by means of said autoregressive model, the geolocation data previously collected and used as statistical database of the positions of the free vehicles in the area concerned by the service.

In this way, the user may know if the distance from the nearest free vehicle is likely to be acceptable or unacceptable, allowing him to plan more certainly his future movements.

According to another aspect of the invention, the mathematical formulation of the autoregressive model is:

n

y(t) = ^ a k y(t - k) + e(t)

where:

y (¾) is the distance from the nearest vehicle at the instant t;

y(t-k) is a vector containing the minimum distances between the free vehicles and the desired position in the predetermined time intervals of the predetermined time period of the geolocation step;

e(t) is the uncertainty about the model and it is typically, but not necessarily, a white process of gaussian distribution;

n is the order of the autoregressive model;

a is a coefficients vector of the autoregressive model.

In other words, from the mathematical formulation it is underlined that in the processing step there is a first calculating operation of a vector of distances from the desired position of the nearest free vehicle in the time instants relative to the predetermined time intervals of the geolocation time period. In other words, the calculated the vector represents a time series of the neighbourhoods of the desired position wherein it has been possible to find a free vehicle, in the geolocation period. Therefore, with this vector and with the above mentioned formulation it is possible to obtain a predictive vector, or a predictive time series, of the neighbourhoods of the desired position wherein it is possible, in the future, to find a free vehicle.

However, to perform that, it is underlined that it is necessary to know both the order of the autoregressive model and the coefficients vector σ.

According to an aspect of the invention, the order of the model is determined in a pre-processing step immediately following the geolocation step. In fact, with the geolocation data using methods of minimization of the errors per se known and classically applied to the autoregressive models, such as the AIC method, the FPE method or the method of the loss function (or Loss Function), the above mentioned order is obtained that is applied to the model at any desired position within the concerned area of the service which is also the area where the geolocation has taken place. For example, this area may consists of the entire metropolitan area of a city.

With regards to the coefficients σ, they are calculated with a specific operation. In particular, as shown in Fig. 2, in the processing step there is a prior calculating operation of the above mentioned coefficients according to which, on the basis of the vector of the distances in the past of the free vehicle nearest to the desired position (resulting from the geolocations), they are calculated with an algorithm of minimization of errors such as, for example, an algorithm of minimization of the prediction of the quadratic error.

A mathematical formulation in this sense uses the aforementioned loss function:

N

/(a) = N " £(t ' a)2

t=l where:

J(a) is the loss function, σ the parameters of the autoregressive model; N is the number of time instants whereon the loss function is evaluated; e(t) e is the error between the measured time series and the predicted time series.

The vector σ is calculated so as to minimize the above mentioned problem, that is the above mentioned function. In other words, of all vectors of possible parameters σ, it is chosen the one that minimizes the figure of merit.

At this point, all the data necessary to the processing of the predictive vector are available, the latter containing, at the end of the calculation, the estimated distance from the desired position of the nearest free vehicle for every future time instant, with a distance, between such time instants, equal to the predetermined time interval and for a total time period equal to the above mentioned predetermined time period. Therefore, the answer to the user consists of the element of the vector of predictions corresponding to the desired time distance.

From a statistical point of view, it is known that the above mentioned time series, an example of which is shown in FIG. 3, may be subjected to deterministic phenomena. Such phenomena may interfere with the success of the processing described so far with regards both to the identification of the order of the autoregressive model and to the calculation of the predictive vector.

For this reason, according to another aspect of the invention both the pre-processing step and the processing step of the geolocations comprise a first calculating operation of a vector of trend tr(t) that occurs in the same geolocations and to be subtracted from the vectors of the time series obtained from the geolocations to obtain stochastic vectors. In fact, it is known that in the time series it is possible to identify the trends that actually represent deterministic phenomena.

For the calculation of the vector of trend the following step is identifying the straight line that best approximates a respective time series. To identify such straight line it is possible to proceed in different ways. In the embodiment inhere described it is used the method of minimization of the quadratic error between straight line and time series, but this should not be considered as limitative for different embodiments of the invention. Once identified the straight line, the time instants of interest are identified thereon obtaining the vector tr(t).

In the pre-processing step of geolocations such vector is identified for each time series used in the calculation of the order of the autoregressive model and it is subtracted from such first series before determining the above mentioned order. In the processing step of the predictive series, the time series used for calculating the prediction is initially used to obtain the above mentioned vector tr(t) that is subsequently subtracted therefrom. Then, the coefficients vector σ is calculated and finally the stochastic vector of the predictions is calculated y s (t). The vector tr(t) is added to the latter obtaining the vector of predictions (t) .

Moreover, it is known that other deterministic phenomena identified in the time series are the periodicities. For this reason, according to a further aspect of the invention, both the pre-processing step and the processing step of the geolocations comprise a second calculating operation of a vector of periodicity p(t) which occurs in the same geolocations and to be subtracted from the vectors of the time series obtained from the geolocations to obtain stochastic vectors.

More in detail, according to the non-limitative embodiment that is described, such periodicities are calculated using the Fast Fourier Transform of the time series under examination. It identifies the peaks of frequency which correspond to the above mentioned periodicities. Then, the periodicities having the above mentioned peaks exceeding a predetermined minimum threshold are considered. From experimental analysis it has been noted that typically there are periodicities of twenty-four hours and of seven days, but this should not be considered as limitative for the invention.

Even more in detail, after the application of the Fast Fourier Transform it is obtained the modulus of the resulting function at several points and its average and the standard deviation considering a gaussian distribution are calculated. If such modulus in the above mentioned points is an outlier, that is it has an aberrant or abnormal value with respect to a predetermined threshold value, for example four times the standard deviation, then, what occurs is a periodicity.

If a periodicity is identified, the vector p(t) is obtained which is the repetition of the periodicity thereof so as to obtain a vector as long as the whole time series. Afterwards, the substraction of such vector from the time series under examination occurs. Then, the Fast Fourier Transform is recalculated upon the resulting time series to verify if there are additional periodicities and, in this case, it is calculated as the latter and it is substracted from the time series. Such operations are repeated recursively until no more periodicities are detected.

As in the case of the vector of trend, even in this case there is a vector of the periodicities which is the sum of all the detected periodicities. In the preprocessing step of the geolocations such vector is identified for each time series used in the calculation of the order of the autoregressive model and it is subtracted from such series before determining the above mentioned order. In the processing step of the predictive series, the time series used for calculating the prediction is initially used to obtain the above mentioned vector p(t) which is subsequently subtracted therefrom. Then, the coefficients vector σ is calculated and finally the stochastic vector of predictions is calculated. The vector p(t) is added to the latter obtaining the vector of predictions y(t) .

Therefore, as heretofore said, the time series used both in the preprocessing step to identify the order of the autoregressive model, and in the processing step to calculate the prediction, consist of stochastic vectors, that is vectors obtained from the original time series wherefrom are subtracted, if not null, the vectors of the deterministic phenomena p(t) and tr(t):

y s (t - fc) = y(t - k) - p(t - k) - tr t - k)

Therefore, in the case of the processing of the prediction, the application of the model has the formulation: where y s is the stochastic time series obtained from the geolocations.

Here-hence the stochastic vector of prediction %{t\t - k) is obtained.

Therefore, the vector of the predictions has the mathematic formulation:

y t\ t - k) = t\t - k) + p(t) + tr(t)

According to a further aspect of the invention, the time series of the predictions is then quantized and saturated. In the first case, the round up of each value of the vector of prediction is performed. For example, a possible quantization consists of rounding up to the multiple of five or ten each value of the vector.

In the case of saturation, the latter is achieved by setting one or more threshold values beyond which a predetermined result is given. For example, according to an embodiment of the invention in case in the vector of the predictions there are values greater than one thousand metres, the result is a message wherein it is indicated that the nearest free vehicle is at a distance greater than a kilometre without specifying its exact value.

As previously mentioned, there are some situations that may affect the statistics of use of the vehicles of the fleet. For example, atmospheric events such as rain and snow may heavily influence such statistics thereby threatening to undermine the obtained indication. In this sense, according to some operative embodiments the autoregressive model comprises exogenous inputs that have parameters connected to such events. In addition to atmospheric events, other phenomena that give rise to exogenous inputs are specific traffic flows due to temporary events such as accidents or road works, number of people in the surrounding area (data obtained from cell tower), presence of other vehicles rental services and number of vehicles of the fleets of these alternative services, concerts, shows or the like.

However, there are also events whose duration is such that they may not be considered as temporary. Permanent changes in the road system, long term road works are two examples thereof. Furthermore, the initial geolocation may give rise to different results according to the season wherein it is performed. For this reason, according to another aspect of the invention the calculating step of the order of the autoregressive model is repeated periodically or when such events occur.

According to a particular operative embodiment, the method for predicting further comprises, using the geolocation data, the prediction of what are, in particular, the free vehicles nearest to the user in the desired position and at the predetermined time distance. Advantageously, this further allows the booking of the vehicle by the users.

Operatively, the heretofore described method is generally performed by a specific plant 1 that can be seen in Fig. 3 and which comprises a central electronic processor 2, communication means 3 with the vehicles to geolocate them and to manage their use by the users, computers 4 placed on each vehicle for their management, geolocation means 5 present on each vehicle and consisting of, for example, GPS devices or triangulation devices with telecommunications networks.

Moreover, the central processor 2 comprises store circuits 6 where to store, among other things, the geolocations, the processed time series and the time series to be processed, the coefficients of the autoregressive model, the order of the model, etc.

The same store circuit 6 further houses a computer product that implements the method as heretofore described and susceptible to be performed by the electronic central processor 2.

It is evident that even such computer product is an object of the invention achieving all the intended objects.

According to another aspect of the invention, such computer product further provides by-products loadable on devices for mobile telephony available to users or on electronic devices always available to users. Furthermore, the same computer product comprises a further by-product susceptible to be performed by accessing to a web site.

For the above mentioned, it is evident that the method for predicting the presence of a vehicle, belonging to a fleet of vehicles that can be used for a free-floating rent thereof, in a neighbourhood of a desired position in a future time instant allows a free-floating rental service to overcome the above described drawbacks belonging the prior art.

In particular, it allows the users to know in advance the estimated distance of the nearest free vehicle of the fleet of the service from a desired position in a future time instant.

Furthermore, the method of the invention considers any extraordinary events such as atmospheric events or seasonal events thus giving indications that are precise and not affected by errors connected thereto.

The invention is susceptible of numerous modifications and variations, all falling within the appended claims. All the details may be replaced with other technically equivalent elements, and the materials may be different according to requirements, without departing from the scope of the invention defined by the appended claims.