Home healthcare has been a growing sector of the economy over the last three decades with roughly 23,000 companies now doing business in the U.S. producing over $56 billion in combined annual revenue. As a highly fragmented market, profitability of individual companies depends on effective management and efficient operations. This dissertation aims at reducing costs and improving productivity for home healthcare companies. The first part of the research involves the development of a new formulation for the therapist routing and scheduling problem as a mixed integer program. Given the time horizon, a set of therapists and a group of geographically dispersed patients, the objective of the model is to minimize the total cost of providing service by assigning patients to therapists while satisfying a host of constraints concerning time windows, labor regulations and contractual agreements. This problem is NP-hard and proved to be beyond the capability of commercial solvers like CPLEX. To obtain good solutions quickly, three approaches have been developed that include two heuristics and a decomposition algorithm. The first approach is a parallel GRASP that assigns patients to multiple routes in a series of rounds. During the first round, the procedure optimizes the patient distribution among the available therapists, thus trying to reach a local optimum with respect to the combined cost of the routes. Computational results show that the parallel GRASP can reduce costs by 14.54% on average for real datasets, and works efficiently on randomly generated datasets. The second approach is a sequential GRASP that constructs one route at a time. When building a route, the procedure tracks the amount of time used by the therapists each day, giving it tight control over the treatment time distribution within a route. Computational results show that the sequential GRASP provides a cost savings of 18.09% on average for the same real datasets, but gets much better solutions with significantly less CPU for the same randomly generated datasets. The third approach is a branch and price algorithm, which is designed to find exact optima within an acceptable amount of time. By decomposing the full problem by therapist, we obtain a series of constrained shortest path problems, which, by comparison are relatively easy to solve. Computational results show that, this approach is not efficient here because: 1) convergence of Dantzig-Wolfe decomposition is not fast enough; and 2) subproblem is strongly NP-hard and cannot be solved efficiently. The last part of this research studies a simpler case in which all patients have fixed appointment times. The model takes the form of a large-scale mixed-integer program, and has different computational complexity when different features are considered. With the piece-wise linear cost structure, the problem is strongly NP-hard and not solvable with CPLEX for instances of realistic size. Subsequently, a rolling horizon algorithm, two relaxed mixed-integer models and a branch-and-price algorithm were developed. Computational results show that, both the rolling horizon algorithm and two relaxed mixed-integer models can solve the problem efficiently; the branch-and-price algorithm, however, is not practical again because the convergence of Dantzig-Wolfe decomposition is slow even when stabilization techniques are applied. / text

Šiame darbe nagrinėjamas patobulintas tabu paieškos metodas, žinomas kaip iteratyvioji tabu paieška (ITP). Pasiūlytos kai kurios ITP metodo modifikacijos, besiremiančios tam tikromis sprendinių mutavimo (pertvarkymo) procedūromis (inversijos, įterpimai ir kt.), kurios įgalina pagerinti gaunamų sprendinių kokybę. Atlikti išsamūs sudaryto ITP algoritmo ir kitų pasiūlytų modifikacijų eksperimentiniai tyrimai, panaudojant testinius KU pavyzdžius iš KU testinių pavyzdžių bibliotekos TSPLIB. Gauti rezultatai patvirtina pasiūlytų modifikacijų pranašumą kitų ITP variantų atžvilgiu. / In this work, one of the heuristic algorithm – the iterated tabu search and its modifications are discussed. The work is organized as follows. Firstly, some basic definitions and preliminaries are given. Then, the iterated tabu search algoritm and its variants based on special type mutations are considered in more details. The ITS algorithms modifications were tested on the TSP instances from the TSP library TSPLIB. The results of this tests (experiments) are presented as well. The work is completed with the conclusions.

