A relation of dominance for the bicriterion bus routing problem

Jacek Widuch

International Journal of Applied Mathematics and Computer Science, Tome 27 (2017), p. 133-155 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2017-01-01
EUDML-ID : urn:eudml:doc:288099

Bibliographie

[000] 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.

[001] 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.

[002] 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.

[003] 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.

[004] 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. | Zbl 0681.90081

[005] 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.

[006] 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. | Zbl 0693.90090

[007] 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.

[008] Chen, P. and Nie, Y.M. (2013). Bicriterion shortest path problem with a general nonadditive cost, Transportation Research B: Methodological 57: 419-435.

[009] 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.

[010] Climaco, J.C. and Martins, E.Q.V. (1982). A bicriterion shortest path algorithm, European Journal of Operational Research 11(4): 399-404. | Zbl 0488.90068

[011] 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. | Zbl 0542.90099

[012] 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. | Zbl 0434.90086

[013] Dell'Olmo, P., Gentili, M. and Scozzari, A. (2005). On finding dissimilar Pareto-optimal paths, European Journal of Operational Research 162(1): 70-82. | Zbl 1132.90303

[014] 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.

[015] Ehrgott, M. (2000). Multicriteria Optimization, Springer-Verlag, Berlin. | Zbl 0956.90039

[016] 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.

[017] 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.

[018] Garey, M. and Johnson, D. (1990). Computers and Intractibility: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co., New York, NY.

[019] 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. | Zbl 0444.90098

[020] Henig, M.I. (1985). The shortest path problem with two objective functions, European Journal of Operational Research 25(2): 281-291. | Zbl 0594.90087

[021] 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.

[022] Jungnickel, D. (1999). Graphs, Networks and Algorithms, 2nd Edition, Springer-Verlag, Berlin. | Zbl 1126.68058

[023] 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.

[024] Kim, B.I., Kim, S. and Park, J. (2012). A school bus scheduling problem, European Journal of Operational Research 218(2): 577-585. | Zbl 1244.90039

[025] 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.

[026] 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. | Zbl 1290.90012

[027] 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.

[028] 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.

[029] 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.

[030] 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.

[031] 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. | Zbl 1162.90594

[032] Martins, E.Q.V. (1984). On a multicriteria shortest path problem, European Journal of Operational Research 16(2): 236-245. | Zbl 0533.90090

[033] 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.

[034] 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. | Zbl 0733.90073

[035] Newton, R.M. and Thomas, W.H. (1969). Design of school bus routes by computer, Socio-Economic Planning Sciences 3(1): 75-85.

[036] 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.

[037] Pareto, V. (1896). Course d'Economie Politique, F. Rouge, Lausanne.

[038] Park, J. and Kim, B.-I. (2010). The school bus routing problem: A review, European Journal of Operational Research 202(2): 311-319. | Zbl 1175.90339

[039] 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. | Zbl 1162.90579

[040] 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. | Zbl 1251.90061

[041] 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. | Zbl 1349.90124

[042] 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.

[043] 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.

[044] 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.

[045] 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.

[046] 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. | Zbl 1042.90633

[047] 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. | Zbl 0955.90144

[048] Tung, C.T. and Chew, K.L. (1988). A bicriterion Pareto-optimal path algorithm, Asia-Pacific Journal of Operational Research 5(2): 166-172. | Zbl 0715.90093

[049] Tung, C.T. and Chew, K.L. (1992). A bicriterion Pareto-optimal path algorithm, European Journal of Operational Research 62(2): 203-209. | Zbl 0769.90079

[050] Widuch, J. (2012). A label correcting algorithm for the bus routing problem, Fundamenta Informaticae 118(3): 305-326. | Zbl 1242.90280

[051] Widuch, J. (2013). A label correcting algorithm with storing partial solutions to solving the bus routing problem, Informatica 24(3): 461-484.

[052] Worwa, K. (2014). A case study in school transportation logistics, Research in Logistics & Production 4(1): 45-54.

[053] 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.