Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
SYSTEM AND METHOD FOR OPTIMIZING DELIVERIES ALLOCATION FOR A FLEET OF VEHICLES
Document Type and Number:
WIPO Patent Application WO/2019/145960
Kind Code:
A1
Abstract:
The subject matter discloses a method for optimizing performance of a fleet of delivery vehicles, comprising receiving multiple delivery requests at a computerized system, the number of the multiple delivery requests is higher than the number of delivery vehicles, calculating potential profit for the fleet of delivery vehicles in a plurality of potential delivery configurations, each of the plurality of potential delivery configurations differs in at least one delivery assignment assigned to a delivery vehicle in the fleet of delivery vehicles, calculating a prediction probability for receiving at least one additional delivery request at the computerized system, an origin of the additional delivery request is located within a predefined distance from a destination of a delivery request of the multiple delivery requests and determining an optimal delivery configurations based on an accumulated profit of the multiple delivery requests and the at least one additional delivery request.

Inventors:
BENCHAYA NACHMAN (IL)
YUKELZON ELI (IL)
ZATSEPIN MARIA (IL)
NACHUM OREN EFRAIM (IL)
DAICH BORIS (IL)
Application Number:
PCT/IL2019/050109
Publication Date:
August 01, 2019
Filing Date:
January 28, 2019
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
RIGGOH APPLICATIONS DEV LTD (IL)
International Classes:
G06Q50/28
Foreign References:
US20120158608A12012-06-21
Attorney, Agent or Firm:
EREZ, Johnathan (IL)
Download PDF:
Claims:
CLAIMS:

1. A method for optimizing performance of a fleet of delivery vehicles, comprising:

receiving multiple delivery requests at a computerized system, the number of the multiple delivery requests is higher than the number of delivery vehicles;

calculating potential profit for the fleet of delivery vehicles in a plurality of potential delivery configurations, each of the plurality of potential delivery configurations differs in at least one delivery assignment assigned to a delivery vehicle in the fleet of delivery vehicles;

calculating a prediction probability for receiving at least one additional delivery request at the computerized system, an origin of the additional delivery request is located within a predefined distance from a destination of a delivery request of the multiple delivery requests;

determining an optimal delivery configurations based on an accumulated profit of the multiple delivery requests and the at least one additional delivery request.

2. The method of claim 1, further comprises computing a cost function of the multiple delivery requests, said cost function receives as input a distance between a current location of a delivery vehicle assigned for the delivery request and an origin location of the delivery request.

3. The method of claim 2, further comprises computing a total vehicle profit according to a delivery assignment assigned to a vehicle in the fleet of vehicles and the at least one additional delivery request.

4. The method of claim 3, further comprises calculating a total configuration profit, said total configuration profit is an accumulation of the total vehicle profit of all the vehicles in the fleet of vehicles in a specific delivery configuration.

5. The method of claim 1 , further comprises removing irrelevant delivery configurations from the plurality of delivery configurations based on a current location of the delivery vehicles.

6. The method of claim 1, wherein calculating the prediction probability for receiving at least one additional delivery request based on prior delivery requests received at the computerized system.

7. The method of claim 1, wherein calculating the prediction probability for receiving at least one additional delivery request comprises obtaining prior delivery requests, analyzing the prior delivery requests according to selected features and frequency and predicting probability of receiving a delivery request for given origin range at a given future time range.

8. The method of claim 1, further comprises extracting properties from the delivery request received at the computerized system and converting the properties into cost-related information.

9. The method of claim 1, further comprises determining a price of the at least one additional delivery request according to potential origin and destination.

10. The method of claim 9, further comprises determining a price per mile of the of the at least one additional delivery request according to potential origin and destination.

11. The method of claim 1, further comprises determining relevant delivery configurations from the potential delivery configurations based on a current location of at least one vehicle in the fleet of vehicles and calculating potential profit for the fleet of delivery vehicles only for the relevant delivery configurations.

Description:
SYSTEM AND METHOD FOR OPTIMIZING DELIVERIES ALLOCATION FOR A

FLEET OF VEHICLES

FIELD OF THE INVENTION

