The Seesaw of Supply and Demand

SMU Assistant Professor Pradeep Varakantham takes on complex urban challenges by dynamically and continuously matching supply with demand. 

Back to Research@SMU Issue 32

Photo Credit: Cyril Ng

SMU Office of Research – The next time you find yourself in a heavy downpour, jostling with the crowd for taxis that seem to have gone into hiding, you might consider it a lesson in economics. The basic problem of limited supply versus unpredictable demand lies at the heart of many common frustrations of city life.

Seeking to address such urban challenges is Assistant Professor Pradeep Varakantham of the Singapore Management University (SMU) School of Information Systems, who uses a variety of methods from artificial intelligence, machine learning, operations research and behavioural economics to dynamically and continuously match supply with demand. “Since we have large data sets for these matching problems, they provide ideal settings for us to understand the potential impact of our research on real-world problems,” he shares.

Part of what draws Professor Varakantham to the field of continuous matching is the real potential to improve the quality of life in urban environments, from reducing waiting times for public transportation to improving public safety. At the same time, these problems are also theoretically and practically challenging, capturing his fascination as a researcher.

Speeding up emergency responses

To find ways to deploy emergency vehicles, security patrols and law enforcement personnel in more effective ways, Professor Varakantham engages with the people who keep Singapore safe around the clock. These include agencies such as the Singapore Civil Defence Force (SCDF, responsible for emergency response vehicles such as ambulances and fire trucks) and the Singapore Police Force and Coast Guard (patrol cars and boats).

Once a problem is identified, Professor Varakantham constructs a model that best represents the available data, and uses it to obtain optimal strategies for matching supply with demand. These strategies are then tested out on a fresh set of real-world data (or on simulated data if this is not available).

In their 2015 paper “Risk based Optimization for Improving Emergency Medical Systems” in Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, Professor Varakantham and his SMU colleagues Professor Lau Hoong Chuin and Sandhya Saisubramanian and used data from SCDF to develop a model and matching algorithms on how to best match ambulances to base stations so that they can respond quickly to emergencies.

“We have shown in simulations that we can improve response times by at least two minutes,” he says, adding that the team will be working with SCDF to apply their findings. 

Better traffic patrolling for safer roads

Another intriguing research question involved the scheduling of traffic police patrols, which Professor Varakantham and colleagues studied in a 2014 paper, “STREETS: Game-Theoretic Traffic Patrolling with Exploration and Exploitation,” in Proceedings of Innovative Applications in Artificial Intelligence (IAAI) at the Twenty-Eighth AAAI Conference on Artificial Intelligence.

Traffic police patrols improve road safety by discouraging reckless driving. But with a limited number of personnel and a large number of road segments, the goal of the study was to reduce traffic violations in Singapore by continuously matching the two.

“This is a fascinating problem because it can be viewed as a game between traffic police and drivers,” explains Professor Varakantham. Drivers are more likely to disregard traffic laws if they can predict when traffic police would not be on a certain road segment. on the other hand, they are extra careful once traffic police are seen on the road.

Using game theory concepts to model randomised strategies, the researchers developed a new algorithm they called STrategic Randomisation with Exploration and Exploitation in Traffic patrol Schedules, or STREETS. Their approach addresses a number of challenges for the first time, including the massive scale (thousands of drivers) and complexity (road networks are dynamic, and certain factors such as congestion and traffic signals are unpredictable) of the problem.

“We proposed the use of randomised patrols that make it difficult for people to predict positions of traffic police at different times of the day, while also guaranteeing coverage of road segments that have high violations,” he says.

Professor Varakantham has used a similar approach to schedule randomised security patrols in rail networks; his approach has been tested in train stations in Los Angeles. In addition, a part of his collaborative work on reducing customer waiting times in theme parks has also been tested at a major theme park in Singapore.

Man versus machine

A major challenge for his field, says Professor Varakantham, is predicting demand. In some cases, there is not enough data to make strong predictions. For instance, it is difficult to find out how many violations occurred on a section of road that is unmonitored by traffic police.

Prediction accuracy, Professor Varakantham believes, can be improved with a combination of machine learning techniques and additional sensors. Tapping into the network of communications between physical objects such as phones and cars, termed the Internet of Things, will help to reduce the human inefficiencies and address problems such as congestion, high response times and high vulnerability, he says. “In essence, the vision is to build a coordinated Internet of Things and People through the use of smart ‘matching’ algorithms that is extremely efficient.”  

There is a balance to be struck, though, and some complex, high-stakes problems such as security will still require human experience. “Given the extreme nature of things that can happen if an error is made, is it possible for our systems to automatically figure out when to yield control to experienced humans?” he asks. “Can matching systems automatically self-analyse, explain and adjust their autonomy online? Undeniably, human expertise is still necessary, and what I’m doing is to make sure that the systems are performing at their best to support human experience.”

Back to Research@SMU Issue 32