Carnegie Mellon University
July 28, 2016

Pennsylvania High School Students Tie World Records for Solving Artificial Intelligence Problem

Students Created Artificial Intelligence Framework for the Vehicle Routing Problem with Time Windows as Part of the Pennsylvania Governor’s School for the Sciences, Held at Carnegie Mellon

By Jocelyn Duffy

Pennsylvania High School Students Tie World Records for Solving Artificial Intelligence Problem Pennsylvania High School Students Tie World Records for Solving Artificial Intelligence Problem

A group of high school students participating in the Pennsylvania Governor’s School for the Sciences (PGSS) at Carnegie Mellon University have tied eight world records for solving a version of the infamous Traveling Salesman Problem.

The students tackled a version of the problem known as the Vehicle Routing Problem with Time Windows. The problem is straightforward: What is the most efficient way to deliver packages to a set number of customers during a given time window? How can you minimize the number of trucks needed and the distance traveled? While the problem is simple to explain, the answer is very complex and gets increasingly more complex with each delivery added to the total number of deliveries. Even if there were only 13 deliveries to be made, the number of possible routes would be in the billions.

The problem is a classic example of complex algorithmic problems called NP-hard problems. These algorithms are of great interest to computer scientists because they have many practical applications and can be applied to a great number of fields. For example, these algorithms can be used for scheduling, arranging components on a computer chip, routing electricity in the power grid or sequencing the human genome.

Nine students – about half of whom did not have any experience in computer science before beginning PGSS – jumped at the chance to try to match world records set for different variations of the Vehicle Routing Problem with Time Windows as their final project for PGSS.

"I wanted to see if a team of talented high school students could match Ph.D.-level scientists,” said Jeff Conway, PGSS instructor and alumnus. “I had a hunch they could, and I was right.”

The students used and modified an artificial intelligence framework, called A*. It starts with a random solution to the problem and then slightly modifies that solution by changing a route or number of trucks used. Each solution is given a score using heuristics, which quantifies routes as being good or bad and allows the computer to choose and modify the best-scoring routes until it finds the optimal solution. Their program was able to solve one version of the problem as efficiently as the world record holding program created by researchers at Brown University. Within days, the group matched seven more records, for a total of eight. 

“There is no doubt about it, this is one of the most impressive results we’ve seen from a PGSS group project,” said Barry Luokkala, PGSS Program Director and Teaching Professor of Physics at CMU.

The students include: Brooke Arner, Freeport Area High School; Arushi Bandi, Pine-Richland High School; Anirban Chowdhury, MMI Preparatory School; Nathan Kaleida, Mars Area High School; Jahnik Kurukulasuriya, Pittsburgh Allderdice High School; Suvir Mirchandani, Fox Chapel High School; Daniel Qian, Southern Lehigh High School; Vamsi Saladi, Conestoga High School; and Nathan Vallapureddy, Central Bucks East High School.

PGSS, a summer enrichment program for high school seniors, returned to Carnegie Mellon’s Pittsburgh campus in 2013. PGSS is funded and supported by the nonprofit PGSS Campaign, Inc., which is organized by alumni of the original PGSS program that ran from 1982-2009, and from private and corporate donors, and the Pennsylvania Department of Education. Each year, the program hosts some of the state’s brightest incoming high school seniors for five weeks and provides the students with course and lab work in biology, chemistry, physics, computer science and mathematics. 

###

Pictured: (Standing L-R): Arushi Bandi, Vamsi Saladi, Daniel Qian, Suvir Mirchandani, Anirban Chowdhury; (Seated L-R): Jahnik Kurukulasuriya, Jeff Conway (instructor), Nathan Kaleida, Brooke Arner, Nathan Vallapureddy.