  In this paper we consider a set of travelers, starting from likely different
locations towards a common destination within a road network, and propose
solutions to find the optimal connecting points for them. A connecting point is
a vertex of the network where a subset of the travelers meet and continue
traveling together towards the next connecting point or the destination. The
notion of optimality is with regard to a given aggregated travel cost, e.g.,
travel distance or shared fuel cost. This problem by itself is new and we make
it even more interesting (and complex) by considering affinity factors among
the users, i.e., how much a user likes to travel together with another one.
This plays a fundamental role in determining where the connecting points are
and how subsets of travelers are formed. We propose three methods for
addressing this problem, one that relies on a fast and greedy approach that
finds a sub-optimal solution, and two others that yield globally optimal
solution. We evaluate all proposed approaches through experiments, where
collections of real datasets are used to assess the trade-offs, behavior and
characteristics of each method.
