Method for forecasting consumption and generating optimal delivery schedules for vehicles involved in delivering propane and other consumables to end consumers

• US 7,676,404 B2
• Filed: 10/14/2003
• Issued: 03/09/2010
• Est. Priority Date: 10/15/2002
• Status: Expired due to Fees

• Current Assignee: RMR Associates LLC
• Original Assignee: RMR Associates LLC
• Inventors: Richard, Dominique M., Adler, Joel
• Primary Examiner(s): DUNHAM, JASON B
• Application Number:
  US10/686,143
• Publication Number:
  US 20050049942A1
• Time in Patent Office: 2,338 Days
• Field of Search: 705/26, 705/27, 705/1, 705/28, 707/1
• US Class Current: 705/28
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders

Abstract

This invention concerns an improved forecasting and routing system for scheduling propane and other consumable deliveries as well as service deliveries to end consumers by one or more trucks in a multi-stop environment. The invention utilizes information regarding weather history and the consumption history of individual consumers to calculate their future expected demand, and the variability on that demand when sufficient delivery history is available. Customers lacking sufficient delivery history use the consumption of similar customers as a surrogate. This information serves to determine the near optimal set of successive days within which to replenish or service each customer. Knowing this demand the system assembles deliveries into daily truck delivery routes that maximize the consumables delivered per hour. The system is designed for use in cooperation with a computer having memory and incorporates item, customer, weather, and routing information databases.

Claims

1. A scheduling and routing system implemented on a processor, said system including an application program that is implemented on said processor for use in calculating delivery routes for delivering a consumable to customers via commercial delivery vehicles, comprising:

a delivery forecasting system implemented on said processor that consumption matches certain customers to other customers with similar attributes and that forecasts from the delivery profiles of the other customers with similar attributes and/or historical profiles of deliveries to said certain customers, when each said certain customer is anticipated to run out of inventory of the consumable;

an integrated inventory replenishment, scheduling and routing system implemented on said processor that generates a delivery route for a commercial delivery vehicle that prioritizes customers for delivery of said consumable based on risk of inventory depletion before delivery of more inventory of the consumable, said delivery route being generated based on (a) said forecasts and (b) variable parameters including road routing economics of making several deliveries in sequence to a plurality of said customers before replenishment of the commercial delivery vehicle; and

a cost trade-off function implemented on said processor that reflects the trade-off between the cost of delivery of the consumable and the cost associated with the risk of running out of the consumable on any given day, whereby a minimum of said cost trade-off function is used by said integrated inventory replenishment, scheduling and routing system as a criterion for selecting a day for customer delivery, said processor further calculating within a routing horizon for each customer a range of allowable days for delivery of the consumable, said range of allowable days being defined as a set of contiguous days within which the cost trade-off function values fall within a given tolerance of an optimal value.

2. The scheduling and routing system of claim 1, wherein the integrated inventory replenishment, scheduling and routing system includes an algorithm for optimal route generation and an algorithm for optimal delivery day selection, said optimal route generation and optimal delivery day selection algorithms being integrated so as to allow a global optimization with cost trade offs among penalties for running out of the consumable, the costs of multiple trips to deliver the consumable over the long term for an individual customer, and the daily costs of time and miles on the road for executing a route to deliver the consumable to a number of different customers.

3. The scheduling and routing system of claim 1, wherein the delivery forecasting system further provides variable statistical parameters for replenishment of inventory of the consumable, the variable statistical parameters including an expected consumption parameter and an estimate of the variability of the expected consumption parameter.

4. The scheduling and routing system of claim 1, wherein the variable parameters include a routing horizon over which customers are routed, availability of the commercial delivery vehicle, and a range of allowable days for delivery.

5. The scheduling and routing system of claim 1, wherein the consumable is propane.

