Formal-language-constrained path problems
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 …
Least possible time paths in stochastic, time-varying networks
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. …
A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem
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, …
Time-Minimum Routes in Time-Dependent Networks
Route planning for mobile robots in time-dependent networks is investigated. The mobile robot is constrained to move in a prespecified network of roads. The environment contains a set of moving obstacles which are not necessarily constrained to move along arcs …
A classification of formulations for the (time-dependent) traveling salesman problem
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 …
FASTEST PATHS IN TIME-DEPENDENT NETWORKS FOR INTELLIGENT VEHICLE-HIGHWAY SYSTEMS APPLICATION∗
We consider the problem of individual route guidance in an Intelligent Vehicle-Highway Systems (IVHS ) environment, based on time-dependent forecasts of link travel time. We propose a consistency condition which deterministic forecasts should be constrained to satisfy, and show that …
Modelling intra-city time-dependent travel speeds for vehicle scheduling problems
Many research papers have presented mathematical models for vehicle scheduling. Several of these models have been embedded in commercial decision support systems for intra-city vehicle scheduling for launderies, grocery stores, banks, express mail customers, etc. Virtually all of these models …
Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms
The time dependent vehicle routing problem (TDVRP) is defined as follows. A vehicle fleet of fixed capacities serves customers of fixed demands from a central depot. Customers are assigned to vehicles and the vehicles routed so that the total time …