Road Network

An open-source suite of algorithmic tools for solving computational problems on road networks

Much attention is focused on solving instances of the traveling-salesman problem (TSP) in the plane--but real-world instances live in graphs that model road networks. Fortunately, a powerful approximation technique enables fast and accurate solution of large TSP instances in road networks.

This software suite includes code to find near-optimal routes for tens of thousands of destinations in road networks of size a million or more.

Traveling salesman in a road network
Vehicle routing

Vehicle routing is a similar optimization problem--one seeks not one tour visiting all destinations but many tours, each handling at most a given number of destinations.

The software suite offers fast and accurate solutions to vehicle-routing problems in road networks.

Facility location involves selecting sites for facilities to serve customers nearby. Similar problems involve forming geographic clusters.

Facility location