Uncertain Time-Varying Shortest Path Problems

In this book, we consider the time-varying shortest path problem with one objective or multi-objectives. In these problems, transit and waiting costs are not necessarily known in each time steps. We survey the time-varying shortest path, regarding to waiting times at vertices. Moreover, the time-varying shortest path problem with arbitrary waiting times at vertices is considered, where transit costs and waiting costs are fuzzy numbers or possibly belong to some intervals. Then, two new algorithms for solving the time-varying shortest path with uncertain costs are proposed. Afterwards, we consider the shortest path problem on a time-varying network with multi-objectives functions to optimize. These K-objectives are associated with K attributes, which cannot combine together. The problem is to find the efficient path P from a source vertex to a target vertex such that the cost of path is minimized, where the total time of path is at most time horizon. Then, the maximum capacity path problem in a time-varying network is presented, where waiting at vertices is not allowable. Furthermore, the capacities are considered the fuzzy numbers.