This paper investigates the linear fractional shortest path problem with time windows. For the specific problem, an elementary path with a minimum cost/time ratio is sought in a directed graph, where two parameters (i.e. cost and time) are associated with each arc and a time window is associated with each node. Indeed, a valid path must satisfy the time window constraints, which are assumed to be of the hard type. Multi-dimensional labelling algorithms are proposed to solve this variant of the classical shortest path problem. Extensive computational tests are carried out on a meaningful number of test problems, with the goal of assessing the behaviour of the proposed approaches. The computational study shows that the introduction of dominance rules and the adoption of a bi-directional search strategy allow the definition of solution approaches that turn out to be very effective in solving the problem under consideration.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
|Titolo:||Multi-Dimensional Labelling Approaches to solve the Linear Fractional Elementary Shortest Path Problem with Time Windows|
|Data di pubblicazione:||2011|
|Appare nelle tipologie:||1.1 Articolo in rivista|