Optimization Online


The color-constrained and interchange-constrained shortest path problems

Nassim Dehouche(nassim.deh***at***mahidol.ac.th)

Abstract: We study two variants of the shortest path problem. Given an integer k, the k-color-constrained and the k-interchange-constrained shortest path problems, respectively seek a shortest path that uses no more than k colors and one that makes no more than k − 1 alternations of colors. We show that the former problem is NP-hard, when the latter is tractable. The study of these problems is motivated by some limitations in the use of diameter-based metrics as quality indicators for transit networks. We notably show that indicators such as the diameter or directness of a transit network fail to adequately account for travel convenience in measuring the connectedness of a network and propose a new network indicator, based on solving the k-interchange-constrained shortest path problem, that aims at alleviating these limitations.

Keywords: Graph Theory, Shortest Path Problem, Transit Networks

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Category 3: Network Optimization

Citation: Technical Report, Mahidol University International College, Technology Health and Society Research Cluster, Technical Report Number 1

Download: [PDF]

Entry Submitted: 03/02/2018
Entry Accepted: 03/03/2018
Entry Last Modified: 03/02/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society