Search

International audience; Des évènements catastrophiques en milieu urbain peuvent causer des impacts considérables. Selon l'étendue et la puissance de l'évènement, cela peut générer un grand volume de débris. Ce travail traite le transport de débris modélisé comme un problème de planification des équipes de travail, suivi de tournées multiples réalisées par des camions-bennes. Des résultats intéressants ont été obtenus pour une étude de cas du tremblement de terre au Haïti en 2010.

International audience

International audience

International audience; The optimisation of operations to clean debris after disasters in urban areas is very relevant to inhabitants to recover from their effects. This study investigates the integrated multi-period scheduling routing problem to clean debris (SRP-CD) after a natural or industrial disasters. SRP-CD considers complex issues such as two levels of synchronization between vehicles necessary to load, transport and unload debris during limited working days. The goal is to minimize the number of days for the overall cleaning in the strategical level ; and minimizing the total costs of vehicle routes in the operational level. Approximate models and methods have been developed. Numerical experiments for the approaches were carried out to measure their performance and robustness.; L’optimisation du nettoyage des débris suite aux catastrophes dans les zones urbaines est très important pour permettre aux habitants de se remettre de leurs effets. Ce travail aborde le problème intégré multi-période de planification et de tournées de véhicules pour nettoyer les débris (de l’anglais Scheduling Routing Problem to clean debris (SRP-CD)) après des catastrophes naturelles ou technologiques. Le SRP-CD inclut des questions complexes telles que deux niveaux de synchronisation entre les véhicules nécessaires pour charger, transporter et décharger les débris pendant journées de travail. Au niveau stratégique, l’objectif est de minimiser le nombre de jours pour le nettoyage global, et de minimiser le coût total de routage au niveau opérationnel. Des modèles et méthodes approchés ont été développés. Des expérimentations pour les approches sont réalisées pour mesurer leur performance et robustesse.

International audience

International audience

International audience

International audience

International audience

In this paper, there is concentration on collaborative transportation planning (CTP) among multiple carriers with pickup and delivery requests and time windows. This problem is a vehicle routing problem with constraints from standard vehicle routing problems and new constraints from a real-world application. In the problem, each carrier has a finite number of vehicles, and each request is a pickup and delivery request with time window. Moreover, each carrier has reserved requests, which must be served by itself, whereas its exchangeable requests can be outsourced to and served by other carriers. This collaboration among carriers can help them to reduce total transportation costs. A mixed integer programming model is proposed to the problem. To solve the model, a hybrid algorithm that combines Genetic Algorithm and Simulated Annealing (GASA) is proposed. This algorithm takes advantages of GASA at the same time. After tuning the parameters of the algorithm with the Taguchi method, the experiments are conducted and experimental results are provided for the hybrid algorithm. The results are compared with those obtained by a commercial solver. The comparison indicates that the GASA significantly outperforms the commercial solver., {"references":["M. Zhang. S. Pratap. G. Q. Huang. and Z. Zhao. \"Optimal collaborative transportation service trading in B2B e-commerce logistics.\" International Journal of Production Research. vol. 55. pp. 5485–5501. 2017.","H. Chen. \"Combinatorial clock-proxy exchange for carrier collaboration in less than truck load transportation.\" Transportation Research Part E. vol. 91. pp. 152-172.","S. D'Amours. and M. Rönnqvist. \"Issues in collaborative logistics.\" Energy. Natural Resources and Environmental Economics. Part 3. Springer.","L. Houghtalen. \"Designing allocation mechanisms for carrier alliances.\" PhD Thesis. Georgia Institute of Technology. USA. 2007.","E. Markakis. and A. Saberi. \"On the core of the multi-commodity flow game .\" EC 03: Proceedings of the 4thACM Conference on Electronic Commerce. ACM Press. New York. USA. PP. 93-97. 2003.","S. Hernandez. and S. Peeta. \"A centralized time dependent multiple less-than-truckload carrier collaboration problem.\" Transportation Research Board. 2007. Accepted. available at the website: http://amonline.trb.org/12juh5/12juh5/1","Y. Li. H. Chen. and C. Prins. \"Adaptive large neighborhood search for the pickup and delivery problem with time windows. profits. and reserved requests.\" European Journal of Operational Research. vol. 252. PP. 27–38. 2016.","J. H. Holland. \"Adaptation in natural and artificial systems:An introductory analysis with applications to biology.\" control and artificial intelligence. Michigan: University of Michigan Press. 1975.","S. H. Karna. and R. Sahi. \"An Overview on Taguchi Method.\" International Journal of Engineering and Mathematical Sciences. vol.1. pp.11-18. 2012.\n[10]\tR. Rao. Sreenivas; R. S. Prakasham. K. Krishna Prasad. S. Rajesham. P. N. Sarma. and L. VenkateswarRao. \"Xylitol production by Candida sp.: parameter optimization using Taguchi approach.\" Process Biochemistry. vol. 39. pp. 951-956. 2004.\n[11]\tG. Taguchi. \"introduction to Quality Engineering-Designing Quality into Products and Processes.\" Asian Productivity Organization. Tokyo. 1986."]}

