Bill payment optimization using a genetic algorithm

• US 7,756,787 B1
• Filed: 08/11/2004
• Issued: 07/13/2010
• Est. Priority Date: 01/22/2003
• Status: Active Grant

• Current Assignee: Intuit, Inc.
• Original Assignee: Intuit, Inc.
• Inventors: Hilton, Kenneth W.
• Primary Examiner(s): Colbert; Ella
• Application Number:
  US10/916,668
• Time in Patent Office: 2,162 Days
• Field of Search: 705/2, 705/39, 705/40, 705/1, 705/35, 706/13, 706/36, 715/255, 715/760, 715/764, 715/769, 707/101, 707/102, 707/104.1
• US Class Current: 705/40
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 20/102 Bill distribution or payments

Abstract

A genetic algorithm determines a plan for payment of payment obligations in accounts payable of a finance account. The genetic algorithm operates to satisfy certain objectives, including maximizing or minimizing the total amount of payments of the payment obligations on a given day within the amount of cash available for the given day. A genome population including a number of vectors is generated. The genome population is modified using a genetic algorithm, until at least one vector represents an optimal bill payment plan for the payment obligations such that payment of each payment obligation in accordance with the vector most nearly satisfies one or more objectives.

Claims

1. A computer-implemented method of determining an optimal bill payment plan corresponding to a plurality of payment obligations in accounts payable of a finance account while evaluating a plurality of objectives related to amounts of payments in the bill payment plan for a day, comprising a 24 hour period, the computer-implemented method comprising:

generating, by a computer processor, a genome population having a first set of vectors, each vector representing the bill payment plan, numerically defining for each payment obligation a payment amount; and

modifying iteratively, by the computer processor, the genome population using a genetic algorithm until a vector of the first set of vectors forming the optimal bill payment plan is determined that maximizes a total amount of payment of the payment obligations on the day within an amount of available cash in the finance account for the day while simultaneously evaluating the plurality of objectives,

wherein the genetic algorithm comprises determining a fitness for the vector of the first set of vectors, and

wherein determining the fitness for the vector comprises;

obtaining a plurality of objective values (O_G) for the plurality of objectives, wherein the plurality of objective values represent a plurality of degrees of optimization of the plurality of objectives when the payment obligations are paid in accordance with the bill payment plan represented by the vector,

normalizing and standardizing the plurality of objective values (O_G) to obtain a plurality of normalized, standardized objective (NSO) values (O_i) for the plurality of objectives,

obtaining a composite objective value (O_comp) corresponding to the vector by the following equation;

$O_{\mathrm{comp}}=\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br><br><br>w_i<br><br>O_i$

where

 

O_comp is the composite objective value corresponding to the vector,

 

O_i is the NSO value corresponding to the plurality of objectives,

 

w_i is a weight corresponding to the plurality of objectives, and

 

n is a number of objectives, and

applying a fitness function to the composite objective value O_comp to obtain a fitness score corresponding to the vector.

2. A computer-implemented method of determining a bill payment plan corresponding to a plurality of payment obligations in accounts payable of a finance account while evaluating one or more objectives related to amounts of payments in the bill payment plan, the computer-implemented method comprising:

generating, by a computer processor, a genome population having a first set of vectors, each vector in the first set of vectors representing the bill payment plan for a day, comprising a 24 hour period, numerically defining a payment amount corresponding to each payment obligation in the accounts payable;

obtaining a plurality of objectives with respect to the bill payment plan, each objective associated with a weight indicating the importance of the objective; and

modifying, by the computer processor, the genome population by use of a genetic algorithm, including;

determining a fitness for each of the vectors in the genome population using objective values, the objective values determined by applying objective functions to the vectors, each objective value weighted by a corresponding weight,

wherein determining the fitness for each vector comprises;

obtaining objective values (O_G) corresponding to associated objectives, each objective value representing a degree to which an associated objective of the associated objectives is optimized when the payment obligations are paid in accordance with the bill payment plan represented by the vector,

normalizing and standardizing each of the objective values (O_G) to obtain normalized, standardized objective values (O_i) corresponding to each of the objectives,

obtaining a composite objective value (O_comp) corresponding to the vector by the following equation;

$O_{\mathrm{comp}}=\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br><br><br>w_i<br><br>O_i$

 

