Speeding up the Passenger Assignment Problem in transit planning by the Direct Link Network representation

When designing a public transport network with the passenger travel time in mind, the passenger assignment problem (PAP) needs to be addressed explicitly. It is a complex problem on its own and even the simplest version requires determination of the shortest path for all demand pairs in the network. It is typically treated as a subproblem of larger problems by public transport planners, such as the transit network design problem (TNDP). In the TNDP, bi-level optimization models and/or metaheuristics are used where the PAP is solved when evaluating a line plan. In doing so, the PAP is often addressed by representing the transit network with a so-called 'Change-and-Go' (CNG) network with dummy transfer nodes in order to model transfer penalties as part of the passenger travel time. Then, in order to solve the PAP, the all-pairs shortest path problem needs to be solved for this CNG network representation. In this paper, we present a much more efficient network representation, 'Direct Link Network' (DLN), where additional edges are added instead of additional nodes. We compare the theoretical complexity of both representations and the computation time required to solve the PAP by using CNG and DLN on the most commonly used benchmark networks and also several real-life networks. The results show that with the DLN representation, the PAP can be solved multiple times faster than with CNG. Consequently, DLN can significantly speed up all TNDP algorithms that solve the PAP multiple times when designing a public transport network.