International audience; Vehicle routing problems (VRPs) represent a rapidly growing research domain in operations research and combinatorial optimization, aiming to develop mathematical models and efficient solution methods. As underlined by Laporte (2009), VRPs are nice laboratory-problems to test new ideas in algorithmics and optimization. Recent trends try to tackle rich VRPs, i.e., problems including many real-word constraints and requiring metaheuristics to solve the large instances met in practice.

International audience

International audience

International audience

International audience

International audience

International audience

International audience

International audience; This book is dedicated to metaheuristics as applied to vehicle routing problems. Several implementations are given as illustrative examples, along with applications to several typical vehicle routing problems.As a first step, a general presentation intends to make the reader more familiar with the related field of logistics and combinatorial optimization. This preamble is completed with a description of significant heuristic methods classically used to provide feasible solutions quickly, and local improvement moves widely used to search for enhanced solutions. The overview of these fundamentals allows appreciating the core of the work devoted to an analysis of metaheuristic methods for vehicle routing problems. Those methods are exposed according to their feature of working either on a sequence of single solutions, or on a set of solutions, or even by hybridizing metaheuristic approaches with others kind of methods.

International audience; The Cumulative Capacitated Vehicle Routing Problem with Time-Dependent Demand(CCVRP-TDD) is a novel problem in humanitarian logistics where the demand is dynamic and the objective is to minimize the sum of arrival times at critical nodes due to the emergency of the situation. Critical nodes are the nodes closest to the source, from which people try to flee to seek first aid, food, etc. This mobilization of people through the affected territory generates an increase in the chaos already caused by the disaster. The vehicles must arrive at these nodes as soon as possible and after they must supply at farthest ones (non critical/safe points). This article presents a mixed integer linear program (MILP) and a two-phase heuristic method (TPHM) based on multi-start iterated local search (MS-ILS). The moves are evaluated in constant time. Both solutions methods are tested in small and medium instances. We show that the heuristic method finds the optimal solution on small instances.

International audience; This study takes place in a national project on disaster logistics and concerns the last mile distribution phase after a large scale disaster, taking the Haiti earthquake as case study. From supply depots in the suburbs, the goal is to design vehicle routes with multiples trips to reach camps of refugees, knowing that the streets can be more or less obstructed, which implies several types of vehicles. The goal is to minimize the total distribution time and the cost of vehicles used. The proposed solution method is a matheuristic derived from Penna et al. (2013), a multi-start iterated local search. The improvement procedure is a variable neighborhood search (VND). A set-partitioning problem (SPP) is solved periodically, using a pool of good routes found by the heuristic, but the communication is bidirectional: the heuristic is also called each time a new solution is obtained during the SPP resolution. The algorithm competes with published metaheuristics on multi-depot VRP instances from the literature. On data from Haiti earthquake (16,000 nodes, 19,000 edges, 12 depots, 62 camps, 3 vehicle types), the algorithm returns in one minute on a PC solutions which are considered as very good by the decision maker.

International audience

International audience

