Improve Performance on GROUP BY - large table PostgreSQL
IN can take a list of values (like you have it) or a set. Long lists don't scale well. See:


Optimizing a Postgres query with a large IN
How to use ANY instead of IN in a WHERE clause with Rails?


Try:

SELECT origin, min(minutes) -- you'll also want to show origin
FROM   tbl
JOIN   unnest($origin_array) o(origin)      USING (origin)
JOIN   unnest($dest_array)   d(destination) USING (destination)
GROUP  BY origin;


Where $origin_array can be an array of the appropriate type int[] or an  array literal like '{100225471,100236548,10263073}'::int[]

The optimal index for this query should be:

CREATE INDEX ON tbl (origin, destination, minutes);


Appending minutes only makes sense if you get index-only scans out of it (introduced with pg 9.2, improved in later versions). But since your table is mostly read-only, it seem like the perfect use case. See:


Can Postgres use an index-only scan for this query with joined tables?


You later commented:


  I want to get the closest (min(minutes)) facility (destination) for each place (origin).


The above query does not achieve that. Only returns the shortest time for any qualifying destination. Use instead:

SELECT DISTINCT ON (origin)
       origin, minutes, destination
FROM   tbl
JOIN   unnest($origin_array) o(origin)      USING (origin)
JOIN   unnest($dest_array)   d(destination) USING (destination)
ORDER  BY origin, minutes;


Depending on cardinalities and value frequencies, this alternative may be faster:

SELECT *
FROM   unnest($origin_array) o(origin)
LEFT   JOIN LATERAL (
   SELECT minutes, destination
   FROM   tbl
   WHERE  origin = o.origin
   AND    destination = ANY ($dest_array)  -- equivalent to IN([long list]) 
   ORDER  BY minutes
   LIMIT  1
   ) t ON true;


One subtle difference: the last query returns origins from the input array with no match in tbl at all. May or may not be desirable - or even necessary. The last query is my favorite.

Further reading on how to optimize queries of this kind:


Select first row in each GROUP BY group?
Optimize GROUP BY query to retrieve latest record per user


Plus, urgently consider upgrading to a current version of Postgres, like a_horse already suggested. Performance for big data has been improved  substantially since Postgres 9.4.

You mentioned lists of up to 2000 items. Combining two long list like that is problematic since it results in a Cartesian product of 2000 x 2000 = 4000000 possible combinations. If that can happen - sure you need to consider that many combinations? That won't be fast.