The shortest path problem with forbidden paths |
| |
| Institution: | 1. CIRRELT and Canada Research Chair in Distribution Management, HEC Montréal, 3000, chemin de la Côte-Sainte-Catherine, Montréal, H3C 3J7, Canada;2. CIRRELT and Department of Mathematics and Industrial Engineering, École Polytechnique de Montréal, C.P. 6079, succ. Centre-ville, Montréal, H3C 3A7, Canada;3. CIRRELT and HEC Montréal, 3000, chemin de la Côte-Sainte-Catherine, Montréal H3C 3J7, Canada;1. Pontificia Universidad Católica de Chile, Chile;2. CIRRELT and Canada Research Chair in Integrated Logistics, Université Laval, Canada;3. Department of Economics and Management, University of Brescia, Italy;1. Dipartimento di Informatica, Università di Pisa, Largo B. Pontecorvo 3, Pisa 56127, Italy;2. Department of Management Science, Lancaster University Management School, LA1 4YX Lancaster, United Kingdom;3. Former PhD student in the Department of Management Science, Lancaster University;1. Département de mathématiques et de génie industriel, Polytechnique Montréal, C.P. 6079, succ. Centre-Ville, Montréal H3C 3A7, Québec, Canada;2. Département d’informatique et de recherche opérationnelle, Université de Montréal, C.P. 6128, succ. Centre-Ville, Montréal H3C 3J7, Québec, Canada;3. Chaire d’excellence en recherche du Canada sur la science des données pour la prise de dcision en temps réel, Polytechnique Montréal, C.P. 6079, succ. Centre-Ville, Montréal H3C 3A7, Québec, Canada;4. Centre interuniversitaire de recherche sur les réseaux d’entreprise, la logistique et le transport, Université de Montréal, C.P. 6128, succ. Centre-Ville, Montréal H3C 3J7, Québec, Canada |
| |
| Abstract: | We consider a variant of the constrained shortest path problem, where the constraints come from a set of forbidden paths (arc sequences) that cannot be part of any feasible solution. Two solution approaches are proposed for this variant. The first uses Aho and Corasick's keyword matching algorithm to filter paths produced by a k-shortest paths algorithm. The second generalizes Martins' deviation path approach for the k-shortest paths problem by merging the original graph with a state graph derived from Aho and Corasick's algorithm. Like Martins' approach, the second method amounts to a polynomial reduction of the shortest path problem with forbidden paths to a classic shortest path problem. Its significant advantage over the first approach is that it allows considering forbidden paths in more general shortest path problems such as the shortest path problem with resource constraints. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