The present invention relates generally to delivery optimization.

BACKGROUND OF THE INVENTION

Delivery organizations, such as shipping organizations provide delivery services of goods, either on roadways, sea or air. These delivery organizations have a fleet of vehicles and staff of employees operating the vehicles in charge of generating income to the organization. These delivery organizations seek to manage the vehicle fleet and employees in an optimal way, mostly defined in financial terms, for example how to maximize income, maximize profits, customer satisfaction and the like.

The organization may receive delivery requests via a phone service, from the organization website, from periodic delivery requests (delivering the same goods every Monday morning) and the like. When the number of delivery requests from the organization’s customers is larger than the number of vehicles available, the delivery organization can maximize its profit and/or performance by selecting the most profitable deliveries.

Currently, managers of delivery organizations consider profitability of potential deliveries using their intuition, which is far from optimizing the delivery organizations’ profits and performance.

SUMMARY OF THE INVENTION

It is an object of the subject matter to disclose a method for optimizing performance of a fleet of delivery vehicles, comprising receiving multiple delivery requests at a computerized system, the number of the multiple delivery requests is higher than the number of delivery vehicles, calculating potential profit for the fleet of delivery vehicles in a plurality of potential delivery configurations, each of the plurality of potential delivery configurations differs in at least one delivery assignment assigned to a delivery vehicle in the fleet of delivery vehicles, calculating a prediction probability for receiving at least one additional delivery request at the computerized system, an origin of the additional delivery request is located within a predefined distance from a destination of a delivery request of the multiple delivery requests and determining an optimal delivery configurations based on an accumulated profit of the multiple delivery requests and the at least one additional delivery request.

In some cases, the method further comprises computing a cost function of the multiple delivery requests, said cost function receives as input a distance between a current location of a delivery vehicle assigned for the delivery request and an origin location of the delivery request. In some cases, the method further comprises computing a total vehicle profit according to a delivery assignment assigned to a vehicle in the fleet of vehicles and the at least one additional delivery request. In some cases, the method further comprises calculating a total configuration profit, said total configuration profit is an accumulation of the total vehicle profit of all the vehicles in the fleet of vehicles in a specific delivery configuration.

In some cases, the method further comprises removing irrelevant delivery configurations from the plurality of delivery configurations based on a current location of the delivery vehicles. In some cases, calculating the prediction probability for receiving at least one additional delivery request based on prior delivery requests received at the computerized system. In some cases, calculating the prediction probability for receiving at least one additional delivery request comprises obtaining prior delivery requests, analyzing the prior delivery requests according to selected features and frequency and predicting probability of receiving a delivery request for given origin range at a given future time range.

In some cases, the method further comprises extracting properties from the delivery request received at the computerized system and converting the properties into cost-related information. In some cases, the method further comprises determining a price of the at least one additional delivery request according to potential origin and destination. In some cases, the method further comprises determining a price per mile of the of the at least one additional delivery request according to potential origin and destination. In some cases, the method further comprises determining relevant delivery configurations from the potential delivery configurations based on a current location of at least one vehicle in the fleet of vehicles and calculating potential profit for the fleet of delivery vehicles only for the relevant delivery configurations.

BRIEF DESCRIPTION OF THE DRAWINGS

Some embodiments of the invention are herein described, by way of example only, with reference to the accompanying drawings. With specific reference now to the drawings in detail, it is stressed that the particulars shown are by way of example and for purposes of illustrative discussion of embodiments of the invention. In this regard, the description taken with the drawings makes apparent to those skilled in the art how embodiments of the invention may be practiced.

In the drawings:

Fig. 1 shows a method for optimizing deliveries, according to exemplary embodiments of the present invention;

Fig. 2 shows a method for computing a delivery cost, according to exemplary embodiments of the present invention;

Fig. 3 shows a method for predicting probability of request for delivery at given destination at given future time, according to exemplary embodiments of the present invention;

Fig. 4 shows a method for calculating a cost function in a linear regression manner, according to exemplary embodiments of the present invention;

Fig. 5 shows a method for calculating a count function in a linear regression manner, according to exemplary embodiments of the present invention;

