Search

International audience; This paper deals with a real application encountered in the construction sector, which consists in a new variant of the pickup and delivery problem, including several constraints that have never been combined in the same variant, denoted MTPDSPTW. This problem is defined by a set of construction sites that have a delivery demand for construction materials and also a waste removal request. Each construction site has a certain profit which is computed according to the urgency of the pickup and delivery demand. Each site can be visited several times during the day, but the delivery must be done within a set of time windows specified by each site. Heterogeneous vehicles with di erent availability located at a massification and waste treatment platform must do multiple tours to serve the requests. The objective is to minimize the total travel distance and to maximise the profit. The developed method is based on the Iterated Local Search metaheuristic which uses a Random Variable Neighborhood Descent (RVND) in the Local Search Procedure. Di erent implementation schemes of the proposed method are tested on set of data instances provided by our industrial partner. The results show the e ectiveness of ILS-RVND compared to ILS with a single local search operator. ILS-RVND improves the results of the SBH heuristic by 13.15%.

International audience; Further reducing empty running by trucks is clearly an important source of efficiency for transportation companies, as well as a valuable way to decrease their carbon footprint. The Pickup and Delivery Problem (PDP) aims at selecting routes such that the distance travelled empty is as short as possible, given a set of transportation requests. In this context, the driving time constraint may be a key factor since it restricts the number of possible routes for each vehicle. To overcome this time constraint, an opportunity is for vehicles to drop or swap their trailer at intermediary transshipment points. In this paper, we evaluate the benefits of using transshipment points in the PDP to reduce the length of the empty backhauls, and we study how the driving time constraint affects those benefits. For this, we apply a MIP model for the PDP integrating transshipment points, and conduct computational experiments comparing the results with a classical PDP. We find that indeed, when driving time is constraining, enabling transshipment points seems to be of interest (up to 25% more reduction in the distance travelled empty).

In 2013, the transportation of materials for roads construction and earthwork represents more than half of the whole activity of in the public works sector. Optimization methods for vehicle routing problems allow to solve big-size problems with industrial sector constraints. In this thesis, we focus on solving the rich full truckload pickup and delivery problem with resource synchronization. First, we solve this vehicle routing problem with a two phase heuristic method. Then, we study the integration of regulation of drivers’ working hours and the addition of lunch breaks in routes of vehicles. These methods are tested on instances from the literature and real life instances from a public works company.; Le transport de matériaux pour la réalisation d’infrastructures routières et le terrassement représente, en 2013, plus de la moitié de l’activité du secteur des travaux publics. Les méthodes d’optimisation de tournées de véhicules permettent aujourd’hui de résoudre des problèmes de grandes tailles en intégrant les contraintes liées au métier. Dans cette thèse, nous nous intéressons à la résolution du problème riche de collectes et livraisons en camions complets avec des contraintes de synchronisation sur les ressources. Dans un premier temps, nous résolvons le problème de tournées de véhicules avec une méthode heuristique en deux phases. Dans un second temps, nous étudions l’intégration des contraintes liées aux temps de conduite des chauffeurs ainsi que l’ajout des pauses déjeuners aux tournées. Nous testons les algorithmes proposés sur des instances de la littérature et des instances réelles issues d’une application industrielle d’une entreprise de Travaux Publics.

