Calculate value differences of rows before and after bounded by multiple referenced rows
SELECT *
      ,CASE WHEN location = 'Loc_B' OR right_tree = 0 AND left_tree = 0 THEN NULL::int
            ELSE CASE WHEN @right_diff &lt; @left_diff THEN right_diff ELSE left_diff END
       END AS min_diff
FROM  (
   SELECT *
         ,CASE WHEN right_tree &gt; 0 THEN start_time - right_end ELSE 1000 END AS right_diff
         ,CASE WHEN left_tree  &gt; 0 THEN end_time  - left_start ELSE 1000 END AS left_diff
   FROM  (
      SELECT *
            ,first_value(end_time)   OVER (PARTITION BY right_tree ORDER BY start_time) AS right_end
            ,first_value(start_time) OVER (PARTITION BY left_tree  ORDER BY start_time DESC) AS left_start
      FROM  (
         SELECT *
               ,count(location = 'Loc_B' OR NULL) OVER (PARTITION BY id ORDER BY start_time) AS right_tree
               ,count(location = 'Loc_B' OR NULL) OVER (PARTITION BY id ORDER BY start_time DESC) AS left_tree
         FROM   travel
         ) a
      ) b
   ) c
   ORDER  BY id, start_time;


Produces your result exactly.

1000 is just some "higher value than any other". Since your actual problem seems to operate with times and intervals infinity would be the perfect choice.

Related answer with detailed explanation how groups (right_tree and left_tree here) are formed:
Select longest continuous sequence

SQL Fiddle.