6. The scheduling and routing system of claim 1, wherein said delivery forecasting system calculates a planning horizon as a function of a routing horizon over which customers are routed, a lead time horizon that specifies an arbitrary safety level that deliveries must respect before the consumable is depleted, and a long-term horizon.

7. The scheduling and routing system of claim 6, wherein said processor is further programmed to calculate a total expected cost of delivery to each customer on every day of the planning horizon as a sum of the cost of delivery of the consumable and an expected out of stock cost for the consumable, whereby a day on which the total expected cost of delivery is a minimum is identified as an optimal delivery day.

8. The scheduling and routing system of claim 7, wherein said integrated inventory replenishment, scheduling and routing system generates a delivery route for each customer for whom the optimal delivery day for that customer is within the planning horizon.

9. The scheduling and routing system of claim 8, wherein said integrated inventory replenishment, scheduling and routing system assigns a routing string to each customer indicating the days of the routing horizon on which the consumable may be delivered to the customer.

10. The scheduling and routing system of claim 8, wherein said integrated inventory replenishment, scheduling and routing system associates routing strings defining the range of allowable days for a customer to a delivery vehicle to be assigned a calculated delivery route.

11. A computer-implemented method of forecasting consumption and generating optimal delivery schedules for delivery of consumables to customers by commercial delivery vehicles, comprising the steps of:

a computer processing instructions for consumption matching a customer to other customers with similar attributes and forecasting the customer'"'"'s consumption of the consumable from the delivery profiles of the other customers with similar attributes and/or historical delivery profiles for deliveries to said customer and, from the customer'"'"'s forecasted consumption, forecasting when said customer is anticipated to run out of inventory of the consumable;

the computer processing instructions for generating a delivery route for a commercial delivery vehicle that prioritizes customers for delivery of said consumable based on risk of inventory depletion before delivery of more inventory of the consumable, said delivery route being generated based on (a) forecasts in said forecasting step and (b) variable parameters for minimizing cost for inventory replenishment of the consumable for individual deliveries by the commercial delivery vehicle, said variable parameters including road routing economics of making several deliveries in sequence to a plurality of said customers before replenishment of the commercial delivery vehicle; and

the computer processing instructions for implementing a cost trade-off function that reflects the trade-off between the cost of delivery of the consumable and the cost associated with the risk of running out of the consumable on any given day, whereby a minimum of said cost trade-off function is used as a criterion for selecting a day for customer delivery, said computer further calculating within a routing horizon for each customer a range of allowable days for delivery of the consumable, said range of allowable days being defined as a set of contiguous days within which the cost trade-off function values fall within a given tolerance of an optimal value.

12. The method of claim 11, wherein the delivery route generating step comprises the step of integrating an algorithm for optimal route generation and an algorithm for optimal delivery day selection so as to allow a global optimization with cost trade offs among penalties for running out of the consumable, the costs of multiple trips to deliver the consumable over the long term for an individual customer, and the daily costs of time and miles on the road for executing a route to deliver the consumable to a number of different customers.

13. The method of claim 11, wherein the days on which deliveries can be made are variable so as to increase the number of possible delivery route assignments for a given delivery of a consumable to a customer.

14. The method of claim 11, wherein the forecasting step includes the step of creating at least one consumption parameter unique to the customer and a variance term.

15. The method of claim 11, comprising the further step of assigning priorities to customers to dictate the order in which commercial vehicle capacity is exhausted.

16. The method of claim 11, wherein the delivery forecasting system further provides variable statistical parameters for replenishment of inventory of the consumable, the variable statistical parameters including an expected consumption parameter and an estimate of the variability of the expected consumption parameter.

17. The method of claim 11, wherein the variable parameters include a routing horizon over which customers are routed, availability of the commercial delivery vehicle, and a range of allowable days for delivery.

18. The method of claim 11, wherein the consumable is propane.

19. A program storage device readable by a processor and storing thereon a program of instructions executable by said processor for forecasting consumption and generating optimal delivery schedules for delivery of consumables to customers by commercial delivery vehicles, said program of instruction causing said processor to:

