Capacitated Vehicle Routing and the k-Delivery n-Traveling Salesman Problem

Michael Andrew Forbes

Blair Student Finalists in National Intel Science Search 


This computer science project concerns a type of vehicle-routing algorithm commonly known as a "Traveling Salesman Problem." This type of problem is of interest to researchers because it

attempts to find the most cost-efficient route for delivering goods to a number of places, such as a supermarket scheduling deliveries to several stores. The situation when a single fixed-capacity vehicle attempts to optimize its delivery route when the levels of supply and demand are different was examined. This paper presents algorithms for solving the problem and suggests a relationship between this problem and others that may be easier to solve.


Michael Andrews Forbes is one of Four Montgomery Blair High School students to become finalists in this year’s Intel Science Talent Search, out of 40 in all of the United States.  This is the most finalists from any high school or school district in the nation.  At Blair, Forbes is president of Blazernet, the high school Internet service provider, and the Linux Users Group. His awards include several for math and the Top Newcomer Award for freestyle competition ballroom dancing. His hobbies include origami, bonsai and golf. Forbes hopes to attend Cornell in preparation for a career in theoretical computer science.