Have a nice trip: an algorithm for identifying excess routes under satisfaction constraints

H. Skov-Petersen, M. Zachariasen, P.K. Kefaloukos

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


Analysis of potential spatial behavior in transport infrastructures is usually carried out by means of a digital network. A basic condition for such a network analysis has traditionally been the desire to find solutions to optimization problems and to achieve greater efficiency in industry. Geographic information system (GIS) tools for network analysis are overwhelmingly targeted at finding solutions to optimization problems, which include the shortest path problem and the traveling salesman problem. This article addresses the problem of the lack of tools for finding solutions to a class of constraint satisfaction problems that are of potential interest to behavioral geographers. Constraint satisfaction problems differ from optimization problems in that they lack an expression to be maximized or minimized. We describe how a constraint-based approach to network analysis can be applied to search for ‘excess routes’ that are longer or in other ways exceed single, optimal routes. Our analysis considers both round-trips and travel from A to B and defines a set of constraints that can characterize such paths. We present a labeling algorithm that can generate solutions to such excess route problems.
Original languageEnglish
Pages (from-to)1745-1758
Number of pages14
JournalInternational Journal of Geographical Information Science
Issue number11
Publication statusPublished - 2010


  • excess routes
  • excess travel
  • Network analysis
  • constrained satisfaction


Dive into the research topics of 'Have a nice trip: an algorithm for identifying excess routes under satisfaction constraints'. Together they form a unique fingerprint.

Cite this