Le travail de ce mémoire apporte une brique fonctionnelle et théorique dans l'élaboration d'un outil informatique générique pour la planification automatisée et optimisée d'une équipe d'employés polyvalents avec une première application dans le domaine de la grande distribution. En pratique, il fournit la formalisation mathématique d'une problématique métier riche où les règles de planification (début, durée, fin, quantité, etc.) à respecter s’appliquent sur différentes granularité temporelle (quart d’heure, plage horaire, horaire journalier, semaine, mois, année). Différentes techniques issues de la Recherche Opérationnelle ont été adaptées et testées tout d’abord pour une version du problème restreint à une semaine, puis pour la version complète à l’année. Ces méthodes correspondent à des heuristiques basées sur la méthode de génération de colonnes où le problème de pricing est résolu par un algorithme dédié de programmation dynamique imbriquée. Les expérimentations ont été réalisées avec des instances issues de cas réels et des instances générées s’inspirant des cas réels comptant jusqu’à une soixantaine d’employés à planifier sur un horizon de planification allant d’une semaine à un an (divisé par périodes de 15 minutes). Les tests réalisés montrent que les méthodes implémentées permettent l’obtention de plannings d'équipe de grande qualité tout en préservant les caractéristiques individuelles de chaque employé (compétences, disponibilité, temps de travail, etc.), le tout utilisable avec un ordinateur de gamme moyenne (simple cœur, moins 4 GB de RAM) avec des temps de calcul raisonnables (quelques secondes à plusieurs heures selon l’instance et méthode). / The thesis provides a practical and theoretical brick for developing a generic software tool for producing automated and optimized schedules of a multi-skill employees team with a first application in retail. We provide a mathematical formulation of a rich staff scheduling problem in which planning rules (start, duration, end, amount, etc.) that must be respected are applied on different time granularity (15 minutes period, timeslot, day-shift, week, month, year). Two variants of the problem with different planning horizons have been considered: the first one with one week and the second one with one year planning horizon. Several methods from Operations Research have been adapted to solve the problem. We propose heuristics based on the column generation approach where the pricing problem is solved using a dedicated nested dynamic programming algorithm. The experiments were performed both on real-life instances and on random instances derived from real cases. Instances have up to sixty employees and a planning horizon from one week to one year (divided by 15 minutes periods). The tests show that the proposed methods are able to find high-quality team schedules while taking into account the individual characteristics of each employee (skills, availability, working time, etc.) and run with a standard PC (single core, less than 4 GB of RAM) with a reasonable computation time (from several seconds to one hour depending on the instance and the used method).

Universiẗat, Diss., 2005--Karlsruhe.

Pickup and delivery problems (PDPs) have been studied extensively in past decades. A wide variety of research exits on both exact algorithms and heuristics for generic variations of the problem as well as real-life applications, which continue to spark new challenges and open up new opportunities for researchers. In this dissertation, we study two variations of pickup and delivery problem that arise in industry and develop new computational methods that are shown to be effective with respect to existing algorithms and scheduling procedures found in practice. The first problem is the pickup and delivery problem with transshipment (PDPT). The work presented here was inspired by a daily route planning problem at a regional air carrier. In structuring the analysis, we describe a unique way to model the transshipment option on a directed graph. With the graph as the foundation, we implemented a branch and price algorithm. Preliminary results showed that it has difficulty in solving large instances. As an alternative, we developed a greedy randomized adaptive search procedure (GRASP) with several novel features. In the construction phase, shipment requests are inserted into routes until all demand is satisfied or no feasible insertion exists. In the improvement phase, an adaptive large neighborhood search algorithm is used to reconstruct portions of the feasible routes. Specialized removal and insertion heuristics were designed for this purpose. We also developed a procedure for generating problem instances in the absence of any in the literature. Testing was done on existing PDP data sets and generated PDPT data set. For the former, the performance and solution quality of the GRASP were comparable to the best known heuristics. For the latter, GRASP found the near optimal solution in most test cases. In the second part of the dissertation, we focus on a new version of the heterogeneous PDP in which the capacity of each vehicle can be modified by reconfiguring its interior to satisfy different types of customer demands. The work was motivated by a daily route planning problem arising at a senior activity center. A fleet of configurable vans is available each day to transport participants to and from the center as well as to secondary facilities for rehabilitative and medical treatment. To find solutions, we developed a two-phase heuristic that makes use of ideas from greedy randomized adaptive search procedures with multiple starts. In phase I, a set of good feasible solutions is constructed using a series of randomized procedures. A representative subset of those solutions is selected as candidates for improvement by solving a max diversity problem. In phase II, an adaptive large neighborhood search (ALNS) heuristic is used to find local optima by reconstructing portions of the feasible routes. Also, a specialized route feasibility check with vehicle type reassignment is introduced to take full advantage of the heterogeneous nature of vehicles. The effectiveness of the proposed methodology is demonstrated by comparing the solutions it provided for the equivalent of several weeks with those that were used in practice and derived manually. The analysis indicates that anywhere from 30% to 40% savings can be achieved with the multi-start ALNS heuristic. An exact method is introduced based on branch and price and cut for settings with more restricted time windows. In the procedure, the master problem at each node in the search tree is solved by column generation to find a lower bound. To improve the bound, subset-row inequalities are applied to the variables of the master problem. Columns are generated by solving the pricing subproblems with a labeling algorithm enhanced by new dominance conditions. Local search on the columns is used to quickly find promising alternatives. Implementation details and ways to improve the performance of the overall procedure are discussed. Testing was done on a set of real instances as well as a set of randomly generated instances with up to 50 customer requests. The results show that optimal solutions are obtained in majority of cases. / text

