Transcript CEC 2005 - Brunel University

ICARUS: Intelligent Coupon
Allocation for Retailers Using Search
Stephen Swift1, Amy Shi2,
Jason Crampton3, Allan Tucker1
1SISCM,
Brunel University, UK
2Loyalty Logic Limited, Fleet, Hampshire, UK
3Information Security Group, Royal Holloway, UK
1
Introduction (1)
• Many retailers run loyalty card schemes
• They offer incentives in the form of
money off coupons
• The total value of the coupons depends
on how much the customer has spent
2
Introduction (2)
This paper deals with the problem of
finding the smallest set of coupons such
that each possible total can be
represented as the sum of a pre-defined
number of these coupons
3
Introduction (3)
For example, if the reward totals ranged
between £2 and £6
Reward Total
£
2
3
4
5
6
Solution using Solution using
{1, 2, 3, 4, 5}
{1, 2, 3}
1+1
1+2
1+3
1+4
1+5
1+1
1+2
2+2
2+3
3+3
The smallest set that can span all solutions is
considered the best, i.e. {1, 2, 3}
4
Introduction (4)
• A mathematical analysis of the problem
is presented
• Leading to a Genetic Algorithm solution
• The algorithm is applied to real world
data using several crossover operators
• Compared to straw-person methods
• Considerable time can be saved
5
Business Description (1)
• Coupons mailed out every 4-6 months
• The reward value is a percentage of
the customer’s expenditure
• The expiry date and value is encoded
as a barcode on each coupon
• The number of coupons is fixed (very
important!)
6
Business Description (2)
• As small a number of denominations of
coupons is needed
– The barcode space (hence range of values)
is small
– A large number of coupon values will mean
that the scheme will have to be redesigned
too quickly
7
Business Description (3)
£ Coupon 1
£ Coupon 2
Retailer Ltd. 
Dear Dr Swift,
£ Coupon 3
£ Coupon 4
Some other money saving
offers, such as fixed amounts
off certain targeted products
…………
8
The Allocation Problem (1)
• The monetary value of each coupon
should be evenly distributed
• “Good looking” numbers are preferred
by customers, e.g. divisible by five
• Coupon values should not exceed the
typical basket value, which is between
9
£25 and £35
The Allocation Problem (2)
An example of well-allocated coupons:
Customer with total reward value of £20.00
£2
£5
£5
£10
:
 balanced
 good looking numbers
 values fit a typical basket
Number of vouchers = 4
An example of badly allocated coupons:
£1
£1
£1
X not balanced
X odd looking numbers
X values are low/high for a typical basket
£17
10
A Short Note
• The problem would be trivial if:
– The number of coupons required was not
specified, e.g. 1, 2, 5, 10, 20, 50, 100, …
– The number of overall coupon
denominations did not have to be as small
as possible
11
Mathematical Representation
• We extensively use the fact that an
instance of the problem can be split
into several smaller instances
• A recursive algorithm can be developed
to see if a particular instance of the
problem can be solved
12
ICARUS
• ICARUS: Intelligent Coupon Allocation for
Retailers Using Search
• We solve the coupon allocation problem using
a binary Genetic Algorithm (GA)
• Find the smallest coupon set (A) that spans a
given reward set V in m coupons
13
ICARUS - Representation
• A Binary string where the length is
application dependant (see paper)
• A candidate coupon solution set is
constructed from the corresponding
chromosome, if gene i is 1 then the set
A contains i
• For 5 genes, 10101 : coupons {1, 3, 5}
14
ICARUS – Fitness Function
Fitness = G(A) x H(V, m, A) (low is better)
G(A) :
Measures how “Good
Looking” the values are
H(V, m , A) : Measures how well A
spans V (uses the
recursive function)
15
ICARUS – Operators
Crossover: Uniform, One Point & AND/OR
Mutation: Binary
Survival: Ranked
16
ICARUS – Post Processing
• The recursive function can be used to
generate all possible solutions for all
reward totals
• The “best” solution for each reward
total can be selected either by the user
or by using some criteria
17
Evaluation
• Three Crossover operators
• Simulated Annealing
• Hill Climbing
• The current manual results
18
Test Problem
• A real world reward, run last year
• 85 reward totals between £0 to £116
• m = 4 (number of coupons)
0
2
4
6
8
10
12
14
16
18
20
22
24
26
28
30
32
34
36
38
40
42
44
46
48
50
52
54
56
58
60
62
64
66
68
70
72
74
76
78
80
82
84
86
88
90
92
94
96
98
100
102
104
106
108
110
112
114
116
• Additional post processing required
19
Results (1)
8000
UNIFORM
ONEPOINT
ANDOR
SA
HC
Manual
7000
6000
5000
4000
3000
0
10000 20000 30000 40000 50000
20
Results (2)
5000
UNIFORM
ONEPOINT
ANDOR
SA
HC
Manual
4500
4000
3500
3000
0
5000
10000
15000
20000
21
Results (3)
Method
UNIFORM
ONEPOINT
ANDOR
SA
HC
Manual
Min.
3010
3010
3010
3010
4644
7826
Max.
3096
3096
3096
3096
7052
7826
Mean
3037.5
3034.1
3071.9
3068.5
6123.2
7826.0
St.Dev.
40.9
39.4
39.4
40.9
666.2
0.0
22
Results (4)
Method
UNIFORM
ONEPOINT
ANDOR
SA
HC
Manual
Coupon Denominations (Number)
1 2 5 10 20 30 32 (7)
1 2 5 10 20 30 32 (7)
1 2 5 10 15 30 33 35 (8)
1 2 5 10 20 30 32 (7)
1 2 3 4 5 12 25 28 35 (9)
1-10 15 20 25 30 35 40 45 50 (18)
23
Concluding Remarks
• We have presented a method for
solving the reward scheme coupon
allocation problem
• This is achieved through the use of a
binary Genetic Algorithm
• The results show that ICARUS using one
point crossover performs best
• The ICARUS method runs in a few
24
minutes
Future Work
• The ICARUS algorithm is really a
prototype/proof of concept
• The use of a Multi-Objective GA could
be explored
• It is intended that ICARUS be used to
determine the next run for the retailer
25
Acknowledgements
The authors would like to thank the
unnamed retailer who provided the
dataset used within this paper, Janet
McFall for her helpful comments and the
reviewers for their constructive advice
26