Cash flow optimization using a genetic algorithm

• US 20040143524A1
• Filed: 01/22/2003
• Published: 07/22/2004
• Est. Priority Date: 01/22/2003
• Status: Active Grant

• Current Assignee: Intuit, Inc.
• Original Assignee: Intuit, Inc.
• Inventors: Hilton, Kenneth W.
• Granted Patent: US 7,124,105 B2
• Time in Patent Office: Days
• US Class Current: 705/35
• 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 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes
• CPC Class Codes: G06Q 40/06 Asset management; Financial planning or analysis
• CPC Class Codes: G06Q 40/10 Tax strategies

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 the minimum daily cash on hand in the finance account. 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 a 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 cash flow plan corresponding to a plurality of payment obligations in accounts payable of a finance account while optimizing at least one objective related to amounts of the payments and dates of the payments in the cash flow plan, the computer-implemented method comprising:

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

iteratively modifying the genome population using a genetic algorithm until a vector forming the optimal cash flow plan is determined that maximizes a minimum daily cash on hand in the finance account while simultaneously optimizing the plurality of objectives.

2. A computer-implemented method of determining a cash flow plan corresponding to a plurality of payment obligations in accounts payable of a finance account while optimizing at least one objective, the computer-implemented method comprising:

generating a genome population having a first set of vectors, each vector in the first set of vectors representing the cash flow plan, numerically defining a payment date and a payment amount corresponding to each payment obligation in the accounts payable;

obtaining a plurality of objectives with respect to the cash flow plan, the objectives including maximizing a minimum daily cash on hand in the finance account and each objective associated with a weight indicating the importance of the objective; and

modifying 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 object value weighted by the corresponding weights; 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 a cash flow plan, such that payment of each payment obligation in the accounts payable in accordance with the cash flow plan maximizes the minimum daily cash on hand in the finance account while optimizing the 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 date and 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

O<

=d<

=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 payment date and a fractional payment amount.

6. The computer-implemented method of claim 2, wherein the payment date in the allele is represented in the form of a date offset relative to a payment due date and a sign of the date offset.

7. 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.

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

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

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

11. The computer-implemented method of claim 7, 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;

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.

12. The computer-implemented method of claim 2, wherein determining a fitness for each vector comprises:

obtaining objective values O_G corresponding to the associated objectives, each objective value representing a degree to which the associated objective is optimized when the payment obligations are paid in accordance with the cash flow plan represented by the vector;

normalizing and standardizing each of the objective values O_G to obtain normalized, standardized objective values O_G 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>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 the weight corresponding to each objective; and

n is the number of objectives; and

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

13. The computer-implemented method of claim 12, wherein the fitness function comprises:

F=O_comp−

(O_average−

2·

O<sub>σ

)</sub>

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.

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

15. The computer-implemented method of claim 12, wherein the weights add up to one.

16. The computer-implemented method of claim 12, wherein the normalized, standardized objective value O_i corresponding to each objective is obtained by dividing a difference between the objective value O_G and an optimum objective value with a normalizing factor.

17. The computer-implemented method of claim 16, wherein the normalizing factor is a difference between the optimum objective value and a worst objective value.

18. The computer-implemented method of claim 12, wherein the associated objectives comprise maximizing a minimum daily cash on hand in the finance account, and the normalized, standardized objective value O_i for the objective of maximizing the minimum daily cash on hand is obtained by:

O_i=|O_A−

O_G|/|O_A−

O_z|,

where O_A is the minimum daily cash on hand that would be available when none of the payment obligations in the accounts payable is paid;

O_Z is the minimum daily cash on hand that would be available when all the payment obligations in the accounts payable are paid on an initial day; and

O_G is total cash generated when the payment obligations in the accounts payable are paid in accordance with the cash flow plan represented by the vector.

19. The computer-implemented method of claim 12, wherein the associated objectives comprise minimizing late payment penalties, and the normalized, standardized objective value O_i for the objective of minimizing late payment penalties is obtained by:

O_i=|O_A−

O_G|/|O_A−

O_z|,

where O_A is a zero;

O_Z is a sum of all late payment penalties associated with the payment obligations when all the payment obligations are paid late; and

O_G is the total amount of late payment penalties to be paid when the payment obligations are paid in accordance with the cash flow plan represented by the vector.

20. The computer-implemented method of claim 12, wherein the associated objectives comprise maximizing tax deduction, and the normalized, standardized objective value O_i for the objective of maximizing tax deduction is obtained by:

O_i=|O_A−

O_G|/|O_A−

O_Z|,

where O_A is the amount of tax deduction available when all the payment obligations are tax deductible;

O_Z is zero; and

O_G is the amount of tax deduction available when the payment obligations are paid in accordance with the cash flow plan represented by the vector.

21. The computer-implemented method of claim 12, wherein the associated objectives comprise minimizing the number of check runs, and the normalized, standardized objective value O_i for the objective of minimizing the number of check runs is obtained by:

O_i=|O_A−

O_G|/|O_A−

O_z|,

where O_A is zero;

