La fabrication du pare-brise automobile est réalisée par un procédé de thermoformage dans un four tunnel où des feuilles de verre subissent un chauffage différentiel par rayonnement par des centaines d'éléments chauffants électriques contrôlés individuellement. Ces travaux ont pour objectif final de répondre à une problématique industrielle formulée en tant que problème d'optimisation. Elle consiste à aider le conducteur du four à retrouver la cartographie de puissance qui permet d'obtenir le champ de température nécessaire à la surface du verre afin d'aboutir à une forme souhaitée. Pour y parvenir, un modèle du four basé sur la méthode de réseau de composants est utilisé afin de simuler le cycle de chauffage. Dans un premier temps, la précision de la température calculée est améliorée par identification paramétrique en se référant à des données de mesures effectuées in situ. Une étude de sensibilité locale et globale a été réalisée au préalable. Par la suite, dans le but d'accélérer ces calculs, une méthode d'optimisation originale est proposée. Elle consiste à combiner la méthode métaheuristique du Recuit Simulé et l'Algorithme de Re-revêtement pour identifier l'émissivité multi-bande des matériaux. Après avoir effectué une validation sur un modèle simplifié 3D de four radiatif de traitement de matériaux, la méthode originale est appliquée pour le modèle du four réel. Outre l'amélioration de la précision des résultats de la simulation, la nouvelle démarche réduit considérablement le temps de calcul. Dans la deuxième partie du travail, plusieurs méthodes métaheuristiques, telles que l'Algorithme Génétique, le Recuit Simulé, la Recherche Tabou ainsi que leur hybridation sont expérimentées pour un modèle simplifié d'une enceinte radiative. Les résultats montrent que la combinaison de l'Algorithme Génétique et du Recuit Simulé a permis d'accélérer la convergence pour atteindre les champs de températures souhaités sur la surface du produit. Cette méthode est par la suite appliquée avec succès pour inverser le modèle du four afin de retrouver les paramètres de commande du four. / The manufacturing of automobile windshield is produced by a thermoforming process in a tunnel furnace where glass undergoes differential heating radiation by hundreds of electrical heating elements individually controlled. The final purpose of this work is to answer a real industrial problem, which is formulated as an optimization problem. It aims at assisting the furnace driver to find the setting that allows obtaining the required temperature distribution on the glass design in order to achieve the desired shape. Based on the method of network components, a model of the furnace is used to simulate the heating cycle. As a first step of this work, the accuracy of the temperature calculated is improved by parametric identification by referring to the data of measurements taken in situ. A local and global sensitivity analysis was performed beforehand. Thereafter, in order to accelerate these calculations, an original and optimization method is proposed. It consists in combining the Simulated Annealing metaheuristic method and the Replating Algorithm to identify multi-band emissivity. First, the original method validation is performed on a simplified 3D model of radiative enclosure, and then applied to the real furnace model. The new approach significantly reduces the computation time while improving the accuracy of the simulation results. In the second part of this work, several metaheuristic methods, such as Genetic Algorithm, Simulated Annealing, Tabu Search, and their hybridization are tested on a simplified model of a radiative enclosure. Results show that the combination of Genetic Algorithm and Simulated Annealing has accelerated the convergence to achieve the desired temperature fields on the product surface. This new method is successfully applied to the real furnace model to find the optimal control parameters.

