Shortest route problem with soft time windows

Abstract

The shortest path problem may be enriched with assigning time windows to the nodes. In case the time windows are of the soft type, earliness and tardiness may be considered of importance when evaluating a path, next to the usual criterion of total path length. While the distance between the nodes may be fixed or time-dependent, criteria like total earliness or total tardiness are, by definition, time-dependent, i.e. they depend on the time one leaves a node. To solve this multi-criteria time-dependent shortest path problem, a dynamic programming approach is used. Numerical examples are given and the performance of the approach is investigated.