The existing dynamic and stochastic shortest path problem (DSSPP) algorithms assume that the mean and variance of link travel time (or other specific random variable such as cost) are available. When they are used with observed data from previous time …
Previous literature on the Traveling Salesman Problem (TSP) assumed that the sites to be visited are stationary. Motivated by practical applications, we introduce a time-dependent generalization of TSP which we call Moving-Target TSP, where a pursuer must intercept in minimum …
In this paper, we apply the stochastic dynamic programming to find the dynamic shortest path from the source node to the sink node in stochastic dynamic networks, in which the arc lengths are independent random variables with exponential distributions. In …
The time-dependent orienteering problem is dual to the time-dependent traveling salesman problem. It consists of visiting a maximum number of sites within a given deadline. The traveling time between two sites is in general dependent on the starting time. For …
We present a best-first heuristic search approach for determining an optimal policy for a stochastic shortest path problem. A vehicle is to travel from an origin, starting at time t0, to a destination, where once the destination is reached a …
A problem often considered in Operations Research and Computational Physics is the traveling salesman problem, in which a traveling salesperson has to find the shortest closed tour between a given set of cities touching each city exactly once. The distances …
This paper investigates minimum time and minimum cost path problems in street networks regulated by periodic traffic lights. We show that the minimum time path problem is polynomially solvable. On the other hand, minimum cost path problems are generally NP-hard. …
A mathematical model is formulated for the time-dependent vehicle routing problem (TDVRP) and a genetic algorithm (GA) is proposed for solving it. Formulation of the problem considers multiple vehicles with different capacities, pick-up or delivery demands with soft time windows, …
There is a requirement in real-time, routing information systems to identify the “optimal” route based on the multiple objectives and the individual decision-making rules of the users. While a number of utility theory-based techniques have been developed to accomplish this …
Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal language L ⊆ Σ*, the formal-language-constrained shortest/simple path problem consists of finding a shortest (simple) path p in G complying with the additional …