International audience; The Pickup and Delivery Problem with Shuttle routes (PDPS) is a special case of the Pickup and Delivery Problem with Time Windows (PDPTW) where the trips between the pickup points and the delivery points can be decomposed into two legs. The rst leg visits only pickup points and ends at some delivery point. The second leg is a direct trip { called a shuttle { between two delivery points. This optimization problem has practical applications in the transportation of people between a large set of pickup points and a restricted set of delivery points. This paper proposes three mathematical models for the PDPS and a branch-and-cutand- price algorithm to solve it. The pricing sub-problem, an Elementary Shortest Path Problem with Resource Constraints (ESPPRC), is solved with a labeling algorithm enhanced with e cient dominance rules. Three families of valid inequalities are used to strengthen the quality of linear relaxations. The method is evaluated on generated and real-world instances containing up to 193 transportation requests. Instances with up to 87 customers are solved to optimality within a computation time of one hour.

International audience; The main objective of this communication is to show how realistic-sized instances of the Pickup and Delivery Problem with Transfers (PDPT) can be solved to optimality with a branch-and-cut-and-price method, under realistic hypotheses. We introduce the Pickup and Delivery Problem with Shuttle routes (PDP-S) which is a special case of the PDPT relying on a structured network with two categories of routes. {\em Pickup routes} visit a set of pickup points independently of their delivery points and end at one delivery point. {\em Shuttle routes} are direct trips between two delivery points. We propose a path based formulation of the PDP-S and solve it with a branch-and-cut-and-price algorithm. We show that this approach is able to solve real-life instances with up to 87 transportation requests.

The Pickup and Delivery Problem with Transfers (PDPT) consists of defining a set of minimum cost routes in order to satisfy a set of transportation requests, allowing them to change vehicles at specific locations. In this problem, routes are strongly interdependent due to request transfers. Then it is critical to efficiently check if inserting a request into a partial solution is feasible or not. In this article, we present a method to perform this check in constant time.

28 pages; The Pickup and Delivery Problem with Shuttle routes (PDPS) is a special case of the Pickup and Delivery Problem with Time Windows (PDPTW) where the trips between the pickup points and the delivery points can be decomposed into two legs. The first leg visits only pickup points and ends at some delivery point. The second leg is a direct trip - called a shuttle - between two delivery points. This optimization problem has practical applications in the transportation of people between a large set of pickup points and a restricted set of delivery points. This paper proposes three mathematical models for the PDPS and a branch- and-cut-and-price algorithm to solve it. The pricing subproblem, an Elementary Shortest Path Problem with Resource Constraints (ESPPRC) is solved with a la- beling algorithm enhanced with efficient dominance rules. Three families of valid inequalities are used to strengthen the quality of linear relaxations. The method is evaluated on generated and real-world instances containing up to 193 transportation requests. Instances with up to 87 customers are solved to optimality within a computation time of one hour.

The thesis deals with the proposal of optimization methods (mathematical models and metaheuristics) and their coupling with a simulation model for the resolution of collection delivery problems including the planning of drivers' schedules. The originality of this work concerns the diversity of resources (vehicle, driver, loading and unloading dock, container, production line, cleaning area) and constraints (vehicle/container incompatibility, earliest start date, desired end date, schedule...) to be taken into account. The objective is to propose an organization allowing to carry out all the transports while minimizing the delays and the overtime. The first part focuses on the transport of a single type of product. The problem is modeled as an RCPSP with a variable resource demand profile. Empty transports are modeled as sequence-dependent setup times. Two integer linear programs are proposed. The second part deals with the transport of several types of products. The problem has a dual complexity that is solved by coupling an iterated local search with a simulation model. The simulation model allows to address the structural and functional complexity, especially due to the diversity of resources. The third part integrates the definition of the drivers' work schedules. An iterative approach including a simulation model, a linear integer program and the coupling previously presented is proposed. This problem is treated in a hospital context for the transport of clean or dirty containers (meals, linen, drugs) between consumption sites and production sites. Each part is experimented with real data., La thèse porte sur la proposition de méthodes d’optimisation (modèles mathématiques et métaheuristique) et leur couplage avec un modèle de simulation pour la résolution de problèmes de livraison collecte incluant la planification des horaires des chauffeurs. L’originalité de ces travaux porte sur la diversité des ressources (véhicule, chauffeur, quai de chargement, de déchargement, contenant, ligne de production, aire de nettoyage) et des contraintes (incompatibilité véhicule/contenant, date de début au plus tôt, date de fin souhaitée, planning…) à prendre en compte. L’objectif est de proposer une organisation permettant de réaliser l’ensemble des transports tout en minimisant les retards et les heures supplémentaires. La première partie s’intéresse au transport d’un seul type de produit. Le problème est modélisé comme un RCPSP avec profil de demande en ressources variable. Les transports à vide sont modélisés comme des temps de montage dépendant de la séquence. Deux programmes linéaires en nombres entiers sont proposés. La seconde partie concerne le transport de plusieurs types de produit. Le problème présente une double complexité qui est résolue par le couplage d’une recherche locale itérée avec un modèle de simulation. Le modèle de simulation permet de répondre à la complexité structurelle et fonctionnelle, notamment en raison de la diversité des ressources. La troisième partie intègre la définition des horaires de travail des chauffeurs. Une approche itérative incluant un modèle de simulation, un programme linéaire en nombres entiers et le couplage précédemment présenté est proposée. Ce problème est traité dans un contexte hospitalier pour le transport de contenants propres ou sales (repas, linge, médicaments) entre sites de consommation et sites de production. Chaque partie fait l’objet d’une expérimentation avec des données réelles.

Transportation companies face gradually larger problems where the use of transshipment can have a significant outcome on the costs. ILOG TPO is a software able to solve such problems, but it is hard for it to take good cross-docking decisions. Moreover, the ILOG TPO solving process is based on local search, and it can be helped for global decisions such as transshipment. This PhD takes place in this context, and its aim is to help ILOG TPO find better solutions. For this matter, a complete formulation is first proposed to solve the smallest instances, and with a cutting-plane technique, optimal solutions are usually found within reasonnable computing time. Then a two-phase algorithm including a network Mixed-Integer Program (MIP) on a network relaxation of the problem is given for larger instances. This two-phase algorithm is a cooperation between the MIP and ILOG TPO, where the MIP gives ILOG TPO, for each shipment, the hub path through which it should be routed. This heuristic finds similar solutions as ILOG TPO alone, but the processing time is significantly reduced.; Les entreprises de transport font face à des problèmes de taille grandissante où l'utilisation de transbordement peut avoir un impact significatif sur les coûts. ILOG TPO est un logiciel capable de résoudre de tels problèmes, mais il lui est difficile de prendre de bonnes décisions concernant le transbordement. De plus, le processus de résolution d'ILOG TPO est basé sur la recherche locale, et il peut être aidé pour certaines décisions globales comme le transbordement. Cette thèse se place dans ce contexte, et son objectif est d'aider ILOG TPO à trouver de meilleures solutions. Pour cela, une formulation complète est d'abord proposée pour résoudre les plus petites instances, et avec une technique de plans coupants, les solutions optimales sont généralement trouvées en un temps raisonnable. Ensuite, un algorithme à deux phases qui inclut un programme en variables mixtes (MIP) sur une relaxation de type réseau du problème est donné pour de plus grandes instances. Cet algorithme est une coopération entre le MIP et ILOG TPO, où le MIP donne à ILOG TPO, pour chaque ordre de transport, le chemin de hubs par lequel il devrait être acheminé. Cette heuristique trouve des solutions similaires à ILOG TPO seul, mais le temps de calcul est réduit de façon significative.

Transportation companies face gradually larger problems where the use of transshipment can have a significant outcome on the costs. ILOG TPO is a software able to solve such problems, but it is hard for it to take good cross-docking decisions. Moreover, the ILOG TPO solving process is based on local search, and it can be helped for global decisions such as transshipment. This PhD takes place in this context, and its aim is to help ILOG TPO find better solutions. For this matter, a complete formulation is first proposed to solve the smallest instances, and with a cutting-plane technique, optimal solutions are usually found within reasonnable computing time. Then a two-phase algorithm including a network Mixed-Integer Program (MIP) on a network relaxation of the problem is given for larger instances. This two-phase algorithm is a cooperation between the MIP and ILOG TPO, where the MIP gives ILOG TPO, for each shipment, the hub path through which it should be routed. This heuristic finds similar solutions as ILOG TPO alone, but the processing time is significantly reduced., Les entreprises de transport font face à des problèmes de taille grandissante où l'utilisation de transbordement peut avoir un impact significatif sur les coûts. ILOG TPO est un logiciel capable de résoudre de tels problèmes, mais il lui est difficile de prendre de bonnes décisions concernant le transbordement. De plus, le processus de résolution d'ILOG TPO est basé sur la recherche locale, et il peut être aidé pour certaines décisions globales comme le transbordement. Cette thèse se place dans ce contexte, et son objectif est d'aider ILOG TPO à trouver de meilleures solutions. Pour cela, une formulation complète est d'abord proposée pour résoudre les plus petites instances, et avec une technique de plans coupants, les solutions optimales sont généralement trouvées en un temps raisonnable. Ensuite, un algorithme à deux phases qui inclut un programme en variables mixtes (MIP) sur une relaxation de type réseau du problème est donné pour de plus grandes instances. Cet algorithme est une coopération entre le MIP et ILOG TPO, où le MIP donne à ILOG TPO, pour chaque ordre de transport, le chemin de hubs par lequel il devrait être acheminé. Cette heuristique trouve des solutions similaires à ILOG TPO seul, mais le temps de calcul est réduit de façon significative.