In the dissertation the nurse rostering problem is investigated. The formulation of the problem is based on real-world data of one of the largest healthcare centers in Lithuania. Most recent publications that tackle the nurse rostering problem and the methods for solving the nurse rostering problem are reviewed, the mathematical formulation of the single objective and the multi-objective nurse rostering problem is presented, the requirements for the roster are described and a new method for solving the single objective and the multi-objective nurse rostering problem is proposed in this dissertation. / Disertacijoje nagrinėjamas sveikatos priežiūros įstaigos darbuotojų darbų grafikų optimizavimo uždavinys, kuris formuluojamas ir sprendžiamas, remiantis vienos didžiausių Lietuvos sveikatos priežiūros įstaigų, realiais duomenimis. Disertacijoje apžvelgiami darbų grafikų optimizavimo uždaviniai bei jų sprendimo metodai. Pateikiama nagrinėjamo darbų grafikų vienakriterio ir daugiakriterio optimizavimo uždavinių matematinės formuluotės. Aprašomos sąlygos, kurias turi tenkinti sudaromasis darbų grafikas. Nagrinėjami metodai, tiek vienakriteriams, tiek daugiakriteriams darbų grafikų optimizavimo uždaviniams spręsti. Pasiūlytas naujas metodas, kuris yra efektyvesnis nei kiti nagrinėti metodai sprendžiant disertacijoje suformuluotą uždavinį.

This thesis deals with the description of the state of resource-constrained project scheduling problem. It defines the formal problem and its complexity. It also describes variants of this problem. Algorithms for solving RCPSP are presented. Heuristic genetic algorithm GARTH is analyzed in depth. The implementation of prototypes solving RCPSP using GARTH is outlined. Several improvements to the original algorithm are designed and evaluated.

Agent-based models are computer models made up of agents that can exist in a finite number of states. The state of the system at any given time is determined by rules governing agents' interaction. The rules may be deterministic or stochastic. Optimization is the process of finding a solution that optimizes some value that is determined by simulating the model. Optimal control of an agent-based model is the process of determining a sequence of control inputs to the model that steer the system to a desired state in the most efficient way. In large and complex models, the number of possible control inputs is too large to be enumerated by computers; hence methods must be developed for use with these models in order to find solutions without searching the entire solution space. Heuristic algorithms have been applied to such models with some success. Such algorithms are discussed; case studies of examples from biology are presented. The lack of a standard format for agent-based models is a major issue facing the study of agent-based models; presentation as polynomial dynamical systems is presented as a viable option. Algorithms are adapted and presented for use in this framework. / Master of Science

Neste trabalho é proposta uma nova técnica de solução para resolver o problema de planejamento da expansão de sistemas de transmissão estático através da introdução da tomada de decisão fuzzy. Na técnica apresentada neste trabalho, a tomada de decisão fuzzy é aplicada para o desenvolvimento de um algoritmo heurístico construtivo. O sistema fuzzy é utilizado para contornar alguns problemas críticos das heurísticas que utilizam o índice de sensibilidade como guia para inserção de novas linhas. A heurística apresentada nesse trabalho é baseada na técnica dividir para conquistar. Verificou-se que a deficiência das heurísticas construtivas é decorrente da decisão de inserir novas linhas baseada em valores não seguros encontrados através da solução do modelo utilizado. Para contornar tal deficiência, sempre que surgirem valores não seguros divide-se o problema original em dois subproblemas, um que analisa a qualidade da resposta para o caso em que a linha é inserida e outro para verificar a qualidade da resposta para o caso em que a linha não é inserida. A tomada de decisão fuzzy é utilizada para decidir sobre quando dividir o problema em dois novos subproblemas. Utilizou-se o modelo cc com a estratégia de Villasana-Garver-Salon para realizar a modelagem da rede elétrica para os problemas da expansão de sistemas de transmissão aqui propostos. Ao serem realizados testes em sistemas de pequeno, médio e grande portes certificou-se que o método pode encontrar a solução ótima de sistemas de pequeno e médio portes. Porém, a solução ótima dos sistemas de grande porte testados não foi encontrada. Para melhorar a qualidade da solução encontrada utilizou, em uma segunda fase, a metaheurística busca tabu. A busca tabu utiliza o modelo cc. Os resultados se mostraram bastante promissores. Os testes foram realizados em alguns sistemas reais brasileiros e com o sistema real colombiano. / A new solution technique to solve the long-term static transmission expansion planning (TEP) problem based on fuzzy decision making is proposed. The technique applies the concepts of fuzzy decision making in a constructive heuristic algorithm. The fuzzy system is used to circumvent some critical problems of heuristics that use sentivity indices as a guide for insertion and construction of new lines. The heuristic algorithm proposed in this work is based on the divide and conquer technique. It has been verified that the deficiency of the constructive heuristics is due to the decision of inserting new lines based only on information given by the index, which usually is calculated from a relaxed mathematical representation of the problem and can become less accurate during the solution process. In order to be able to deal with such problem, whenever the quality of the index decreases, the original problem is divided into two sub-problems: one examines the quality of the solution when the transmission line indicated by the sensitivity index is inserted and the other subproblem checks the opposite. Fuzzy decision-making is used to decide the moment to divide the problem into two subproblems based on other information. The hybrid linear model is used to model the long-term transmission expansion planning problem and is used in the proposed algorithm. Tests was done with systems of small-term, medium-term and long-term. The optimal solution of small-term and medium-term was foundo using just the construtive heuristic algorithm with fuzzy decision-making. To deal with long-term systems was used the solutions of the construtive heuristic algorithm with fuzzy decision-making to init a tabu search. The tabu search uses the dc model. The results are very promising. The test was done with some real brazilian systems and with the real colombian system.