O_Z is equal to the number of payment obligations; and

O_G is the required number of check runs when the payment obligations are paid in accordance with the cash flow plan represented by the vector.

22. The computer-implemented method of claim 12, wherein the associated objectives comprise minimizing the number of check runs per vendor, and the normalized, standardized objective value O_i for the objective of minimizing the number of check runs per vendor is obtained by:

O_i=|O_A−

O_G|/|O_A−

O_Z|,

where O_A is O;

O_Z is equal to the number of payment obligations to the vendor; and

O_G is the number of check runs for the vendor when the payment obligations are paid in accordance with the cash flow plan represented by the vector.

23. The computer-implemented method of claim 12, wherein the associated objectives comprise minimizing a total postage fee, and the normalized, standardized objective value O_i for the objective of minimizing the total postage fee is obtained by:

O_i=|O_A−

O_G|/|O_A−

O_Z|,

where O_A is a total postage fee when all payments corresponding to the payment obligations are mailed by using a lowest available postage;

O_Z is a total postage fee when all payments corresponding to the payment obligations are mailed using a most expensive available postage; and

O_G is a total postage fee that would be incurred when the payment obligations are paid in accordance with the cash flow plan represented by the vector.

24. The computer-implemented method of claim 12, wherein the associated objectives comprise minimizing regret value, and the normalized, standardized objective value O_i for the objective of minimizing regret value is obtained by:

O_i=|O_A−

O_G|/|O_A−

O_Z|,

where O_A is O;

O_Z is 1; and

O_G is the average regret value when the payment obligations are paid in accordance with the cash flow plan represented by the vector.

25. The computer-implemented method of claim 2, wherein:

the finance account includes a secondary account from which cash may be transferred to a primary account; and

each vector in the genome population includes a plurality of alleles and a sweep account allele, each of the plurality of alleles corresponding to a payment obligation in the accounts payable and indicating a payment date and a fractional payment amount, and the sweep account allele representing a fraction of the amount of cash available in the secondary account to be transferred to the primary account.

26. A computer program product for determining a cash flow plan corresponding to a plurality of payment obligations in accounts payable of a finance account while optimizing at least one objective, the computer program product stored on a computer readable medium and adapted to perform a method comprising:

generating a genome population having a first set of vectors, each vector in the first set of vectors representing a cash flow plan, numerically defining a payment date and a payment amount corresponding to each payment obligation in the accounts payable;

obtaining a plurality of objectives with respect to the cash flow plan, the objectives including maximizing a minimum daily cash on hand in the finance account and each objective associated with a weight indicating the importance of the objective; and

modifying 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 and weighted by the corresponding weights; 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 a cash flow plan, such that payment of each payment obligation in the accounts payable in accordance with the cash flow plan maximizes the minimum daily cash on hand in the finance account while optimizing the objectives.

27. The computer program product of claim 26, 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.

28. The computer program product of claim 26, wherein determining a fitness for each vector comprises:

obtaining objective values O_G corresponding to the associated objectives, each objective value representing a degree to which the associated objective is optimized when the payment obligations are paid in accordance with a cash flow 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>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 the weight corresponding to each objective; and

n is the number of objectives; and

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

29. The computer program product of claim 28, 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.

30. A computer program product for determining an optimal cash flow plan corresponding to a plurality of payment obligations in accounts payable of a finance account while optimizing at least one objective related to amounts of the payments and dates of the payments in the cash flow plan, the computer program product stored on a computer readable medium and adapted to perform a method comprising:

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

iteratively modifying the genome population using a genetic algorithm until a vector forming the optimal cash flow plan is determined that maximizes a minimum daily cash on hand in the finance account while simultaneously optimizing the plurality of objectives.

31. A system for determining a cash flow plan corresponding to a plurality of payment obligations in accounts payable of a finance account while optimizing a plurality of objectives with respect to the cash flow plan by a genetic algorithm, the objectives including maximizing a minimum daily cash on hand and each objective being associated with a weight indicating the importance of the objective, the system comprising:

an initialization module for obtaining a genome population having a first set of vectors, each vector in the first set of vectors representing a cash flow plan, numerically defining a payment date and a payment amount corresponding to each payment obligation in the accounts payable;

a scoring module for determining fitness for each vector in the genome population using objective values, the objective values associated with the objectives and weighted by the corresponding weights;

a selection module for selecting mating vectors from the first set of vectors based on the fitness of each of the first set of vectors;

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

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

a replacement module for replacing selected ones of vectors in the first set of vectors in the genome population with the third set of vectors, the replacement module replacing the vectors until at least one of the vectors in the genome population represents a cash flow plan, such that payment of each payment obligation in accordance with the cash flow plan maximizes the minimum daily cash on hand while optimizing the objectives.

32. The system of claim 31, 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 the payment date and the payment amount.

33. The system of claim 32, wherein the payment date in the allele is represented in the form of a date offset relative to a payment due date and a sign of the date offset.

34. The system of claim 32, wherein the payment amount in the allele is represented in the form of a fractional payment amount.