Les développements continus en micro-spectroscopie vibrationnelle IR et en analyse numérique de données multidimensionnelles ont permis récemment l'émergence de l'histologie spectrale. A l'échelle tissulaire et sur une base biomoléculaire, cette nouvelle approche représente un outil prometteur pour une meilleure analyse et caractérisation de différents états physiopathologiques, et potentiellement une aide au diagnostic clinique. Dans ce travail, en utilisant un modèle tissulaire de côlon normal chez la Souris et chez l’Homme, nous avons apporté des améliorations à la chaîne de traitements des données afin d'automatiser et d'optimiser cette histologie spectrale.En effet, dans un premier temps, le développement d’une double application hiérarchique d'indices de validité a permis de déterminer le nombre optimal de classes nécessaire à une caractérisation complète des structures histologiques. Dans un second temps, cette méthode a été généralisée à l'échelle interindividuelle par couplage d'un prétraitement par EMSC (Extended Multiplicative Signal Correction) et d'une classification non-supervisée k-Means; ce couplage étant appliqué conjointement à toutes les images spectrales IR. Enfin, compte tenu de l'essor des métaheuristiques et de leur capacité à résoudre des problèmes complexes d'optimisation numérique, nous avons transposé un algorithme mémétique aux données spectrales IR. Ce nouvel algorithme se compose d'un algorithme génétique et d'un raffinement par classification non-supervisée k-Means. Comparé aux méthodes classiques de clustering, cet algorithme mémétique appliqué aux images spectrales IR, a permis de réaliser une classification non-supervisée optimale et indépendante de l'initialisation. / Recent developments in IR vibrational microspectroscopy and numerical multidimensional analysis have led to the emergence of spectral histology. At the tissue level, this new approach represents an attractive tool for a better analysis and characterization of pathophysiological states and for diagnostic challenges. Here, using normal murine and human colon tissues, data processing steps have been improved for automating and optimizing this spectral histology. First, the development of a hierarchical double application of validity indices permitted to determine the optimal number of clusters that correctly identified the different colon histological components. Second, this method has been improved to perform spectral histology at the inter-individual level. For this, EMSC (Extended Multiplicative Signal Correction) preprocessing has been successfully combined to k-Means clustering. Finally, given the ability of metaheuristics to solve complex optimization problems, a memetic algorithm has been developed for IR spectral data clustering. This algorithm is composed of a genetic algorithm and a k-Means clustering refinement. Compared with conventional clustering methods, our memetic algorithm allowed to generate an optimal and initialization-independent clustering.

[pt] Esta dissertação estuda modelos e algoritmos para o Problema de Alocação Generalizada (PAG) . A motivação para este estudo foi uma nova aplicação do PAG: o Problema de Carregamento de Caminhões (PCC) . A pesquisa desenvolvida concentra-se no estudo e na proposta de algoritmos aproximados (metaeurísticas) e exatos para a resolução do PAG. Os algoritmos aproximados propostos baseiam-se em um conceito recentemente criado por Fischetti e Lodi (2003), que utiliza programação matemática inteira para a exploração eficiente de vizinhanças mais abrangentes. Os resultados obtidos foram comparáveis aos melhores conhecidos, com a vantagem de exigir um esforço pequeno de implementação e um menor tempo de processamento. O algoritmo exato proposto é um algoritmo de branch-and-cut- and-price, que tem como ponto de partida o algoritmo de branch-and-price de Savelsbergh (1997). Técnicas de estabilização da geração de colunas similares às propostas por Du Merle, Villeneuve, Desrosiers e Hansen (1999), foram estudadas no âmbito desta dissertação, que experimenta com diferentes implementações deste mecanismo. O algoritmo de branch-andcut-and-price estabilizado demonstrou sua eficiência ao resolver à otimalidade instâncias que se encontravam em aberto na literatura. Finalmente, experiências com PCC permitiram que os códigos desenvolvidos pudessem ser avaliados em problemas reais. / [en] This dissertation tackles the Generalized Assignment Problem (PAG), models and algorithms are studied and proposed. This work was motivated by a real world application: the Truck Loading Problem (PCC). Research was done on approximated (metaheuristics) and exact algorithm for solving the PAG. The approximated algorithms proposed were based on a recent idea from Fischetti and Lodi (2003). It uses integer programming to explore wider neighborhoods. The results were compared to the best known, while demanding much less implementation effort and using less cpu time. The exact algorithm proposed is a branch-and-cut- and-price developed from the branch-and-price algorithm of Savelsbergh (1997). We used stabilized column generation techniques similar to the one by Du Merle, Villeneuve, Desrosiers and Hansen (1999), and devised experiments with different implementations of this mechanism. The resulting algorithm proved its efficiency by solving to optimality open instances from the literature. Finally, experiments with the PCC turned possible the evaluation of the codes developed on real problems.