Submitted by Luanna Matias (lua_matias@yahoo.com.br) on 2015-02-06T19:23:12Z No. of bitstreams: 2 Dissertação - Marcos Antônio Almeida de Oliveira - 2014..pdf: 1092566 bytes, checksum: 55edbdaf5b3ac84fe3f6835682fe2a13 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-02-19T14:34:20Z (GMT) No. of bitstreams: 2 Dissertação - Marcos Antônio Almeida de Oliveira - 2014..pdf: 1092566 bytes, checksum: 55edbdaf5b3ac84fe3f6835682fe2a13 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-02-19T14:34:20Z (GMT). No. of bitstreams: 2 Dissertação - Marcos Antônio Almeida de Oliveira - 2014..pdf: 1092566 bytes, checksum: 55edbdaf5b3ac84fe3f6835682fe2a13 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-09-03 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / A variation of the Beasley (1992) algorithm for the Euclidean Steiner tree problem is presented. This variation uses the Node-Depth-Degree Encoding, which requires an average time of O(n) in operations to generate and manipulate spanning forests. For spanning tree problems, this representation has linear time complexity when applied to network design problems with evolutionary algorithms. Computational results are given for test cases involving instances up to 500 vertices. These results demonstrate the use of the Node-Depth-Degree in an exact heuristic, and this suggests the possibility of using this representation in other techniques besides evolutionary algorithms. An empirical comparative and complexity analysis between the proposed algorithm and a conventional representation indicates the efficiency advantages of the solution found. / É apresentada uma variação do algoritmo de Beasley (1992) para o Problema árvore de Steiner Euclidiano. Essa variação utiliza a Representação Nó-Profundidade-Grau que requer, em média, tempo O(n) em operações para gerar e manipular florestas geradoras. Para problemas de árvore geradora essa representação possui complexidade de tempo linear sendo aplicada em problemas de projeto de redes com algoritmos evolutivos. Resultados computacionais são dados para casos de teste envolvendo instâncias de até 500 vértices. Esses resultados demonstram a utilização da representação Nó-Profundidade-Grau em uma heurística exata, e isso sugere a possibilidade de utilização dessa representação em outras técnicas além de algoritmos evolutivos. Um comparativo empírico e da análise de complexidade entre o algoritmo proposto e uma representação convencional indica vantagens na eficiência da solução encontrada.

