  Shortest path queries over graphs are usually considered as isolated tasks,
where the goal is to return the shortest path for each individual query. In
practice, however, such queries are typically part of a system (e.g., a road
network) and their execution dynamically affects other queries and network
parameters, such as the loads on edges, which in turn affects the shortest
paths. We study the problem of collectively processing shortest path queries,
where the objective is to optimize a collective objective, such as minimizing
the overall cost. We define a temporal load-aware network that dynamically
tracks expected loads while satisfying the desirable `first in, first out'
property. We develop temporal load-aware extensions of widely used shortest
path algorithms, and a scalable collective routing solution that seeks to
reduce system-wide congestion through dynamic path reassignment. Experiments
illustrate that our collective approach to this NP-hard problem achieves
improvements in a variety of performance measures, such as, i) reducing average
travel times by up to 63%, ii) producing fairer suggestions across queries, and
iii) distributing load across up to 97% of a city's road network capacity. The
proposed approach is generalizable, which allows it to be adapted for other
concurrent query processing tasks over networks.
