Estudio y desarrollo de un modelo matemático para el problema de rutas escolares (SBRP)
Este trabajo se expone en tres capítulos. En el primero, se muestran las definiciones y ejemplos más importantes para nuestro trabajo, además del estudio de herramientas básicas para la construcción de continuos, como lo son la intersección anidada de continuos, el producto numerable de continuos, e...
- Autores:
-
Bustos Gutierrez, Maribel
Pinilla Cifuentes, Astrid Carolina
- Tipo de recurso:
- http://purl.org/coar/version/c_b1a7d7d4d402bcce
- Fecha de publicación:
- 2016
- Institución:
- Universidad Industrial de Santander
- Repositorio:
- Repositorio UIS
- Idioma:
- spa
- OAI Identifier:
- oai:noesis.uis.edu.co:20.500.14071/34780
- Palabra clave:
- Problema De Rutas Escolares (Sbrp)
Selección De Paradas
Problema De Ruteo De Vehículos (Vrp)
Ramificación Y Acotamiento
Metaheurística
Búsqueda Tabú.
School bus routing problem (SBRP)
consists in finding one or more routes on a network of bus stops
with known origin and common destiny
where every student must be assigned to one of these
later each bus to visit those stops according to the route drawn on the network and transfer the students to school. The objective of this research is to solve the problem of school routes using a model of binary integer linear programming
in which seeks to minimize the subset of selected stops
to which students are assigned
as long as they comply with the allowed distance to walk to a stop
and then develop a series of routes that minimize the total distance traveled by all buses. The solution SBRP will through exact methods with the algorithm branch and bound
and by methods approximate the development of a system based on metaheuristic Tabu Search algorithm whose initial solution is provided through the algorithm savings Clarke and Wright. The results obtained by the algorithm
finally were compared with those calculated by the exact method
in order to test the efficiency and effectiveness of the algorithm developed. This comparison showed that
for instances evaluated
the algorithm presented a maximum difference of 10
5% compared to the optimal solution
but that is offset by a faster computational time 99
7%.
- Rights
- License
- Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)