Distribution of fiscal coupons via Genetic Algorithms and Greedy Randomized Adaptive Search Procedure

Abstract

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 optimization 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 solve this problem by means of two metaheuristics, namely Genetic Algorithms and Greedy Randomized Adaptive Search Procedure. Finally, we evaluate the proposed algorithms by comparing their results against the relaxed versions of the proposed problem. The computational experiments indicate that both approaches are competitive, as they can be used to solve realistic problems in a matter of few seconds by utilizing standard personal computers.