Assessing the optimal location for parking lots is surprisingly mathematically challenging, and a subset of a classic computational complexity problem with far wider applications. A team of data scientists has combined quantum annealing with a process that attempts to mimic the underlying processes of human intuition in a technique that delivers a solution accuracy that’s far superior to conventional approaches.
The technique is described in a paper first appeared online on September 30, 2022 in Intelligent and Converged Networks.
The Facility Location Problem, or FLP, is a long-standing challenge within operations research—the application of scientific methods to decision-making and problem-solving by managers in large commercial, public or military organizations. The FLP aims to determine the optimal location and number of facilities in a given area, given certain constraints
Decision-makers in a health care system, for example, may have to assess where a new hospital should be sited. If they site this facility in a location that is too difficult for the elderly to access, mortality rates might increase. The constraint here is trying to minimize mortality. But if they site the hospital in a location that is more easily accessible, real estate costs might eat up more of their budget—another constraint. This might also reduce healthcare providers’ ability to provide service, once again increasing mortality rates.
It may seem like identifying one or even any number of sweet spots where mortality rates and spending are lowest is mathematically straightforward. But finding exact solutions to this and other examples of the FLP—with many more constraints on what needs to be optimized than just distance and cost—is computationally challenging.
In fact, the FLP, a combinatorial optimization problem, is classified by complexity theory scholars to be in the “NP-hard” category of problems—the hardest there are. There is no one solution that can be applied to location planning for different situations in different domains.
Optimal parking-lot location is just another example of the FLP, and one that is of keen interest to city administrators wanting to avoid congestion and, by extension, reduce greenhouse gas emissions. The less time motorists spend looking for a place to park, the less traffic and fewer GHGs. In many cities in rapidly urbanizing regions, not least in the developing world, this is an urgent concern.
Conventional methods used to produce decent (but not exact) solutions to the parking lot location problem include various types of algorithms performed by artificial intelligence on classical computers (as opposed to quantum computers). But once the volume of data involved rises significantly, the performance of these “classical intelligent algorithms” decreases sharply.
“At this point, the intuition of a person can outperform the computer,” said Sumin Wang, co-author of the paper and a researcher with the Key Laboratory of Specialty Fiber Optics and Optical Access Networks at Shanghai University. “But such intuition shouldn’t be thought of as mystical or mere ‘gut feelings.’ There is a solid scientific explanation for where human intuition comes from, and this can inspire us to try to mimic it with computers.”
When an engineer or architect has a feeling that a bridge, building system or other engineered structure is about to fail, but cannot straightforwardly justify why, this may come about as a result of decades of experience. A cyclist can sense exactly when their bike is about to topple over without being able to explain what it was that they were sensing that allowed them to perform such an assessment.
The extensive experience and accumulated knowledge can allow the individual to rapidly assess the totality of a situation and directly perceive a fact without working through a process of traditional reasoning, permitting quick and efficient decisions despite the complex environments.
Those who study human intuition describe what is happening in the brain as a rapid, sharp reduction in the “search space”—the term computer scientists use to describe the landscape of feasible solutions. The experience and knowledge allow humans to “just know” how to selectively attend to the most salient aspects of the problem, discard the rest, and thus simplify the necessary calculations.
“Artificial intuition,” replicating human intuition artificially, is an emerging field of research within the field of artificial intelligence. The aim is to develop human-brain-inspired intuitive reasoning methods—one of the most powerful capabilities we possess—that similarly focus on core data while ignoring non-important data to narrow the search space.
Using the optimal parking lot location problem, the researchers developed what they call a Selective Attention Mechanism (SAM), inspired by human intuition, and combined it with quantum annealing (QA).
QA has separately received a lot of attention in recent years as a new computational paradigm for solving classical optimization problems. QA algorithms provide significant improvements in terms of algorithm running time and solution quality for some NP-hard problems that are poorly solved by classical methods.
In optimization problems, one is searching for the optimum of many possible combinations, a minimum or maximum. And in physics, everything is on the hunt for its minimum energy state, from balls rolling down hills to excited electrons returning to their ground state. This means that optimization problems can in essence be recast as energy minimization problems. QA just exploits quantum physics to locate the lowest energy states of a problem, and thus the minimum or maximum of the target attribute. QA has already been deployed in various applications from traffic optimization to resource scheduling and quantum chemistry.
For their parking lot optimization problem, the researchers used SAM to reduce the search space and provide direction for the next search step, and QA to search that space and improve search efficiency.
They applied their concept to a real-world parking experience using real latitude and longitude data from Luohu District in Shenzhen, China. This open-platform government data included sites of high demand for parking, possible parking locations, existing parking lot locations, and their parking capacity. Luohu District covers an area of about 80 square kilometers, far too large a region for any classical intelligent algorithm with limited computing resources to directly calculate all the data in the area.
The whole area was first partitioned into blocks to save computational resources, then SAM was applied to focus on important data points, which were automatically filtered and optimized. New location results were then obtained by simulating QA’s preference for low energy states. Selective attention points were in turn updated based on those facility location results, and the process repeated multiple times until a clear solution—the location of a proposed new parking lot in the region—emerged
To evaluate their approach, the researchers used a technique commonly used to measure the solution accuracy of multiple-objective algorithms. Compared with competing approaches, the SAM plus QA technique produced more optimal and feasible solution sets in shorter run time.
The researchers now want to take their approach and apply it to other siting problems and related applications of artificial intuition.
More information:
Chao Wang et al, An asymptotically optimal public parking lot location algorithm based on intuitive reasoning, Intelligent and Converged Networks (2022). DOI: 10.23919/ICN.2022.0017
The paper is also available on SciOpen by Tsinghua University Press.
Provided by
Tsinghua University Press
Citation:
‘Artificial intuition’ delivers better answers to thorny parking-lot optimization problem (2023, January 13)
