title: How to optimize my pathfinding algorithm on a GTFS network
body: <h1>Intro</h1>
  
  <p>I'm using a slightly modified <a href="https://developers.google.com/transit/gtfs/reference" rel="nofollow noreferrer">GTFS</a> database.</p>
  
  <p>I have a first step algorithm that given two geographical locations provides:</p>
  
  <ul>
  <li>the list of stops around departure and arrival</li>
  <li>the list of routes that connects those list of stops</li>
  </ul>
  
  <p>The second step algorithm finds the best journeys matching those stops and routes.<br>
  This is working well on direct journeys as well as journeys using one connection.</p>
  
  <p>My problem arises when trying to find the best journey using 2 connections (so there are 3 trips to be searched).</p>
  
  <h1>Database</h1>
  
  <p>The GTFS format has the following tables (each table has a foreign key to the previous/next table in this list):</p>
  
  <ul>
  <li><code>stops</code>: stop information (geolocation, name, etc)</li>
  <li><code>stop_times</code>: timetable</li>
  <li><code>trips</code>: itinerary taken by a vehicle (bus, metro, etc)</li>
  <li><code>routes</code>: family of trips that roughly take the same path (e.g. standard and express trips on the same route, but different stops taken)</li>
  </ul>
  
  <p>I have added the following tables</p>
  
  <ul>
  <li><code>stop_connections</code>: <code>stop</code> to <code>stop</code> connections (around 1 to 20)</li>
  <li><code>stops_routes</code>: lists the available <code>routes</code> at every <code>stop</code></li>
  </ul>
  
  <p>Here's the table row count in a city where I get slow results (Paris, France):</p>
  
  <ul>
  <li><code>stops</code>: 28k</li>
  <li><code>stop_times</code>: 12M</li>
  <li><code>trips</code>: 513k</li>
  <li><code>routes</code>: 1k</li>
  <li><code>stop_connections</code>: 365k</li>
  <li><code>stops_routes</code>: 227k</li>
  </ul>
  
  <h1>Algorithm</h1>
  
  <p>The first step of my algo takes two latitude/longitude points as input, and provides:</p>
  
  <ul>
  <li>the list of stops at each location</li>
  <li>the routes that can be used to connect those stops (with up to two connections)</li>
  </ul>
  
  <p>The second step takes each start stop, and analyses the available journeys that use only the routes selected by the first step.</p>
  
  <p>This is the part that I'm trying to optimize. Here's how I'm querying the database:</p>
  
  <p><img src="https://i.stack.imgur.com/59sxE.jpg" alt="Query schema written on paper"></p>
  
  <p>My search terms (green in the picture):</p>
  
  <ul>
  <li>one departure stop</li>
  <li>several arrival stops (1 to 20)</li>
  <li>allowed routes at departure, at first connection and on last trip</li>
  <li>service ID (not relevant here, can be ignored)</li>
  </ul>
  
  <p>Here's what I do now:</p>
  
  <ol>
  <li>Start from a stop => get timetable => get trips => get routes; filter on allowed routes.  </li>
  <li>Connect the arrival stops of the first trip to a list of possible stops using <code>stop_connections</code></li>
  <li>Repeat from step 1 two times so that I have 3 trips/2 connections</li>
  </ol>
  
  <h1>The problem</h1>
  
  <p>This is working fine on some cases, but it can be very slow in others. Usually as soon as I join the timetable or the stop connections, there is a 10x increase of the returned rows. Since I'm joining these table 8 times, there are potentially 10^8 rows to be searched by the engine.</p>
  
  <p>Now I'm sure that I can get this to be more efficient.</p>
  
  <p>My problem is that the number of rows increases at every join, and the arrival stop selection is made at the very end.<br>
  I mean I get all the possible journeys from a given stop at a given departure time (there can be millions of combinations), and <em>only</em> when my search reaches the last trip, I can filter on the ~20 allowed arrival stops.<br>
  It could be much faster if I could somehow 'know' soon enough that a route isn't worth searching.</p>
  
  <h1>Optimizations</h1>
  
  <p>Here's what I tried/thought of:</p>
  
  <h2>1. Inner join <code>stops_routes</code> when joining <code>stop_connections</code></h2>
  
  <blockquote>
    <p>Only select stops at a connection that lead to the allowed routes at next trip.</p>
  </blockquote>
  
  <p>This is sometimes efficient when there is a lot of connections and not all the connected stops are interesting (some connected stop might only be used by a route we don't want to take).<br>
  <em>However this inner join can <strong>increase</strong> the number of rows if there are not many connected stops and a lot of allowed routes.</em></p>
  
  <h2>2. Partition the <code>stop_times</code> table</h2>
  
  <blockquote>
    <p>Create a smaller copy of the <code>stop_times</code> that contains only the timetable of the next two hours or so. Indeed, having the database engine search for the timetable (up to 10pm for example) when my trips starts at 8am is useless. Keeping only 8am-10am is enough and much faster.</p>
  </blockquote>
  
  <p><em>This is very efficient, because it dramatically decreases the number of rows to be searched.</em></p>
  
  <p>I have implemented this with success, it decreased the search time by a factor of about 10x or even 100x.</p>
  
  <h2>3. Identify 'good' and 'bad' routes</h2>
  
  <blockquote>
    <p>There is usually, in a metropolitan area, large routes that are very useful when travelling large distances. But these routes aren't the best option when travelling small distances. A human person who knows his own city's public transportation system will quickly tell that from this neighborhood to this other, the best option is to take a specific route.</p>
  </blockquote>
  
  <p><em>However this is very difficult to do, and requires a customization on every city</em>.</p>
  
  <p>I plan to make this algo completely independant of the city, so I'm not really willing to go down that road</p>
  
  <h2>4. Use crowdsourcing to identify paths that work well</h2>
  
  <blockquote>
    <p>The first search is slow, but the information taken from it can be used to serve fast result to the next person with a similar journey.</p>
  </blockquote>
  
  <p><em>However there are so many combinations of departure and arrival stops that the information taken from one query might not be very useful.</em></p>
  
  <p>I don't know if this is a good idea. I haven't implemented it.</p>
  
  <h1>Next</h1>
  
  <p>I'm running out of ideas. I know this is not a <em>programming</em> question, but rather a request of ideas on an algorithm. I hope this falls into the SO scope.</p>