Minimal Effective Time Two-Way Park and Ride Problem

With the growing phenomenon of urbanization and people moving towards urban areas, public transportation networks and road infrastructures are constantly improved and extended. Route planning within these urban scenarios is thus becoming a very important problem to address. Some of the available routing devices and services are confined within their domain (e.g., a car navigation system plans only road routes), others try to plan routes involving multiple modes of transportation. The last ones solve the so called multi-modal route planning problem. All of these usually work by stating a departure location and a destination, together with a departure time and the desired transportation modes for the route (including or excluding certain combinations, for example). Their output is an (sometimes sub-) optimal route that contains the roads and public transportation lines to use for the trip. Routing in general has been a widely researched and experimented problem, with many different combinations of characteristics explored. The scenario we specifically focus on in this work is finding a two-way route between two locations using a private vehicle (like a car, a motorcycle or a bicycle) for the first part of the trip, after which it will be parked and public transportation will then be used for the remaining part (so-called park and ride). The parked vehicle will then have to be retrieved during the return trip, before returning to the departure location. By two-way route we thus mean a route from a departure location to a destination and from the destination back to the departure location at a later time, opposed to classic one-way routing which simply finds the best route in one direction. The goal of this work is to optimize both directions of the two-way trip together, by choosing an optimal parking location which makes the combination of the two legs optimal. This kind of route planning has not been researched as widely as classic one-way route planning, but has immediate real-world applications. In fact, when looking at the scenario where the user starts his journey with a private vehicle (a car or a bicycle), we immediately observe why it is important to search for an optimal path taking into account both legs: the user has to park the vehicle on the outward leg and needs to retrieve it on the return leg. The parking location that is chosen during the first leg is in fact a very important constraint on the second leg and it is not possible to optimize both legs separately, as it could result in having two different parking locations for the two legs. On the other hand, optimizing only one of the two legs and then finding the best route that uses the chosen parking location may lead to sub-optimal routes. Indeed, when moving from the departure location to the destination, one could choose a particular parking location which is the best choice for the outward trip, but which is not served by public transportation at the time of the return trip. In other cases the chosen parking location could force the user to use streets which are heavily influenced by traffic during the return trip (e.g., in rush hours), thus making the return trip much longer than needed. Solving this problem efficiently is particularly impactful in many realistic scenarios involving entering the city and then exiting it at a later time, like a person living in the suburbs that has an appointment in the city center or wanting to find the best combination of transportation modes to get to work downtown and back home. The shortest paths for the two legs of the two-way trip will in fact usually be significantly different when computed separately, since the timetables of public transportation and the traffic conditions change during the day.