Algorithms for Time-Dependent Bicriteria Shortest Path Problems

In: Discrete Optimization. Volume 3 , P. 238--254, 2006

Authors

• Horst W. Hamacher
• Stefan Ruzika
• Stevanus A. Tjandra

Abstract

In this paper we generalize the classical shortest path problem in two ways. We consider two objective functions and time-dependent data. The resulting problem, called the time-dependent bicriteria shortest path problem (TdBiSP), has several interesting practical applications, but has not gained much attention in the literature. After reviewing relevant literature we develop a new algorithm for the TdBiSP with non-negative data. Numerical tests show the superiority of our algorithm compared with an existing algorithm in the literature. Furthermore, we discuss algorithms for the TdBiSP with negative data.

BibTeX

 
@Article{ HamacherEtAl:BicriteriaShortestPath, 
   title = { Algorithms for Time-Dependent Bicriteria Shortest Path Problems }, 
   author = { Horst W. Hamacher and Stefan Ruzika and Stevanus A. Tjandra },    
   journal = { Discrete Optimization },  
   volume = { 3  },        
   pages = { 238--254 },   
   year = 2006, 
} 

---

This publication belongs to the project DeNDeMA.