Constrained Shortest Path

The shortest path (SP) problem is the most fundamental and used subproblem in transport problems: to identify the least cost path through a network from an origin to a destination. It can be solved optimally via efficient algorithms. The constrained version includes one additional constraint establishing an upper limit, e.g. travel time, for the path. Unfortunately, the addition of such constraints to the SP problem generally results in a NP-hard problem. Here an efficient approach can solve easily large scale instances. 

The real voyage of discovery consists not in seeking new landscapes, but in having new eyes. Marcel Proust