A framework is proposed for determining the least expected cost path in a schedule-based time-expanded public transit network where travel times, and thus bus arrival and departure times at stops, are stochastic. Transfer reliability is incorporated in a label-correcting algorithm with a penalty function for the expected waiting time when transferring that reflects the likelihood of making a successful transfer. The algorithm is implemented in transit assignment on an Austin, Texas test network, using actual bus arrival and departure time distributions from vehicle location data. Assignment results are compared with those of a deterministic shortest path based on the schedule and from a calibrated transit assignment model. Simulations of the network and passenger paths are also conducted to evaluate the overall path reliability. The reliable shortest path algorithm is found to penalize transferring and provide paths with improved transfer and overall reliability. The proposed model is realistic, incorporating reliability measures from vehicle location data, and practical, given the efficient shortest path approach and application to transit assignment. / text

Surveillance is an important application for unmanned aerial vehicles (UAVs). The sensed information often has high priority and it must be made available to human operators as quickly as possible. Due to obstacles and limited communication range, it is not always possible to transmit the information directly to the base station. In this case, other UAVs can form a relay chain between the surveillance UAV and the base station. Determining suitable positions for such UAVs is a complex optimization problem in and of itself, and is made even more difficult by communication and surveillance constraints. To solve different variations of finding positions for UAVs for surveillance of one target, two new algorithms have been developed. One of the algorithms is developed especially for finding a set of relay chains offering different trade-offs between the number of UAVsand the quality of the chain. The other algorithm is tailored towards finding the highest quality chain possible, given a limited number of available UAVs. Finding the optimal positions for surveillance of several targets is more difficult. A study has been performed, in order to determine how the problems of interest can besolved. It turns out that very few of the existing algorithms can be used due to the characteristics of our specific problem. For this reason, an algorithm for quickly calculating positions for surveillance of multiple targets has been developed. This enables calculation of an initial chain that is immediately made available to the user, and the chain is then incrementally optimized according to the user’s desire.