Fig. 6 shows a computerized environment for optimizing deliveries, according to exemplary embodiments of the present invention;

Fig. 7 shows a computerized environment for optimizing deliveries, according to exemplary embodiments of the present invention; and,

Fig. 8 shows a computerized system for optimizing deliveries, according to exemplary embodiments of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

The present invention discloses a method for selecting delivery assignments of vehicles. The selection is made according to a predefined incentive, for example to maximize the fleet’s total performance, or total profit, considering the delivery cost to the organization. The selection of delivery considers a pre-calculated probability that the vehicle allocated to the delivery will have another delivery from the destination of the last delivery. For example, when receiving a delivery from point A to point B and arriving at point B on lune 11, computing the probability to have a delivery request at point B on lune 11 or lune 12, as elaborated below. Such computation may also consider the probability to have a delivery request within a predefined distance from point B, the destination of the delivery, the cost of reaching the delivery from point B, the estimated profit from the next delivery and the like. Computing the probability for a delivery at the destination enables the organization to provide a more competitive offer according to a total profit of more than one delivery, and to reject delivery requests which are less profitable. The probability for the next delivery in a specific time and place may be extracted from a database of prior delivery requests taken over time, for example over one or more years.

The method disclosed in the subject matter may be adjusted according to specific needs of the organization using the methods. For example, some organizations may assign different weights to different parameters, or optimize the deliveries according to another criteria than the criteria disclosed herein. In some other cases, the method solves the optimization problem as a multi objective problem. The method of the subject matter comprises a general method disclosed in figure 1, and additional sub-methods elaborated in figures 2-5. None of the steps disclosed herein limits the scope of the subject matter. The method may be performed periodically, for example once a day, once a week and the like, or in response to a predefined event, for example change in the organization vehicle fleet or when a new potential delivery becomes available seems more appropriate to me. The method may be performed in response to a request from the organization personnel, for example the finance department, for example when the finance department is required to provide cost estimate to a specific delivery that must be issued by the organization, and the finance department wishes to have information about the total profitability of the specific delivery. In such a case, the specific delivery details are inputted into the function in addition to other properties described above. The method is performed by a computerized server, for example an online server or an offline server. The method may be implemented using computer software operating on the server. The input of the method is a set of delivery requests and a database of known past delivery requests, for example in selected 1200 destinations relevant to the delivery organization, as well as information relevant to the organization, for example number and type of vehicles, cost of personnel associated with each vehicle per time unit and the like.

Fig. 1 shows a method for optimizing deliveries, according to exemplary embodiments of the present invention.

Step 110 discloses obtaining a target set of potential deliveries. The target set may be obtained from one more sources such as a website via which customers request deliveries from the organization seeking to optimize its profit.

Step 120 discloses obtaining statistical data. The statistical data is defined as a probability of the vehicle associated with a specific delivery to have a request for a second delivery from the destination of the specific delivery. For example, the probability may be 0.2. The probability may differ from one vehicle to another, according to different capabilities of different vehicles in the vehicle fleet.

Step 130 discloses adding deliveries to the database using statistical and algorithmic methods. The added deliveries may be added in order to provide additional configurations not enabled from a known list of prior delivery requests. The additional configurations may enable the organization to optimize its profits by evaluating additional options.

Step 140 discloses storing several delivery configurations. The delivery configurations may include all or portion of the deliveries assigned to each vehicle from the vehicle fleet. For example, in case there are 120 delivery requests and 20 vehicles, the total number of delivery configurations is 2400 (20 times 120).

Step 150 discloses removing irrelevant delivery configurations from the memory module. The algorithm accesses the memory module when performing the selection method. Removing irrelevant delivery configurations is required to reduce computation time of the selection method elaborated below. The irrelevant optional delivery configurations removed from the memory module may be determined according to various properties, for example a distance between a vehicle’s current location and an origin of a specific delivery. Another property may be a predicted profit. At the end of step 150, only relevant configurations are stored in the memory module and the profit is computed only regarding the relevant configurations.