Nous nous intéressons dans cette thèse aux possibilités d’hybridation entre les méthodes exactes et les méthodes heuristiques afin de pouvoir tirer avantage de chacune des deux approches : optimalité de la résolution exacte, caractère moins déterministe et rapidité de la composante heuristique. Dans l’objectif de résoudre des problèmes NPdifficiles de taille relativement importante tels que les problèmes de transports, nous nous intéressons dans les deux dernières parties de ce mémoire à la conception de méthodes incomplètes basées sur ces hybridations. Dans la première partie, nous allons nous intéresser aux méthodes de résolution par recherche arborescente. Nous introduisons une nouvelle approche pour la gestion des décisions de branchement, que nous appelons Dynamic Learning Search (DLS). Cette méthode définit de manière dynamique des règles de priorité pour la sélection des variables à chaque noeud et l’ordre des valeurs sur lesquelles brancher. Ces règles sont conçues dans une optique de généricité, de manière à pouvoir utiliser la méthode indépendamment du problème traité. Le principe général est de tenir compte par une technique d’apprentissage de l’impact qu’ont eu les décisions de branchement dans les parties déjà explorées de l’arbre. Nous évaluons l’efficacité de la méthode proposée sur deux problèmes classiques : un problème d’optimisation combinatoire et un problème à satisfaction de contraintes. La deuxième partie de ce mémoire traite des recherches à grand voisinage. Nous présentons un nouvel opérateur de voisinage, qui détermine par un algorithme de programmation dynamique la sous-séquence optimale d’un chemin dans un graphe. Nous montrons que cet opérateur est tout particulièrement destiné à des problèmes de tournées pour lesquels tous les noeuds ne nécessitent pas d’être visités. Nous appelons cette classe de problème les Problèmes de Tournées avec Couverture Partielle et présentons quelques problèmes faisant partie de cette classe. Les chapitres 3 et 4 montrent, à travers des tests expérimentaux conséquents, l’efficacité de l’opérateur que nous proposons en appliquant cette recherche à voisinage large sur deux problèmes, respectivement le Problème de l’Acheteur Itinérant (TPP) et le Problème de Voyageur de Commerce Généralisé (GTSP). Nous montrons alors que cet opérateur peut être combiné de manière efficace avec des métaheuristiques classiques, telles que des algorithmes génétiques ou des algorithmes d’Optimisation par Colonies de Fourmis. Enfin, la troisième partie présente des méthodes heuristiques basées sur un algorithme de Génération de Colonnes. Ces méthodes sont appliquées sur un problème complexe : le problème de Tournées de Véhicules avec Contraintes de Chargement à Deux Dimensions (2L-VRP). Nous montrons une partie des possibilités qu’il existe afin de modifier une méthode a priori exacte en une méthode heuristique et nous évaluons ces possibilités à l’aide de tests expérimentaux / We are interested in this thesis in the possibilities of hybridization between the exact methods and the methods heuristics to be able to take advantage of each of both approaches: optimality of the exact resolution, the less determinist character and the speed of the constituent heuristics. In the objective to resolve problems NP-hard of relatively important size such as the transportation problems, we are interested in the last two parts of this report in the conception of incomplete methods based on these hybridizations. In the first part, we are going to be interested in the methods of resolution by tree search. We introduce a new approach for the management of the decisions of connection, which we call Dynamic Learning Search ( DLS). This method defines in a dynamic way rules of priority for the selection of variables in every knot and the order of the values on which to connect. These rules are conceived in an optics of genericity, so as to be able to use the method independently of the treated problem. The general principle is to take into account by a technique of learning of the impact which had the decisions of connection in the parts already investigated in the tree. We estimate the efficiency of the method proposed on two classic problems: a combinatorial optimization problem and a constraints satisfaction problem. The second part of this report handles large neighborhood search. We present a new operator of neighborhood, who determines by an algorithm of dynamic programming the optimal sub-sequence of a road in a graph. We show that this operator is quite particularly intended for problems of tours for which all the vertices do not require to be visited. We call this class of problem the Problems of Tours with Partial Cover and present some problems being a part of this class. Chapters 3 and 4 show, through consequent experimental tests, the efficiency of the operator which we propose by applying this search to wide neighborhood on two problems, respectively the Traveling Purchaser Problem (TPP) and Generalized Traveling Salesman Problem ( GTSP). We show while this operator can be combined in a effective way with classic metaheuristics, such as genetic algorithms or algorithms of Ant Colony Optimization

