1 |
[en] A SIMPLE AND EFFECTIVE HYBRID GENETIC SEARCH FOR THE JOB SEQUENCING AND TOOL SWITCHING PROBLEM / [pt] UMA BUSCA GENÉTICA HÍBRIDA SIMPLES E EFETIVA PARA O PROBLEMA DE SEQUENCIAMENTO DE TAREFAS E TROCA DE FERRAMENTASJORDANA ZERPINI MECLER 19 August 2020 (has links)
[pt] O problema de sequenciamento de tarefas e troca de ferramentas (job sequencing and tool switching problem - SSP) tem sido extensivamente estudado na área de pesquisa operacional, devido à sua relevância prática e interesse metodológico. Dada uma máquina que pode carregar uma quantidade limitada de ferramentas simultaneamente e um número de tarefas que requerem um subconjunto das ferramentas disponíveis, o SSP procura uma sequência de tarefas que minimize o número total de trocas de ferramentas na máquina. Para resolver este problema, é proposta uma busca genética híbrida simples e efetiva baseada em uma representação de solução genérica, um operador de decodificação sob medida, buscas locais eficientes e técnicas de gerenciamento de diversidade. Para orientar a busca, um objetivo secundário desenvolvido para tratar empates é introduzido. Essas técnicas permitem explorar soluções estruturalmente distintas e escapar de ótimos locais. Conforme apresentado nos experimentos computacionais em instâncias clássicas, o algoritmo proposto supera significativamente todas as abordagens anteriores, mesmo sendo de fácil entendimento e implementação. Por fim, resultados obtidos em um novo conjunto de instâncias maiores são reportados para estimular futuras pesquisas e análises comparativas. / [en] The job sequencing and tool switching problem (SSP) has been extensively studied in the field of operations research, due to its practical relevance and methodological interest. Given a machine that can load a limited amount of tools simultaneously and a number of jobs that require a subset of the available tools, the SSP seeks a job sequence that minimizes the number of tool switches in the machine. To solve this problem, we propose a simple and efficient hybrid genetic search based on a generic solution representation, a tailored decoding operator, efficient local searches and diversity management techniques. To guide the search, we introduce a secondary objective designed to break ties. These techniques allow to explore structurally different solutions and escape local optima. As shown in our computational experiments on classical benchmark instances, our algorithm significantly outperforms all previous approaches while remaining simple to apprehend and easy to implement. We finally report results on a new set of larger instances to stimulate future research and comparative analyses.
|
2 |
[en] IMPROVED HYBRID GENETIC SEARCH FOR THE INVENTORY ROUTING PROBLEM / [pt] MELHORIA DE BUSCA GENÉTICA HÍBRIDA PARA O PROBLEMA DE ROTEAMENTO DE INVENTÁRIOBRUNO GUIMARAES DE CASTRO 15 February 2024 (has links)
[pt] Tema: Este estudo investiga o Problema de Roteamento de Inventário
(IRP) no contexto do Gerenciamento de Inventário pelo Fornecedor (VMI),
uma prática comum na cadeia de suprimentos onde os fornecedores assumem a
responsabilidade pela reposição. O IRP, um problema combinatório estudado
amplamente há quase 40 anos, engloba três subproblemas distintos: programação de entregas, gerenciamento de estoque e roteamento de veículos. Problema: Apesar de sua idade, o IRP continua a atrair a atenção da indústria e
da academia. O recente décimo segundo Desafio de Implementação DIMACS dedicou uma
categoria ao IRP, e entre os benchmarks comumente utilizados, 401 instâncias
ainda não possuem soluções ótimas, especialmente no desafiador subconjunto
de instâncias grandes. Hipótese e Justificativa: O framework HGS proposto
por Vidal et al. (2012) surgiu como uma ferramenta proeminente utilizada por
várias equipes de forma satisfatória na competição. No entanto, até onde sabemos, o framework HGS não foi testada para o IRP. Este estudo propõe uma
solução que combina o framework HGS com uma estratégia de busca local eficiente, o método NSIRP proposto por Diniz et al. (2020), para abordar o IRP.
Metodologia: Implementamos a solução proposta e comparamos seu desempenho com 21 abordagens existentes, utilizando os benchmarks da literatura.
Resumo dos Resultados: Nossa abordagem identificou 79 novas Melhores
Soluções Conhecidas (BKS) dentre 1100 instâncias. Se aplicada sob as mesmas
regras da competição DIMACS, nossa solução teria garantido o primeiro lugar.
Contribuições e Impactos: Este trabalho contribui para o desenvolvimento
contínuo de soluções para o IRP, oferecendo uma abordagem eficiente e competitiva que pode inspirar futuras pesquisas e aplicações práticas no campo do
gerenciamento de estoque e roteamento de veículos. / [en] Theme: This study investigates the Inventory Routing Problem (IRP)
within the context of Vendor-Managed Inventory (VMI), a prevalent supply
chain practice where suppliers assume responsibility for replenishment. The
IRP, a combinatorial problem that has been widely studied for almost 40 years,
encompasses three distinct subproblems: delivery scheduling, inventory management, and vehicle routing. Problem: Despite its age, the IRP continues
to attract industry and academia attention. The recent 12th DIMACS Implementation Challenge dedicated a track to the IRP, and among the commonly
used benchmarks, 401 instances still lack optimal solutions, particularly in the
challenging Large instance subset. Hypothesis and Justification: The HGS
framework proposed by Vidal et al. (2012) emerged as a prominent tool used
successfully by numerous teams in the competition. However, to the best of our
knowledge, the HGS framework has not been tested for the IRP. This study
proposes a method combining the HGS framework with an efficient local search
strategy, namely NSIRP proposed by Diniz et al. (2020), to tackle the IRP.
Methodology: We implemented the proposed method and compared its performance to 21 existing methods using the literature benchmarks. Summary
of Results: Our approach identified 79 new Best Known Solutions (BKS) out
of 1100 instances. If applied under the same rules as the DIMACS competition,
our method would have secured the first place. Contributions and Impacts:
This work contribute to the ongoing development of IRP methods, offering an
efficient and competitive approach that may inspire further research and practical applications in the realm of inventory management and vehicle routing.
|
Page generated in 0.0474 seconds