Solving the Problem of Distribution of Fiscal Coupons by Using a Steady State Genetic Algorithm

摘要

When customers buy goods or services from business entities they are usually given a receipt that is known with the name fiscal or tax coupon, which, among the others, contains details about the value of the transaction. In some countries, the fiscal coupons can be collected during a certain period of time and, at the end of the collection period, they can be handed over to the tax authorities in exchange for a reward, whose price depends on the number of collected coupons and the sum of their values. From the optimisation perspective, this incentive becomes interesting when, both the number of coupons and the sum of their value is large. Hence, in this paper, we model this problem in mathematical terms and devise a test set that can be used for benchmarking purposes. Furthermore, we propose a solution based on Genetic Algorithms, where we compare its results versus the results to the solution of the relaxed versions of the proposed problem. The computational experiments indicate that the proposed solution obtains promising results for complex problem instances, which show that the proposed algorithm can be used to solve realistic problems in a matter of few seconds by utilizing standard personal computers.