  A weighted point-availability time-dependent network is a list of temporal
edges, where each temporal edge has an appearing time value, a travel time
value, and a cost value. In this paper we consider the single source Pareto
problem in weighted point-availability time-dependent networks, which consists
of computing, for any destination d, all Pareto optimal pairs (t, c), where t
and c are the arrival time and the cost of a path from s to d, respectively (a
pair (t, c) is Pareto optimal if there is no path with arrival time smaller
than t and cost no worse than c or arrival time no greater than t and better
cost). We design and analyse a general algorithm for solving this problem,
whose time complexity is O(M log P), where M is the number of temporal edges
and P is the maximum number of Pareto optimal pairs for each node of the
network. This complexity significantly improves the time complexity of the
previously known solution. Our algorithm can be used to solve several different
minimum cost path problems in weighted point-availability time-dependent
networks with a vast variety of cost definitions, and it can be easily modified
in order to deal with the single destination Pareto problem. All our results
apply to directed networks, but they can be easily adapted to undirected
networks with no edges with zero travel time.
