This short paper presents ongoing work on solving the Book Scanning problem introduced in the Google Hash Code 2020 competition. The problem requires scheduling library signups and book scanning activities to maximize the total score, subject to time and capacity constraints. Two metaheuristic approaches are investigated: Iterated Local Search (ILS) and Genetic Algorithms (GA). A Greedy Randomized Adaptive Search Procedure (GRASP) is used to construct the initial solution, which is subsequently improved through neighborhood-based search. The methods are evaluated on a set of benchmark and synthetically generated instances. Results show that both ILS and GA produce competitive solutions, with GA consistently matching or exceeding best-known results across most instances and demonstrating lower variability. ILS performs similarly in terms of solution quality but tends to exhibit higher fluctuation across runs. The findings highlight the efectiveness of metaheuristic approaches in large-scale, constrained scheduling problems and confirm GA's advantage in consistency and robustness.
Let be the set of books and the set of libraries. Denote by the total number of days available for scanning. For each book ∈ , let be the score awarded when the book is scanned.
For each library ∈ , we define ⊆ as the set of books available in library . Let be the number of days required to complete the signup process for library , and be the number of books that can be scanned each day from library once the signup process is completed.
We define the following decision variables: • ∈ {0, 1}, ∈ , a binary variable which takes the value 1 if library is selected for signup, and 0 • ∈ {0, 1}, ∈ , ∈ , a binary variable which takes the value 1 if book is scanned from library
LGOBE
CEUR
ceur-ws.org • ∈ {0, 1}, ∈ , a binary variable which takes the value 1 if book is scanned from any library, and 0 otherwise.
before library 2, and 0 otherwise. • 1, 2 ∈ {0, 1}, 1, 2 ∈ , 1 ≠ 2, a binary variable which takes the value 1 if library 1 is processed • ∈ {0, 1, … , − 1} , ∈ , an integer variable which gives the day on which the signup process for library starts.
Using these definitions, the Book Scanning Problem can be formulated as a Mixed-Integer Linear Programming (MILP) model using the following equations:
Maximize subject to: ∑ ∈ ∈ ≥ ≤ ∑ ≤ 1 ∀ ∈ , ∀ ∈ , ∀ ∈ ∀ ∈ , ∀ ∈ , , 1, 2 + 2, 1 ≤ 1 ∀ 1, 2 ∈ , 1 ≠ 2, 2 ≥ 1 + 1 ⋅ 1 − ⋅ (1 − 1, 2)
∀ 1, 2 ∈ , 1 ≠ 2, 1, 2 + 2, 1 ≥ 1
+ 2 − 1 ∀ 1, 2 ∈ , 1 ≠ 2, + ⋅ ≤ ∀ ∈ , ∑ ≤ ⋅ ( − − ) ⋅
∀ ∈ , ∈ ∈ ≤ ∑ ,
∈ ∑ ≤ | | ⋅
∀ ∈ ,
∀ ∈ ,
, , , 1, 2 ∈ {0, 1} ∀, 1, 2 ∈ , ∀ ∈ ,
∈ {0, 1, … , − 1} ∀ ∈ .
(
The objective function (
Constraints (
Constraints (
Finally, constraints (12) and (13) state that the decision variables are binary or non-negative integers as appropriate.
Our approach to solving the Book Scanning problem is twofold: one based on single-state solutions, such as Iterated Local Search (ILS) [3], and the other based on population-based methods, such as Genetic Algorithms (GA) [4]. Both approaches have proven efective in solving various planning and scheduling problems across diverse domains, such as technician routing and scheduling [5], and flexible job shop scheduling [6].
As part of the preprocessing phase, we begin by extracting the key structural components of the problem: books, libraries, and time constraints. Each book is associated with a unique score, while each library is characterized by its signup time, daily scanning capacity, and the list of books it holds. These books are sorted in decreasing order of their scores to prioritize higher-value selections during scanning. Additionally, we construct a hash table data structure that maps each book to the list of libraries in which it is available. This mapping facilitates eficient lookup during library selection and book allocation in later stages of the algorithm.
Figure 2.1 illustrates a snapshot of a possible solution configuration. Libraries that have already been signed up are represented as a list of hash tables, each mapping a library ID (as the key) to a list of book indices assigned for scanning from that library. Libraries that have not yet been signed up are grouped into a separate list, and books that remain unscanned are also tracked explicitly.
Based on this structure, the search space of the problem includes all possible ways to choose and order libraries for signup, all possible subsets of books to scan from those libraries, as well as the possible decisions to leave some libraries unsigned and some books unscanned.
More formally, let be the set of all libraries, and let be the set of all books. For each library ∈ , let ⊆ denote the set of books available in that library. Then the search space consists of: • All possible subsets ′ ⊆ representing the libraries selected for signup, and all permutations of ′ representing the signup order; • For each signed-up library ∈ ′, all possible subsets ⊆ of books selected for scanning, such that the scanning of can be completed within the remaining time after the library’s signup; • The set of libraries not selected for signup, ∖ ′, and the set of books not scanned in the solution, given by ∖ ⋃∈ ′ .
Efectively, the search space includes decisions about which subset of libraries to sign up, the order in which to sign them up, and the subset of books to scan from each selected library. It also involves deciding which libraries to exclude entirely and which books to leave unscanned.
The fitness function (Equation (
The initial solution is constructed using four diferent strategies, with the best among them adopted as the initial solution before the algorithm enters its iterative phase. Below, we provide details about each strategy.
Greedy by Signup and Book Score: This strategy prioritizes libraries with shorter signup times and higher total book scores. Libraries are sorted first by ascending signup days, then by descending total book score. Libraries are selected one by one, ensuring that the total number of days is not exceeded and that no duplicate books are scanned. For each selected library, the most valuable unscanned books are chosen, and the scanned book list and remaining days are updated accordingly.
Greedy by Eficiency : This strategy uses a priority queue (heap) to always select the library with the highest scanning eficiency. Eficiency is defined as the ratio of the potential book score (from the most
valuable books that can be scanned within the remaining time) to the library’s signup days. At each step, the most eficient library is selected, scanned books and remaining time are updated, and the heap is adjusted if needed.
Weighted Eficiency with Penalization : This strategy enhances the basic greedy approach by penalizing libraries selected later or those with high signup durations. It introduces two tunable parameters, α (alpha) and β (beta), to control the impact of signup time and selection order. Each library’s eficiency is calculated using a weighted formula that balances book value against registration cost and selection delay. At each step, the library with the highest weighted eficiency is selected, and the scanned book list, remaining time, and library count are updated. Parameters α and β can be fine-tuned for optimal performance.
GRASP-Based Initialization: This strategy constructs the initial solution using the Greedy Randomized Adaptive Search Procedure (GRASP) [7]. Libraries are first sorted by ascending signup days and then by descending total book score. At each step, one library is randomly selected from a Restricted Candidate List (RCL), containing the top 5% of libraries according to this ordering. Libraries are added sequentially, with their books scheduled for scanning immediately after signup. The process stops when no additional library can be added without exceeding the time limit.
To explore the solution space efectively and escape local optima, we define a set of neighborhood operators that modify the current solution in controlled ways. These operators generate neighboring solutions by altering the structure of the library signup order and book selections, while preserving feasibility with respect to the problem constraints.
The neighborhood is composed of the following six move types: • Swap between two signed-up libraries: Two libraries currently included in the solution are randomly selected, and their positions in the signup sequence are swapped. This move changes the order in which their scanning begins and can afect the number of books ultimately scanned due to timing constraints. • Swap of signed library with an unsigned library: A library that has been signed up is replaced with one that has not been signed up. The unsigned library is inserted into the same position in the signup sequence, and its book selection is initialized based on available scanning time. • Swap books between libraries that share common books: If two signed-up libraries contain overlapping books in their inventories, a book from one library can be swapped with a diferent book from the other. • Swap the last book of a selected library with an unscanned book: For a given library, the last book scheduled for scanning can be replaced with a book that has not yet been scanned. This allows fine-tuning of the scanned book list, potentially replacing low-value books with higher-scoring alternatives. • Random reordering of libraries with reassigned book sets: This move shufles the library order and attempts to reassign books from their old libraries to new randomly chosen ones. For each reassigned library, books are filtered to exclude those already scanned or not available in the new library. • Insert Library – Inserts a randomly selected unused library into a random position in the signed library list. From that position onward, the solution is completely rebuilt.
These neighborhood operations provide both diversification and intensification capabilities. By mixing structural changes (e.g., reordering libraries) with content-level changes (e.g., modifying scanned books), the search is guided toward promising regions of the solution space while maintaining suficient variability to avoid premature convergence.
The ILS algorithm [8] for the Book Scanning problem combines the described initial solution procedure with iterative refinement and perturbation mechanisms. The implementation follows the ILS with Random Restarts framework described by Luke [9]. The initial solution is generated using the procedure detailed in Section 2.2, which prioritizes libraries with shorter signup times and higher total book scores.
In the iterative phase of the algorithm, the solution is improved using a local search (hill climbing) procedure that applies several neighborhood operations, including swapping signed and unsigned libraries, reordering libraries with overlapping books, applying crossover-based reordering, and replacing the last book in a library with an unscanned, higher-value book. Neighborhoods are selected probabilistically, with 50% assigned to the move that swaps signed-up libraries with unsigned ones, 20% to the library reordering move, and the remaining 30% equally distributed among the other neighborhood operations. Only improving moves are accepted, except with a small probability (10%) of accepting worse solutions to escape local optima.
In each iteration, a perturbation step is applied using a destroy-and-rebuild strategy: a random subset of signed libraries is removed, and candidate replacements are evaluated greedily based on their average book score, scanning eficiency, and signup time. The algorithm runs until a total time limit (default: 300 seconds) or a maximum number of iterations (default: 1000) is reached.
The proposed approach [10] is based on the Genetic Algorithm with Elitism described by Luke [9], and initializes the population using small variations of the procedure in Section 2.2, generated through limited hill climbing steps. This introduces diversity while maintaining reasonably fit initial solutions.
After initialization, the algorithm evolves through multiple generations. In each generation, individuals are ranked by fitness, enabling efective selection. The best solution is preserved via elitism to ensure no loss of progress.
Ofspring are generated using tournament selection, where two parents are chosen by selecting the best individual from small random subsets of the population. This method favors stronger candidates while preserving diversity by giving weaker ones a chance.
Crossover is performed in a partially random but structured manner. Half of the library signup order is randomly taken from the first parent, with remaining positions filled by non-duplicate libraries from the second parent. Any missing libraries are appended to ensure completeness. This ensures valid ofspring while promoting trait inheritance from both parents.
Mutation is applied to each ofspring with a probability of 1.0, meaning it always occurs. Instead of random tweaks, mutation runs hill climbing for several steps, integrating local search into the genetic process. This hybrid approach forms a memetic algorithm, combining global evolution with greedy local refinement.
Over successive generations, fitter individuals are more likely to reproduce, guiding the population toward better solutions. Crossover and mutation introduce variation, while selection and elitism ensure steady improvement. The algorithm terminates after a fixed number of generations, returning the best solution found.
The preliminary experiments were conducted on a test set of 20 instances, with each algorithm executed ifve times. Both ILS and GA were run for a total of 12 minutes: 2 minutes were allocated for generating the initial solution, and the remaining 10 minutes were dedicated to the iterative phase of each respective algorithm. All computations were performed on standard computing machines without the use of parallelization or specialized hardware.
The test set used for evaluation consists of two subsets. The first subset includes five benchmark instances originally provided in the Google Hash Code 2020 competition. These instances vary significantly in size and complexity, featuring between 78,600 and 100,000 books, 100 to 30,000 libraries, and scanning periods ranging from 200 to 100,000 days. The average book score ranges from 65 to over 400, and library characteristics span from small, fast-signup libraries to very large ones with high daily throughput.
The second subset contains 15 additional instances generated using a custom instance generator [11]. These synthetic instances introduce controlled variations in structural parameters such as the number of books (ranging from 300 to 100,000), number of libraries (from 11 to 850), and available scanning days (from 14 to 140). The generator also allows for tuning average signup times and book shipment capacities per library. These instances provide a more diverse and challenging testbed for evaluating the scalability and robustness of the proposed algorithms under diferent constraint combinations.
For evaluation purposes, we use upper bound values as a theoretical benchmark. The upper bound is estimated by calculating, for each library, the total score of the books it could scan if it were signed up first. The libraries are then ranked by their maximum potential contribution, and the scores of the top- libraries—where is the number of libraries that can be signed up sequentially within the time limit—are summed.
Additionally, for comparative analysis, we include the results of state-of-the-art approaches found in the literature, specifically those by Bartosz et al. [ 12], Indzhev et al. [13], and Rodrigues [14], who ranked 5th, 28th, and 33rd, respectively, in the Google Hash Code Competition. In the tables below, for each instance, we present the best result achieved among these three approaches and refer to it as the Best Known value.
Table 1 presents the performance of ILS and GA compared to MILP results and the best-known values across all benchmark instances. The column Best Known refers to the highest score obtained by any known method from the literature or our experiments. In several cases, both ILS and GA match the best-known results, with GA slightly outperforming ILS in a few larger instances. Integer Programming results are included where available, primarily for smaller instances due to its computational limits. Overall, the results highlight the efectiveness of metaheuristic methods, with GA showing more consistent superiority in complex instances and ILS demonstrating competitive performance in many cases.
Table 2 complements the previous results by reporting standard deviations and relative performance comparisons between ILS and GA. The standard deviations show that GA exhibits lower variability than ILS in 4 instances, while both algorithms have a standard deviation of zero in the remaining 14 instances. In terms of relative performance, both ILS and GA show small average deviations from the best-known or IP-based values, with ILS yielding an average diference of 0.23% and GA achieving the same. When comparing their best solutions directly, the average performance diference between ILS and GA is (0.00%), suggesting that while GA tends to be more stable, both methods are capable of producing similarly competitive results.
In summary, both ILS and GA demonstrate strong performance across the benchmark instances. GA shows greater consistency, with lower variability in several cases and frequent matches with the best-known solutions. ILS is equally competitive in terms of best-case results but tends to exhibit higher variability, making it less stable across runs. The baseline approaches, including Integer Programming (where applicable), remain efective—particularly in smaller or less complex instances—but are consistently outperformed by the metaheuristic methods in larger and more challenging problem settings.
We thank all students of the Master’s study program in Computer or Software Engineering, generation 2024/2025, at the Faculty of Electrical and Computer Engineering, University of Prishtina, for their contributions in implementing various algorithm components in Python, as well as developing supporting tools such as the validator, instance generator, and solution visualizer.
During the preparation of this work, the authors used ChatGPT-4o and Claude.ai to check the grammar and spelling of the paper, as well as to analyze and reason about the mathematical model of the problem. Following the use of these AI tools, the authors reviewed and edited the content as necessary and assume full responsibility for the content of the publication.
ILS (STD) GA (STD)
b_read_on c_incunabula d_tough_choices e_so_many_books f_libraries_of_the_world B300_L11_D20 B500_L14_D18 B750_L20_D14 B1k_L18_D17 B1.5k_L20_D40 B2.5k_L25_D50 B4k_L30_D60 B5k_L90_D21 B6k_L35_D70 B9k_L40_D80 B50k_L400_D28 B60k_L70_D140 B90k_L850_D21 B95k_L2k_D28 B100k_L600_D28 Average
netlify.app/, 2025. Accessed: 2024-04-05. [12] B. Kostka, Ghc 2020 - google hash code 2020 repository, https://github.com/Kostero/ghc20, 2020.
Accessed: 2025-05-21. [13] E. Indzhev, Book scanning solution - google hash code 2020, https://github.com/indjev99/
Optimizational-Problems-Solutions/blob/master/book_scanning.cpp, 2020. Accessed: 2025-05-21. [14] P. Rodrigues, Hash code models, https://github.com/pedromig/hashcode-models/tree/main, 2021.
Accessed: 2025-05-21.