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.