where

 

O_comp is the composite objective value corresponding to the vector,

 

O_i is the normalized, standardized objective value corresponding to each of the objectives,

 

w_i is a weight corresponding to each objective, and

 

n is a number of objectives, and

applying a fitness function to the composite objective value O_comp to obtain a fitness score corresponding to the vector; and

introducing new vectors in the genome population derived from other vectors including the first set of vectors, until at least one of the vectors in the genome population represents the bill payment plan for the day, such that payment of each payment obligation in the accounts payable in accordance with the bill payment plan maximizes a total amount of payment of the payment obligations within an amount of available cash in the finance account for the day while simultaneously evaluating the one or more objectives.

3. The computer-implemented method of claim 2, wherein generating a genome population having a first set of vectors comprises generating the first set of vectors by random selection of numerical values representing the payment amount corresponding to each payment obligation in the accounts payable.

4. The computer-implemented method of claim 2, wherein each vector in the first set of vectors comprises a plurality of alleles each including a plurality of bits, and obtaining a genome population having a first set of vectors comprises:

randomly choosing a bit density d from a uniform distribution, wherein 0 is less than or equal to d and less than or equal to 1; and

in each of the first set of vectors, randomly setting each bit of each allele to one with a probability of d.

5. The computer-implemented method of claim 2, wherein each vector in the genome population includes a plurality of alleles, each allele corresponding to a payment obligation in the accounts payable and indicating a fractional payment amount.

6. The computer-implemented method of claim 2, wherein introducing new vectors in the genome population comprises:

selecting mating vectors from the first set of vectors based on the fitness of each of the first set of vectors;

mating the selected mating vectors to obtain a second set of vectors;

mutating the second set of vectors to obtain a third set of vectors; and

replacing selected ones of vectors in the first set of vectors in the genome population with the third set of vectors.

7. The computer-implemented method of claim 6, wherein the mating vectors are selected by roulette wheel selection.

8. The computer-implemented method of claim 6, wherein the mating vectors are selected by tournament selection.

9. The computer-implemented method of claim 6, wherein the mating vectors are mated by single point crossover.

10. The computer-implemented method of claim 6, wherein replacing selected ones of vectors in the first set of vectors comprises:

adding the third set of vectors to the first set of vectors to obtain a modified first set of vectors;

determining fitness of each vector in the modified first set of vectors;

removing a first predetermined number of the worst vectors from the modified first set of vectors based upon the determined fitness of the modified first set of vectors; and

adding a second predetermined number of the best vectors in the first set of vectors to the modified first set of vectors based upon the determined fitness of the first set of vectors.

11. The computer-implemented method of claim 2, wherein the fitness function comprises:

F=O_comp−

(O_average−

2·

O_σ

)

where

F is the fitness score corresponding to the vector;

O_comp is the composite objective value corresponding to the vector;

O_average is an average of the composite objective values corresponding to all the vectors in the genome population; and

O_σ

is a standard deviation of the composite objective values corresponding to all the vectors in the genome population.

12. The computer-implemented method of claim 2, wherein the weight is a user-specified value.

13. The computer-implemented method of claim 2, wherein the normalized, standardized objective value (O_i) corresponding to each objective is obtained by calculating a difference between the objective value (O_G) and an optimum objective value (O_A), and dividing the difference by a normalizing factor.

14. The computer-implemented method of claim 13, wherein the normalizing factor is a difference between the optimum objective value (O_A) and a worst objective value (O_Z).

15. The computer-implemented method of claim 2, wherein the associated objectives comprise maximizing the total amount of payments of the payment obligations within the amount of available cash in the finance account for the day.

16. The computer-implemented method of claim 2, wherein the associated objectives comprise maximizing or minimizing payments of important ones of the payment obligations according to user-specified importance levels.

17. The computer-implemented method of claim 2, wherein the associated objectives comprise maximizing discounts in the payment obligations.

18. The computer-implemented method of claim 2, wherein the associated objectives comprise minimizing late fees incurred by payment of the payment obligations.

19. The computer-implemented method of claim 2, wherein the associated objectives comprise minimizing new late fees incurred by payment of the payment obligations.

20. The computer-implemented method of claim 2, wherein the associated objectives comprise maximizing amount of payments of late payables in the payment obligations.