Zugl.: Diss.

This thesis describes a stochastic ship routing problem with inventory management. The problem involves finding a set of least costs routes for a fleet of ships transporting a single commodity when the demand for the commodity is uncertain. Storage at consumption and supply ports is limited and inventory levels are monitored in the model. Consumer demands are at a constant rate within each time period in the deterministic problem, and in the stochastic problem, the demand rate for a period is not known until the beginning of that period. The demand situation in each time period can be described by a scenario tree with corresponding probabilities. Several possible solution approaches for solving the problem are studied in the thesis. This problem can be formulated as a mixed integer programming (MIP) model. However solving the problem this way is very time consuming even for a deterministic problem with small problem size. In order to solve the stochastic problem, we develop a decomposition formulation and solve it using a Branch and Price framework. A master problem (set partitioning with extra inventory constraints) is built, and the subproblems, one for each ship, involve solving stochastic dynamic programming problems to generate columns for the master problem. Each column corresponds to one possible tree of schedules for one ship giving the schedule for the ship for all demand scenarios. In each branch-and-bound node, the node problem is solved by iterating between the master problem and the subproblems. Dual variables can be obtained solving the master problem and are used in the subproblems to generate the most promising columns for the master problem. Computational results are given showing that medium sized problems can be solved successfully. Several extensions to the original model are developed, including a variable speed model, a diverting model, and a model which allows ships to do extra tasks in return for a bonus. Possible solution approaches for solving the variable speed and the diverting model are presented and computational results are given.

No description available.