Step 160 discloses running the selection method. The outcome of the selection method comprises delivery assignments for at least one of the vehicles in the organization’s vehicle fleet. The selection method selects which delivery assignments to be handled by the organization. The selection method may be adjusted according to a target function, for example maximizing total profit, maximizing income, reducing labor time of the organization’s employees and the like. Such target function may be inputted by the organization’s personnel.

Step 170 discloses calculating the possible profit for each possible delivery assignment. The delivery profit may be determined according to the delivery income minus the outcome, including gas, labor time, time or distance to access the delivery origin and the like.

Fig. 2 shows a method for computing a delivery cost, according to exemplary embodiments of the present invention.

Step 210 discloses calculating the cost of driving to the delivery origin location. Such calculation is performed for each vehicle in a given potential configuration. The cost may include time, gas, number of employees in the vehicle and the like.

Step 220 discloses calculating the profit of performing the delivery assignment. Such calculation considers the delivery income minus all the organization’s expenses associated with the specific delivery, for example gas, labor time and the like. The cost of performing the delivery assignment may vary according to the vehicle assigned to execute the delivery assignment, time for executing the delivery assignment and the like.

Step 230 discloses calculating the total vehicle profit of performing the delivery assignment. The total vehicle profit is calculated in case the vehicle is assigned more than a single delivery. For example, when a new delivery request is received at the computerized system or the delivery organization. The new delivery request may be associated with a prior delivery assignment in case the origin location and time of the new delivery request match rules related to the destination location and time of a delivery assignment already assigned to a vehicle in the fleet of vehicles. The total vehicle profit is associated with a specific vehicle in the fleet of vehicles, in a specific delivery configuration. In some embodiments, the distance between the destination of one delivery and the origin of the next delivery is weighted in the cost function. Step 240 discloses calculating total configuration profit obtained from multiple deliveries. The total configuration profit is the accumulation of the total vehicle profit of all vehicles in a specific delivery configuration. A delivery configuration defines which delivery assignments are assigned to which vehicles in the fleet of vehicles.

Step 250 discloses calculating, using statistical information, the probability of receiving a delivery request within a predefined range from the destination location of its last feasible delivery. The total possibility of finding deliveries may be the weighted multiplication of the possibility for each vehicle. In some cases, the calculation also considers a value of an income from the delivery to be found in the destination location, as the original delivery’s profitability is different when the next delivery’s income is 500$ or 5,000$. The outcome of the cost function is selection of one of the delivery configuration according to the target function defined by the software, or according to target or constraints inputted by the organization.

Fig. 3 shows a method for predicting probability of request for delivery at given destination at given future time, according to exemplary embodiments of the present invention.

Step 310 discloses obtaining prior delivery requests. The prior delivery requests may be stored in a memory module accessed by the entity that performs the method, for example a dedicated server or a computer associated with the delivery organization. The delivery organization receives the delivery requests and determines which vehicles will execute each delivery assignment. The prior delivery requests may be provided from multiple delivery organizations, bulletin boards, governmental information and the like. The prior delivery requests comprise requests relevant to a specific data or range of dates, for example June l-June 15.

Step 320 discloses analyzing prior delivery requests according to selected features and frequency. Such features may be feature parameters, as location and date parameters, time parameters of the delivery requests, origin and destination points, and additional data of van types and user details. Additional feature parameters may include price per mile, duration of the rides calculated by distance, duration of the time of the delivery requests including subsequent categorical parameters and the like.

Step 330 discloses grouping the data into categories depend on place and time parameters. Time categories comprise at least one of day of the week or month number, the number of the week in the year, the number of the day in the month, and the number of the day in the year. Step 340 discloses predicting probability of request for delivery at a given destination at a given future time.

Step 350 discloses Re-evaluating number of deliveries. Such re-evaluation may be performed using a predefined function taking into account weights and specific parameters, for example according to the following formula: Y(number_of_deliveies_at_specific_day)=al xl(mean-this-day)+a2x2(mean week) +a3x3(mean month) +a4x4 (mean monthday).

Fig. 4 shows a method for calculating a cost function in a linear regression manner, according to exemplary embodiments of the present invention.