Notre travail porte sur l'étude du Problème de Routage et d'Allocation de Longueur d'Onde (Routing and Wavelength Allocation - RWA) dans des réseaux optiques WDM, indépendamment de la topologie physique sous-jacente. Le problème a été idntifié comme étant NP-difficile et plusieurs approches, tant exactes qu'approchées, existent. Nous fournissons d'abord une revue de littérature dans laquelle nous présentons quelques formulations mathématiques pour le problème ainsi que plusieurs manières d'obtenir des bornes inférieures et des heuristiques. Nous considérons le problème min-RWA dans lequel on doit satisfaire un certain nombre de requêtes avec le moins de longueurs d'onde possible. Nous présentons une méthodologie reposant sur une recherche locale de type Descente à Voisinage Variable (Variable Neighborhood Descent - VND) que l'on appelle VND-BFD. Son objectif principal est de supprimer des longueurs d'onde. Nous présentons également une méthode hybride VND-BT. Ensuite, nous proposons une nouvelle approche, elle-aussi reposant sur la VND. Elle consiste à ré-arranger les requêtes entre les longueurs d'onde disponibles. Lorsqu'elle atteint un optimum local, une procédure de perturbation est appliquée et le schéma est similaire à la Recherche Locale Itérée (Iterated Local Search - ILS). Quatre variantes sont définies selon les stratégies appliquées dans VND et ILS : VNDr-ILSp, VNDe-ILSp, VNDr-ILS5p et VNDe-ILS5p. Les résultats expérimentaux montrent que cette nouvelle approche est plus performante, en particulier la version VNDe-ILS5p. La méthode est compétitive avec les meilleures méthodes de la littérature puisque VNDe-ILS5p a permis d'améliorer une grande partie des meilleures solutions connues sur les instances standard du min-RWA. Enfin, nous considérons aussi le problème max-RWA dans lequel on doit maximiser le nombre de requêtes traitées avec un nombre donné de longueurs d'onde. Nous proposons des modèles compacts ainsi que des améliorations destinées à accélérer la résolution par des solveurs en nombre entiers. Après avoir décrit des modèles existants utilisant la génération de colonnes, nous proposons un nouveau modèle, PG-MAX-IS-IRC, utilisant lui-aussi la génération de colonnes. Il permet d'obtenir des bornes supérieures de même qualité en un temps très fortement réduit. / This work deals with the routing and Wavelength assignment (RWA) in optical WDM networks independently on the underlying physical topology. We begin with a review of the literature presented some mathematical models formulated to solve theproblem, are also reviewed methods for setting lower bounds and heuristic methods. This problem has been shown to be NP-hard and several heuristic algorithms have been developed to solve it. We present in this work a methodology based on metaheuristic Variable Neighborhood Descent (VND), which we call VND-BFD, primarily with the focus on the elimination of wavelengths and a hybrid method VND-BT to solve the problem. Then we introduce a new approach also based on VND, but this time with the focus on the rearrangement of the requests, when this new version of the VND fails the procedure activates a disturbance, as the metaheuristic Iterated Local Search. We define four variants to this method, which we call VNDr-ILSp, VNDe-ILSp, VNDr-ILS5p and VNDe-ILS5p. The computational experiments show that the approach with the focus on requestsproved more efficient, especially the version VNDe-ILS5p. The proposed method is competitive with respect to the best methods in the literature. Finally, we present compact models aimed at maximizing the number of requests accepted and some simplifications are proposed in order to speed up the resolution of problems. Although we present some models of literature based on column generation and a new methodology is proposed. The new methodology, which we call PG-MAX-IS-IRC, was able to solve all instances faster than the method of the literature and always found the same upper bound.