consumption match a customer to other customers with similar attributes and to forecast the customer'"'"'s consumption of the consumable from the delivery profiles of the other customers with similar attributes and/or historical delivery profiles for deliveries to said customer and, from the customer'"'"'s forecasted consumption, forecasting when said customer is anticipated to run out of inventory of the consumable,

generate a delivery route for a commercial delivery vehicle that prioritizes customers for delivery of said consumable based on risk of inventory depletion before delivery of more inventory of the consumable based on (a) forecasts in said forecasting step and (b) variable parameters for minimizing cost for inventory replenishment of the consumable for individual deliveries by the commercial delivery vehicle, said variable parameters including road routing economics of making several deliveries in sequence to a plurality of said customers before replenishment of the commercial delivery vehicle;

implement a cost trade-off function that reflects the trade-off between the cost of delivery of the consumable and the cost associated with the risk of running out of the consumable on any given day, whereby a minimum of said cost trade-off function is used as a criterion for selecting a day for customer delivery; and

calculate within a routing horizon for each customer a range of allowable days for delivery of the consumable, said range of allowable days being defined as a set of contiguous days within which the cost trade-off function values fall within a given tolerance of an optimal value.

20. The program storage device of claim 19, wherein the program of instructions further causes the processor to integrate an algorithm for optimal route generation and an algorithm for optimal delivery day selection so as to allow a global optimization with cost trade offs among penalties for running out of the consumable, the costs of multiple trips to deliver the consumable over the long term for an individual customer, and the daily costs of time and miles on the road for executing a route to deliver the consumable to a number of different customers.

21. The program storage device of claim 19, wherein the days on which deliveries can be made are variable so as to increase the number of possible delivery route assignments for a given delivery of a consumable to a customer.

22. The program storage device of claim 19, wherein the program of instructions further creates at least one consumption parameter unique to the customer and a variance term.

23. The program storage device of claim 19, wherein the program of instructions further assigns priorities to customers to dictate the order in which commercial vehicle capacity is exhausted.

24. The program storage device of claim 19, wherein the delivery forecasting system further provides variable statistical parameters for replenishment of inventory of the consumable, the variable statistical parameters including an expected consumption parameter and an estimate of the variability of the expected consumption parameter.

25. The program storage device of claim 19, wherein the variable parameters include a routing horizon over which customers are routed, availability of the commercial delivery vehicle, and a range of allowable days for delivery.

26. The program storage device of claim 19, wherein the consumable is propane.

27. A scheduling and routing system implemented on a processor, said system including an application program that is implemented on said processor for use in calculating delivery routes for providing periodically scheduled services to customers via commercial delivery vehicles, comprising:

a delivery forecasting system implemented on said processor that consumption matches certain customers to other customers with similar attributes and that forecasts from the delivery profiles of the other customers with similar attributes and/or historical profiles of deliveries of the periodically scheduled services to said certain customers when each said certain customer is anticipated to need the periodically scheduled services;

an integrated scheduling and routing system implemented on said processor that generates a delivery route for a commercial delivery vehicle that prioritizes customers for delivery of said services based on risk of needing the services before delivery of the periodically scheduled services, said delivery route being generated based on (a) said forecasts and (b) variable parameters including road routing economics of making several deliveries in sequence to a plurality of said customers before rerouting of the commercial delivery vehicle; and

a cost trade-off function implemented on said processor that reflects the trade-off between the cost of delivery of the consumable and the cost associated with the risk of running out of the consumable on any given day, whereby a minimum of said cost trade-off function is used by said integrated inventory replenishment, scheduling and routing system as a criterion for selecting a day for customer delivery, said processor further calculating within a routing horizon for each customer a range of allowable days for delivery of the consumable, said range of allowable days being defined as a set of contiguous days within which the cost trade-off function values fall within a given tolerance of an optimal value.

