August 01, 2016
The problem is straightforward: What is the most efficient way to deliver packages to a set number of customers during a given time window? And, how can you minimize the number of trucks needed and the distance traveled? The students' final project tackled a version of the problem known as the Vehicle Routing Problem with Time Windows.
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. For example, they can be used for scheduling, arranging components on a computer chip, routing electricity in the power grid or sequencing the human genome.
"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 created 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 first solved one variation of the problem as efficiently as a world record holding program created by researchers at Brown University. Within days, they matched world records for seven other variations of the problem, tying a total of eight world records.
"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 student team members are: 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.
High School Students Tie World Records for Solving Traveling Salesman Problem
Work Was Final Project by Students in Pa. Governor’s School for the Sciences at Carnegie Mellon
By Jocelyn Duffy / 412-268-9982 / jhduffy@andrew.cmu.edu
A group of nine 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 problem is straightforward: What is the most efficient way to deliver packages to a set number of customers during a given time window? And, how can you minimize the number of trucks needed and the distance traveled? The students' final project tackled a version of the problem known as the Vehicle Routing Problem with Time Windows.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. For example, they can be used for scheduling, arranging components on a computer chip, routing electricity in the power grid or sequencing the human genome.
"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 created 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 first solved one variation of the problem as efficiently as a world record holding program created by researchers at Brown University. Within days, they matched world records for seven other variations of the problem, tying a total of eight world records.
"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 student team members are: 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.