International audience; La biomasse est souvent utilisée pour la production de biocarburants. Ces derniers sont avantageux car ils produisent moins de gaz à effet de serre (GES) que le pétrole et parce qu'ils sont fabriqués à partir de sources renouvelables, mais leur viabilité économique est toujours une question cruciale pour leur développement à grande échelle. Une partie non négligeable de la recherche se concentre actuellement sur l'amélioration de la productivité de la biomasse et sur la conception des processus de conversion les plus efficaces. En comparaison, les aspects logistiques sont relativement peu étudiés. Ces derniers sont pourtant critiques pour approvisionner les unités de conversion de manière régulière, fiable, et avec des quantités suffisantes de biomasse de qualité. De plus, une part significative du coût de la biomasse à l'entrée d'une bio-raffinerie réside dans les coûts logistiques. Une chaîne d'approvisionnement efficace est donc un moyen de contribuer à la viabilité économique, sociale et environnementale de l'industrie des biocarburants. Par rapport à la logistique industrielle, la logistique pour la biomasse induit des difficultés particulières, comme la dispersion des sources d'approvisionnement, l'irrégularité des productions le long de l'année ou les dégradations liées à des processus physiques ou chimiques. Cette étude s’inscrit dans le cadre du programme GENESYS de l'Institut pour la Transition Energétique (ITE) PIVERT (Picardie Innovations Végétales, Enseignements et Recherches Technologiques) portant sur la bioraffinerie oléagineuse du futur. L'analyse conduite dans cette étude, associée à l’état de l'art, a permis d'établir un modèle mathématique adéquat pour traiter le problème réel, ainsi qu’une méthode de résolution approchée.

International audience

International audience; Optimization is an important aspect of logistics management. It can reduce significantly logistics costs and also be a good tool for decision support. In this paper, we address a planning problem specific to biomass supply chain. We propose a new mixed integer linear programming (MILP) model dealing with different feedstock production operations such as harvesting, packing, storage, preprocessing and transportation, with the objective of minimizing the total logistic cost of the system on a regional basis. It determines the optimal number of harvesting machines, the fleet size of trucks for transportation and the amount of each type of biomass harvested, stored and preprocessed in each period to satisfy demands of bio-refineries in each period. The effectiveness of the proposed model is illustrated with a numerical example, a case study in Aube (France department), which gives preliminary and interesting results on a small test case.

International audience

International audience

International audience

International audience

International audience

International audience

International audience; This special issue of RAIRO-Operations Research is dedicated to the 14th ROADEF Conference (ROADEF 2013)of the Operations Research (OR) and Management Science (MS) French Society, held in Troyes, Université de Technologie de Troyes (UTT) on February 13-15, 2013. Twenty-four articles were submitted to the special issue "Combinatorial Optimization in production and logistics systems". The six selected contributions are a sample of the rich diversity of studies presented in ROADEF 2013, and address the following topics: mathematical formulations for healthcare, a generalized consistent neighborhood search for satellite range scheduling problems, metaheuristics for a lot-sizing production planning problem with returns, a multi-objective exact procedure for a network design problem, and notation and classification for vehicle routing problems and network design models.

International audience

International audience

International audience; The robust vehicle routing problem with discrete scenarios is defined on a complete directed graph G=(V,A). V includes one depot with m vehicles of capacity Q and n customers with demands d(i). The arc costs are defined by p scenarios, c(i,j,k) denoting the cost of arc (i,j) in scenario k. The goal is to determine a VRP solution minimizing the worst total cost over all scenarios. A mixed integer program and four metaheuristics using a common local search are presented for this extremely hard problem: one GRASP, one Iterated Local Search (ILS), one multi-start ILS (MS-ILS) and one MS-ILS involving giant tours and a new splitting procedure. 18 small instances (max n=10-20, m=2-3 and p=10-20) and 24 larger ones (max n=50-100, m=5-20 and p=10-20) are randomly generated. The two MS-ILS give the best results. On a 2.2 GHz Intel Core i7 PC, they retrieve in less than 5 seconds the optima found by CPLEX on small instances, and even improve three upper bounds when the solver cannot reach an optimum in 4 hours. On large instances, they last less than one minute and the giant tour version is significantly better than the one working only on complete RVRP solutions.

Uncertain parameters appear in many optimization problems raised by real-world applications. To handle such problems, several approaches to model uncertainty are available, such as stochastic programming and robust optimization. This study is focused on robust optimization, in particular, the criteria to select and determine a robust solution. We provide an overview on robust optimization criteria and introduce two new classifications criteria for measuring the robustness of both scenarios and solutions. They can be used independently or coupled with classical robust optimization criteria and could work as a complementary tool for intensification in local searches.