Orientadores: Paulo de Barros Correia, Ieda Geriberto Hidalgo / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecânica / Made available in DSpace on 2018-08-28T12:05:23Z (GMT). No. of bitstreams: 1 Barros_RegianeSilvade_D.pdf: 4190585 bytes, checksum: c320645bbd13fd28d572f5b9751d4ff7 (MD5) Previous issue date: 2015 / Resumo: Este trabalho propõe um modelo de despacho ótimo no horizonte diário de operação, que permite coordenar a operação entre uma usina eólica e uma usina hidrelétrica. Nessa abordagem, a usina eólica é despachada em primeira instância. Para suprir eventuais saídas forçadas que possam ocorrer na geração eólica, aloca-se um valor de reserva girante incremental na usina hidrelétrica usando o conceito de Value at Risk como métrica de risco da geração eólica. O modelo é formulado como um problema multiobjetivo que busca maximizar a geração de energia e minimizar o número de partidas e paradas da usina hidrelétrica. O acoplamento hidráulico é considerado através da meta diária de defluência da usina. O problema é solucionado em duas etapas. A primeira resolve 24 problemas estáticos, que representam o despacho horário da usina hidrelétrica, separadamente. Essa etapa emprega o Algoritmo Genético para otimizar a operação da usina em termos da geração de energia elétrica. A segunda etapa soluciona o problema dinâmico, ou seja, o despacho diário da usina. A natureza do problema dinâmico, correspondendo à obtenção de caminhos mínimos eficientes em termos de partidas e paradas, sugeriu o uso da técnica de Otimização por Colônia de Formigas. As restrições de reserva girante, meta de defluência, atendimento do contrato de demanda e limites operacionais das usinas são plenamente satisfeitas. A diferença entre os montantes de energia produzidos e contratados é liquidada no mercado de curto prazo e valorada ao preço de liquidação das diferenças. O modelo se mostrou adequado em termos de tempo computacional e em relação à qualidade das soluções obtidas / Abstract: This work proposes an optimal dispatch model in the daily horizon, which coordinates the operation of a wind farm and a hydroelectric plant. In this approach the wind farm is dispatched first. In order to provide eventual faults that may occur in the wind farm generation, an incremental spinning reserve is allocated in the hydroelectric plant using the concept of Value at Risk. The model is formulated as a multiobjective problem which seeks to maximize the energy generation and to minimize the number of start-ups and shut-downs of the hydroelectric plant. The plant¿s hydraulic coupling is considered through the daily released flow goal. The model is solved in two stages, the first one solves, separately, 24 static problems that represents the hourly dispatch of the hydroelectric plant. This stage employs Genetic Algorithm to optimize the operation of the hydroelectric plant in terms of electric energy generation. The second stage considers the dynamic problem, which is the plant¿s daily dispatch. The nature of the dynamic problem, which implies in obtaining efficient shortest paths in terms of start-ups and shut-downs, suggests the use of the Ant Colony Optimization. The spinning reserve, the released flow goal, the demand contract and the generating unit¿s operational limits are fully satisfied. The difference between the energy amounts produced and contracted are liquidated in the spot market and it is valuated with the settlement differences price. Regarding computational costs and solutions quality, the model suitability is shown / Doutorado / Planejamento de Sistemas Energeticos / Doutora em Planejamento de Sistemas Energéticos

Submitted by Nadir Basilio (nadirsb@uninove.br) on 2016-07-01T14:58:21Z No. of bitstreams: 1 Marisa Carla Voigt Gava.pdf: 1946904 bytes, checksum: 369bf987709311eddcb1f66a7c5fad55 (MD5) / Made available in DSpace on 2016-07-01T14:58:21Z (GMT). No. of bitstreams: 1 Marisa Carla Voigt Gava.pdf: 1946904 bytes, checksum: 369bf987709311eddcb1f66a7c5fad55 (MD5) Previous issue date: 2016-02-29 / The cutting problem involves cutting larger objects into smaller items with the aim of minimizing waste. The objects can be raw materials, such as rolls of paper, glass sheets, metal plates, steel, aluminum or wood. The items represent the shape to be cut and may be described as concave or convex irregular geometries. The cut of raw material is an industrial process which has attracted the attention of many researchers, since it can generate large waste, increasing the production cost. Nevertheless, the set of possible solutions to this problem has a large number of combinations and, therefore, its computational complexity is considered NP-Hard. In this work, we proposed an approach based on Genetic Algorithm (GA) and Digital Image Processing (DIP) to deal with the problem of to cut rectangular plates (objects) in equal parts (items) with irregular shapes, categorized in the literature as 2D-I-IIPP. The aim is to maximize the number of items to be cut into the available area of the object in order to reduce waste and thus adding economic gains to the cutting process. In this approach the object and the items are represented as digital images. The GA is responsible for generating possible solutions (sets of translations and orientations of items). The evaluation of each solution generated by GA is performed by a RPID algorithm, which basically detects overlaps between the items placed on the object and calculates the quality of solution. To develop the proposed approach it was used the programming language C/C++ in addition to GAlib and Proeikon libraries. Based on computational experiments conducted the results indicate that the proposed approach is a good alternative to solve the problem investigated. / O problema de corte consiste em cortar objetos maiores em itens menores com o objetivo de minimizar as sobras. Os objetos podem ser matérias-primas, tais como bobinas de papel, folhas de vidro, placas de metal, aço, alumínio ou madeira. Os itens representam o formato que deverá ser cortado e podem ser descritos como de geometrias irregulares côncavas ou convexas. O corte de matéria-prima é um processo industrial que tem atraído a atenção de muitos pesquisadores, visto que pode gerar grandes desperdícios, elevando o custo da produção. Não obstante, o conjunto de possíveis soluções para esse tipo de problema possui um grande número de combinações e, por esse motivo, sua complexidade computacional é considerada NP-Hard. Neste trabalho é proposta uma abordagem baseada em Algoritmo Genético (AG) e Processamento de Imagens Digitais para lidar com o problema de cortar placas retangulares (objetos) em peças idênticas (itens) com formas irregulares, categorizado na literatura como 2D-I-IIPP. O objetivo é maximizar o número de itens a serem cortados na área disponível do objeto, visando diminuir os desperdícios e, consequentemente, agregando ganhos econômicos ao processo de corte. Nesta abordagem tanto os objetos como os itens são representados como imagens digitais. O AG é responsável por gerar as possíveis soluções (conjuntos de translações e orientações dos itens). A avaliação de cada solução gerada pelo AG é realizada por um algoritmo de Processamento de Imagens Digitais que basicamente detecta as sobreposições entre os itens posicionados sobre o objeto e calcula a qualidade da solução. Para desenvolver a abordagem proposta foi utilizada a linguagem de programação C/C++, além das bibliotecas GAlib e Proeikon. Os resultados obtidos nos experimentos computacionais realizados indicam que a abordagem proposta é uma boa alternativa para solução do problema investigado.