Le problème de routage de véhicules avec fenêtres de temps et routes multiples (MTVRPTW) est une généralisation du problème de routage de véhicules avec fenêtres de temps (VRPTW). Dans le MTVRPTW, on autorise un véhicule à effectuer plusieurs routes durant une période de planification, ce qui permet d'optimiser les transports lorsque le nombre de véhicules est limité et peu élevé. Nous proposons dans cette thèse la première méthode exacte permettant de résoudre ce problème. Notre modélisation prend la forme d'un problème de couverture des clients dont les variables sont des routes. Des contraintes d'exclusion mutuelle expriment la disponibilité des véhicules. Nous utilisons la Génération de Colonnes, avec un sous-problème effectuant, par programmation dynamique, une recherche de plus court chemin élémentaire contraint en ressources. Notre méthode de programmation dynamique tient compte des dépendances de plusieurs ressources grâce à la notion de label représentatif, et est ainsi plus efficace qu'une approche classique. La méthode de Génération de Colonnes est incluse dans un schéma de Branch and Price composé de deux types de branchement, l'un basé sur les arcs, l'autre sur la résolution d'un VRPTW. Nous avons mis en place diverses méthodes accélératrices spécifiques du MTVRPTW. Nous donnons les résultats de l'algorithme sur les instances de Solomon. Des résultats issus de méthodes exactes étaient disponibles dans la littérature pour le MTVRPTW avec durée limite sur les routes. Nous avons proposé un nouvel algorithme plus performant, et basé sur nos méthodes, pour cette variante du problème. / The multi-trip vehicle routing problem with time windows (MTVRPTW) is a generalization of the vehicle routing problem with time windows (VRPTW). In the MTVRPTW, one vehicle can perform several trips during a planning period. This allows optimizing the transport when the number of vehicles is limited and small.We propose here the first exact method for solving this problem.Our model is designed as a coverage problem for customers where the variables are trips. Mutual exclusion constraints express the availability of vehicles. We use a column generation scheme in which the sub-problem is an elementary shortest path problem with resource constraints (ESPPRC). Our dynamic programming method for ESPPRC takes into account dependencies of several resources through the concept of representative label. It is thus more efficient than a conventional approach. The column generation method is included in a Branch and Price scheme with two types of branching. One is based on arc selection, and the other on solving a VRPTW. We have implemented various accelerating methods which are specific to MTVRPTW. We give the results of our algorithm on Solomon instances.Results from exact methods were available in the literature for the MTVRPTW with time limit on the trips. We proposed a new and more efficient algorithm, based on our methods, to solve this variant of the problem.

Les terminaux à conteneurs utilisent les nouvelles technologies (EDI, RFID et GPS) pour échanger des données avec leurs partenaires, pour localiser les conteneurs et leurs équipements dans le terminal, et pour automatiser des tâches. Dans cette thèse, nous montrons comment ces informations peuvent être utilisées dans la gestion des opérations.La première partie utilise les informations sur les volumes annoncés pour affecter des ressources internes dans le but de minimiser le retard global au terminal. Nous représentons cette problématique à l'aide d'un problème de flot que nous implémentons comme programme linéaire mixte. Une étude de cas est réalisée pour un terminal du Grand Port Maritime de Marseille. En outre, nous combinons le problème d'affectation de ressources avec le dimensionnement d'un système de rendez-vous. Ceci permet de minimiser le retard global.La deuxième partie utilise les informations sur les conteneurs à retirer et leurs emplacements pour optimiser le déstockage. Le but est de retirer tous les conteneurs d'une rangée en minimisant le nombre de repositionnements parasites. Nous améliorons un modèle binaire, proposons une approche exacte de type branch and price - avec un sous-problème binaire et deux variantes d'un sous-problème énumératif - et en dérivons une approche heuristique - avec un sous-problème heuristique. L'approche exacte ne résout que les petites instances ; l'approche heuristique obtient des résultats satisfaisants mais devra être améliorée. Nous nous intéressons aussi à la version dynamique du problème où les informations sur les conteneurs à retirer arrivent petit à petit et comparons différentes stratégies de repositionnement. / Container terminals use intelligent freight technologies (e.g., EDI, RFID and GPS) to exchange data with their partners, to locate containers and equipment within the terminal, and to automate tasks. This thesis illustrated, via two examples, how this data may be used to optimize operations at the terminal.The first part uses information on announced volumes to allocate internal handling equipment. The objective is to minimize overall delays at the terminal. The problem is represented as a network flow problem and implemented as a linear mixed integer programming model. A case study for a terminal at the Grand Port Maritime de Marseille is carried out. We also showed that combining the allocation problem with the dimensioning of a truck appointment system may reduce overall delays at the terminal. The second part uses information on announced container retrievals and container positions to improve retrieval operations. The objective is to retrieve containers from a bay in a given sequence with a minimum number of parasite relocations. We improve an existing binary programming model and introduce an exact branch and price approach - with a binary subproblem and two variants of an enumerative subproblem - and a heuristic branch and price approach - with a heuristic subproblem. The exact approach solves only small instances; the heuristic approach performs well on several instances, but should be improved further. We also deal with a dynamic version of the problem where the retrieval order becomes revealed over time and evaluate different relocation strategies for this case.