Neste trabalho é proposta uma nova técnica de solução para resolver o problema de planejamento da expansão de sistemas de transmissão estático através da introdução da tomada de decisão fuzzy. Na técnica apresentada neste trabalho, a tomada de decisão fuzzy é aplicada para o desenvolvimento de um algoritmo heurístico construtivo. O sistema fuzzy é utilizado para contornar alguns problemas críticos das heurísticas que utilizam o índice de sensibilidade como guia para inserção de novas linhas. A heurística apresentada nesse trabalho é baseada na técnica dividir para conquistar. Verificou-se que a deficiência das heurísticas construtivas é decorrente da decisão de inserir novas linhas baseada em valores não seguros encontrados através da solução do modelo utilizado. Para contornar tal deficiência, sempre que surgirem valores não seguros divide-se o problema original em dois subproblemas, um que analisa a qualidade da resposta para o caso em que a linha é inserida e outro para verificar a qualidade da resposta para o caso em que a linha não é inserida. A tomada de decisão fuzzy é utilizada para decidir sobre quando dividir o problema em dois novos subproblemas. Utilizou-se o modelo cc com a estratégia de Villasana-Garver-Salon para realizar a modelagem da rede elétrica para os problemas da expansão de sistemas de transmissão aqui propostos. Ao serem realizados testes em sistemas de pequeno, médio e grande portes certificou-se que o método pode encontrar a solução ótima de sistemas de pequeno e médio portes. Porém, a solução ótima dos sistemas de grande porte testados não foi encontrada. Para melhorar a qualidade da solução encontrada utilizou, em uma segunda fase, a metaheurística busca tabu. A busca tabu utiliza o modelo cc. Os resultados se mostraram bastante promissores. Os testes foram realizados em alguns sistemas reais brasileiros e com o sistema real colombiano. / A new solution technique to solve the long-term static transmission expansion planning (TEP) problem based on fuzzy decision making is proposed. The technique applies the concepts of fuzzy decision making in a constructive heuristic algorithm. The fuzzy system is used to circumvent some critical problems of heuristics that use sentivity indices as a guide for insertion and construction of new lines. The heuristic algorithm proposed in this work is based on the divide and conquer technique. It has been verified that the deficiency of the constructive heuristics is due to the decision of inserting new lines based only on information given by the index, which usually is calculated from a relaxed mathematical representation of the problem and can become less accurate during the solution process. In order to be able to deal with such problem, whenever the quality of the index decreases, the original problem is divided into two sub-problems: one examines the quality of the solution when the transmission line indicated by the sensitivity index is inserted and the other subproblem checks the opposite. Fuzzy decision-making is used to decide the moment to divide the problem into two subproblems based on other information. The hybrid linear model is used to model the long-term transmission expansion planning problem and is used in the proposed algorithm. Tests was done with systems of small-term, medium-term and long-term. The optimal solution of small-term and medium-term was foundo using just the construtive heuristic algorithm with fuzzy decision-making. To deal with long-term systems was used the solutions of the construtive heuristic algorithm with fuzzy decision-making to init a tabu search. The tabu search uses the dc model. The results are very promising. The test was done with some real brazilian systems and with the real colombian system.

