{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,15]],"date-time":"2024-05-15T23:10:32Z","timestamp":1715814632822},"reference-count":26,"publisher":"University of Zielona G\u00f3ra, Poland","issue":"1","license":[{"start":{"date-parts":[[2017,3,28]],"date-time":"2017-03-28T00:00:00Z","timestamp":1490659200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,3,28]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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.<\/jats:p>","DOI":"10.1515\/amcs-2017-0010","type":"journal-article","created":{"date-parts":[[2017,4,2]],"date-time":"2017-04-02T10:00:29Z","timestamp":1491127229000},"page":"133-155","source":"Crossref","is-referenced-by-count":3,"title":["A Relation of Dominance for the Bicriterion Bus Routing Problem"],"prefix":"10.61822","volume":"27","author":[{"given":"Jacek","family":"Widuch","sequence":"first","affiliation":[{"name":"Institute of Informatics Silesian University of Technology, ul. Akademicka 16, 44-100 Gliwice , Poland"}]}],"member":"37438","published-online":{"date-parts":[[2017,5,4]]},"reference":[{"key":"2021040611402781021_j_amcs-2017-0010_ref_001_w2aab2b8c19b1b7b1ab1ab1Aa","unstructured":"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 Research3(12): 26\u201336."},{"key":"2021040611402781021_j_amcs-2017-0010_ref_002_w2aab2b8c19b1b7b1ab1ab2Aa","unstructured":"Arias-Rojas, J.S., Jim\u00e9nez, J.F. and Montoya-Torres, J.R. (2012). Solving of school bus routing problem by ant colony optimization, Revista EIA9(17): 193\u2013208."},{"key":"2021040611402781021_j_amcs-2017-0010_ref_003_w2aab2b8c19b1b7b1ab1ab3Aa","unstructured":"Azevedo, J.A. and Martins, E.Q.V. (1991). An algorithm for the multiobjective shortest path problem on acyclic networks, Investiga\u00e7\u00e3o Operacional11(1): 52\u201369."},{"key":"2021040611402781021_j_amcs-2017-0010_ref_004_w2aab2b8c19b1b7b1ab1ab4Aa","unstructured":"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 Applications9(2): 56\u201362."},{"key":"2021040611402781021_j_amcs-2017-0010_ref_005_w2aab2b8c19b1b7b1ab1ab5Aa","doi-asserted-by":"crossref","unstructured":"Brumbaugh-Smith, J. and Shier, D. (1989). An empirical investigation of some bicriterion shortest path algorithms, European Journal of Operational Research43(2): 216\u2013224.","DOI":"10.1016\/0377-2217(89)90215-4"},{"key":"2021040611402781021_j_amcs-2017-0010_ref_006_w2aab2b8c19b1b7b1ab1ab6Aa","unstructured":"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\u201323."},{"key":"2021040611402781021_j_amcs-2017-0010_ref_007_w2aab2b8c19b1b7b1ab1ab7Aa","doi-asserted-by":"crossref","unstructured":"Carraway, R.L., Morin, T.L. and Moskowitz, H. (1990). Generalized dynamic programming for multicriteria optimization, European Journal of Operational Research44(1): 95\u2013104.","DOI":"10.1016\/0377-2217(90)90318-6"},{"key":"2021040611402781021_j_amcs-2017-0010_ref_008_w2aab2b8c19b1b7b1ab1ab8Aa","unstructured":"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\u201310."},{"key":"2021040611402781021_j_amcs-2017-0010_ref_009_w2aab2b8c19b1b7b1ab1ab9Aa","doi-asserted-by":"crossref","unstructured":"Chen, P. and Nie, Y.M. (2013). Bicriterion shortest path problem with a general nonadditive cost, Transportation Research B: Methodological57: 419\u2013435.","DOI":"10.1016\/j.trb.2013.05.008"},{"key":"2021040611402781021_j_amcs-2017-0010_ref_010_w2aab2b8c19b1b7b1ab1ac10Aa","doi-asserted-by":"crossref","unstructured":"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 ONE10(7): 1\u201320. DOI:10.1371\/journal.pone.0132600.","DOI":"10.1371\/journal.pone.0132600"},{"key":"2021040611402781021_j_amcs-2017-0010_ref_011_w2aab2b8c19b1b7b1ab1ac11Aa","doi-asserted-by":"crossref","unstructured":"Climaco, J.C. and Martins, E.Q.V. (1982). A bicriterion shortest path algorithm, European Journal of Operational Research11(4): 399\u2013404.","DOI":"10.1016\/0377-2217(82)90205-3"},{"key":"2021040611402781021_j_amcs-2017-0010_ref_012_w2aab2b8c19b1b7b1ab1ac12Aa","doi-asserted-by":"crossref","unstructured":"Corley, H.W. and Moon, I.D. (1985). Shortest paths in networks with vector weights, Journal of Optimization Theory and Application46(1): 79\u201386.","DOI":"10.1007\/BF00938761"},{"key":"2021040611402781021_j_amcs-2017-0010_ref_013_w2aab2b8c19b1b7b1ab1ac13Aa","doi-asserted-by":"crossref","unstructured":"Daellenbach, H.G. and De Kluyver, C.A. (1980). Note on multiple objective dynamic programming, Journal of the Operational Research Society31(7): 591\u2013594.","DOI":"10.1057\/jors.1980.114"},{"key":"2021040611402781021_j_amcs-2017-0010_ref_014_w2aab2b8c19b1b7b1ab1ac14Aa","doi-asserted-by":"crossref","unstructured":"Dell\u2019Olmo, P., Gentili, M. and Scozzari, A. (2005). On finding dissimilar Pareto-optimal paths, European Journal of Operational Research162(1): 70\u201382.","DOI":"10.1016\/j.ejor.2003.10.033"},{"key":"2021040611402781021_j_amcs-2017-0010_ref_015_w2aab2b8c19b1b7b1ab1ac15Aa","unstructured":"D\u00edaz-Parra, O., Ruiz-Vanoye, J.A., Buenabad-Arias, A. and Coc\u00f3n, 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\u201371."},{"key":"2021040611402781021_j_amcs-2017-0010_ref_016_w2aab2b8c19b1b7b1ab1ac16Aa","doi-asserted-by":"crossref","unstructured":"Ehrgott, M. (2000). Multicriteria Optimization, Springer-Verlag, Berlin.","DOI":"10.1007\/978-3-662-22199-0"},{"key":"2021040611402781021_j_amcs-2017-0010_ref_017_w2aab2b8c19b1b7b1ab1ac17Aa","doi-asserted-by":"crossref","unstructured":"Ellegood, W. A., Campbell, J. F. and North, J. (2015). Continuous approximation models for mixed load school bus routing, Transportation Research B77: 182\u2013198.","DOI":"10.1016\/j.trb.2015.03.018"},{"key":"2021040611402781021_j_amcs-2017-0010_ref_018_w2aab2b8c19b1b7b1ab1ac18Aa","doi-asserted-by":"crossref","unstructured":"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 Computation2: 15\u201324.","DOI":"10.1016\/j.swevo.2011.10.002"},{"key":"2021040611402781021_j_amcs-2017-0010_ref_019_w2aab2b8c19b1b7b1ab1ac19Aa","unstructured":"Garey, M. and Johnson, D. (1990). Computers and Intractibility: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co., New York, NY."},{"key":"2021040611402781021_j_amcs-2017-0010_ref_020_w2aab2b8c19b1b7b1ab1ac20Aa","doi-asserted-by":"crossref","unstructured":"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\u2013127.","DOI":"10.1007\/978-3-642-48782-8_9"},{"key":"2021040611402781021_j_amcs-2017-0010_ref_021_w2aab2b8c19b1b7b1ab1ac21Aa","doi-asserted-by":"crossref","unstructured":"Henig, M.I. (1985). The shortest path problem with two objective functions, European Journal of Operational Research25(2): 281\u2013291.","DOI":"10.1016\/0377-2217(86)90092-5"},{"key":"2021040611402781021_j_amcs-2017-0010_ref_022_w2aab2b8c19b1b7b1ab1ac22Aa","unstructured":"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\u20134149."},{"key":"2021040611402781021_j_amcs-2017-0010_ref_023_w2aab2b8c19b1b7b1ab1ac23Aa","doi-asserted-by":"crossref","unstructured":"Jungnickel, D. (1999). Graphs, Networks and Algorithms, 2nd Edition, Springer-Verlag, Berlin.","DOI":"10.1007\/978-3-662-03822-2"},{"key":"2021040611402781021_j_amcs-2017-0010_ref_024_w2aab2b8c19b1b7b1ab1ac24Aa","doi-asserted-by":"crossref","unstructured":"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 Applications9(5): 107\u2013126.","DOI":"10.14257\/ijseia.2015.9.5.11"},{"key":"2021040611402781021_j_amcs-2017-0010_ref_025_w2aab2b8c19b1b7b1ab1ac25Aa","doi-asserted-by":"crossref","unstructured":"Kim, B.I., Kim, S. and Park, J. (2012). A school bus scheduling problem, European Journal of Operational Research218(2): 577\u2013585.","DOI":"10.1016\/j.ejor.2011.11.035"},{"key":"2021040611402781021_j_amcs-2017-0010_ref_026_w2aab2b8c19b1b7b1ab1ac26Aa","unstructured":"Kim, T. and Park, B.J. (2013). Model and algorithm for solving school bus problem, Journal of Emerging Trends in Computing and Information Sciences4(8): 596\u2013600."}],"container-title":["International Journal of Applied Mathematics and Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/content.sciendo.com\/view\/journals\/amcs\/27\/1\/article-p133.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.sciendo.com\/article\/10.1515\/amcs-2017-0010","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,15]],"date-time":"2024-05-15T22:57:24Z","timestamp":1715813844000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.sciendo.com\/article\/10.1515\/amcs-2017-0010"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,28]]},"references-count":26,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2017,5,4]]},"published-print":{"date-parts":[[2017,3,28]]}},"alternative-id":["10.1515\/amcs-2017-0010"],"URL":"https:\/\/doi.org\/10.1515\/amcs-2017-0010","relation":{},"ISSN":["2083-8492"],"issn-type":[{"value":"2083-8492","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,28]]}}}