Uma abordagem heurística para o single-finger keyboard layout problem

Abstract

The popularization of mobile devices and other equipments with virtual singlefinger keyboards unveils the fact that the QWERTY layout, originally developed for typing with all ten fingers, is not suited for the users’ needs. The problem associated with the design of a single-finger keyboard layout is denoted SK-QAP and it was formally introduced in the literature as a variation of the Quadratic Assignment Problem (QAP), a classical and challenging optimization problem. A literature review was conducted to gather related work regarding single-finger and n finger keyboard layouts’ design that employ an Operations Research-based methodology. This work proposes a heuristic approach to solve the SK-QAP by means of an Iterated Local Search (ILS) algorithm, called ILS-SKQAP. Three neighborhood structures were incorporated in the local search fase of the algorithm. Two of them (contour filling and pairwise-exchange) were previously applied to solve the SK-QAP, whereas two pairs swap was adapted, in this work, from a QAP neighborhood. Furthermore, two perturbation mechanisms were developed for the ILS-SKQAP: ejection chain and multiple pairwise-exchange. ILS-SKQAP was used to solve the 24 existing instances for English, French, Italian and Spanish languages with highly competitive results both in terms of solution quality and CPU time. Moreover, a set of six instances for the Portuguese language was developed and solved by the algorithm.