A Label Correcting Algorithm for the Bus Routing Problem

• Autorzy: Widuch J.
• Języki publikacji: EN

Abstrakty

EN

This paper proposes a label correcting algorithm for solving the bus routing problem (BRP). The goal of the BRP is finding a route from the start stop to the final stop minimizing the time and the cost of travel. Additionally the time of starting travel at the start stop is given. The problem belongs to the group of multicriteria optimization problems (MOP), whose the solution is a set of non-dominated solutions. The algorithm makes possible to find all routes which belong to the set of non-dominated solutions. Apart from that the results of experimental tests are presented.

Słowa kluczowe

EN

bus routing problem; multicriteria optimization; relation of dominance; set of non-dominated solutions; bicriterion shortest path problem; directed weighted graph; variable weights; shortest path; label correcting algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 118, nr 3
• Strony: 305--326
• Opis fizyczny: Bibliogr. 36 poz., tab., wykr.

Twórcy

autor

Widuch J.

• Institute of Informatics, Silesian University of Technology, ul. Akademicka 16, 44–100 Gliwice, Poland,

Bibliografia

• [1] Bellman, R.. On a routing problem, Quarterly of Applied Mathematics, 16(1), 1958, 87-90.
• [2] Brumbaugh-Smith, J., Shier, D.: An empirical investigation of some bicriterion shortest path algorithms, European Journal of Operational Research, 43(2), 1989, 216-224.
• [3] Climaco, J., Martins, E.: A bicriterion shortest path algorithm, European Journal of Operational Research, 11(4), 1982,399-404.
• [4] Coello, C. C: A comprehensive survey of evolutionary-based multiobjective optimization techniques, Knowledge and Information Systems, 1(3), 1999,269-308.
• [5] Coello, C. C, van Veldhuizen, D., Lamont, G.: Evolutionary algorithms for solving multi-objective problems, Kluwer Academic Publishers, New York, New York, USA, 2002.
• [6] Corley, H., Moon, I.: Shortest paths in networks with vector weights, Journal of Optimization Theory and Application, 46(1), 1985,79-86.
• [7] Daellenbach, H., Kluyver, C. D.: Note on multiple objective dynamic programming, Journal of the Operational Research Society, 31(7), 1980,591-594.
• [8] Dell'Olmo, P., Gentili, M., Scozzari, A.: On finding dissimilar Pareto-optimal paths, European Journal of Operational Research, 162(1), 2005,70-82.
• [9] Dijkstra, E.: A note on two problems in connexion with graphs, Numerical Mathematics, 1, 1959,269-271.
• [10] Ehrgott, M.: Multicriteria optimization, Vorlesungsskripte, Sonstiges, Department of Mathematics, University of Kaiserslautern, Germany, 1999.
• [11] Ehrgott, M., Gandibleux, X.: A survey and annotated bibliography of multiobjective combinatorial optimization, OR Spektrum, 22(4), 2000, 425-460.
• [12] Floyd, R.: Algorithm 97: Shortest path, Communications of the ACM, 5(6), 1962, 345.
• [13] Ford, L., Fulkerson, D.: Flows in networks, Princeton University Press, 1962.
• [14] Garey, M., Johnson, D.: Computers and intractibility: a guide to the theory of NP-completeness, W. H. Freeman & Co., New York, New York, USA, 1990.
• [15] Hansen, P.: Bicriterion path problems, Multiple Criteria Decision Making: Theory and Application, Springer-Verlag, Berlin, Germany, 1980.
• [16] Henig, M.: The shortest path problem with two objective functions, European Journal of Operational Research, 25(2), 1985,281-291.
• [17] Johnson, D.: Efficient algorithms for shortest paths in sparse networks, Journal of the ACM, 24(1), 1977, 1-13.
• [18] Jungnickel, D.: Graphs, networks and algorithms, Springer, Berlin, Germany, 1999.
• [19] Korhonen, P.: Multiple criteria decision support - a review, European Journal of Operational Research, 63(3), 1992,361-375.
• [20] Machuca, E., Mandow, L., de la Cruz, J. P.: An Evaluation of Heuristic Functions for Bicriterion Shortest Path Problems, Proceedings of the XIV Portuguese Conference on Artificial Inteligence {EPIA 2009), Universidade de Aveiro, Portugal, 2009.
• [21] Mandow, L., de-la Cruz, J. P.: Frontier Search for Bicriterion Shortest Path Problems, Proceeding of the 2008 conference on ECAI 2008 I8th European Conference on Artificial Intelligence, 2008.
• [22] Mandow, L., de-la Cruz, J. P.: Path recovery in frontier search for multiobjective shortest path problems, Journal of Intelligent Manufacturing, 21(1), 2008, 89-99.
• [23] Marti, R., Velarde, J. G., Duarte, A.: Heuristics for the bi-objective path dissimilarity problem, Computers & Operations Research, 36(11), 2009, 2905-2912.
• [24] Martins, E.: On a multicriteria shortest path problem, European Journal of Operational Research, 16(2), 1982,236-245.
• [25] Martins, E., Santos, J.: The labelling algorithm for the multiobjective shortest path problem, Technical report, Departamento de Matematica, Universidade de Coimbra, Portugal, 1999.
• [26] Mote, J., Murthy, I., Olson, D.: A parametric approach to solving bicriterion shortest path problems, European Journal of Operational Research, 53(1), 1991, 81-92.
• [27] Pareto, V.: Course d'Economie Politique, F. Rouge, Lausanne, Switzerland, 1896.
• [28] Raith, A., Ehrgott, M.: A comparison of solution strategies for biobjective shortest path problems, Journal Computers and Operations Research, 36(4), 2009, 1299-1331.
• [29] Roy, B., Vincke, P.: Multicriteria analysis: survey and new directions, European Journal of Operational Research, 8(3), 1981,207-218.
• [30] Skriver, A., Andersen, K.: A classification of bicriteria shortest path (BSP) algorithms, Asia-Pacific Journal of Operational Research, 17, 2000, 199-212.
• [21] Skriver, A , Andersen. K.: A label correcting approach for solving bicriferion shortest-path problems, Computers & Operations Research, 27(6), 2000, 507-524.
• [32] Stadler, W.: A survey of multicriteria optimization or the vector maximum problem, part I: 1776-1960, Journal of Otimization Theory & Applictions, 29(1), 1979, 1-52.
• [33] Tung, C, Chew, K.: A bicriterion Pareto-optimal path algorithm, Asia-Pacific Journal of Operational Research 5, 1988, 166-172.
• [34] Tung, C, Chew, K.: A multicriteria Pareto-optimal path algorithm, European Journal of Operational Research,62(2), 1992,203-209.
• [35] Ulungu, E., Teghem, J.: Multi-objective combinatorial optimization problems: a survey, Journal of Multi-Criteria Decision Analysis, 3(2), 1994, 83-104.
• [36] Voorneveld, M.: Characterization of Pareto dominance, Operations Research Letters, 31(1), 2003, 7-11