Amazon delivery trucks

Delivery trucks are all over town, getting as many packages to people as quickly as possible. Is it possible to find the best route through town? This is an important question for many companies, such as Amazon. (The US Postal Service solves a different problem.) In this simple form this is the Traveling Salesman Problem (TSP), which has been studied extensively. But Amazon has some liberties: packages can be spread out over days (unless you have Amazon Prime), and there are multiple trucks to divide the area over.

This project walks a student through a heuristic solution of the TSP and the `multiple TSP'. With the full implementation, students can explore some scenarios.

The project description explicitly targets an object-oriented formulation; this project is much harder in a non-OO language.

This project is preferably done by two students in close collaboration; it will take about two weeks at the end of a first or second semester programming course. The code is written completely from scratch, and requires no input data.

  • Summary. Model the `Multiple Traveling Salesman Problem ' by way of delivery trucks.

  • Topics. Recursion, arrays, classes

  • Audience. Undergraduate or AP high school

  • Difficulty. Moderate to high

  • Strengths. Appealing, opportunity for experimentation

  • Weaknesses. Requires many pieces to be in place before the code does something useful. No graphics output, so the interpretation of output requires some imagination

  • Dependencies. No specific background in CS (such as the Traveling Salesman Problem) is needed. Familiarity with the notions of heuristics and search is welcome.

  • Variants. The code can be extended to slightly different problem statements, such as HEB (big supermarket chain) curb-side delivery shoppers.