Users of public transit networks require tools that generate travel plans to traverse them. The main issue is that public transit networks are time and space dependent. Travel plans depend on the current location of users and transit units, along with a set of user preferences and time restrictions. In this work, we propose the design and development of artificial intelligence (AI) planning models for engineering travel plans for such networks. The proposed models consider temporal actions, bus locations, and user preferences as constraints, to restrict the set of travel plans generated. Our approach decouples model design from algorithm construction, providing a greater level of flexibility and richness of solutions. We also introduce an integer linear programming formulation, and a fast preprocessing procedure, to evaluate the quality of the solutions returned by the proposed planning models. Experimental results show that AI planning models can efficiently generate close to optimal solutions. Furthermore, our analysis identifies user preferences as the most critical factor that increases solution complexity for planning models.
Research paper: https://doi.org/10.1080/08839514.2019.1582859
For a user that has a set of specific preferences, the AI Public-Routing Planning AI-PRP problem consists of traveling from an origin to a destination in a public transportation network, taking into account the location information of the user and the transportation units in the network.
(2) Objective Function: Minimization of the total travel time: Total walking time + Total travel time in transportation units and boarding time.
(3) and (4) constraints relate to the origin and destination of the users.
(5) guarantees flow balance along the network.
(6) restricts the amount of walking time (it is a user preference).
(7) detects transfers between two lines
(8) bounds the total cost of the trip
(9) avoids cycles
Meganodes is a technique that pre-processes public transportation networks to reduce their sizes without compromising solution quality.
Results on Reduced Network Instances with the Meganodes Technique