Les soins de santé à domicile (HHC) sont un large éventail de services de santé pouvant être dispensés à domicile pour une maladie ou une blessure. Ces dernières années, le secteur des soins de santé est devenu l'un des plus grands secteurs de l'économie des pays développés. L'un des défis les plus importants dans le domaine des HHC consiste à affecter plus efficacement les ressources en main-d'œuvre et les équipements sous des ressources limitées. Étant donné que le coût du transport est l’une des dépenses les plus critiques dans les activités de l’entreprise, il est très important d’optimiser le problème de routage des véhicules pour les sociétés HHC.Cependant, la majorité des travaux existants ne prennent en compte que le modèle déterministe. Dans la pratique de HHC, le décideur et les aidants rencontrent souvent des incertitudes. Il est donc essentiel d'intégrer l'incertitude dans le modèle pour établir un calendrier raisonnable pour la société HHC. Cette thèse aborde le problème du routage et de la planification HHC en prenant en compte respectivement la demande non déterministe, le service et le temps de parcours. Le corps principal de la thèse est composé de trois œuvres indépendantes.(1) Sur la base de la théorie de la crédibilité floue, nous avons proposé un modèle de programmation par contraintes de hasard flou (FCCP) pour le problème de routage HHC avec une demande floue. Ce modèle présente à la fois des caractéristiques d'optimisation combinatoire et de FCCP. Pour faire face au problème à grande échelle, nous avons développé un algorithme génétique hybride avec la simulation de Monte Carlo. Trois séries d'expériences ont été menées pour valider les performances du modèle et de l'algorithme proposés. Enfin, l’analyse de sensibilité a également porté sur l’observation du paramètre variable impliqué dans la prise de décision floue.(2) En fonction de l'activité des soignants de HHC, nous avons proposé un modèle de programmation stochastique en deux étapes avec recours (SPR) pour la livraison et la reprise simultanées avec des temps de trajet et de service stochastiques dans HHC. Pour résoudre le modèle, nous avons d’une part réduit le modèle au cas déterministe. Le solveur de Gurobi, le recuit simulé (SA), l’algorithme de chauve-souris, l’algorithme de luciole ont été proposés pour résoudre le modèle déterministe pour 56 instances respectivement. Enfin, le SA a été adopté pour traiter le modèle SPR. Une comparaison entre les solutions obtenues par les deux modèles a également été réalisée pour mettre en évidence la prise en compte des temps de parcours et de service stochastiques.(3) Pour garantir la qualité du service, sur la base d’un budget de la théorie de l’incertitude, nous avons proposé un modèle d’optimisation robuste (RO) pour HHC Routing, prenant en compte les exigences en termes de temps de déplacement et de service. La vérification de la solution réalisable a été réécrite en tant que fonction récursive complexe. Recherche tabou, SA, Recherche de voisinage variable sont également adaptés pour résoudre le modèle. Un grand nombre d'expériences ont été réalisées pour évaluer le modèle déterministe et le modèle RO. Une analyse de sensibilité des paramètres a également été effectuée. / Home health care (HHC) is a wide range of healthcare services that can be given in one's home for an illness or injury. In recent years, the healthcare industry has become one of the largest sectors of the economy in developed countries. One of the most significant challenges in HHC domain is to assign the labor resources and equipment more efficiently under limited resources. Since the transportation cost is one of the most critical spendings in the company activities, it is of great significance to optimize the vehicle routing problem for HHC companies.However, a majority of the existing work only considers the deterministic model. In the practical of HHC, the decision-makers and caregivers often encounter with uncertainties. So, it is essential to incorporate the uncertainty into the model to make a reasonable and robust schedule for HHC company. This thesis addresses the HHC routing and scheduling problem with taking into account the non-deterministic demand, uncertain service and travel time respectively. The main body the thesis is composed of three independent works.(1) Based on the Fuzzy Credibility Theory, we proposed a fuzzy chance constraint programming (FCCP) model for HHC routing problem with fuzzy demand. This model has both characteristics of combinatorial optimization and FCCP. To deal with the large-scale problem, we developed a Hybrid Genetic Algorithm with the Monte Carlo simulation. Three series of experiments were conducted to validate the performance of the proposed model and algorithm. At last the sensitivity analysis was also carried out the observe the variable parameter involved in the fuzzy decision-making.(2) According to the activity of the caregivers in HHC, we proposed a two-stage stochastic programming model with recourse (SPR) for the simultaneous delivery and pick-up with stochastic travel and service times in HHC. To solve the model, firstly, we reduced the model to the deterministic one. Gurobi Solver, Simulated Annealing (SA), Bat Algorithm (BA), Firefly Algorithm (FA) were proposed to solve the deterministic model for 56 instances respectively. At last the SA was adopted to address the SPR model. Comparison between the solutions obtained by the two models was also conducted to highlight the consideration of the stochastic travel and service times.(3) To guarantee the service quality, based on a budget of uncertainty theory, we proposed a Robust Optimization (RO) model for HHC Routing with considering skill requirements under travel and service times uncertainty. The feasible solution check was rewritten as a complex recursive function. Tabu Search, SA, Variable Neighborhood Search are adapted to solve the model. A large number of experiments had been performed to evaluate the deterministic model and the RO model.

Many companies have traveling salesmen that market and sell their products.This results in much traveling by car due to the daily customer visits. Thiscauses costs for the company, in form of travel expenses compensation, and environmentaleffects, in form of carbon dioxide pollution. As many companies arecertified according to environmental management systems, such as ISO 14001,the environmental work becomes more and more important as the environmentalconsciousness increases every day for companies, authorities and public.The main task of this thesis is to compute reasonable limits on the mileage ofthe salesmen; these limits are based on specific conditions for each salesman’sdistrict. The objective is to implement a heuristic algorithm that optimizes thecustomer tours for an arbitrary chosen month, which will represent a “standard”month. The output of the algorithm, the computed distances, will constitute amileage limit for the salesman.The algorithm consists of a constructive heuristic that builds an initial solution,which is modified if infeasible. This solution is then improved by a local searchalgorithm preceding a genetic algorithm, which task is to improve the toursseparately.This method for computing mileage limits for traveling salesmen generates goodsolutions in form of realistic tours. The mileage limits could be improved if theinput data were more accurate and adjusted to each district, but the suggestedmethod does what it is supposed to do.