International audience; Introduction According to the Global Health Observatory (GHO), more than half of the total population lived in urban areas in 2010. This proportion is expected to reach 60% by 2030 and 70% by 2050. The increasing concentration of population and the unplanned extension of urban areas raise several challenges, among which the management of the urban network infrastructures. The TOAST project (Tactical OptimizAtion Strategies to adapt urban Transportation networks) aims at investigating a new set of emerging tactical optimization problem [1]. It consists in setting directions on each street to improve the global transport system. This research has been funded in 2013 by the DRRT (Délégation Régionale à la Recherche et à la Technologie, Champagne-Ardennes region, France). Decision Making System An optimization framework core has been developed to deal with a class of tactical optimization problems [2], where two objectives are optimized independently: (i) Allow fast origin-destination transportation requests (ii) Prevent drivers from entering critical areas such as city centers or touristic points. The ongoing work will include the computation of the global congestion and address several other settings (such as lanes) to deal with promising applications. The optimization core can be embedded in a support decision systems as shown in Figure 1. The core TOAST encloses sophisticated heuristics and metaheuristics such as Iterated Local Search (ILS) and Relaxed ILS (RILS), Evolutionary Local Search (ELS) and Relaxed ESL (RELS), Variable Neighborhood Search (VNS) and Intelligent VNS (IVNS), applied to produce high quality results for different networks structures. Results The methods were tested on Manhattan graphs (grid structure) instances, as well as on real instances from the Clermont-Ferrand and Troyes cities, France. The first results are presented in [3]. Figure 2 illustrates the relation between the convergence and the trade-off between the solutions quality and the running time, using a medium-sized instance for the Clermont-Ferrand city, France. Figure 3 shows a typical output from our solver for the center of Troyes, The proposed framework is able to solve the core problem of setting directions and evaluating the global impact on an urban network for the goals (i) and (ii). We are currently extending it: • To manage the global congestion • To quickly provide good traffic redirections when some streets are blocked due to maintenance, natural perils (freezing rain, hail storm, flood, fire, etc), road accidents, manifestations (fairs, etc.), …

International audience; Dans ce travail nous étudions le problème de tournées de véhicules cumulatif avec capacités et routes multiples où les tournées sont réalisées avec un seul véhicule. Ce dernier doit visiter tous les sommets une et une seule fois et minimiser la somme des temps d'arrivée. Nous rencontrons ce problème lors des opérations logistique en cas de catastrophe où cette fonction objectif reflète mieux l'urgence de la situation. Une méthode exacte basée sur un algorithme de plus court chemin élémentaire avec des contraintes de ressources est proposée afin de résoudre ce problème. Le problème est formulé comme un modèle de plus court chemin où chaque route se transforme en un super-nœud, les sites à visiter deviennent des ressources. Ce réseau est orienté et acyclique grâce à des propriétés du problème de base. La méthode de résolution décompose le problème en deux phases. Dans la première phase le problème de plus court chemin est résolu sur un sous-ensemble de super-nœuds. Dans la deuxième phase l'arbre généré pendant la première phase est intégré pour résoudre le problème complet et le résultat de la première phase devient une borne supérieure pour la deuxième. Plusieurs règles de dominance, bornes supérieures et bornes inférieures sont ajoutés afin d'accélérer la procédure de recherche. Les résultats numériques sont présentés sur des instances issues de la littérature pour le CVRP classique et comparés avec un modèle linéaire en nombres entiers mixtes.

International audience; Cette étude s'inscrit dans le cadre du Programme GENESYS du projet national P.I.V.E.R.T. (Picardie Innovations Végétales, Enseignements et Recherches Technologiques) portant sur la bioraffinerie oléagineuse du futur. Nous nous focalisons ici sur le problème d'approvisionnement de biomasse qui s'apparente à un problème de flot à coût minimum. Une chaîne d'approvisionnement en biomasse est un réseau complexe comprenant un nombre important de paramètres, de variables de décision et de contraintes. Sa particularité vient des caractéristiques spéciales issues de la biomasse, et qui posent plusieurs questions liées à chaque couche de la chaine, chacune devant être considérées et traitées pour obtenir un système d'approvisionnement économiquement viable. Nous présentons d'abord les principales approches utilisées dans la littérature pour modéliser ce type de problème. Ensuite, nous proposons un modèle tactique multi-échelon, multi-périodes, avec plusieurs types et formes de biomasse. L'objectif est de minimiser les différents coûts logistiques liés à cette chaine. La structure de la chaîne d'approvisionnement est décrite par un graphe G avec un ensemble de nœuds (comprenant un ensemble de zones de production, un ensemble de sites de stockage, un ensemble de sites de prétraitements, et un ensemble de bioraffineries) et un ensemble d'arcs reliant les différents sites et représentant le transport et le flux de matières. Enfin nous présentons les résultats numériques d'une étude de cas avec OPL-STUDIO (Modeleur de haut niveau basé sur CPLEX).

