The goal of the shortest path problem is to find the shortest (or cheapest) path from origin to destination. It is widely used in practice, for example in Google Directions, parcel delivery networks and routing data through the internet.

This basic problem can be extended in many ways. For example, the total travel time can be forced to be below a set limit. This is a common practice in parcel delivery networks because companies guarantee delivery time to their customers. So, if you are living in Atlanta and ordering new Nike shoes that are shipped from California, then then the delivery company (UPS) has to make sure that you get your shoes in 2 days as you expected and paid for. Also, it can be useful to find multiple alternative paths within the timeframe since that may allow better consolidation, thereby decreasing costs.

Below is a demo showing a crossdocking hub network in the U.S. Each hub is connected to its neighbor by a truck lane. Additionally, long distance rail and air connections are available between some pairs of hubs. The shipping costs are based on the distance and type of transportation. Shipping by rail is cheaper and slower compared to trucks, while air transportation is much faster but will also cost more.

After selecting origin, destination, service time and number of paths, an optimization will start to find the best paths. The algorithm will find the cheapest paths that satisfy the service time constraints. The paths will then be displayed on the map, showing the types of shipping modes used between each pair of hubs.

Truck Air Rail