Title

Shortest Path Problem with Cache-Dependent Path Lengths

Publication Type

Conference Proceeding Article

Publication Date

12-2003

Abstract

Here, we are motivated by the problem of finding the shortest path in a network when traversing Web pages where cache size determines path length. The shortest path problem with cache-dependent path lengths is shown to be NP-complete. It is a new problem for which we propose several effective heuristics, including a Dijkstra heuristic, genetic algorithms and tabu search.

Discipline

Operations and Supply Chain Management

Research Areas

Operations Management

Publication

CEC 2003: 2003 Congress on Evolutionary Computation: Proceedings: Canberra, Australia, 8-12 December 2003

Volume

4

First Page

2756

Last Page

2761

ISBN

9780780378049

Identifier

10.1109/CEC.2003.1299437

Publisher

IEEE

City or Country

Piscataway, NJ

Additional URL

http://dx.doi.org/10.1109/CEC.2003.1299437