A relation of dominance for the bicriterion bus routing problem

• Autorzy: Widuch J.

Identyfikatory

DOI

10.1515/amcs-2017-0010

• Języki publikacji: EN

Abstrakty

EN

A bicriterion bus routing (BBR) problem is described and analysed. The objective is to find a route from the start stop to the final stop minimizing the time and the cost of travel simultaneously. Additionally, the time of starting travel at the start stop is given. The BBR problem can be resolved using methods of graph theory. It comes down to resolving a bicriterion shortest path (BSP) problem in a multigraph with variable weights. In the paper, differences between the problem with constant weights and that with variable weights are described and analysed, with particular emphasis on properties satisfied only for the problem with variable weights and the description of the influence of dominated partial solutions on non-dominated final solutions. This paper proposes methods of estimation a dominated partial solution for the possibility of obtaining a non-dominated final solution from it. An algorithm for solving the BBR problem implementing these estimation methods is proposed and the results of experimental tests are presented.

Słowa kluczowe

EN

multicriteria optimization; set of nondominated solutions; bicriterion shortest path problem; variable weights; label correcting algorithm; transportation problem

PL

optymalizacja wielokryterialna; zbiór rozwiązań niezdominowanych; problem dwukryterialny najkrótszej ścieżki; zmienne wagi; problem transportowy

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2017
• Tom: Vol. 27, no. 1
• Strony: 133--155
• Opis fizyczny: Bibliogr. 54 poz., rys., tab., wykr.

Twórcy

autor

Widuch J.

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

Bibliografia