[pt] A indústria de transporte marítimo é essencial para o comércio internacional. No entanto, no despertar da crise financeira de 2008, essa indústria foi severamente atingida. Nessas ocasiões, empresas de transporte só são capazes de obter lucro se suas frotas forem roteadas de forma eficaz. Neste trabalho, nós estudamos uma classe de problemas de roteamento de navios relacionados ao Pickup and Delivery Problem with Time Windows. Para resolver esses problemas, nós introduzimos um método heurístico e um exato. O método heurístico é uma meta-heurística híbrida com uma vizinhança larga baseada em set partitioning, enquanto o método exato é um algoritmo de branch-and-price. Nós conduzimos experimentos em um conjunto de instâncias baseadas em rotas de navios reais. Os resultados obtidos mostram que nossos algoritmos superam as metodologias estado da arte. Em seguida, nós adaptamos o conjunto de instâncias para modelar um problema de roteamento de navios no qual a velocidade em cada segmento de rota é uma variável de decisão, e o consumo de combustível por unidade de tempo é uma função convexa da velocidade e carga do navio. A fim de resolver esse novo problema de roteamento de navios com otimização de velocidade, nós estendemos nossa meta-heurística para encontrar decisões de velocidade ótimas em toda avaliação de solução vizinha de uma busca local. Nossos experimentos demonstram que essa abordagem pode ser altamente rentável, e que requer apenas um aumento moderado de recursos computacionais. / [en] The shipping industry is essential for international trade. However, in the wake of the 2008 financial crisis, this industry was severely hit. In these times, transportation companies can only obtain profit if their fleet is routed effectively. In this work, we study a class of ship routing problems related to the Pickup and Delivery Problem with Time Windows. To solve these problems, we introduce a heuristic and an exact method. The heuristic method is a hybrid metaheuristic with a set-partitioning-based large neighborhood, while the exact method is a branch-and-price algorithm. We conduct experiments on a benchmark suite based on real-life shipping segments. The results obtained show that our algorithms largely outperform the state-of-the-art methodologies. Next, we adapt the benchmark suite to model a ship routing problem where the speed on each sailing leg is a decision variable, and fuel consumption per time unit is a convex function of the ship speed and payload. To solve this new ship routing problem with speed optimization, we extend our metaheuristic to find optimal speed decisions on every local search move evaluation. Our computational experiments demonstrate that such approach can be highly profitable, with only a moderate increase in computational effort.

[pt] Serviços Médicos de Emergência (SME) proveem ajuda essencial a pessoas em situações de emergência, através de atendimento com primeiros socorros e transporte para unidades de saúde. Sistemas SME devem utilizar da melhor maneira possível seus recursos limitados de atendimento. Esse desafio já foi amplamente estudado por pesquisadores, na forma de problemas de roteamento de veículos, tanto estáticos quanto dinâmicos. No presente trabalho, estudamos um problema estático de roteamento de ambulâncias, cujo objetivo é minimizar o tempo ponderado de espera dos pacientes. O problema considera também o tempo acumulado de espera, restrições de compatibilidade de ambulâncias a serviços, seleção de pacientes, redirecionamento de ambulâncias e redistribuição de ambulâncias. Implementamos um algoritmo exato usando Branch and Price e uma formulação do problema como uma Partição de Conjuntos, usando código aberto. Estudamos os resultados obtidos com esse algoritmo e os comparamos com métodos heurísticos online estudados anteriormente. Para tal, utilizamos dados obtidos do SAMU da cidade do Rio de Janeiro. Os resultados possibilitam a avaliação do valor de informação perfeita nesse contexto e proveem resultados comparativos para embasar o futuro desenvolvimento de algoritmos online. / [en] Emergency Medical Service (EMS) systems provide life-saving support to people in emergency situations via first aid treatment and emergency transport to medical facilities. Such systems must strive to make the best use of their limited resources; they have thus been studied in the context of static and dynamic vehicle routing problems. In this work, we study a static ambulance routing problem aiming to minimize the weighted sum of patients waiting time while considering ambulance compatibility, patients priorities, ambulance redirection, and ambulance reassignment. We implement an exact Branch-andPrice algorithm over a Set Partitioning Formulation, study the results of this algorithm, and compare them to previously studied online heuristics using data from Rio de Janeiro s public SAMU system. The results obtained allow us to assess the value of perfect information in such systems, providing a comparative baseline for subsequent developments of online algorithms.