Step 410 discloses uploading data into a memory module accessed by the entity performing the method. In some cases, only data with a predefined price range is uploaded to the memory module.

Step 420 discloses removing main feature outliers from the memory module. The outliers may be determined according to a predefined rule, for example all deliveries excluded from price per mile range of 0.5$ to 8$ are excluded from the list of configurations considered when performing the method.

Step 430 discloses calculating an average price per mile and a standard deviation for pairs of cities in the uploaded data.

Step 440 discloses removing outliers from the uploaded data according to the calculated average price. For example, the method may remove all configurations in which the prices are out of 3 standard deviation from mean.

Step 450 discloses testing promising combinations of parameter as input for linear regression, with different preparation of parameters.

Step 460 discloses evaluating performance of the models using cross correlation. The cross correlation may have a range of 20-45%. The training set may be achieved after several permutations test set, and cross validation of 4-5 permutations between the data for training and test sets. Step 470 discloses optimizing the model using regression parameters exhaustive search.

Fig. 5 shows a method for calculating a count function in a linear regression manner, according to exemplary embodiments of the present invention.

Step 510 discloses uploading data with known destinations and dates into the memory module accessed by the entity performing the method. In some cases, only data with a predefined price range is uploaded to the memory module. Step 520 discloses constructing categories of events by time frames and assigning constructed categories to each entry. Step 530 discloses calculating for each city the averages for deliveries and the standard deviation.

Step 540 discloses normalizing outliers as disclosed above. For example, the method may remove all configurations in which the prices are out of 3 standard deviation from mean.

Step 550 discloses testing promising combinations of parameter as input for linear regression, with different preparation of parameters. Step 560 discloses Evaluating performance of the models using cross correlation with 30% test set, and cross validation of 4-5 permutations between the data for training and test sets. Step 570 discloses optimizing the model using regression parameters exhaustive search.

Fig. 6 shows a computerized environment for optimizing deliveries, according to exemplary embodiments of the present invention. The computerized environment comprises the delivery vehicles 610 configured to deliver goods or persons from a delivery origin to a delivery destination. The vehicles 610 may vary in properties such as size, number of passengers allowed in the vehicle, special drivers’ license required for the vehicle, personnel associated with the vehicle or vehicle type, cargo volume and the like. The vehicles 610 may have a location module configured to receive signals from remote entities, such as satellites or cellular towers, compute the vehicle’s location at a certain point in time and send the location to the computerized system 620 that manages the processes for optimizing deliveries. The computerized system 620 may be a computerized software running on a computerized platform. The platform may be a web server, on the cloud, or on an electrical device, such as a personal computer, server and the like. The computerized system 620 is described in details in figure 8. The computerized system 620 is configured to receive delivery requests from user’s devices 630 of users that contact the computerized system 620 and send assignments to the vehicles’ 610 crew according to an optimization process configured to optimize the profits from the entire fleet of vehicles. The optimization process considers a current location of the vehicles, known delivery requests and predictions of additional delivery requests that are likely to be received at the computerized system 620. The additional delivery requests are to be associated with current requests or a current location of one or more vehicles in the fleet.

Fig. 7 shows a physical environment for providing deliveries, according to exemplary embodiments of the present invention. The physical environment comprises vehicles 720, 722, located at different locations. Vehicle 720 is located near delivery origin 732 and vehicle 722 is located relatively close to delivery origin 730. The vehicles 720, 722 receive delivery assignments from the computerized system that manages the processes for optimizing the profits from the entire fleet of vehicles. The system has three delivery requests - the first request is from origin 730 to destination 740, the second request is from origin 732 to destination 742 and the third request is from origin 735 to destination 745. This way, the computerized system computes a cost function for each vehicle of the vehicles 720, 722, to perform each of the delivery assignments. The computerized system also predicts two additional delivery requests having origins at locations 752, 755. Hence, the computerized system has to estimate whether or not any vehicle of the fleet of vehicles can handle the potential additional delivery requests. The computerized system may compute the price of one of the three delivery requests based on prediction probability that the same vehicle will handle the additional delivery request, before the additional delivery request is received at the computerized system.

