Browsing by Author "Subramanian, Anand"

Now showing 1 - 10 of 10
  • No Thumbnail Available
    Item
    An iterated local search heuristic for multi-capacity bin packing and machine reassignment problems.
    (2013) Masson, Renaud; Vidal, Thibaut Victor Gaston; Michallet, Julien; Penna, Puca Huachi Vaz; Petrucci, Vinicius; Subramanian, Anand; Dubedout, Hugues
    This paper proposes an efficient Multi-Start Iterated Local Search for Packing Problems (MS-ILS-PPs) metaheuristic for Multi-Capacity Bin Packing Problems (MCBPP) and Machine Reassignment Problems (MRP). The MCBPP is a generalization of the classical bin-packing problem in which the machine (bin) capacity and task (item) sizes are given by multiple (resource) dimensions. The MRP is a challenging and novel optimization problem, aimed at maximizing the usage of available machines by reallocating tasks/processes among those machines in a cost-efficient manner, while fulfilling several capacity, conflict, and dependency-related constraints. The proposed MS-ILS-PP approach relies on simple neighborhoods as well as problem-tailored shaking procedures. We perform computational experiments on MRP benchmark instances containing between 100 and 50,000 processes. Near-optimum multi-resource allocation and scheduling solutions are obtained while meeting specified processing-time requirements (on the order of minutes). In particular, for 9/28 instances with more than 1000 processes, the gap between the solution value and a lower bound measure is smaller than 0.1%. Our optimization method is also applied to solve classical benchmark instances for the MCBPP, yielding the best known solutions and optimum ones in most cases. In addition, several upper bounds for non-solved problems were improved.
  • No Thumbnail Available
    Item
    An iterated local search heuristic for the heterogeneous fleet vehicle routing problem.
    (2013) Penna, Puca Huachi Vaz; Subramanian, Anand; Ochi, Luiz Satoru
    This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP is NP-hard since it is a generalization of the classical Vehicle Routing Problem (VRP), in which clients are served by a heterogeneous fleet of vehicles with distinct capacities and costs. The objective is to design a set of routes in such a way that the sum of the costs is minimized. The proposed algorithm is based on the Iterated Local Search (ILS) metaheuristic which uses a Variable Neighborhood Descent procedure, with a random neighborhood ordering (RVND), in the local search phase. To the best of our knowledge, this is the first ILS approach for the HFVRP. The developed heuristic was tested on well-known benchmark instances involving 20, 50, 75 and 100 customers. These test-problems also include dependent and/or fixed costs according to the vehicle type. The results obtained are quite competitive when compared to other algorithms found in the literature.
  • No Thumbnail Available
    Item
    Aplicação da metaheurística Busca Tabu ao problema de alocação de aulas a salas em uma instituição universitária.
    (2011) Subramanian, Anand; Medeiros, José Maurício Fernandes; Formiga, Lucídio dos Anjos; Souza, Marcone Jamilson Freitas
    Este artigo trata do Problema de Alocação de Aulas a Salas de uma Instituição Universitária. Na instituição analisada, a resolução deste problema é feita manualmente, tornando o processo árduo e demorado, além de frequentemente não produzir soluções que atendam a todas as restrições do problema. Desta forma, faz-se necessário automatizar o processo de alocação e, além disso, recorrer a estratégias computacionais que proporcionem soluções de qualidade e baixo custo. Devido à natureza combinatória do problema, recorreu-se à metaheurística Busca Tabu, que tem se mostrado adequada para a resolução desta classe de problemas. O algoritmo proposto parte de uma solução inicial gerada por um procedimento construtivo, o qual é capaz de produzir soluções viáveis em menos de um segundo. A seguir, esta solução é refinada pela Busca Tabu usando-se movimentos de realocação e troca de aulas entre salas para explorar o espaço de busca. O algoritmo proposto foi testado usando-se dados relativos à alocação de aulas de um semestre letivo e demonstrou ser bastante eficiente, tendo gerado soluções de alta qualidade quando comparado com a solução manual.
  • No Thumbnail Available
    Item
    Exact and heuristic approaches for traveling salesman problems with drones.
    (2021) Freitas, Júlia Cária de; Penna, Puca Huachi Vaz; Toffolo, Túlio Ângelo Machado; Penna, Puca Huachi Vaz; Toffolo, Túlio Ângelo Machado; Souza, Marcone Jamilson Freitas; Subramanian, Anand
    The technological advances concerning drones have encouraged the market to consider drone applications in different areas including last mile delivery. However, limitations due to battery capacity, maximum weight, and legal regulations restrict the effective operational range of drones in many practical applications. To overcome the battery issue, hybrid operations involving one or more drones launching from a larger vehicle have emerged, in which the larger vehicle operates as a mobile depot and a recharging platform. In this dissertation, we describe a routing model that leverage the drone and truck working as a synchronized unit. The Flying Sidekick Traveling Salesman Problem (FSTSP) considers a delivery system composed by a truck and a drone. The drone launches from the truck with a single package to deliver to a customer. Each drone must return to the truck to recharge batteries, pick up another package, and launch again to a new customer location. This work proposes two novel Mixed Integer Programming (MIP) formulations and a heuristic approach to address the problem. The proposed MIP formulations yields better linear relaxation bounds than previously proposed formulations for all instances, and was capable of optimally solving several unsolved instances from the literature. We developed a hybrid heuristic based on the General Variable Neighborhood Search metaheuristic to tackle a generalization of the FSTSP called Multiple Traveling Salesman Problem with Drones, in which multiple trucks and drones are considered as part of the delivery system. The heuristic obtained high-quality solutions for large-size instances. The efficiency of the algorithm was evaluated on 410 benchmark instances from the literature, and over 80% of the best known solutions were improved.
  • No Thumbnail Available
    Item
    Exponential-size neighborhoods for the pickup-and-delivery traveling salesman problem.
    (2022) Pacheco, Toni Tiago da Silva; Pinto, Rafael Martinelli; Subramanian, Anand; Toffolo, Túlio Ângelo Machado; Vidal, Thibaut Victor Gaston
    Neighborhood search is a cornerstone of state-of-the-art traveling salesman and vehicle routing metaheuristics. While neighborhood exploration procedures are well developed for problems with individual services, their counterparts for one-to-one pickup-and-delivery problems have been more scarcely studied. A direct extension of classic neighborhoods is often inefficient or complex due to the necessity of jointly considering service pairs. To circumvent these issues, we introduce major improvements to existing neighborhood searches for the pickup-and-delivery traveling salesman problem and new large neighborhoods. We show that the classical Relocate-Pair neighborhood can be fully explored in O(n 2 ) instead of O(n 3 ) time. We adapt the 4-Opt and Balas-Simonetti neighborhoods to consider precedence constraints. Moreover, we introduce an exponential-size neighborhood called 2k-Opt, which includes all solutions generated by multiple nested 2-Opts and can be searched in O(n 2 ) time using dynamic programming. We conduct extensive computational experiments, highlighting the significant contribution of these new neighborhoods and speedup strategies within two classical metaheuristics. Notably, our approach permits to repeatedly solve small pickup-and-delivery problem instances to optimality or near-optimality within milliseconds, and therefore it represents a valuable tool for time-critical applications such as meal delivery or mobility on demand.
  • No Thumbnail Available
    Item
    A hybrid algorithm for the heterogeneous fleet vehicle routing problem.
    (2012) Subramanian, Anand; Penna, Puca Huachi Vaz; Barboza, Eduardo Uchoa; Ochi, Luiz Satoru
    This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP generalizes the classical Capacitated Vehicle Routing Problem by considering the existence of different vehicle types, with distinct capacities and costs. The objective is to determine the best fleet composition as well as the set of routes that minimize the total costs. The proposed hybrid algorithm is composed by an Iterated Local Search (ILS) based heuristic and a Set Partitioning (SP) formulation. The SP model is solved by means of a Mixed Integer Programming solver that interactively calls the ILS heuristic during its execution. The developed algorithm was tested in benchmark instances with up to 360 customers. The results obtained are quite competitive with those found in the literature and new improved solutions are reported.
  • No Thumbnail Available
    Item
    A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet.
    (2019) Penna, Puca Huachi Vaz; Subramanian, Anand; Ochi, Luiz Satoru; Vidal, Thibaut Victor Gaston; Prins, Christian
    We consider a family of rich vehicle routing problems (RVRP) which have the particularity to combine a heterogeneous fleet with other attributes, such as backhauls, multiple depots, split deliveries, site dependency, open routes, duration limits, and time windows. To efficiently solve these problems, we propose a hybrid metaheuristic which combines an iterated local search with variable neighborhood descent, for solution improvement, and a set partitioning formulation, to exploit the memory of the past search. Moreover, we investigate a class of combined neighborhoods which jointly modify the sequences of visits and perform either heuristic or optimal reassignments of vehicles to routes. To the best of our knowledge, this is the first unified approach for a large class of heterogeneous fleet RVRPs, capable of solving more than 12 problem variants. The efficiency of the algorithm is evaluated on 643 well-known benchmark instances, and 71.70% of the best known solutions are either retrieved or improved. Moreover, the proposed metaheuristic, which can be considered as a matheuristic, produces high quality solutions with low standard deviation in comparison with previous methods. Finally, we observe that the use of combined neighborhoods does not lead to significant quality gains. Contrary to intuition, the computational effort seems better spent on more intensive route optimization rather than on more intelligent and frequent fleet re-assignments.
  • No Thumbnail Available
    Item
    Otimização de processos produtivos em sistemas de manufatura flexível.
    (2023) Soares, Leonardo Cabral da Rocha; Carvalho, Marco Antonio Moreira de; Carvalho, Marco Antonio Moreira de; Subramanian, Anand; Chaves, Antônio Augusto; Souza, Marcone Jamilson Freitas; Toffolo, Túlio Ângelo Machado
    A complexidade geral do gerenciamento de produção de um sistema de manufatura flexível tem inspirado pesquisadores ao estudo de diversos problemas computacionais advindos de tais sistemas desde a década de 1980. Estudos recentes demonstram que o número de publicações em temas correlatos cresce constantemente desde o ano de 1988, reforçando a relevância e a atualidade do tema. Diante disto, neste trabalho são abordados alguns dos principais problemas advindos deste cenário. Todos os problemas abordados possuem publicações recentes em prestigiados veículos internacionais. Para cada problema abordado apresenta-se definição formal, revisão bibliográfica, método computacional para solução e análise comparativa dos resultados obtidos em relação ao atual estado da arte. Entre os métodos computacionais propostos há predominância da meta-heurística busca local iterada e do algoritmo genético de chaves aleatórias viciadas, entretanto, cada implementação foi cuidadosamente elaborada considerando-se as características individuais dos problemas abordados. Em síntese, inicialmente apresenta-se dois problemas fundamentais relacionados ao escalonamento de tarefas em máquinas flexíveis, o problema de minimização de trocas de ferramentas e o problema do escalonamento de tarefas em máquinas paralelas idênticas com restrições de ferramentas, visando fornecer um referencial teórico para embasar e direcionar o estudo dos demais problemas. Em seguida, são abordados o problema de minimização de blocos de uns consecutivos, o problema de minimização de trocas de ferramentas uniforme, o problema de sequenciamento de tarefas em máquinas paralelas com limitação de recursos e o problema de sequenciamento de tarefas em máquinas paralelas não-idênticas com restrições de ferramentas. Para cada problema abordado realizou-se uma ampla campanha experimental, analisando-se as instâncias disponíveis na literatura e os resultados gerados pelos métodos propostos e pelos métodos que compõem o estado da arte. Análises estatísticas foram realizadas e confirmaram a alta qualidade das soluções reportadas pelos métodos propostos.
  • No Thumbnail Available
    Item
    Problema de roteamento de veículos assimétrico com frota heterogênea limitada : um estudo de caso em uma indústria de bebidas.
    (2016) Kramer, Raphael Harry Frederico Ribeiro; Subramanian, Anand; Penna, Puca Huachi Vaz
    Este artigo aborda um estudo de caso em uma indústria de bebidas relativo ao Problema de Roteamento de Veículos Assimétrico com Frota Heterogênea Limitada (PRVAFHL). O objetivo é definir as rotas dos veículos de modo a reduzir os custos de distribuição. O PRVAFHL pertence à classe NP-difícil, isto é, sua resolução por meio de métodos exatos é uma tarefa extremamente árdua. Problemas desta natureza são geralmente tratados na prática de forma heurística. Dentre as diversas abordagens existentes, optou-se por realizar uma adaptação de uma heurística da literatura que se mostrou eficiente, sendo capaz de gerar soluções de qualidade elevada em um tempo de execução aceitável. Experimentos computacionais foram realizados em um conjunto de 7 instâncias obtidas junto à empresa em questão. Os resultados obtidos mostram que houve uma redução considerável no número de veículos utilizados e na distância total percorrida em relação às soluções adotadas pela empresa.
  • No Thumbnail Available
    Item
    Scheduling the Brazilian OR conference.
    (2022) Correia, Rubens; Subramanian, Anand; Bulhões, Teobaldo; Penna, Puca Huachi Vaz
    In this paper, we propose an efficient matheuristic approach for solving the problem of scheduling the Brazilian OR conference. The event has traditionally around 300 presentations across a period of 3 to 4 days, and building a schedule for the technical sessions is an ardu- ous task. The developed algorithm integrates the concepts of iterated local search and simulated annealing with two mathematical programming-based procedures. The idea is to group the presentations via a clustering procedure, and handle the side constraints in a subproblem via an integer programming formulation. A set partitioning procedure is applied at the end of the algorithm to find the optimal combination of clusters found during the search. We first assess the performance of the method by comparing our results with those attained by other algorithms from the literature on two existing sets of artificial instances derived from two other conferences. Next, we executed our approach on real-life instances derived from different SBPO editions, and compared the solutions with the manual solutions, when available, or with upper bounds (we solve a maximisation problem) found by an exact algorithm from the literature. The results obtained show that the matheuristic is capable of achieving high quality solutions both on the artificial and real-life instances.