Ce manuscrit aborde des problèmes d’ordonnancement et de transport avec une modélisation explicite du transport. De tels problèmes se modélisent communément sous forme de graphes qui sont évalués afin d’obtenir les dates de début des opérations.Les évaluations classiques des graphes sont effectuées au moyen d’algorithmes de plus long chemin permettant d’obtenir une solution semi-active, où toutes les dates des opérations sont au plus tôt. Néanmoins, ces évaluations permettent généralement de ne prendre en compte que des critères de temps ou de distance à minimiser. Les travaux présentés dans ce manuscrit proposent de tenir compte de critères de qualité de service dans la fonction objectif. Cette prise en considération nécessite de nouvelles fonctions d’évaluation du graphe afin d’obtenir des solutions non nécessairement semi-actives permettant de maximiser la qualité de service. En effet, une solution semi-active propose rarement une qualité de service optimale. Les critères de qualité de service adoptés portent sur les ordonnancements et sur le transport.Trois problèmes intégrés sont successivement traités. Le premier problème est un problème de Job-shop avec transport et qualité de service, appelé Job-shop Scheduling Problem with Routing (JSPR). Des pièces, définies par une succession d’opérations, sont à fabriquer sur différentes machines, et entre deux opérations, la pièce doit être transportée de machine en machine. Le critère de qualité de service dans ce problème est dépendant des délais entre, d’une part les différentes opérations sur les machines, et d’autre part entre les différentes opérations de transport. Les gammes opératoires et les opérations de transport sont dépendantes les unes des autres.Le second problème est un problème de Workforce Scheduling and Routing Problem (WSRP), assimilable à un problème de planification de visites à domicile par un ensemble d’employés, et où le transport est pris en compte. Pour ce problème, le critère de qualité de service dépend des dates de début des visites. Les tournées sont indépendantes les unes des autres.Le troisième problème est le Generalised Workforce Scheduling and Routing Problem (GWSRP), qui prend en compte des contraintes de coordination entre les employés. Les tournées de ces derniers sont dépendantes les unes des autres. Elles nécessitent d’être toutes considérées simultanément pour évaluer les dates des visites respectant les contraintes de coordination et maximisant la qualité de service.Pour chaque problème, une nouvelle fonction d’évaluation est proposée. Pour le JSPR, cette fonction est basée sur l’algorithme de (Cordeau and Laporte, 2003) qui est initialement prévu pour le Dial-A-Ride Problem, ainsi que sur l’insertion de time-lags dans le graphe disjonctif du JSPR. Cette évaluation est incluse dans une métaheuristique. Pour le WSRP, la fonction d’évaluation est basée sur un algorithme de calcul du plus court chemin avec un algorithme de type programmation dynamique à labels. Elle est généralisée pour être utilisée dans une génération de colonnes. Et enfin, pour le GWSRP, l’évaluation est effectuée par un modèle PPC qui combiné à une génération de colonnes définissent tous deux un schéma d’optimisation global. / This manuscript addresses scheduling and transport problems where the transport is explicitly taken into account. Such problems are commonly modelled by graphs that are evaluated to obtain the starting times of operations.Classic graph evaluations are performed using longer path algorithms to obtain a semi-active solution, where all operations are left shifted. Nevertheless, these evaluations generally allow only time or distance criteria to be taken into account. The work presented in this thesis propose to take the quality of service criteria into account in the objective function. These considerations require new graph evaluation functions in order to obtain non-semi-active solutions that maximise the quality of service. Indeed, a semi-active solution rarely offers maximum quality of service. Three integrated problems are successively addressed. The first problem is a Job-shop Scheduling Problem with transport and quality of service, referred to as Job-shop Scheduling Problem with Routing (JSPR). Jobs, defined by a succession of operations, are to be performed on different machines, and between two operations, the job must be transported from a machine to another machine. The quality of service criterion in this problem depends on the delay between, on the one hand, the different operations belonging to the same job, and on the other hand, between the different transport operations. Machine-operations and transport-operations are dependent.The second problem is a Workforce Scheduling and Routing Problem (WSRP), which is similar to a problem of planning home services by a set of employees, and where transport is taken into account. For this problem, the quality of service criterion depends on the starting times of the visits. The trips of employees are independent.The third problem is the Generalised Workforce Scheduling and Routing Problem (GWSRP), which takes coordination constraints between employees into account. The trips are dependent on each other. The evaluation function of the starting times must consider simultaneously all trips in order to respect all coordination constraints and to maximise the service quality.For each problem, a new evaluation function is proposed. For the JSPR, this function is based on the algorithm of (Cordeau and Laporte, 2003) which is introduced first for the Dial-A-Ride Problem. The evaluation function, for the JSPR, is based on the insertion of time-lags in the disjunctive graph. This evaluation is included in a metaheuristic. For the WSRP, the evaluation function is based on the dynamic labelling algorithm used for an Elementary Shortest Path Problem With Resource Constraints. This function is generalised in order to be included in a column generation scheme. Finally, for the GWSRP, the evaluation is performed by a PPC model combined with a generation of columns and both define an overall optimisation scheme.

