An iterated local search for the Book Scanning Problem
This paper presents an iterated local search algorithm with automatically configured parameters and a public benchmark of 324 instances to solve the Book Scanning Problem, achieving superior solution quality compared to existing methods while proving optimality for 21 cases.
Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer
Imagine a library network preparing for a massive digitization project. They have a strict deadline, a fleet of libraries ready to scan, and millions of books to process. The challenge is not just about having the scanners; it is about the schedule. Each library must sign up before it can start scanning, but only one library can sign up at a time. Once signed up, a library begins scanning its books immediately, working in parallel with the others. However, every day spent waiting for a library to sign up is a day lost for the scanning process. Furthermore, many books exist in multiple libraries. If a rare book is held by three different libraries, the project only gets credit for scanning it once, regardless of how many times it is physically copied. The goal is to decide the order in which libraries sign up and which specific books each library should scan to maximize the total value of the collection digitized before time runs out. This is a complex puzzle of timing and selection, where a poor choice early on can waste the potential of a valuable library later.
This specific puzzle, known as the Book Scanning Problem, was the subject of a major competition in 2020. While many teams created custom solutions to win that contest, those solutions were often tailored so specifically to the test cases that they could not be easily applied to new situations. A team of researchers from Kosovo has now developed a more general approach to solve this problem. They created a method called an "iterated local search," which acts like a persistent explorer trying to find the best possible schedule. Instead of guessing a single answer, the method starts with a rough plan and then repeatedly makes small adjustments to see if the result improves. It tries swapping the order of libraries, removing a library that isn't contributing much, or inserting a new one that might bring in rare books. If a change makes the score worse, the method sometimes still accepts it, just as a hiker might take a slightly longer path to avoid a dead end, hoping to find a better route later.
The researchers tested their method on hundreds of different scenarios, ranging from small collections to massive archives containing two million books. They compared their results against the best existing solutions from the original competition. The new method proved to be highly effective, scoring higher than the combined best of six other methods on the majority of the test cases. In total, it achieved a score that was 2.362% higher than the previous best aggregate results. This might seem like a small percentage, but in the context of digitizing millions of books, it represents a significant increase in the amount of cultural heritage preserved. The researchers also found that their method was particularly good at handling difficult cases where libraries had very different signing-up times and scanning speeds. In some instances, the method found solutions that were mathematically proven to be the absolute best possible, meaning no other schedule could possibly do better.
A key discovery in this work was understanding which parts of the method actually mattered most. The researchers broke down their system to see what each piece contributed. They found that the most important part was not the initial guess or the random shuffling, but the ability to change the set of libraries that were actually working. Simply rearranging the order of the same libraries helped, but swapping a library out for a different one entirely had the biggest impact on the final score. This suggests that the hardest part of the problem is deciding which libraries should participate at all, rather than just the order in which they line up. The method also showed great stability; when run multiple times on the same problem, it produced nearly identical results every time, proving that it is a reliable tool rather than a lucky guess.
The study does not claim to have solved every possible version of this problem, nor does it claim to have beaten every single record set during the original contest. In fact, on the five official contest instances, the new method was slightly behind the very best specialized solutions, which were hand-tuned by experts for those specific cases. However, the strength of this new approach is its flexibility. It uses a single, consistent strategy for every type of problem it encounters, without needing to be reprogrammed for each new library network. The researchers also provided a public collection of test cases and their results, allowing other scientists to verify their work and build upon it. By combining a clear mathematical model with a robust search strategy, they have shown that a general, adaptable method can compete with highly specialized ones, offering a transparent and reproducible way to tackle complex planning problems in the real world.
Drowning in papers in your field?
Get daily digests of the most novel papers matching your research keywords — with technical summaries, in your language.