Constrained shortest path problems in bi-colored graphs: a label-setting approach.

Definition of an optimal path in the real-world routing problems is not necessarily the shortest one, because parameters such as travel time, safety, quality, and smoothness also played essential roles in the definition of optimality. In this paper, we use bi-colored graphs for modeling urban and heterogeneous environments and introduce variations of constraint routing problems. Bi-colored graphs are a kind of directed graphs whose vertices are divided into two subsets of white and gray. We consider two criteria, minimizing the length and minimizing the number of gray vertices and present two problems called gray vertices bounded shortest path problem and length bounded shortest path problem on bi-colored graphs. We propose an efficient time label-setting algorithm to solve these problems. Likewise, we simulate the algorithm and compare it with the related path planning methods on random graphs as well as real-world environments. The simulation results show the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]