28. The scheduling and routing system of claim 27, wherein the integrated scheduling and routing system includes an algorithm for optimal route generation and an algorithm for optimal delivery day selection, said optimal route generation and optimal delivery day selection algorithms being integrated so as to allow a global optimization with cost trade offs among penalties for the customer requiring the service, the costs of multiple trips to deliver the service over the long term for an individual customer, and the daily costs of time and miles on the road for executing a route to deliver the service to a number of different customers.

29. A computer-implemented method of providing periodically scheduled services to customers by commercial delivery vehicles, comprising the steps of:

a computer processing instructions for consumption matching a customer to other customers with similar attributes and forecasting the customer'"'"'s need for the services from the delivery profiles of the other customers with similar attributes and/or historical delivery profiles for deliveries of the periodically scheduled services to said customer and, from the customer'"'"'s forecasted need, forecasting when said customer is anticipated to need the periodically scheduled services; and

the computer processing instructions for generating a delivery route for a commercial delivery vehicle that prioritizes customers for delivery of said services based on risk of needing the services before delivery of the periodically scheduled services, said delivery route being generated based on (a) said forecasts and (b) variable parameters including road routing economics of making several deliveries in sequence to a plurality of said customers before rerouting of the commercial delivery vehicle; and

the computer processing instructions for implementing a cost trade-off function that reflects the trade-off between the cost of delivery of the consumable and the cost associated with the risk of running out of the consumable on any given day, whereby a minimum of said cost trade-off function is used as a criterion for selecting a day for customer delivery, said computer further calculating within a routing horizon for each customer a range of allowable days for delivery of the consumable, said range of allowable days being defined as a set of contiguous days within which the cost trade-off function values fall within a given tolerance of an optimal value.

30. The method of claim 29, wherein the delivery route generating step comprises the step of integrating an algorithm for optimal route generation and an algorithm for optimal delivery day selection so as to allow a global optimization with cost trade offs among penalties for the customer requiring the service, the costs of multiple trips to deliver the service over the long term for an individual customer, and the daily costs of time and miles on the road for executing a route to deliver the service to a number of different customers.

31. A program storage device readable by a processor and storing thereon a program of instructions executable by said processor for forecasting need for periodically scheduled services and generating optimal delivery schedules for delivery of the services to customers by commercial delivery vehicles, said program of instruction causing said processor to:

consumption match a customer to other customers with similar attributes and to forecast the customer'"'"'s need for the services from the delivery profiles of the other customers with similar attributes and/or historical delivery profiles for deliveries of the periodically scheduled services to said customer and, from the customer'"'"'s forecasted need, forecasting when said customer is anticipated to need provision of the periodically scheduled services,

generate a delivery route for a commercial delivery vehicle that prioritizes customers for delivery of said services based on risk of needing the services before delivery of the periodically scheduled services, said delivery route being generated based on (a) said forecasts and (b) variable parameters for minimizing cost for individual deliveries by the commercial delivery vehicle, said variable parameters including road routing economics of making several deliveries in sequence to a plurality of said customers before rerouting of the commercial delivery vehicle;

implement a cost trade-off function that reflects the trade-off between the cost of delivery of the consumable and the cost associated with the risk of running out of the consumable on any given day, whereby a minimum of said cost trade-off function is used as a criterion for selecting a day for customer delivery; and

calculate within a routing horizon for each customer a range of allowable days for delivery of the consumable, said range of allowable days being defined as a set of contiguous days within which the cost trade-off function values fall within a given tolerance of an optimal value.

32. The program storage device of claim 31, wherein the program of instructions further causes the processor to integrate an algorithm for optimal route generation and an algorithm for optimal delivery day selection so as to allow a global optimization with cost trade offs among penalties for the customer requiring the service, the costs of multiple trips to deliver the service over the long term for an individual customer, and the daily costs of time and miles on the road for executing a route to deliver the service to a number of different customers.