This thesis deals with optimization problems with main focus on logistic Vehicle Routing Problem (VRP). In the first part term optimization is established and most important optimization problems are presented. Next section deals with methods, which are capable of solving those problems. Furthermore it is explored how to apply those methods to specific VRP, along with presenting some enhancement of those algorithms. This thesis also introduces learning method capable of using knowledge of previous solutions. At the end of the paper, experiments are performed to tune the parameters of used algorithms and to discuss benefit of suggested improvements.

The public transport system in South Africa is in a precarious state, capturing no more than 50% of the passenger market. The three public transport modes that are currently utilized—train, bus, and minibus-taxi—are competing for market share instead of complementing one another. Furthermore, most public transport networks have not been properly redesigned over the past three decades. Improvements were initiated reactively in the past: transit stops and routes were added or removed from the network when demand fluctuated. This reactive process has diminished the confidence of commuters in the public transport networks, forcing commuters to use private transport. A proactive redesign method is needed—one that includes all the modes of public transport, and anticipates an increase in demand and rapid development in geographic areas, while ensuring good accessibility to the network. Current network design models do not include multiple modes of public transport, and are based on the geographical layout of developed cities and their particularities, which makes them unsuitable for the South African environment with its unique land use disparities. This dissertation proposes a multimodal network design model that is capable of designing real world and large scale networks for the South African metropolitan areas. The City of Tshwane Metropolitan Municipality (CTMM) transport network area was used to develop and test the model, which consists of four components. The Geographic Information System (GIS) component has a central role in storing, manipulating, and exchanging the geographic data within the model. For the GIS the appropriate input data is identified, and a design for the geo-database is proposed. The Population Generation Algorithm (PGA) component translates the demographic data into point data representing the transit demand in the study area. The Bus Stop Placement Algorithm (BSPA) component is a metaheuristic that searches for near-optimal solutions for the placement of bus stops in the study area. A novel solution approach proposed in this dissertation uses geographic data of commuters to evaluate the bus stop placement in the study area. The Multimodal Network Design Algorithm (MNDA) component also employs a metaheuristic, enabling the design of near-optimal multimodal networks. The addition of multiple modes to the Transit Network Design Problem (TNDP) is also a novel and significant contribution. The two metaheuristic components are first tested on a test network, and subjected to a comprehensive sensitivity analysis. After identifying suitable parameter values and algorithm settings, the components are applied to the entire CTMM. / Dissertation (MSc)--University of Pretoria, 2009. / Industrial and Systems Engineering / unrestricted