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. …
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 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 …
In this paper, two computationally efficient algorithms are presented for determining the least possible time paths for all origins to a single destination in networks where the arc weights are discrete random variables whose probability distribution functions vary with time. …
Dynamic programming (DP) algorithms for the traveling salesman problem (TSP) can easily incorporate time dependent travel times, time windows, and precedence relationships which present difficulties for algorithms based on linear or nonlinear programming formulations and for many TSP heuristics. However, …
The time-dependent traveling salesman problem (TDTSP) is a generalization of the classical traveling salesman problem where the cost of any given arc is dependent of its position in the tour. The TDTSP can model several real world applications (e.g., one-machine …