• [1] Addor, J.A., Amponsah, S.K., Annan, J. and Sebil, C. (2013). School bus routing: A case study of wood bridge school complex, Sekondi-Takoradi, Ghana, International Journal of Business and Social Research 3(12): 26–36.
• [2] Arias-Rojas, J.S., Jiménez, J.F. and Montoya-Torres, J.R. (2012). Solving of school bus routing problem by ant colony optimization, Revista EIA 9(17): 193–208.
• [3] Azevedo, J.A. and Martins, E.Q.V. (1991). An algorithm for the multiobjective shortest path problem on acyclic networks, Investigação Operacional 11(1): 52–69.
• [4] Bronshtein, E.M. and Vagapova, D.M. (2015). Comparative analysis of application of heuristic and metaheuristic algorithms to the school bus routing problem, Informatics and Its Applications 9(2): 56–62.
• [5] Brumbaugh-Smith, J. and Shier, D. (1989). An empirical investigation of some bicriterion shortest path algorithms, European Journal of Operational Research 43(2): 216–224.
• [6] Caceres, H., Batta, R. and He, Q. (2014). School bus routing with stochastic demand and duration constraints, Transportation Research Board 93rd Annual Meeting, Washington, DC, USA, pp. 1–23.
• [7] Carraway, R.L., Morin, T.L. and Moskowitz, H. (1990). Generalized dynamic programming for multicriteria optimization, European Journal of Operational Research 44(1): 95–104.
• [8] Chalkia, E., Grau, J.M.S., Bekiaris, E., Ayfandopoulou, G., Ferarini, C. and Mitsakis, E. (2014). Routing algorithms for the safe transportation of pupils to school using school buses, Transport Research Arena (TRA) 5th Conference: Transport Solutions from Research to Deployment, Paris, France, pp. 1–10.
• [9] Chen, P. and Nie, Y.M. (2013). Bicriterion shortest path problem with a general nonadditive cost, Transportation Research B: Methodological 57: 419–435.
• [10] Chen, X., Kong, Y., Dang, L., Hou, Y. and Ye, X. (2015). Exact and metaheuristic approaches for a bi-objective school bus scheduling problem, PLoS ONE 10(7): 1–20. DOI:10.1371/journal.pone.0132600.
• [11] Climaco, J.C. and Martins, E.Q.V. (1982). A bicriterion shortest path algorithm, European Journal of Operational Research 11(4): 399–404.
• [12] Corley, H.W. and Moon, I.D. (1985). Shortest paths in networks with vector weights, Journal of Optimization Theory and Application 46(1): 79–86.
• [13] Daellenbach, H.G. and De Kluyver, C.A. (1980). Note on multiple objective dynamic programming, Journal of the Operational Research Society 31(7): 591–594.
• [14] Dell’Olmo, P., Gentili, M. and Scozzari, A. (2005). On finding dissimilar Pareto-optimal paths, European Journal of Operational Research 162(1): 70–82.
• [15] Díaz-Parra, O., Ruiz-Vanoye, J.A., Buenabad-Arias, A. and Cocón, F. (2012). A vertical transfer algorithm for the school bus routing problem, 4th World Congress on Nature and Biologically Inspired Computing (NaBIC), Mexico City, Mexico, pp. 66–71.
• [16] Ehrgott, M. (2000). Multicriteria Optimization, Springer-Verlag, Berlin.
• [17] Ellegood, W. A., Campbell, J. F. and North, J. (2015). Continuous approximation models for mixed load school bus routing, Transportation Research B 77: 182–198.
• [18] Euchi, J. and Mraihi, R. (2012). The urban bus routing problem in the Tunisian case by the hybrid artificial ant colony algorithm, Swarm and Evolutionary Computation 2: 15–24.
• [19] Garey, M. and Johnson, D. (1990). Computers and Intractibility: A Guide to the Theory of NP-Completeness,W.H. Freeman & Co., New York, NY.
• [20] Hansen, P. (1980). Bicriterion path problems, in G. Fandel and T. Gal (Eds.), Multiple Criteria Decision Making: Theory and Application, Springer-Verlag, Berlin, pp. 109–127.
• [21] Henig, M.I. (1985). The shortest path problem with two objective functions, European Journal of Operational Research 25(2): 281–291.
• [22] Huang, L.C., Guan, W. and Xiong, J. (2014). Routing design optimization of bus joint for passenger transfer centers, in M. Sun and Y. Zhang (Eds.), Renewable Energy and Environmental Technology, Applied Mechanics and Materials, Vol. 448, Trans Tech Publications, Zurich, pp. 4140–4149.
• [23] Jungnickel, D. (1999). Graphs, Networks and Algorithms, 2nd Edition, Springer-Verlag, Berlin.
• [24] Kang, M., Kim, S.K., Felan, J.T., Choi, H.R. and Cho, M. (2015). Development of a genetic algorithm for the school bus routing problem, International Journal of Software Engineering and Its Applications 9(5): 107–126.
• [25] Kim, B.I., Kim, S. and Park, J. (2012). A school bus scheduling problem, European Journal of Operational Research 218(2): 577–585.
• [26] Kim, T. and Park, B.J. (2013). Model and algorithm for solving school bus problem, Journal of Emerging Trends in Computing and Information Sciences 4(8): 596–600.
• [27] Kinable, J., Spieksma, F.C.R. and Berghe, G.V. (2014). School bus routing—a column generation approach, International Transactions in Operational Research 21(3): 453–478.
• [28] López, E.R. and Romero, J. (2015). A hybrid column generation and clustering approach to the school bus routing problem with time windows, Ingeniería 20(1): 111–127.
• [29] Machuca, E., Mandow, L. and Pérez de la Cruz, J.L. (2009). An evaluation of heuristic functions for bicriterion shortest path problems, Proceedings of the 14 Portuguese Conference on Artificial Inteligence (EPIA 2009), Aveiro, Portugal, pp. 205–216.
• [30] Mandow, L. and Pérez de la Cruz, J.L. (2008). Path recovery in frontier search for multiobjective shortest path problems, Journal of Intelligent Manufacturing 21(1): 89–99.
• [31] Manumbu, D.M., Mujuni, E. and Kuznetsov, D. (2014). A simulated annealing algorithm for solving the school bus routing problem: A case study of Dar es Salaam, Computer Engineering and Intelligent Systems 5(8): 44–58.
• [32] Martí, R., González Velarde, J.L. and Duarte, A. (2009). Heuristics for the bi-objective path dissimilarity problem, Computers & Operations Research 36(11): 2905–2912.
• [33] Martins, E.Q.V. (1984). On a multicriteria shortest path problem, European Journal of Operational Research 16(2): 236–245.
• [34] Martins, E.Q.V., Pascoal, M.M.B., Rasteiro, D.M.L.D. and Santos, J.L.E. (1999). The optimal path problem, Investigação Operacional 19(1): 43–60.
• [35] Mote, J., Murthy, I. and Olson, D.L. (1991). A parametric approach to solving bicriterion shortest path problems, European Journal of Operational Research 53(1): 81–82.
• [36] Newton, R.M. and Thomas, W.H. (1969). Design of school bus routes by computer, Socio-Economic Planning Sciences 3(1): 75–85.
• [37] Pacheco, J., Caballero, R., Laguna, M. and Molina, J. (2013). Bi-objective bus routing: An application to school buses in rural areas, Transportation Science 47(3): 397–411.
• [38] Pareto, V. (1896). Course d’Economie Politique, F. Rouge, Lausanne.
• [39] Park, J. and Kim, B.-I. (2010). The school bus routing problem: A review, European Journal of Operational Research 202(2): 311–319.
• [40] Raith, A. and Ehrgott, M. (2009). A comparison of solution strategies for biobjective shortest path problems, Journal Computers and Operations Research 36(4): 1299–1331.
• [41] Riera-Ledesma, J. and Salazar-González, J.J. (2012). Solving school bus routing using the multiple vehicle traveling purchaser problem: A branch-and-cut approach, Computers & Operations Research 39(2): 391–404.
• [42] Riera-Ledesma, J. and Salazar-González, J.J. (2013). A column generation approach for a school bus routing problem with resource constraints, Computers & Operations Research 40(2): 566–583.
• [43] Schittekat, P., Kinable, J., Sörensen, K., Sevaux, M. and Spieksma, F. (2013). A metaheuristic for the school bus routing problem with bus stop selection, European Journal of Operational Research 229(2): 518–528.
• [44] Serafini, P. (1987). Some considerations about computational complexity for multi objective combinatorial problems, in J. Jahn and W. Krabs (Eds.), Recent Advances and Historical Development of Vector Optimization, Lecture Notes in Economics and Mathematical Systems, Vol. 294, Springer, Berlin/Heidelberg, pp. 222–232.
• [45] Sghaier, S.B., Guedria, N.B. and Mraihi, R. (2013). Solving school bus routing problem with genetic algorithm, International Conference on Advanced Logistics and Transport (ICALT’2013), Sousse, Tunisia, pp. 7–12.
• [46] Siqueira, V.S., Silva, F.J.E.L., Silva, E.N., Silva, R.V.S. and Rocha, M.L. (2016). Implementation of the metaheuristic grasp applied to the school bus routing problem, International Journal of e-Education, e-Business, e-Management and e-Learning 6(2): 137–145.
• [47] Skriver, A.J.V. and Andersen, K.A. (2000a). A classification of bicriteria shortest path (BSP) algorithms, Asia-Pacific Journal of Operational Research 17(2): 199–212.
• [48] Skriver, A.J.V. and Andersen, K.A. (2000b). A label correcting approach for solving bicriterion shortest-path problems, Computers & Operations Research 27(6): 507–524.
• [49] Tung, C.T. and Chew, K.L. (1988). A bicriterion Pareto-optimal path algorithm, Asia-Pacific Journal of Operational Research 5(2): 166–172.
• [50] Tung, C.T. and Chew, K.L. (1992). A bicriterion Pareto-optimal path algorithm, European Journal of Operational Research 62(2): 203–209.
• [51] Widuch, J. (2012). A label correcting algorithm for the bus routing problem, Fundamenta Informaticae 118(3): 305–326.
• [52] Widuch, J. (2013). A label correcting algorithm with storing partial solutions to solving the bus routing problem, Informatica 24(3): 461–484.
• [53] Worwa, K. (2014). A case study in school transportation logistics, Research in Logistics & Production 4(1): 45–54.
• [54] Yigit, T. and Unsal, O. (2016). Using the ant colony algorithm for real-time automatic route of school buses, International Arab Journal of Information Technology 13(5): 559–565.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).