A multi-objective capacitated rural school bus routing problem with heterogeneous fleet and mixed loads. (English) Zbl 1387.90042
Summary: Four multi-objective meta-heuristic algorithms are presented to solve a multi-objective capacitated rural school bus routing problem with a heterogeneous fleet and mixed loads. Three objectives are considered: the total weighted traveling time of the students, the balance of routes among drivers, and the routing costs. The proposed methods were compared with one from the literature, and their performance assessed observing three multi-objective metrics: cardinality, coverage, and hyper-volume. All four devised methods outperformed the one from the literature. The algorithm with a path relinking procedure embedded during the crowding distance selection scheme had the best overall performance.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90B50 | Management decision making, including multiple objectives |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
Keywords:
capacitated rural school bus routing problem; mixed loads; multi-objective optimization; multi-objective meta-heuristics; developing countries; decision support systemsReferences:
| [1] | Assis LP, Maravilha AL, Vivas A, Campelo F, Ramírez JA (2013) Multiobjective vehicle routing problem with fixed delivery and optional collections. Optim Lett 7(7):1419-1431 · Zbl 1280.90006 · doi:10.1007/s11590-012-0551-z |
| [2] | Batista LS, Campelo F, Guimarães FG, Ramírez JA (2011) Pareto cone \[\varepsilon\] ε-dominance: improving convergence and diversity in multiobjective evolutionary algorithms. In: International Conference on Evolutionary Multi-Criterion Optimization. Springer Berlin Heidelberg, pp 76-90 · Zbl 1185.90173 |
| [3] | Beume N, Fonseca CM, López-Ibáñez M, Paquete L, Vahrenhold J (2009) On the complexity of computing the hypervolume indicator. IEEE Trans Evol Comput 13(5):1075-1082 · doi:10.1109/TEVC.2009.2015575 |
| [4] | Bodin LD, Berman L (1979) Routing and scheduling of school buses by computer. Transp Sci 2(13):113-129 · doi:10.1287/trsc.13.2.113 |
| [5] | Bowerman R, Hall B, Calamai P (1995) A multi-objective optimization approach to urban school bus routing: formulation and solution method. Transp Res Part A 29(2):107-123 |
| [6] | Braca J, Bramel J, Posner B, Simchi-Levi D (1997) A computerized approach to the New York City school bus routing problem. IIE Trans 29:693-702 |
| [7] | Bradstreet L (2011) The hypervolume indicator for multi-objective optimisation: calculation and use. University of Western Australia |
| [8] | Carvalho WL, Cruz ROM, Câmara MT, Aragão JJG (2010) Rural school transportation in emerging countries: the Brazilian case. Res Transp Econ 29:401-409 · doi:10.1016/j.retrec.2010.07.051 |
| [9] | Chen DS, Kallsen HA (1988) School bus routing and scheduling: as expert system approach. Comput Ind Eng 15:179-183 · doi:10.1016/0360-8352(88)90082-4 |
| [10] | Clark G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12(4):568-581 · doi:10.1287/opre.12.4.568 |
| [11] | Corberán A, Fernández E, Laguna M, Martí R (2002) Heuristic solutions to the problem of routing school buses with multiple objectives. J Oper Res Soc 53:427-435 · Zbl 1130.90305 · doi:10.1057/palgrave.jors.2601324 |
| [12] | Deb K (2001) Multi-objective Optimization Using Evolutionary Algorithms. Wiley, London (ISBN 9780471873396) · Zbl 0970.90091 |
| [13] | Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evolut Comput 6(2):182-197 · doi:10.1109/4235.996017 |
| [14] | Gendreau M, Laporte G, Potvin J-Y (2001) Metaheuristics for the capacitated VRP. In: Toth P, Vigo D (eds) The vehicle routing problem. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA 129-154 · Zbl 1076.90545 |
| [15] | Gillett BE, Miller LR (1974) A heuristic algorithm for the vehicle-dispatch problem. Oper Res 22(2):340-349 · Zbl 0274.90013 · doi:10.1287/opre.22.2.340 |
| [16] | Glover F, Laguna M, Martí R (2000) Fundamentals of scatter search and path relinking. Control Cybern 39:653-684 · Zbl 0983.90077 |
| [17] | Golden B, Assad A, Levy L, Gheysens F (1984) The fleet size and mix vehicle routing problem. Comput Oper Res 11(1):49-66 · Zbl 0607.90043 · doi:10.1016/0305-0548(84)90007-8 |
| [18] | Hansen P, Mladenović N (2001) Variable neighborhood search: principles and applications. Eur J Oper Res 130(3):449-467 · Zbl 0981.90063 · doi:10.1016/S0377-2217(00)00100-4 |
| [19] | Hochberg Y (1988) A sharper bonferroni procedure for multiple tests of significance. Biometrika 75(4):800-802 · Zbl 0661.62067 · doi:10.1093/biomet/75.4.800 |
| [20] | INEP (2013) School census—2013. http://portal.inep.gov.br/basica-censo (in Portuguese) · Zbl 0661.62067 |
| [21] | Laporte G, Semet F (2002) 5. Classical heuristics for the capacitated VRP, Chapter 5, pp 109-128 · Zbl 1076.90549 |
| [22] | Li L, Fu Z (2002) The school bus routing problem: a case study. J Oper Res Soc 53:552-558 · Zbl 1059.90025 · doi:10.1057/palgrave.jors.2601341 |
| [23] | Li F, Golden B, Wasil S (2007) The open vehicle routing problem: algorithms, large-scale test problems, and computational results. Comput Oper Res 34:2918-2930 · Zbl 1185.90173 · doi:10.1016/j.cor.2005.11.018 |
| [24] | Lima FMS, Pereira DS, Conceio SV, Nunes NTR (2016) A mixed load capacitated rural school bus routing problem with heterogeneous fleet: Algorithms for the Brazilian context. Expert Syst Appl 56:320-334 · doi:10.1016/j.eswa.2016.03.005 |
| [25] | Marler RT, Arora JS (2010) The weighted sum method for multi-objective optimization: new insights. Struct Multidiscip Optim 41(6):853-862 · Zbl 1274.90359 · doi:10.1007/s00158-009-0460-7 |
| [26] | Martí R, Campos V, Resende MG, Duarte A (2011) Multi-objective grasp with path-relinking. AT&T Labs Research Technical Report · Zbl 1339.90305 |
| [27] | Pacheco J, Martí R (2006) Tabu search for a multi-objective routing problem. J Oper Res Soc 57:29-37 · Zbl 1121.90128 · doi:10.1057/palgrave.jors.2601917 |
| [28] | Pacheco J, Caballero R, Laguna M, Molina J (2013) Bi-objective bus routing: an application to school buses in rural areas. Transp Sci 47(3):397-411 · doi:10.1287/trsc.1120.0437 |
| [29] | Pareto V (1896) Cours d’économie politique professé a l’université de Lausanne, volume I. Librairie de l’Universit · Zbl 1175.90339 |
| [30] | Pareto V (1897) Cours d’économie politique professé a l’université de Lausanne, volume II. Librairie de l’Universit |
| [31] | Park J, Kim BI (2010) The school bus routing problem: a review. Eur J Oper Res 202:311-319 · Zbl 1175.90339 · doi:10.1016/j.ejor.2009.05.017 |
| [32] | Park J, Tae H, Kim BI (2012) A post-improvement procedure for the mixed load school bus routing problem. Eur J Oper Res 217:204-213 · Zbl 1244.90046 · doi:10.1016/j.ejor.2011.08.022 |
| [33] | Salkind Neil J (2006) Encyclopedia of measurement and statistics. Sage Publications · Zbl 0274.90013 |
| [34] | Schittekat P, Sevaux M, Sorensen K (2006) A mathematical formulation for a school bus routing problem. In: 2006 international conference on service systems and service management, vol 2. IEEE, pp 1552-1557 · Zbl 1244.90046 |
| [35] | Thangiah SR, Nygard KE (1992) School bus routing using genetic algorithm. In: Proceedings of the SPIE conference on applications of artificial intelligence, X: Knowledge Based Systems, Orlando, Florida, pp 387-398 · Zbl 1274.90359 |
| [36] | Vincent S (Ed.) (1999) The multigrade classroom: a resource handbook for small, rural schools, volume 1. Northwest Regional Education Laboratory, Book 1: Review of the Research on Multigrade Instruction · Zbl 0983.90077 |
| [37] | Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evolut Comput 3(4):257-271 · doi:10.1109/4235.797969 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
