Time dependency in multiple objective dynamic programming (Q2367667)

The paper presents a theoretical and algorithmic development for the problem of path planning in networks including multiple time dependent costs on the links. The goal is to compute all nondominated paths in an efficient computational procedure. A general network, not assumed to be acyclic is considered. It consists of a (finite) set of nodes and a (finite) set of links. Each link carries one or more attributes. The cost functions are assumed to be positive vector-valued functions of time and are not assumed to be continuous. The study contains theoretical results and two algorithms solving time dependent multiple criteria routing problems. The first applies backward dynamic programming and solves the routing problem generating all nondominated paths which lead from every node in the network to the destination node. The second is an adoption of forward dynamic programming and solves the routing problem for the set of feasible paths from the origin node to all other nodes in the network. The relationship between the forward and backward case is explored. Numerical examples that apply the two introduced algorithms are also included.