Commuters’ paths with penalties for early or late arrival time. (English) Zbl 0724.90075

de Palma, André; Hansen, Pierre; Labbé, Martine

Transp. Sci. 24, No. 4, 276-286 (1990).

Summary: We 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 exogenous 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.

MSC:

90C35	Programming involving graphs or networks
90B06	Transportation, logistics and supply chain management
90-08	Computational methods for problems pertaining to operations research and mathematical programming
90C60	Abstract computational complexity for mathematical programming problems

Keywords:

generalized shortest path problem; NP-hard; polynomial subcases; pseudo- polynomial algorithm