Repositório Institucional da UFPB
Use este identificador para citar ou linkar para este item:
https://repositorio.ufpb.br/jspui/handle/123456789/22887| Tipo: | TCC |
| Título: | Uma meta-heurística Iterated Local Search para o School Bus Routing Problem |
| Autor(es): | Teixeira, Ewerton Victor Paredes da Penha |
| Primeiro Orientador: | Subramanian, Anand |
| Resumo: | O problema de roteamento de ˆonibus escolares, do inglˆes School Bus Routing Problem (SBRP), consiste em uma variante do Problema de Roteamento de Ve´ıculos Capacitados (PRVC) em que h´a a necessidade de realizar o transporte de estudantes at´e as escolas. O presente trabalho lida com uma variante do SBRP considerando a sele¸c˜ao das paradas de ˆonibus adotadas, aloca¸c˜ao dos estudantes a essas paradas e realiza¸c˜ao da roteiriza¸c˜ao dos ve´ıculos considerando uma ´unica escola, objetivando-se diminui¸c˜ao do custo total de roteiriza¸c˜ao enquanto se obedece restri¸c˜oes de capacidade dos ˆonibus e distˆancia m´axima que os alunos podem caminhar das suas casas at´e as paradas. E proposto um algoritmo ´ h´ıbrido baseado na meta-heur´ıstica Iterated Local Search (ILS) com uma formula¸c˜ao de programa¸c˜ao linear inteira (PLI). O algoritmo foi testado em 95 instˆancias j´a conhecidas na literatura, obtendo resultados competitivos, bem como melhorando resultados de 10 das 95 instˆancias testadas. |
| Abstract: | The School Bus Routing Problem (SBRP) consists on a variant of the Capacitated Vehicle Routing Problem (CVRP) in which there is a need to transport students to schools. The present work deals with a variant of the SBRP in which it is necessary to select the bus stops adopted, allocate students to those stops and perform the routing of vehicles considering a single school, aiming at reducing the total cost of routing while obeying capacity restrictions of the buses and the maximum distance that students can walk from their homes to the stops. An hybrid algorithm based on Iterated Local Search (ILS) with an integer linear programming formulation is proposed. The algorithm was tested in 95 instances already known in the literature, obtaining competitive results, as well as improving results in 10 of the 95 tested instances. |
| Palavras-chave: | Roteamento de ˆonibus escolares Meta-heurística Iterated Local Search |
| CNPq: | CNPQ::ENGENHARIAS::ENGENHARIA DE PRODUCAO |
| Idioma: | por |
| País: | Brasil |
| Editor: | Universidade Federal da Paraíba |
| Sigla da Instituição: | UFPB |
| Departamento: | Engenharia de Produção |
| Tipo de Acesso: | Acesso aberto |
| URI: | https://repositorio.ufpb.br/jspui/handle/123456789/22887 |
| Data do documento: | 7-Ago-2020 |
| Aparece nas coleções: | TCC - Engenharia Química |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| TCC - EWERTON VICTOR PAREDES DA PENHA TEIXEIRA.pdf | 949,56 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.