Fig. 8 shows a computerized system for optimizing deliveries, according to exemplary embodiments of the present invention.

The computerized system comprises request interface module 810 configured to enable receipt of delivery requests at the system. The request interface module 810 may comprise a predefined menu for enabling users of the computerized system to input information, such as delivery origin location, delivery destination location, requested time to deliver the goods, amount of items to be delivered, total volume, total mass and the like. The request interface module 810 may be connected to electrical devices such as personal computers, tablet computers, smartphones and the like, for example via web browsers, dedicated software such as mobile applications and the like. The request interface module 810 may be connected to the electrical devices via communication module 860 elaborated below.

The computerized system comprises vehicles location module 820 configured to obtain the location of the vehicles of the fleet of vehicles. The locations may be acquired by location modules installed in the vehicles. The vehicles’ location are used by the processing module 850 of the computerized system to optimize the assignment of delivery requests among the vehicles, for example by computing a cost of sending a vehicle from its current location to an origin location of a delivery assignment. The vehicles location module 820 may also be used to supervise the vehicles’ operation, for example verify that delivery assignments are executed as planned. For example, that the vehicle is located 200 kilometers from the origin location 3 hours after arriving at the origin and receiving the goods to be delivered.

The computerized system comprises requests prediction module 830 configured to predict additional delivery requests to be received at the request interface module 810. The prediction module 830 uses a database of prior requests stored at the computerized system or at a server communicating with the computerized system. The database may be sorted by time, geographical regions, type of delivery assignments and the like. The requests prediction module 830 utilizes rules and algorithms stored in the memory module 840 of the computerized system, as detailed above. The processes of predicting additional delivery requests may be activated periodically, for example every day or twice per hour, or may be activated in response to a predefined event, for example shutting down of a vehicle in the fleet of vehicles, receipt of a delivery request at the request interface module 810 and the like. The requests prediction module 830 may predict additional delivery requests in general, or predict specific additional delivery requests, for example based on a limited time span, limited area and the like. The limited time span may be within 24 hours after an estimated time in which a vehicle is expected to reach a destination and end a delivery assignment. The limited area may be within 50 kilometers from a destination of a delivery assignment or within 40 minutes’ drive from the destination of a delivery assignment.

The computerized system comprises a memory module 840 configured to store information relevant to the processes of optimizing performance of the fleet of vehicles. Such information may be rules or algorithms used by the requests prediction module 830 when predicting additional delivery requests to be received at the request interface module 810. Such information may be delivery requests already assigned to each vehicle in the fleet of vehicles. The memory module may also store prior delivery assignments already executed by the fleet of vehicles, for example as a basis for pricing new delivery requests received at the request interface module 810, for example the cost function of each of the executed delivery assignments.

The computerized system comprises a processing module 850 configured to manage the computerized system. For example, when a new delivery request is received at the request interface module 810, the request interface module 810 transfers the new delivery request to the processing module 850 which determines the price of the new delivery request. The processing module 850 may also determine whether or not any of the vehicles of the fleet of vehicles is available for the new delivery request based on locations of the vehicles as received at the vehicles location module 820. The pricing may depend on a cost function of prior executed delivery assignments, the cost is stored in the memory module 840, and the memory address in the memory module 840 that is relevant for the specific cost is accessed by the processing module 850.

The computerized system comprises a communication module 860 configured to communicate with external entities, for example with the vehicles and the electrical devices of users inputting delivery requests into the computerized system. The communication module 860 may comprise an internet gateway, a modem, an antenna, or use any communication infrastructure in the facility where the computerized system is located. The communication module 860 may convert the messages received from another entity to a predefined format configured to be processed by the processing module 850 of the computerized system.

While the disclosure has been described with reference to exemplary embodiments, it will be understood by those skilled in the art that various changes may be made and equivalents may be substituted for elements thereof without departing from the scope of the invention. In addition, many modifications may be made to adapt a particular situation or material to the teachings without departing from the essential scope thereof. Therefore, it is intended that the disclosed subject matter not be limited to the particular embodiment disclosed as the best mode contemplated for carrying out this invention, but only by the claims that follow.