A relation of dominance for the bicriterion bus routing problem

Jacek Widuch

International Journal of Applied Mathematics and Computer Science (2017)

  • Volume: 27, Issue: 1, page 133-155
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Jacek Widuch. "A relation of dominance for the bicriterion bus routing problem." International Journal of Applied Mathematics and Computer Science 27.1 (2017): 133-155. <http://eudml.org/doc/288099>.

@article{JacekWiduch2017,
abstract = {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.},
author = {Jacek Widuch},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {multicriteria optimization; set of non-dominated solutions; bicriterion shortest path problem; variable weights; label correcting algorithm; transportation problem},
language = {eng},
number = {1},
pages = {133-155},
title = {A relation of dominance for the bicriterion bus routing problem},
url = {http://eudml.org/doc/288099},
volume = {27},
year = {2017},
}

TY - JOUR
AU - Jacek Widuch
TI - A relation of dominance for the bicriterion bus routing problem
JO - International Journal of Applied Mathematics and Computer Science
PY - 2017
VL - 27
IS - 1
SP - 133
EP - 155
AB - 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.
LA - eng
KW - multicriteria optimization; set of non-dominated solutions; bicriterion shortest path problem; variable weights; label correcting algorithm; transportation problem
UR - http://eudml.org/doc/288099
ER -

References

top
  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. Zbl0681.90081
  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. Zbl0693.90090
  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. Zbl0488.90068
  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. Zbl0542.90099
  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. Zbl0434.90086
  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. Zbl1132.90303
  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. Zbl0956.90039
  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. Zbl0444.90098
  21. Henig, M.I. (1985). The shortest path problem with two objective functions, European Journal of Operational Research 25(2): 281-291. Zbl0594.90087
  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. Zbl1126.68058
  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. Zbl1244.90039
  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. Zbl1290.90012
  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. Zbl1162.90594
  33. Martins, E.Q.V. (1984). On a multicriteria shortest path problem, European Journal of Operational Research 16(2): 236-245. Zbl0533.90090
  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. Zbl0733.90073
  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. Zbl1175.90339
  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. Zbl1162.90579
  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. Zbl1251.90061
  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. Zbl1349.90124
  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. Zbl1042.90633
  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. Zbl0955.90144
  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. Zbl0715.90093
  50. Tung, C.T. and Chew, K.L. (1992). A bicriterion Pareto-optimal path algorithm, European Journal of Operational Research 62(2): 203-209. Zbl0769.90079
  51. Widuch, J. (2012). A label correcting algorithm for the bus routing problem, Fundamenta Informaticae 118(3): 305-326. Zbl1242.90280
  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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.