Category: Java

Traveling Schoolteacher Problem

Posted in Java


The Traveling Schoolteacher Problem

The Traveling Schoolteacher Problem (TSTP) is a variation on the Traveling Salesperson Problem (TSP).

The Traveling Schoolteacher Problem supposes a schoolteacher that is traveling from school to school in order to give lessons at different schools. Being a poor schoolteacher, they are only able to afford an older car that gets bad mileage and has a small gas tank.

After visiting each school …

Tags:    computer science    guava    graph    TSP   

Better Timing of Guava Traveling Salesperson Problem Code: Timing Scripts

Posted in Java


Before We Begin: The Code

Note that all of the code discussed/shown in this post is available from the traveling salesperson problem repository on The guava/ directory contains the guava solution to the traveling salesperson problem, along with the timing scripts discussed below, and several example output files.


Timing a piece …

Tags:    computer science    command line    guava    graph    TSP    make    awk    performance   

Fixing Bottlenecks in the Guava Traveling Salesperson Problem Code

Posted in Java



In a prior blog post we introduced you to the traveling salesperson problem (TSP), which involves finding the shortest path through every city in a group of cities connected by a network of roads. Using Google Guava, we have implemented a solution to the TSP in Java.

Our philosophy toward timing, profiling, and optimization is that it is always best to work from data - and timing …

Tags:    computer science    guava    graph    TSP    performance