International audience; Le problème de voyageur de commerce avec les classes de priorité (VDCp) est un cas particulier du problème de voyageur de commerce clusterisé (VDCc) où l'ensemble de villes à visiter est divisé en sous-ensembles avec une contrainte de précédence : le véhicule ne peut pas sortir d'un cluster sans visiter toutes les villes de ce cluster et il ne peut aller à un cluster dont la priorité est inférieure à celui qu'il vient de quitter. Une des applications possibles de ce problème est observée dans la logistique humanitaire. Après une catastrophe naturelle ou industrielle, la situation est évaluée et les zones sont triées selon l'importance de l'impact. Les zones les plus touchées doivent naturellement être secourues prioritairement. Jongens et Volgenant [1] ont proposé une relaxation lagrangienne pour le VDCc mais leur modèle ne permet pas de résoudre le cas où il y a un ordre prédéfini de visite des clusters. Nous proposons un modèle de programmation linéaire en nombres entiers et sa relaxation lagrangienne inspirée de celle de Jongens et Volgenant. Nous démontrons que, lorsque la relaxation trouve une solution réalisable, cette dernière est optimale, sans aucune autre condition. Afin de juger la qualité et l'efficacité de cette méthode, elle est testée sur les instances de la littérature et générées aléatoirement contenant jusqu'à 200 sommets. [1] Jongens K. Volgenant T. The symmetric clustered traveling salesman problem . European Journal of Operational Research 1985: 19 (1) : 68-75

International audience; Cet article concerne un problème de planification dans un réseau de distribution à deux échelons (des entrepôts fournissent des produits finis à plusieurs dépôts) intégrant la gestion de stocks de produits périssables, le dimensionnement de lots, des alternatives d'approvisionnement et une flotte homogène. Un dépôt peut être approvisionné par plusieurs entrepôts, le choix des alternatives d'approvisionnement est déterminé en fonction de la disponibilité des produits dans les entrepôts, des moyens de transport, mais aussi des coûts de transport. L'objectif consiste à trouver un compromis entre les coûts de transport, de stockage aux entrepôts et aux dépôts, de la perte due à l'obsolescence des produits. La méthode utilisée est basée sur une heuristique constructive " gloutonne ". Elle construit la solution étape par étape, guidée par des règles de priorité. L'heuristique est scindée en trois procédures principales pour mieux équilibrer les stocks dans les cas de pénurie ou de capacité très limitée. La première consiste à déterminer les quantités nécessaires afin d'éviter la rupture de stock des dépôts. Ensuite, nous cherchons à atteindre le stock objectif (niveau stock idéal). Enfin, le surplus des entrepôts est déployé vers les dépôts. Nous donnons à l'utilisateur un choix de priorisation, il s'agit de trier les stocks selon un critère choisi. Afin d'améliorer la qualité des solutions fournies par l'heuristique, nous avons introduit une randomisation. Le problème étudié est assez répandu dans le domaine industriel comme celui des produits laitiers. Un programme linéaire mixte a été élaboré, cependant une heuristique est nécessaire pour deux raisons, à savoir : la résolution de problèmes de très grande taille et une meilleure compréhension de la construction de la solution (les solutions construites par les solveurs commerciaux de Programmation Linéaire étant souvent difficiles à expliquer). L'heuristique, qui a été incluse dans un APS (Advanced Planning System), est comparée avec une résolution optimale du modèle sur des instances issues de données réelles.

International audience; Cluster-first route-second methods like the sweep heuristic (Gillett and Miller, 1974) are well known in vehicle routing. They determine clusters of customers compatible with vehicle capacity and solve a traveling salesman problem for each cluster. The opposite approach, called route-first cluster-second, builds a TSP tour (also called giant tour) covering all customers and splits it into feasible trips. Cited as a curiosity for a long time but lacking numerical evaluations, this technique has led to successful solution methods for various vehicle routing problems in the last decade. As many implementations define an ordering of the customers instead of building really a giant tour, such algorithms are better called order-first split-second methods. The talk will present the principles of these approaches and examples of applications, from simple cases to less obvious contexts.

International audience

International audience

International audience

International audience

International audience

International audience

International audience