{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Coding a RAPTOR toy example\n", "\n", "## Goal\n", "\n", "Learn the RAPTOR algorithm by coding it for a toy example with the data structures advised in the paper. We code RAPTOR for a super simple toy example with only two routes and two trips each.\n", "\n", "## Toy example\n", "- TODO updates:\n", " - additional route r2 that goes from A to E slowly\n", " - walking paths\n", "![toy_example](img/RAPTOR_example.png) \n", "\n", "## Encoding the data structures\n", "### General considerations\n", "We adhere to the data structures proposed by Delling et al. These structures aim to minimize read times in memory by making use of consecutive in-memory adresses. Thus, structures with varying dimensions (e.g dataframes, python lists) are excluded. We illustrate the difficulty with an example. \n", "\n", "Each route has a potentially unique number of stops. Therefore, we cannot store stops in a 2D array of routes by stops, as the number of stops is not the same for each route. We adress this problem by storing stops consecutively by route, and keeping track of the index of the first stop for each route.\n", "\n", "This general strategy is applied to all the required data structures.\n", "\n", "### routes\n", "The `routes` array will contain arrays `[n_trips, n_stops, pt_1st_stop, pt_1st_trip]` where all four values are `int`. To avoid overcomplicating things and try to mimic pointers in python, `pt_1st_stop` and `pt_1st_trip` contain integer indices." ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "lines_to_next_cell": 0 }, "outputs": [], "source": [ "import numpy as np\n", "routes = np.array([[2, 3, 0, 0], #r0\n", " [2, 3, 3, 6], #r1\n", " [2, 2, 6, 12]]) # r2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### routeStops\n", "`routeStops` is an array that contains the ordered lists of stops for each route. `pt_1st_stop` in `routes` is required to get to the first stop of the route. is itself an array that contains the sequence of stops for route $r_i$." ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "lines_to_next_cell": 0 }, "outputs": [], "source": [ "routeStops = np.array([0, 1, 2, # A, B, C\n", " 3, 2, 4, # D, C, E\n", " 0, 4]) # A, E" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### stopTimes\n", "\n", "The i-th entry in the `stopTimes` array is itself an array which contains the arrival and departure time at a particular stop for a particular trip. `stopTimes` is sorted by routes, and then by trips. We retrieve the index of the first (earliest) trip of the route with the pointer `pt_1st_trip` stored in `routes`. We may use the built-in `numpy` [date and time data structures](https://blog.finxter.com/how-to-work-with-dates-and-times-in-python/). In short, declaring dates and times is done like this: `np.datetime64('YYYY-MM-DDThh:mm')`. Entries with a `NaT` arrival or departure times correspond to beginning and end of trips respectively.\n", "\n", "Note that trips are indexed implicitely in stopTimes, but we decided to change a little bit from the paper and index them according to their parent route instead of giving them an absolute index. It makes things a bit easier when coding the algorithm." ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [], "source": [ "stopTimes = np.array([\n", " # r0, t0\n", " [None, '2020-05-11T08:00'],\n", " ['2020-05-11T08:25', '2020-05-11T08:30'],\n", " ['2020-05-11T08:55', None],\n", "\n", " # ro, t1\n", " [None, '2020-05-11T08:10'],\n", " ['2020-05-11T08:35', '2020-05-11T08:40'],\n", " ['2020-05-11T09:05', None],\n", " \n", " # r1, t0 \n", " [None, '2020-05-11T08:00'],\n", " ['2020-05-11T08:05', '2020-05-11T08:10'],\n", " ['2020-05-11T08:15', None],\n", "\n", " # r1, t1\n", " [None, '2020-05-11T09:00'],\n", " ['2020-05-11T09:05', '2020-05-11T09:10'],\n", " ['2020-05-11T09:15', None],\n", " \n", " #r2, t0\n", " [None, '2020-05-11T08:20'],\n", " ['2020-05-11T09:20', None],\n", " \n", " #r2, t1\n", " [None, '2020-05-11T08:30'],\n", " ['2020-05-11T09:30', None]],\n", " dtype='datetime64')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`NaT` is the `None` equivalent for `numpy datetime64`." ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([ True, False])" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "np.isnat(stopTimes[0])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### stopRoutes\n", "\n", "`stopRoutes` contains the routes associated with each stop. We need the pointer in `stops` to index `stopRoutes` correctly." ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [], "source": [ "stopRoutes = np.array([0, 2, # A\n", " 0, # B\n", " 0,1, # C\n", " 1, # D\n", " 1, 2]) # E" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We should also build an array for transfer times (including walking times), but for now let's ignore this additional complexity. Finally, the i-th entry in the `stops` array points to the first entry in `stopRoutes` (and `transfers` when that will be tried) associated with stop $p_i$" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [], "source": [ "stops = np.array([[0, None],# A\n", " [2, None], # B\n", " [3, None],# C\n", " [5, None], # D\n", " [6, None], # E\n", " [len(stopRoutes), None]]) # fictive stop to account for length of E" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Coding the standard RAPTOR\n", "\n", "Below, we code RAPTOR as it is described in the paper, with all optimizations. That corresponds to the pseudocode block in the article. It solves the earliest arrival time problem: we enter an start stop, a target stop and a departure time and it finds the earliest arrival time in k rounds (i.e taking at most k transports). Note that walking between stops is not considered a transport." ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [], "source": [ "p_s = 0 # start stop = A\n", "p_t = 4 # target stop = E\n", "tau_0 = np.datetime64('2020-05-11T08:05') # departure time 08:05\n", "k_max = 10 # we set a maximum number of transports to pre-allocate memory for the numpy array tau_i" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [], "source": [ "def raptor_standard(p_s, p_t, tau_0, routes, routeStops, stopTimes, stopRoutes, stops,\n", " k_max=10):\n", " \n", " #******************************************initialization******************************************\n", " n_stops = len(stops)-1 # to remove the fictive stop to account for all the routes belonging to the last stop\n", "\n", " # earliest arrival time at each stop for each round.\n", " tau = np.full(shape=(k_max, n_stops), fill_value = np.datetime64('2100-01-01T00:00')) # 2100 instead of infinity # number of stops * max number of transports\n", "\n", " # earliest arrival time at each stop, indep. of round\n", " tau_star = np.full(shape=n_stops, fill_value = np.datetime64('2100-01-01T00:00'))\n", "\n", " # to backtrack the journey of TRANSPORTS once it is finished\n", " #[route, trip, boarding stop, exit stop]\n", " # we will keep [r, t, p_b, p_e, p_f1, pf2, t_w] i.e \n", " # [route, trip (offset by route, not absolute), boarding stop, exit stop, beginning stop of the walk, target stop of the walk, time walked]\n", " journey = np.full(shape=(k_max, n_stops, 7), fill_value = -1, dtype=int)\n", " \n", " marked = [p_s]\n", " q = []\n", " tau[0, p_s] = tau_0\n", " \n", " #Maybe TODO (but not in original raptor): footpaths from the departure stop\n", "\n", " #****************************************** main loop******************************************\n", " for k in np.arange(1, k_max+1):\n", " print('\\n******************************STARTING round k={}******************************'.format(k))\n", " # accumulate routes serving marked stops from previous rounds\n", " q = []\n", " marked = list(set(marked)) # removing potential duplicate stops in marked due to walking paths\n", " print('Marked stops at the start of the round: {}'.format(marked))\n", " for p in marked:\n", " for r in stopRoutes[stops[p][0]:stops[p+1][0]]: # foreach route r serving p\n", " print('Route considered for the queue: ({0}, {1})'.format(r, p))\n", " inQueue = False\n", " for idx, (rPrime, pPrime) in enumerate(q): \n", " # is there already another stop from the same route in q ?\n", " if (rPrime == r): \n", " # is there already a later stop from the same route in q ?\n", " if(np.where(routeStops[routes[r][2]:routes[r][2]+routes[r][1]] == pPrime)[0][0] >\\\n", " np.where(routeStops[routes[r][2]:routes[r][2]+routes[r][1]] == p)[0][0]):\n", " #in that case, replace the later stop pPrime by stop p in q\n", " q[idx] = (r, p)\n", " inQueue = True\n", " # is there already an earlier stop from the same route in q ?\n", " else:\n", " # in that case, do not add p to the q.\n", " inQueue=True\n", " if not inQueue:\n", " q.append((r, p))\n", "\n", " marked = [] # unmarking all stops\n", "\n", " print('Queue before traversing each route: {}'.format(q))\n", " # traverse each route\n", " for (r, p) in q:\n", " print('\\n****TRAVERSING ROUTE r={0} from stop p={1}****'.format(r, p))\n", " # t is the t-th trip in route r, not the t-th trip in all trips. This makes things easier\n", " t = None\n", " # we will keep [r, t, p_b, p_e, p_f, t_w] i.e \n", " # [route, trip (offset by route, not absolute), boarding stop, exit stop, target stop of the walk, time walked]\n", " t_journey = np.empty(4, dtype=int)# contains tripID, board and exit stops to backtrack the journey\n", "\n", "\n", " # we only traverse the route starting at p, not from the beginning of the route\n", " for p_i in routeStops[routes[r][2]+np.where(routeStops[routes[r][2]:routes[r][2]+routes[r][1]] == p)[0][0]:\\\n", " routes[r][2]+routes[r][1]]:\n", " print(\"p_i: {}\".format(p_i))\n", "\n", " if (t is not None):\n", " # 1st trip of route + \n", " # offset for the right trip + \n", " # offset for the right stop\n", " arr_t_p_i = stopTimes[routes[r][3] + \\\n", " t * routes[r][1] + \\\n", " np.where(routeStops[routes[r][2]:routes[r][2]+routes[r][1]] == p_i)[0][0]][0]\n", " print(\"arr_t_p_i: {}\".format(arr_t_p_i))\n", "\n", " if arr_t_p_i < min(tau_star[p_i], tau_star[p_t]):\n", " tau[k][p_i] = arr_t_p_i\n", " tau_star[p_i] = arr_t_p_i\n", " marked.append(p_i)\n", " # keep a trace that we went down the trip taken before at this stop\n", " t_journey[3] = p_i\n", " journey[k][p_i][0:4] = t_journey\n", " # Can we catch an earlier trip at p_i ?\n", " print('\\n----scanning departure times for route r={0} at stop p_i={1}----'.format(r, p_i))\n", " t_r = 0\n", " while True:\n", " t_r_dep = stopTimes[routes[r][3]+\\\n", " # offset corresponding to stop p_i in route r\n", " np.where(routeStops[routes[r][2]:routes[r][2]+routes[r][1]] == p_i)[0][0] + \\\n", " routes[r][1]*t_r][1]\n", "\n", " print(\"Earliest arrival time at previous step: tau[k-1][p_i]: {}\".format(tau[k-1][p_i]))\n", " print(\"Departure time considered: t_r_dep: {}\".format(t_r_dep))\n", " # We hop on the first trip that departs later than our arrival time at p_i in k-1 transports\n", " if t_r_dep > tau[k-1][p_i]:\n", " t = t_r\n", " print('\\n!!!!Hopped on route r={0}, trip t={1} at stop p_i={2}!!!!'.format(r, t, p_i))\n", "\n", " # here we probably need to save the trip and boarding stop (boarding time will not be useful)\n", " t_journey[0] = r\n", " t_journey[1] = t\n", " t_journey[2] = p_i\n", " break\n", " t_r += 1\n", "\n", " # we could not hop on any trip at this stop\n", " if t_r == routes[r][0]:\n", " break\n", " \n", " print('\\n****FOOTPATHS****')\n", " \n", " marked_footpaths = [] # storing marked stops for footpaths in a separate list to avoid inifinite loops\n", " for p in marked:\n", " if stops[p][1] is not None:\n", " print('checking walking paths from stop {}'.format(p))\n", " # making sure there are footpaths for that stop\n", " # finding the next stop where there are footpaths to find the next index\n", " next_stop = p\n", " next_stop_found = False\n", " while next_stop < len(stops)-1: #carefully check that's the correct version\n", " next_stop = next_stop+1\n", " if stops[next_stop][1] is not None:\n", " next_stop_found = True\n", " break\n", " \n", " # reinitializing next_stop to p in case no next stop with not 'None' stops[p][1] is found\n", " if not next_stop_found:\n", " next_stop = p+1 # this works because transfers[p:None] is equivalent to transfers[p:]\n", " \n", " \n", " for f in transfers[stops[p][1]:stops[next_stop][1]]:\n", " print(\"Considering footpaths from {} to {}\".format(p, f[0]))\n", " \n", " # we only consider footpaths if they strictly ameliorate the arrival time at the arrival stop of the path.\n", " if(tau[k][p]+np.timedelta64(f[1], 's') < min(tau_star[f[0]], tau_star[p_t])): \n", " print(\"Walking to {} is faster !\".format(f[0]))\n", " tau[k][f[0]] = tau[k][p]+np.timedelta64(f[1], 's')\n", " tau_star[f[0]] = tau[k][p]+np.timedelta64(f[1], 's')\n", " marked_footpaths.append(f[0])\n", " \n", " # keeping tracks of footpaths to backtrack the journey:\n", " # [departure stop, arrival stop, walking time]\n", " journey[k][f[0]][4:7] = [p, f[0], f[1]]\n", " \n", " marked.extend(marked_footpaths) # to avoid infinite loops if marked gets appended dynamically\n", " # stopping criterion: no stops were marked\n", " if not marked:\n", " break\n", " return(tau, tau_star, k, journey)" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "******************************STARTING round k=1******************************\n", "Marked stops at the start of the round: [0]\n", "Route considered for the queue: (0, 0)\n", "Route considered for the queue: (2, 0)\n", "Queue before traversing each route: [(0, 0), (2, 0)]\n", "\n", "****TRAVERSING ROUTE r=0 from stop p=0****\n", "p_i: 0\n", "\n", "----scanning departure times for route r=0 at stop p_i=0----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T08:05\n", "Departure time considered: t_r_dep: 2020-05-11T08:00\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T08:05\n", "Departure time considered: t_r_dep: 2020-05-11T08:10\n", "\n", "!!!!Hopped on route r=0, trip t=1 at stop p_i=0!!!!\n", "p_i: 1\n", "arr_t_p_i: 2020-05-11T08:35\n", "\n", "----scanning departure times for route r=0 at stop p_i=1----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: 2020-05-11T08:30\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: 2020-05-11T08:40\n", "p_i: 2\n", "arr_t_p_i: 2020-05-11T09:05\n", "\n", "----scanning departure times for route r=0 at stop p_i=2----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: NaT\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****TRAVERSING ROUTE r=2 from stop p=0****\n", "p_i: 0\n", "\n", "----scanning departure times for route r=2 at stop p_i=0----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T08:05\n", "Departure time considered: t_r_dep: 2020-05-11T08:20\n", "\n", "!!!!Hopped on route r=2, trip t=0 at stop p_i=0!!!!\n", "p_i: 4\n", "arr_t_p_i: 2020-05-11T09:20\n", "\n", "----scanning departure times for route r=2 at stop p_i=4----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: NaT\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****FOOTPATHS****\n", "\n", "******************************STARTING round k=2******************************\n", "Marked stops at the start of the round: [1, 2, 4]\n", "Route considered for the queue: (0, 1)\n", "Route considered for the queue: (0, 2)\n", "Route considered for the queue: (1, 2)\n", "Route considered for the queue: (1, 4)\n", "Route considered for the queue: (2, 4)\n", "Queue before traversing each route: [(0, 1), (1, 2), (2, 4)]\n", "\n", "****TRAVERSING ROUTE r=0 from stop p=1****\n", "p_i: 1\n", "\n", "----scanning departure times for route r=0 at stop p_i=1----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T08:35\n", "Departure time considered: t_r_dep: 2020-05-11T08:30\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T08:35\n", "Departure time considered: t_r_dep: 2020-05-11T08:40\n", "\n", "!!!!Hopped on route r=0, trip t=1 at stop p_i=1!!!!\n", "p_i: 2\n", "arr_t_p_i: 2020-05-11T09:05\n", "\n", "----scanning departure times for route r=0 at stop p_i=2----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:05\n", "Departure time considered: t_r_dep: NaT\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:05\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****TRAVERSING ROUTE r=1 from stop p=2****\n", "p_i: 2\n", "\n", "----scanning departure times for route r=1 at stop p_i=2----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:05\n", "Departure time considered: t_r_dep: 2020-05-11T08:10\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:05\n", "Departure time considered: t_r_dep: 2020-05-11T09:10\n", "\n", "!!!!Hopped on route r=1, trip t=1 at stop p_i=2!!!!\n", "p_i: 4\n", "arr_t_p_i: 2020-05-11T09:15\n", "\n", "----scanning departure times for route r=1 at stop p_i=4----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:20\n", "Departure time considered: t_r_dep: NaT\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:20\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****TRAVERSING ROUTE r=2 from stop p=4****\n", "p_i: 4\n", "\n", "----scanning departure times for route r=2 at stop p_i=4----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:20\n", "Departure time considered: t_r_dep: NaT\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:20\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****FOOTPATHS****\n", "\n", "******************************STARTING round k=3******************************\n", "Marked stops at the start of the round: [4]\n", "Route considered for the queue: (1, 4)\n", "Route considered for the queue: (2, 4)\n", "Queue before traversing each route: [(1, 4), (2, 4)]\n", "\n", "****TRAVERSING ROUTE r=1 from stop p=4****\n", "p_i: 4\n", "\n", "----scanning departure times for route r=1 at stop p_i=4----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:15\n", "Departure time considered: t_r_dep: NaT\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:15\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****TRAVERSING ROUTE r=2 from stop p=4****\n", "p_i: 4\n", "\n", "----scanning departure times for route r=2 at stop p_i=4----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:15\n", "Departure time considered: t_r_dep: NaT\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:15\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****FOOTPATHS****\n" ] } ], "source": [ "tau, tau_star, k, journey = raptor_standard(p_s, p_t, tau_0, \n", " routes = routes, routeStops = routeStops, stopTimes = stopTimes, stopRoutes = stopRoutes, stops = stops)" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array(['2100-01-01T00:00', '2020-05-11T08:35', '2020-05-11T09:05',\n", " '2100-01-01T00:00', '2020-05-11T09:15'], dtype='datetime64[m]')" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tau_star" ] }, { "cell_type": "code", "execution_count": 45, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "array([['2020-05-11T08:05', '2100-01-01T00:00', '2100-01-01T00:00',\n", " '2100-01-01T00:00', '2100-01-01T00:00'],\n", " ['2100-01-01T00:00', '2020-05-11T08:35', '2020-05-11T09:05',\n", " '2100-01-01T00:00', '2020-05-11T09:20'],\n", " ['2100-01-01T00:00', '2100-01-01T00:00', '2100-01-01T00:00',\n", " '2100-01-01T00:00', '2020-05-11T09:15'],\n", " ['2100-01-01T00:00', '2100-01-01T00:00', '2100-01-01T00:00',\n", " '2100-01-01T00:00', '2100-01-01T00:00']], dtype='datetime64[m]')" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "k_last = k\n", "\n", "tau[0:k_last+1]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`journey` contains all the necessary information to backtrack from the solution to the actual journey in terms of sequence of transports.\n", "\n", "`journey` has dimensions `k` by `n_stops` by 4+3.\n", "- The 4 first values store the route and trip taken, the departure and arrival stops.\n", "- The 3 last values are used by footpaths. They contain the departure stop for the walk, the arrival stop for the walk and the walking time in seconds.\n", "\n", "When we hop on a trip, we store the trip (with the route) and the boarding and exit stops as the array `t_journey`: `(r, t, p_boarding, p_exit)`. At each stop `p_i` where we ameliorate the arrival time in round `k`, we store `t_journey` in the first 4 cells of `journey[k][p_i]`. `p_i` corresponds to the exit stop when backtracking.\n", "\n", "When walking to stop `p_i` is shorter, we store the departure, arrival stops and walking time in the 3 last cells of `journey[k][p_i]`.\n", "\n", "The end result is a `journey` array which contains -1 values in all seven cells in `journey[k][p_i]` if the arrival time at `p_i` was not ameliorated at step `k`. `journey[k][p_i]` where there are values other than -1 indicate that the arrival time was ameliorated either by walking or by taking a transport. " ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "array([[[-1, -1, -1, -1, -1, -1, -1],\n", " [-1, -1, -1, -1, -1, -1, -1],\n", " [-1, -1, -1, -1, -1, -1, -1],\n", " [-1, -1, -1, -1, -1, -1, -1],\n", " [-1, -1, -1, -1, -1, -1, -1]],\n", "\n", " [[-1, -1, -1, -1, -1, -1, -1],\n", " [ 0, 1, 0, 1, -1, -1, -1],\n", " [ 0, 1, 0, 2, -1, -1, -1],\n", " [-1, -1, -1, -1, -1, -1, -1],\n", " [ 2, 0, 0, 4, -1, -1, -1]],\n", "\n", " [[-1, -1, -1, -1, -1, -1, -1],\n", " [-1, -1, -1, -1, -1, -1, -1],\n", " [-1, -1, -1, -1, -1, -1, -1],\n", " [-1, -1, -1, -1, -1, -1, -1],\n", " [ 1, 1, 2, 4, -1, -1, -1]]])" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "journey[0:k_last]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Backtracking\n", "\n", "We reconstruct the actual journey from the `journey` array by backtracking from the arrival stop to the departure stop. At each round k where we notice that the arrival time for the target stop was ameliorated, we start a new leg corresponding to a journey reaching the target stop in k transports.\n", "\n", "When backtracking without footpaths, it is sufficient at each round k to check at which stop the trip at round k-1 began. \n", "\n" ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [], "source": [ "def backtrack_journey(k_last, p_t, journey):\n", " # journey_act = actual journey, will contain the sequence of transports in the correct order\n", " journey_act = [[] for k in range(0, k_last)] # there's maximum k routes to get to the final stop\n", " p_board = p_t\n", " n_legs = 1 # each leg is a journey to from the departure stop to the target stop in exactly k transports\n", " journey_found = False\n", "\n", " # iterating backwards in rounds from k_last -1 to 1\n", " for k in range(k_last-1, 0, -1): # second argument in range is not included in the boundaries\n", " # Was the tarrival time at the target stop ameliorated at round k ? \n", " if np.any(journey[k][p_t]!=np.array([-1, -1, -1, -1, -1, -1, -1])):\n", "\n", " # starting a new leg in the list of actual journeys\n", " journey_found = True\n", " # iterating from k to 0 to reconstruct the actual journey in k transports\n", " p_board = p_t\n", " for k_prime in range(k, 0, -1):\n", "\n", " # did we get to that stop by walking ?\n", " if journey[k_prime][p_board][5] !=-1:\n", "\n", " # we keep track of the stop to which we walked to as well as the departure stop of the walk\n", " stop_walk_dep = journey[k_prime][p_board][4]\n", " journey_act[k].append([journey[k_prime][stop_walk_dep], journey[k_prime][p_board]])\n", " p_board = journey[k_prime][stop_walk_dep][2]\n", "\n", " # we did not get to that stop by walking\n", " else:\n", "\n", " journey_act[k].append(journey[k_prime][p_board])\n", " p_board = journey[k_prime][p_board][2]\n", "\n", " # reversing the order of journey_act to get journeys from the start stop to the target stop\n", " journey_act = [j[::-1] for j in journey_act]\n", "\n", " # building a human readable output for the trip:\n", " for k, j in enumerate(journey_act):\n", "\n", " if j: # going only through non-empty journeys\n", " print('******************JOURNEY IN {} TRIPS******************'.format(k))\n", " print('raw representation of the journey in {} trips: {}'.format(k, j))\n", "\n", " for k_prime, t in enumerate(j):\n", " # We did not walk at step k\n", " if len(t) !=2:\n", " p_boarding = t[2]\n", " p_exit = t[3]\n", " r_k = t[0]\n", " time_boarding = stopTimes[routes[r_k][3] + \\\n", " np.where(routeStops[routes[r_k][2]:routes[r_k][2]+routes[r_k][1]] == p_boarding)[0][0] + \\\n", " t[1]*routes[r_k][1]][1]\n", " time_exit = stopTimes[routes[r_k][3] + \\\n", " np.where(routeStops[routes[r_k][2]:routes[r_k][2]+routes[r_k][1]] == p_exit)[0][0] + \\\n", " t[1]*routes[r_k][1]][0]\n", " print(\"At stop {}, take route {} leaving at time {} \\n...\".format(p_boarding, r_k, time_boarding))\n", "\n", " print(\" and exit at stop {} at time {}\".format(p_exit, time_exit))\n", "\n", " # We walked at step k\n", " elif len(t)==2:\n", " print(t)\n", " p_boarding = t[0][2]\n", " p_exit = t[0][3]\n", " r_k = t[0][0]\n", " time_boarding = stopTimes[routes[r_k][3] + \\\n", " np.where(routeStops[routes[r_k][2]:routes[r_k][2]+routes[r_k][1]] == p_boarding)[0][0] + \\\n", " t[0][1]*routes[r_k][1]][1]\n", " time_exit = stopTimes[routes[r_k][3] + \\\n", " np.where(routeStops[routes[r_k][2]:routes[r_k][2]+routes[r_k][1]] == p_exit)[0][0] + \\\n", " t[0][1]*routes[r_k][1]][0]\n", " p_start_walk = t[1][4]\n", " p_end_walk = t[1][5]\n", " walk_duration = t[1][6]/60\n", "\n", " print(\"At stop {}, take route {} leaving at time {} \\n...\".format(p_boarding, r_k, time_boarding))\n", "\n", " print(\"... exit at stop {} at time {}... \".format(p_exit, time_exit))\n", "\n", " print(\"and walk for {} minutes from stop {} to stop {}.\".format(walk_duration, p_start_walk, p_end_walk))\n", " \n", " if not journey_found:\n", " print('No journey was found for this query')\n", " return journey_found " ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "******************JOURNEY IN 1 TRIPS******************\n", "raw representation of the journey in 1 trips: [array([ 2, 0, 0, 4, -1, -1, -1])]\n", "At stop 0, take route 2 leaving at time 2020-05-11T08:20 \n", "...\n", " and exit at stop 4 at time 2020-05-11T09:20\n", "******************JOURNEY IN 2 TRIPS******************\n", "raw representation of the journey in 2 trips: [array([ 0, 1, 0, 2, -1, -1, -1]), array([ 1, 1, 2, 4, -1, -1, -1])]\n", "At stop 0, take route 0 leaving at time 2020-05-11T08:10 \n", "...\n", " and exit at stop 2 at time 2020-05-11T09:05\n", "At stop 2, take route 1 leaving at time 2020-05-11T09:10 \n", "...\n", " and exit at stop 4 at time 2020-05-11T09:15\n" ] } ], "source": [ "backtrack_journey(k_last, p_t, journey);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Let's add footpaths\n", "\n", "For now, we have not tried including footpaths in our dataset. Below, we modify the timetable by adding a new route r3, which links a new stop F to E in a single travel. F may be reached in a very long time from A, but in a short time from B, meaning that it should become shorter to:\n", "\n", "- Take a trip from A to B\n", "- Walk from B to F\n", "- Take a trip from F to E\n", "\n", "rather than the current best trip:\n", "- Take a trip from A to C\n", "- Take a trip from C to E\n", "\n", "\n", "Note that the single transport solution:\n", "- Take a trip from A to E\n", "\n", "should still appear as the optimal solution for k = 1, i.e one transport is taken." ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [], "source": [ "routes = np.array([[2, 3, 0, 0], #r0\n", " [2, 3, 3, 6], #r1\n", " [2, 2, 6, 12], #r2\n", " [2, 2, 8, 16]]) # r3" ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [], "source": [ "routeStops = np.array([0, 1, 2, # A, B, C\n", " 3, 2, 4, # D, C, E\n", " 0, 4, # A, E\n", " 5, 4]) #F, E" ] }, { "cell_type": "code", "execution_count": 51, "metadata": {}, "outputs": [], "source": [ "stopTimes = np.array([\n", " # r0, t0\n", " [None, '2020-05-11T08:00'],\n", " ['2020-05-11T08:25', '2020-05-11T08:30'],\n", " ['2020-05-11T08:55', None],\n", "\n", " # ro, t1\n", " [None, '2020-05-11T08:10'],\n", " ['2020-05-11T08:35', '2020-05-11T08:40'],\n", " ['2020-05-11T09:05', None],\n", " \n", " # r1, t0 \n", " [None, '2020-05-11T08:00'],\n", " ['2020-05-11T08:05', '2020-05-11T08:10'],\n", " ['2020-05-11T08:15', None],\n", "\n", " # r1, t1\n", " [None, '2020-05-11T09:00'],\n", " ['2020-05-11T09:05', '2020-05-11T09:10'],\n", " ['2020-05-11T09:15', None],\n", " \n", " #r2, t0\n", " [None, '2020-05-11T08:20'],\n", " ['2020-05-11T09:20', None],\n", " \n", " #r2, t1\n", " [None, '2020-05-11T08:30'],\n", " ['2020-05-11T09:30', None],\n", " \n", " #r3, t0\n", " [None, '2020-05-11T08:05'],\n", " ['2020-05-11T08:25', None],\n", "\n", " #r3, t1\n", " [None, '2020-05-11T08:45'],\n", " ['2020-05-11T09:05', None]],\n", " dtype='datetime64')" ] }, { "cell_type": "code", "execution_count": 52, "metadata": {}, "outputs": [], "source": [ "stopRoutes = np.array([0, 2, # A\n", " 0, # B\n", " 0,1, # C\n", " 1, # D\n", " 1, 2, 3, # E\n", " 3]) # F" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## transfers\n", "The `transfers` is a 2D `np.ndarray` where each entry `[p_j, time]` represents the time it takes to reach p_j from stop p_i. The correspondance between the indexing of `transfers` and p_i is done via `stops[p_i][1]`, i.e the first entry in `transfers` containing a connection from stop p_i.\n", "\n", "As we cannot store different data types in numpy arras, `time` will have to be converted to `np.timedelta64`, the format used to make differences between `np.datetime.64` variables. We will consider all `time` values as **positive values in seconds**." ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "numpy.timedelta64(-30,'m')" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "stopTimes[0][1] - stopTimes[1][1]" ] }, { "cell_type": "code", "execution_count": 54, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "numpy.timedelta64(30,'s')" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "np.timedelta64(30, 's')" ] }, { "cell_type": "code", "execution_count": 55, "metadata": {}, "outputs": [], "source": [ "transfers = np.array([[5, 3600], # A -> F\n", " [5, 300], # B -> F\n", " [0, 3600], # F -> A\n", " [1, 300] # F -> A\n", " ])" ] }, { "cell_type": "code", "execution_count": 56, "metadata": {}, "outputs": [], "source": [ "stops = np.array([[0, 0],# A\n", " [2, 1], # B\n", " [3, None],# C\n", " [5, None], # D\n", " [6, None], # E\n", " [9, 2], # F\n", " [len(stopRoutes), None]]) # fictive stop to account for length of E" ] }, { "cell_type": "code", "execution_count": 57, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "******************************STARTING round k=1******************************\n", "Marked stops at the start of the round: [0]\n", "Route considered for the queue: (0, 0)\n", "Route considered for the queue: (2, 0)\n", "Queue before traversing each route: [(0, 0), (2, 0)]\n", "\n", "****TRAVERSING ROUTE r=0 from stop p=0****\n", "p_i: 0\n", "\n", "----scanning departure times for route r=0 at stop p_i=0----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T08:05\n", "Departure time considered: t_r_dep: 2020-05-11T08:00\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T08:05\n", "Departure time considered: t_r_dep: 2020-05-11T08:10\n", "\n", "!!!!Hopped on route r=0, trip t=1 at stop p_i=0!!!!\n", "p_i: 1\n", "arr_t_p_i: 2020-05-11T08:35\n", "\n", "----scanning departure times for route r=0 at stop p_i=1----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: 2020-05-11T08:30\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: 2020-05-11T08:40\n", "p_i: 2\n", "arr_t_p_i: 2020-05-11T09:05\n", "\n", "----scanning departure times for route r=0 at stop p_i=2----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: NaT\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****TRAVERSING ROUTE r=2 from stop p=0****\n", "p_i: 0\n", "\n", "----scanning departure times for route r=2 at stop p_i=0----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T08:05\n", "Departure time considered: t_r_dep: 2020-05-11T08:20\n", "\n", "!!!!Hopped on route r=2, trip t=0 at stop p_i=0!!!!\n", "p_i: 4\n", "arr_t_p_i: 2020-05-11T09:20\n", "\n", "----scanning departure times for route r=2 at stop p_i=4----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: NaT\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****FOOTPATHS****\n", "checking walking paths from stop 1\n", "Considering footpaths from 1 to 5\n", "Walking to 5 is faster !\n", "\n", "******************************STARTING round k=2******************************\n", "Marked stops at the start of the round: [1, 2, 4, 5]\n", "Route considered for the queue: (0, 1)\n", "Route considered for the queue: (0, 2)\n", "Route considered for the queue: (1, 2)\n", "Route considered for the queue: (1, 4)\n", "Route considered for the queue: (2, 4)\n", "Route considered for the queue: (3, 4)\n", "Route considered for the queue: (3, 5)\n", "Queue before traversing each route: [(0, 1), (1, 2), (2, 4), (3, 5)]\n", "\n", "****TRAVERSING ROUTE r=0 from stop p=1****\n", "p_i: 1\n", "\n", "----scanning departure times for route r=0 at stop p_i=1----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T08:35\n", "Departure time considered: t_r_dep: 2020-05-11T08:30\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T08:35\n", "Departure time considered: t_r_dep: 2020-05-11T08:40\n", "\n", "!!!!Hopped on route r=0, trip t=1 at stop p_i=1!!!!\n", "p_i: 2\n", "arr_t_p_i: 2020-05-11T09:05\n", "\n", "----scanning departure times for route r=0 at stop p_i=2----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:05\n", "Departure time considered: t_r_dep: NaT\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:05\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****TRAVERSING ROUTE r=1 from stop p=2****\n", "p_i: 2\n", "\n", "----scanning departure times for route r=1 at stop p_i=2----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:05\n", "Departure time considered: t_r_dep: 2020-05-11T08:10\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:05\n", "Departure time considered: t_r_dep: 2020-05-11T09:10\n", "\n", "!!!!Hopped on route r=1, trip t=1 at stop p_i=2!!!!\n", "p_i: 4\n", "arr_t_p_i: 2020-05-11T09:15\n", "\n", "----scanning departure times for route r=1 at stop p_i=4----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:20\n", "Departure time considered: t_r_dep: NaT\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:20\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****TRAVERSING ROUTE r=2 from stop p=4****\n", "p_i: 4\n", "\n", "----scanning departure times for route r=2 at stop p_i=4----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:20\n", "Departure time considered: t_r_dep: NaT\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:20\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****TRAVERSING ROUTE r=3 from stop p=5****\n", "p_i: 5\n", "\n", "----scanning departure times for route r=3 at stop p_i=5----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T08:40\n", "Departure time considered: t_r_dep: 2020-05-11T08:05\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T08:40\n", "Departure time considered: t_r_dep: 2020-05-11T08:45\n", "\n", "!!!!Hopped on route r=3, trip t=1 at stop p_i=5!!!!\n", "p_i: 4\n", "arr_t_p_i: 2020-05-11T09:05\n", "\n", "----scanning departure times for route r=3 at stop p_i=4----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:20\n", "Departure time considered: t_r_dep: NaT\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:20\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****FOOTPATHS****\n", "\n", "******************************STARTING round k=3******************************\n", "Marked stops at the start of the round: [4]\n", "Route considered for the queue: (1, 4)\n", "Route considered for the queue: (2, 4)\n", "Route considered for the queue: (3, 4)\n", "Queue before traversing each route: [(1, 4), (2, 4), (3, 4)]\n", "\n", "****TRAVERSING ROUTE r=1 from stop p=4****\n", "p_i: 4\n", "\n", "----scanning departure times for route r=1 at stop p_i=4----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:05\n", "Departure time considered: t_r_dep: NaT\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:05\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****TRAVERSING ROUTE r=2 from stop p=4****\n", "p_i: 4\n", "\n", "----scanning departure times for route r=2 at stop p_i=4----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:05\n", "Departure time considered: t_r_dep: NaT\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:05\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****TRAVERSING ROUTE r=3 from stop p=4****\n", "p_i: 4\n", "\n", "----scanning departure times for route r=3 at stop p_i=4----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:05\n", "Departure time considered: t_r_dep: NaT\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-11T09:05\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****FOOTPATHS****\n" ] } ], "source": [ "tau, tau_star, k, journey = raptor_standard(p_s, p_t, tau_0, \n", " routes = routes, routeStops = routeStops, stopTimes = stopTimes, stopRoutes = stopRoutes, stops = stops)" ] }, { "cell_type": "code", "execution_count": 58, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([['2020-05-11T08:05', '2100-01-01T00:00', '2100-01-01T00:00',\n", " '2100-01-01T00:00', '2100-01-01T00:00', '2100-01-01T00:00'],\n", " ['2100-01-01T00:00', '2020-05-11T08:35', '2020-05-11T09:05',\n", " '2100-01-01T00:00', '2020-05-11T09:20', '2020-05-11T08:40'],\n", " ['2100-01-01T00:00', '2100-01-01T00:00', '2100-01-01T00:00',\n", " '2100-01-01T00:00', '2020-05-11T09:05', '2100-01-01T00:00'],\n", " ['2100-01-01T00:00', '2100-01-01T00:00', '2100-01-01T00:00',\n", " '2100-01-01T00:00', '2100-01-01T00:00', '2100-01-01T00:00']],\n", " dtype='datetime64[m]')" ] }, "execution_count": 58, "metadata": {}, "output_type": "execute_result" } ], "source": [ "k_last = k\n", "tau[0:k_last+1]" ] }, { "cell_type": "code", "execution_count": 59, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array(['2100-01-01T00:00', '2020-05-11T08:35', '2020-05-11T09:05',\n", " '2100-01-01T00:00', '2020-05-11T09:05', '2020-05-11T08:40'],\n", " dtype='datetime64[m]')" ] }, "execution_count": 59, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tau_star" ] }, { "cell_type": "code", "execution_count": 60, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "array([[[ -1, -1, -1, -1, -1, -1, -1],\n", " [ -1, -1, -1, -1, -1, -1, -1],\n", " [ -1, -1, -1, -1, -1, -1, -1],\n", " [ -1, -1, -1, -1, -1, -1, -1],\n", " [ -1, -1, -1, -1, -1, -1, -1],\n", " [ -1, -1, -1, -1, -1, -1, -1]],\n", "\n", " [[ -1, -1, -1, -1, -1, -1, -1],\n", " [ 0, 1, 0, 1, -1, -1, -1],\n", " [ 0, 1, 0, 2, -1, -1, -1],\n", " [ -1, -1, -1, -1, -1, -1, -1],\n", " [ 2, 0, 0, 4, -1, -1, -1],\n", " [ -1, -1, -1, -1, 1, 5, 300]],\n", "\n", " [[ -1, -1, -1, -1, -1, -1, -1],\n", " [ -1, -1, -1, -1, -1, -1, -1],\n", " [ -1, -1, -1, -1, -1, -1, -1],\n", " [ -1, -1, -1, -1, -1, -1, -1],\n", " [ 3, 1, 5, 4, -1, -1, -1],\n", " [ -1, -1, -1, -1, -1, -1, -1]]])" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" } ], "source": [ "journey[0:k_last]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Backtracking with footpaths\n", "\n", "When backtracking, with footpaths, we first look through the footpaths to backtrack to the departure stop for the walk, and then use the departure stop of the walk as an arrival stop for a transport.\n", "\n", "But with footpaths added, it is possible to reach a stop C from stop A by:\n", "- first taking a transport to a stop B\n", "- walking from stop B to stop C.\n", "\n", "Therefore, we need to keep track of all the footpaths taken at step i that ameliorated arrival times at the target stop.\n", "\n" ] }, { "cell_type": "code", "execution_count": 61, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "******************JOURNEY IN 1 TRIPS******************\n", "raw representation of the journey in 1 trips: [array([ 2, 0, 0, 4, -1, -1, -1])]\n", "At stop 0, take route 2 leaving at time 2020-05-11T08:20 \n", "...\n", " and exit at stop 4 at time 2020-05-11T09:20\n", "******************JOURNEY IN 2 TRIPS******************\n", "raw representation of the journey in 2 trips: [[array([ 0, 1, 0, 1, -1, -1, -1]), array([ -1, -1, -1, -1, 1, 5, 300])], array([ 3, 1, 5, 4, -1, -1, -1])]\n", "[array([ 0, 1, 0, 1, -1, -1, -1]), array([ -1, -1, -1, -1, 1, 5, 300])]\n", "At stop 0, take route 0 leaving at time 2020-05-11T08:10 \n", "...\n", "... exit at stop 1 at time 2020-05-11T08:35... \n", "and walk for 5.0 minutes from stop 1 to stop 5.\n", "At stop 5, take route 3 leaving at time 2020-05-11T08:45 \n", "...\n", " and exit at stop 4 at time 2020-05-11T09:05\n" ] }, { "data": { "text/plain": [ "True" ] }, "execution_count": 61, "metadata": {}, "output_type": "execute_result" } ], "source": [ "backtrack_journey(k_last, p_t, journey)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Trying to run the standard RAPTOR on real size data\n", "### Loading real sized data" ] }, { "cell_type": "code", "execution_count": 62, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[1 11 0 0]\n", " [1 11 11 11]\n", " [1 11 22 22]\n", " ...\n", " [1 6 237432 245713]\n", " [1 13 237438 245719]\n", " [3 2 237451 245732]]\n", "We find 16210 routes in the data\n" ] } ], "source": [ "import pickle\n", "# step 1 convert the data from string to numpy series\n", "routes_real = pickle.load( open( \"../data/routes_array2.pkl\", \"rb\" ) )\n", "print(routes_real)\n", "print('We find {} routes in the data'.format(len(routes_real)))" ] }, { "cell_type": "code", "execution_count": 65, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[0 None]\n", " [4 None]\n", " [7 None]\n", " ...\n", " [7841 None]\n", " [7844 None]\n", " [7847 None]]\n", "We find 1407 stops in the data\n" ] } ], "source": [ "stops_real = pickle.load(open( \"../data/stops_array.pkl\", \"rb\" ) )\n", "print(stops_real)\n", "print('We find {} stops in the data'.format(len(stops_real)))" ] }, { "cell_type": "code", "execution_count": 66, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[ 'NaT' '2020-05-21T16:53:00.000000000']\n", " ['2020-05-21T16:55:00.000000000' '2020-05-21T16:55:00.000000000']\n", " ['2020-05-21T16:57:00.000000000' '2020-05-21T16:57:00.000000000']\n", " ...\n", " ['2020-05-21T15:10:00.000000000' 'NaT']\n", " [ 'NaT' '2020-05-21T16:45:00.000000000']\n", " ['2020-05-21T17:05:00.000000000' 'NaT']]\n", "We find 245738 arrival/departure times for stops in the data\n" ] } ], "source": [ "stopTimes_real = pickle.load(open( \"../data/stop_times_array1.pkl\", \"rb\" ) )\n", "print(stopTimes_real)\n", "print('We find {} arrival/departure times for stops in the data'.format(len(stopTimes_real)))" ] }, { "cell_type": "code", "execution_count": 67, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[1166 146]\n", " [1270 360]\n", " [ 2 8]\n", " ...\n", " [ 108 371]\n", " [ 102 439]\n", " [1739 519]]\n", "We find 12564 footpaths (bidirectional) in the data\n" ] } ], "source": [ "transfer_real = pickle.load(open( \"../data/transfer_array.pkl\", \"rb\" ) )\n", "print(transfer_real)\n", "print('We find {} footpaths (bidirectional) in the data'.format(len(transfer_real)))" ] }, { "cell_type": "code", "execution_count": 68, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[ 0 1 88 ... 736 735 736]\n", "We find 8000 (r, p) route stops combinations in the data\n" ] } ], "source": [ "stopRoutes_real = pickle.load(open( \"../data/stop_routes_array.pkl\", \"rb\" ) )\n", "# The route index alone was not selected:\n", "#stopRoutes_real = stopRoutes_real[:, 1]\n", "print(stopRoutes_real)\n", "print('We find {} (r, p) route stops combinations in the data'.format(len(stopRoutes_real)))\n", "#print('We find {} unique routes desserving stops'.format(len(np.unique(stopRoutes_real))))" ] }, { "cell_type": "code", "execution_count": 72, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[ 0 1 2 ... 759 554 493]\n", "We find 7849 route, stops combinations\n", "We find 1407 unique stops desserving routes\n" ] } ], "source": [ "routeStops_real = pickle.load(open( \"../data/route_stops_array.pkl\", \"rb\" ) )\n", "print(routeStops_real)\n", "print('We find {} route, stops combinations'.format(len(routeStops_real)))\n", "print('We find {} unique stops desserving routes'.format(len(np.unique(routeStops_real))))" ] }, { "cell_type": "code", "execution_count": 71, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "******************************STARTING round k=1******************************\n", "Marked stops at the start of the round: [0]\n", "Route considered for the queue: (0, 0)\n", "Route considered for the queue: (1, 0)\n", "Route considered for the queue: (88, 0)\n", "Route considered for the queue: (89, 0)\n", "Queue before traversing each route: [(0, 0), (1, 0), (88, 0), (89, 0)]\n", "\n", "****TRAVERSING ROUTE r=0 from stop p=0****\n", "p_i: 0\n", "\n", "----scanning departure times for route r=0 at stop p_i=0----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-21T12:00\n", "Departure time considered: t_r_dep: 2020-05-21T16:53:00.000000000\n", "\n", "!!!!Hopped on route r=0, trip t=0 at stop p_i=0!!!!\n", "p_i: 1\n", "arr_t_p_i: 2020-05-21T16:55:00.000000000\n", "\n", "----scanning departure times for route r=0 at stop p_i=1----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: 2020-05-21T16:55:00.000000000\n", "p_i: 2\n", "arr_t_p_i: 2020-05-21T16:57:00.000000000\n", "\n", "----scanning departure times for route r=0 at stop p_i=2----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: 2020-05-21T16:57:00.000000000\n", "p_i: 0\n", "arr_t_p_i: NaT\n", "\n", "----scanning departure times for route r=0 at stop p_i=0----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2020-05-21T12:00\n", "Departure time considered: t_r_dep: 2020-05-21T16:53:00.000000000\n", "\n", "!!!!Hopped on route r=0, trip t=0 at stop p_i=0!!!!\n", "p_i: 1\n", "arr_t_p_i: 2020-05-21T16:55:00.000000000\n", "\n", "----scanning departure times for route r=0 at stop p_i=1----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: 2020-05-21T16:55:00.000000000\n", "p_i: 2\n", "arr_t_p_i: 2020-05-21T16:57:00.000000000\n", "\n", "----scanning departure times for route r=0 at stop p_i=2----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: 2020-05-21T16:57:00.000000000\n", "p_i: 3\n", "arr_t_p_i: 2020-05-21T17:01:00.000000000\n", "\n", "----scanning departure times for route r=0 at stop p_i=3----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: 2020-05-21T17:01:00.000000000\n", "p_i: 4\n", "arr_t_p_i: 2020-05-21T17:01:00.000000000\n", "\n", "----scanning departure times for route r=0 at stop p_i=4----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: 2020-05-21T17:01:00.000000000\n", "p_i: 5\n", "arr_t_p_i: 2020-05-21T17:03:00.000000000\n", "\n", "----scanning departure times for route r=0 at stop p_i=5----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: 2020-05-21T17:03:00.000000000\n", "p_i: 6\n", "arr_t_p_i: 2020-05-21T17:03:00.000000000\n", "\n", "----scanning departure times for route r=0 at stop p_i=6----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: 2020-05-21T17:03:00.000000000\n", "p_i: 7\n", "arr_t_p_i: 2020-05-21T17:04:00.000000000\n", "\n", "----scanning departure times for route r=0 at stop p_i=7----\n", "Earliest arrival time at previous step: tau[k-1][p_i]: 2100-01-01T00:00\n", "Departure time considered: t_r_dep: NaT\n", "\n", "****TRAVERSING ROUTE r=1 from stop p=0****\n" ] }, { "ename": "IndexError", "evalue": "index 0 is out of bounds for axis 0 with size 0", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mIndexError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 6\u001b[0m tau, tau_star, k, journey = raptor_standard(p_s, p_t, tau_0, \n\u001b[0;32m----> 7\u001b[0;31m routes = routes_real, routeStops = routeStops_real, stopTimes = stopTimes_real, stopRoutes = stopRoutes_real, stops = stops_real)\n\u001b[0m", "\u001b[0;32m\u001b[0m in \u001b[0;36mraptor_standard\u001b[0;34m(p_s, p_t, tau_0, routes, routeStops, stopTimes, stopRoutes, stops, k_max)\u001b[0m\n\u001b[1;32m 64\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 65\u001b[0m \u001b[0;31m# we only traverse the route starting at p, not from the beginning of the route\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 66\u001b[0;31m for p_i in routeStops[routes[r][2]+np.where(routeStops[routes[r][2]:routes[r][2]+routes[r][1]] == p)[0][0]:\\\n\u001b[0m\u001b[1;32m 67\u001b[0m routes[r][2]+routes[r][1]]:\n\u001b[1;32m 68\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"p_i: {}\"\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mp_i\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mIndexError\u001b[0m: index 0 is out of bounds for axis 0 with size 0" ] } ], "source": [ "p_s_real = 10 # start stop = A\n", "p_t = 4 # target stop = E\n", "tau_0 = np.datetime64('2020-05-21T12:00:00') # departure time 08:05\n", "k_max = 10 # we set a maximum number of transports to pre-allocate memory for the numpy array tau_i\n", "\n", "tau, tau_star, k, journey = raptor_standard(p_s, p_t, tau_0, \n", " routes = routes_real, routeStops = routeStops_real, stopTimes = stopTimes_real, stopRoutes = stopRoutes_real, stops = stops_real)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Code for prototyping and debugging:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "0" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "p_s = 0 # start stop = A\n", "p_t = 4 # target stop = E\n", "tau_0 = np.datetime64('2020-05-11T08:05') # departure time 08:05\n", "k_max = 10 # we set a maximum number of transports to pre-allocate memory for the numpy array tau_i" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# initialization\n", "n_stops = len(stops)\n", "\n", "# earliest arrival time at each stop for each round.\n", "tau = np.full(shape=(k_max, n_stops), fill_value = np.datetime64('2100-01-01T00:00')) # 2100 instead of infinity # number of stops * max number of transports\n", "\n", "# earliest arrival time at each stop, indep. of round\n", "tau_star = np.full(shape=n_stops, fill_value = np.datetime64('2100-01-01T00:00'))\n", "\n", "marked = [p_s]\n", "q = []\n", "tau[0, p_s] = tau_0" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "np.where(routeStops[routes[r][2]:routes[r][2]+routes[r][1]] == p_i)[0][0]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "routeStops[routes[r][2]:routes[r][2]+routes[r][1]] == p_i" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "p_i" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "t_r_dep = stopTimes[routes[r][3]+\\\n", " # offset corresponding to stop p_i in route r\n", " np.where(routeStops[routes[r][2]:routes[r][2]+routes[r][1]] == p_i)[0][0] + \\\n", " routes[r][1]*t_r][1]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "if np.where(routeStops[routes[1][2]:routes[1][2]+routes[1][1]] == 2) <\\\n", "np.where(routeStops[routes[1][2]:routes[1][2]+routes[1][1]] == 3):\n", " print(\"hello\")" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "routeStops[routes[1][2] + np.where(routeStops[routes[1][2]:routes[1][2]+routes[1][1]] == 2)[0][0]:routes[1][2]+routes[1][1]]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "routeStops[routes[1][2] + np.where(routeStops[routes[1][2]:routes[1][2]+routes[1][1]] == 2)[0][0]:6]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "routeStops[routes[1][2]]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "routeStops[np.where(routeStops[routes[1][2]:routes[1][2]+routes[1][1]] == 2)[0][0]]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "if True and \\\n", " True:\n", " print(\"hello\")" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "tau[0][0]" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "stopTimes[3][1]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a = np.arange(1, 10)\n", "a" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a[1:10:2]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "stopTimes[routes[0][3]+\\\n", " # offset corresponding to stop p_i in route r\n", " np.where(routeStops[routes[0][2]:routes[0][2]+routes[0][1]] == 0)[0][0]:\\\n", " # end of the trips of r\n", " routes[0][3]+routes[0][0]*routes[0][1]:\\\n", " # we can jump from the number of stops in r to find the next departure of route r at p_i\n", " routes[0][1]\n", " ]\n", "# we may more simply loop through all trips, and stop as soon as the departure time is after the arrival time\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "stopTimes[routes[0][3]+\\\n", " # offset corresponding to stop p_i in route r\n", " np.where(routeStops[routes[0][2]:routes[0][2]+routes[0][1]] == 0)[0][0]][1]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "stopTimes[routes[1][3]+\\\n", " # offset corresponding to stop p_i in route r\n", " np.where(routeStops[routes[1][2]:routes[1][2]+routes[1][1]] == 3)[0][0] + \\\n", " routes[1][1]*1][1]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# t_r is a trip that belongs to route r. t_r can take value 0 to routes[r][0]-1\n", "t = None\n", "r = 1\n", "tau_k_1 = tau[0][0]\n", "p_i = 3\n", "\n", "t_r = 0\n", "while True:\n", " \n", " t_r_dep = stopTimes[routes[r][3]+\\\n", " # offset corresponding to stop p_i in route r\n", " np.where(routeStops[routes[r][2]:routes[r][2]+routes[r][1]] == p_i)[0][0] + \\\n", " routes[r][1]*t_r][1]\n", " \n", " if t_r_dep > tau_k_1:\n", " # retrieving the index of the departure time of the trip in stopTimes\n", " #t = routes[r][3] + t_r * routes[r][1]\n", " t = t_r\n", " break\n", " t_r += 1\n", " # we could not hop on any trip at this stop\n", " if t_r == routes[r][0]:\n", " break\n", " \n", "print(\"done\")\n", "print(t)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "r = 1\n", "t = 1\n", "p_i = 2\n", "# 1st trip of route + offset for the right trip + offset for the right stop\n", "stopTimes[routes[r][3] + t * routes[r][1] + np.where(routeStops[routes[r][2]:routes[r][2]+routes[r][1]] == p_i)]" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "d = []\n", "not d" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "r = 1\n", "t = 0\n", "p_i = 4\n", "arr_t_p_i = stopTimes[routes[r][3] + \\\n", " t * routes[r][1] + \\\n", " np.where(routeStops[routes[r][2]:routes[r][2]+routes[r][1]] == p_i)[0][0]][0]\n", "arr_t_p_i" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "np.datetime64('NaT') > np.datetime64('2100-01-01')" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "np.datetime64('NaT') < np.datetime64('2100-01-01')" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "jupytext": { "formats": "ipynb,md,py:percent" }, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.6" } }, "nbformat": 4, "nbformat_minor": 4 }