Commuters’ paths with penalties for early or late arrival time

The authors formulate the choice of a best path for a commuter leaving his/her home at a given time and willing to arrive at his/her destination within a given time interval. The objective function integrates constant costs for use of arcs, travel times and schedule delay. The travel times along arcs, which depend on exogeneous congestion, are represented by functions of the arrival time at the origin node of the arc. The schedule delay is taken into consideration by penalizing arrival time at the destination outside the desired time interval. The problem is shown to be NP-hard, polynomial subcases are determined and a pseudo-polynomial algorithm is provided for the general case.