21. The computer-implemented method of claim 2, wherein the associated objectives comprise favoring payment of aged payables in the payment obligations.

22. The computer-implemented method of claim 2, wherein the associated objectives comprise minimizing delivery costs incurred by payment of the payment obligations.

23. The computer-implemented method of claim 2, wherein the associated objectives comprise maximizing payment of least recently paid ones of the payment obligations.

24. The computer-implemented method of claim 2, wherein the associated objectives comprise maximizing partial payment of the payment obligations.

25. The computer-implemented method of claim 2, wherein the associated objectives comprise minimizing full payment of the payment obligations.

26. The computer-implemented method of claim 2, wherein the associated objectives comprise maximizing number of payment obligations paid.

27. The computer-implemented method of claim 2, wherein the associated objectives comprise minimizing a total number of days of late payment of the payment obligations.

28. The computer-implemented method of claim 2, wherein the associated objectives comprise minimizing a total number of days of early payment of the payment obligations.

29. A computer readable medium storing computer executable instructions for determining an optimal bill payment plan corresponding to a plurality of payment obligations in accounts payable of a finance account while evaluating a plurality of objectives related to amounts of payments in the bill payment plan for a day, comprising a 24 hour period, the instructions comprising functionality for:

generating a genome population having a first set of vectors, each vector representing the bill payment plan, numerically defining for each payment obligation a payment amount; and

modifying iteratively the genome population using a genetic algorithm until a vector of the first set of vectors forming the optimal bill payment plan is determined that maximizes a total amount of payment of the payment obligations on the day within an amount of available cash in the finance account for the day while simultaneously evaluating the plurality of objectives

wherein the genetic algorithm comprises determining a fitness for the vector of the first set of vectors, and

wherein determining the fitness for the vector comprises;

obtaining a plurality of objective values (O_G) for the plurality of objectives, wherein the plurality of objective values represent a plurality of degrees of optimization of the plurality of objectives when the payment obligations are paid in accordance with the bill payment plan represented by the vector,

normalizing and standardizing the plurality of objective values (O_G) to obtain a plurality of normalized, standardized objective (NSO) values (O_i) for the plurality of objectives,

obtaining a composite objective value (O_comp) corresponding to the vector by the following equation;

$O_{\mathrm{comp}}=\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br><br><br>w_i<br><br>O_i$

where

 

O_comp is the composite objective value corresponding to the vector,

 

O_i is the NSO value corresponding to the plurality of objectives,

 

w_i is a weight corresponding to the plurality of objectives, and

 

n is a number of objectives, and

applying a fitness function to the composite objective value O_comp to obtain a fitness score corresponding to the vector.

30. A computer-implemented method of determining an optimal bill payment plan corresponding to a plurality of payment obligations in accounts payable of a finance account while evaluating a plurality of objectives related to amounts of payments in the bill payment plan for a day, comprising a 24 hour period, the computer-implemented method comprising:

generating, by a computer processor, a genome population having a first set of vectors, each vector representing the bill payment plan, numerically defining for each payment obligation a payment amount; and

modifying iteratively, by the computer processor, the genome population using a genetic algorithm until a vector of the first set of vectors forming the optimal bill payment plan is determined that minimizes a total amount of payment of the payment obligations on the day while simultaneously evaluating the plurality of objectives,

wherein the genetic algorithm comprises determining a fitness for the vector of the first set of vectors, and

wherein determining the fitness for the vector comprises;

obtaining a plurality of objective values (O_G) for the plurality of objectives, wherein the plurality of objective values represent a plurality of degrees of optimization of the plurality of objectives when the payment obligations are paid in accordance with the bill payment plan represented by the vector,

normalizing and standardizing the plurality of objective values (O_G) to obtain a plurality of normalized, standardized objective (NSO) values (O_i) for the plurality of objectives,

obtaining a composite objective value (O_comp) corresponding to the vector by the following equation;

$O_{\mathrm{comp}}=\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br><br><br>w_i<br><br>O_i$

where

 

O_comp is the composite objective value corresponding to the vector,

 

O_i is the NSO value corresponding to the plurality of objectives,

 

w_i is a weight corresponding to the plurality of objectives; and

n is a number of objectives, and

applying a fitness function to the composite objective value O_comp to obtain a fitness score corresponding to the vector.