Retour au site du LAAS-CNRS

Laboratoire d’analyse et d’architecture des systèmes

Publications de l'équipe ROC

Choisir la langue : FR | EN

624documents trouvés

18064
15/03/2018

Soft-Cascade Learning with Explicit Computation Time Considerations

FBARBOSA ANDA, F.LERASLE, C.BRIAND, A.A.MEKONNEN

RAP, ROC

Manifestation avec acte : IEEE Winter Conference on Applications of Computer Vision ( WACV ) 2018 du 12 mars au 15 mars 2018, Lake Tahoe (USA), Mars 2018, 10p. , N° 18064

Lien : https://hal.archives-ouvertes.fr/hal-01726292

Diffusable

Plus d'informations

Abstract

This paper presents a novel framework for learning a soft-cascade detector with explicit computation time considerations. Classically, training techniques for soft-cascade detectors select a set of weak classifiers and their respective thresholds, solely to achieve the desired detection performance without any regard to the detector response time. Nevertheless, since computation time performance is of utmost importance in many time-constrained applications , this work divulges an optimization approach that aims to minimize the mean cascade response time, given a desired detection performance, fixed beforehand. The resulting problem is NP-Hard, therefore finding an optimal threshold vector can be very time-consuming, especially when building a soft-cascade detector of long length. An efficient local search procedure is presented that deals with long-length detectors. Our evaluations on two challenging public datasets confirm that a faster cascade detector can be learned while maintaining similar detection performances .

142834
18029
02/03/2018

A Three-step Decomposition Method for Solving the Minimum-Fuel Geostationary Station Keeping of Satellites Equipped with Electric Propulsion

C.GAZZINO, D.ARZELIER, L.CERRI, D.LOSA, C.LOUEMBET, C.PITTET-MECHIN

MAC, ROC, CNES, Thalès Alenia Space

Rapport LAAS N°18029, Mars 2018, 14p.

Lien : https://hal.laas.fr/hal-01696455

Diffusable

Plus d'informations

Abstract

In this paper, a control scheme is elaborated in order to perform the station keeping of a geostationary satellite equipped with electric propulsion while minimizing the fuel consumption. The use of electric thrusters imposes to take into account some additional non linear and operational constraints that make the overall station keeping optimal control problem difficult to solve directly. That is why the station keeping problem is decomposed in three successive control problems. The first one consists in solving a classical optimal control problem with an indirect method initialized by a direct method without enforcing the thrusters operational constraints. Starting from this non feasible solution for the genuine problem, the thrusters operating constraints are incorporated in the second problem, whose solution produces a feasible but non optimal control profile via two different ways. Finally, the third optimizes the commutation times thanks to a method borrowed to the switched systems theory. Simulation results on a realistic example validate the benefit of this particular control scheme in the reduction of the fuel consumption for the geostationary station keeping problem.

142572
18024
01/03/2018

Long-term electric geostationary station-keeping via integer programming

C.GAZZINO, D.ARZELIER, C.LOUEMBET

MAC, ROC

Rapport LAAS N°18024, Mars 2018, 34p.

Diffusable

142512
18074
21/02/2018

Une méthode exacte pour le problème du jobshop cyclique robuste

I.HAMAZ, L.HOUSSIN, S.CAFIERI

ROC, ENAC

Manifestation avec acte : Congrès Annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision ( ROADEF ) 2018 du 21 février au 23 février 2018, Lorient (France), Février 2018, 3p. , N° 18074

Lien : https://hal-enac.archives-ouvertes.fr/hal-01737765

Diffusable

Plus d'informations

Abstract

Description du problème Le problème d'ordonnancement cyclique de base (BCSP) est définit par un ensemble T = {1, ..., n} de n tâches génériques. Chaque tâche i ∈ T a une durée p i et doit être exécutée une infinité de fois. On note < i, k > la k éme occurrence de la tâche i. Un ordonnancement σ est une affectation des dates de début t(i, k) pour chaque occurrence < i, k >. Un ordonnancement est dit périodique avec un temps de cycle α si t(i, k) = t(i, 0) + αk, ∀ i ∈ T , ∀ k ≥ 1. (1) Afin de simplifier la notation, nous définissions t i = t(i, 0) pour chaque tâche i dans T. D'après (1), un ordonnancement périodique peut donc être défini seulement avec les dates de début des premières occurrences (t i) i∈T ainsi que le temps de cycle α. Le différentes tâches sont liées par un ensemble de contraintes de précédence dites contraintes uniformes. Ces contraintes sont données par : t(i, k) + p i t(j, k + H ij), ∀i, j ∈ T, ∀k ≥ 0. (2) où i et j sont deux tâches génériques, et H ij un entier naturel, appelé hauteur, qui représente le décalage entre les occurrences des tâches i et j. L'objectif du problème est de trouver un ordonnancement σ opt qui satisfait les contraintes uniformes (2) et minimise le temps de cycle α. Un graphe orienté G = (V, E) peut être associé à ce problème. Un noeud du graphe G représente une tâche et un arc (i, j) est présent si une contrainte de précédence existe entre les deux tâches correspondantes. Dans ce cas, l'arc (i, j), appelé arc uniforme, est étiqueté par deux valeurs, une longueur L ij = p i et une hauteur H ij ∈ Z. Le temps de cycle minimum est donné par le poids moyen maximum du graphe G. Celui-ci est donné par α = max c∈C (i,j)∈c L ij (i,j)∈c H ij Où C est l'ensemble des circuits du graphe G. Le circuit c donnant le poids moyen maximum est appelé circuit critique. Différents algo-rithmes sur le calcul de circuits critiques peuvent être trouvés dans la littérature [3]. Le problème du jobshop cyclique peut être vu comme un problème d'ordonnancement cy-clique de base avec des contraintes de ressources. Nous considérons un ensemble M = {1, ..., m} de m machines tel que m < n. Chaque tâche i ∈ T est exécutée sans interruption sur la machine M (i). Les tâches sont organisées sous forme de job et celles appartenant au même job

142937
18050
24/01/2018

Technologies respectueuses de la vie privée pour le covoiturage. Privacy-Enhancing Technologies for Ridesharing

U.M.AIVODJI

TSF, ROC

Doctorat : Université de Toulouse III - Paul Sabatier, 24 Janvier 2018, 142p., Président: B.NGUYEN, Rapporteurs: J.DOMINGO-FERRER, D.FEILLET, Examinateurs: C.BRIAND, F.FESSANT, B.LE CUN, Directeurs de thèse: M.O.KILLIJIAN, M.J.HUGUET , N° 18050

Lien : https://hal.laas.fr/tel-01735575

Diffusable

Plus d'informations

Résumé

L’émergence des téléphones mobiles et objets connectés a profondément changé notre vie quotidienne. Ces dispositifs, grâce à la multitude de capteurs qu’ils em- barquent, permettent l’accès à un large spectre de services. En particulier, les capteurs de position ont contribué au développent des services de localisation tels que la navigation, le covoiturage, le suivi de la congestion en temps réel. . . En dépit du confort offert par ces services, la collecte et le traitement des données de localisation portent de sérieuses atteintes à la vie privée des utilisateurs. En effet, ces données peuvent renseigner les fournisseurs de services sur les points d’intérêt (domicile, lieu de travail, orientation sexuelle), les habitudes ainsi que le réseau social des utilisateurs. D’une façon générale, la protection de la vie privée des utilisateurs peut être assurée par des dispositions légales ou techniques. Même si les mesures d’ordre légal peuvent dissuader les fournisseurs de services et les individus malveillants à enfreindre le droit à la vie privée des utilisateurs, les effets de telles mesures ne sont observables que lorsque l’infraction est déjà commise et détectée. En revanche, l’utilisation des technologies renforçant la protection de la vie privée (PET pour Privacy Enhancing Technologies) dès la phase de conception des systèmes permet de réduire le taux de réussite des attaques contre la vie privée des utilisateurs. L’objectif principal de cette thèse est de montrer la viabilité de l’utilisation des PET comme moyens de protection des données de localisation dans les services de covoiturage. Ce type de service de localisation, en aidant les conducteurs à partager les sièges vides dans les véhicules, contribue à réduire les problèmes de congestion, d’émissions et de dépendance aux combustibles fossiles. Dans cette thèse, nous étudions les problèmes de synchronisation d’itinéraires et d’appariement relatifs au covoiturage avec une prise en compte explicite des contraintes de protection des données de localisation (origine, destination). Les solutions proposées dans cette thèse combinent des algorithmes de calcul d’itinéraires multimodaux avec plusieurs techniques de protection de la vie privée telles que le chiffrement homomorphe, l’intersection sécurisée d’ensembles, le secret partagé, la comparaison sécurisée dentier. Elles garantissent des propriétés de protection de vie privée comprenant l’anonymat, la non-chainabilité et la minimisation des données. De plus, elles sont comparées à des so- lutions classiques, ne protégeant pas la vie privée. Nos expérimentations indiquent que les contraintes de protection des données privées peuvent être prise en compte dans les services de covoiturage sans dégrader leurs performances.

Abstract

The emergence of mobile phones and connected objects has profoundly changed our daily lives. These devices, thanks to the multitude of sensors they embark, allow access to a broad spectrum of services. In particular, position sensors have contributed to the development of location-based services such as navigation, ridesharing, real-time congestion tracking. . . Despite the comfort offered by these services, the collection and processing of location data seriously infringe the privacy of users. In fact, these data can inform service providers about points of interests (home, workplace, sexual orientation), habits and social network of the users. In general, the protection of users’ privacy can be ensured by legal or technical provisions. While legal measures may discourage service providers and malicious individuals from infringing users’ privacy rights, the effects of such measures are only observable when the offense is already committed and detected. On the other hand, the use of privacy-enhancing technologies (PET) from the design phase of systems can reduce the success rate of attacks on the privacy of users. The main objective of this thesis is to demonstrate the viability of the usage of PET as a means of location data protection in ridesharing services. This type of location-based ser- vice, by allowing drivers to share empty seats in vehicles, helps in reducing congestion, CO2 emissions and dependence on fossil fuels. In this thesis, we study the problems of synchro- nization of itineraries and matching in the ridesharing context, with an explicit consideration of location data (origin, destination) protection constraints. The solutions proposed in this thesis combine multimodal routing algorithms with sev- eral privacy-enhancing technologies such as homomorphic encryption, private set intersection, secret sharing, secure comparison of integers. They guarantee privacy properties including anonymity, unlinkability, and data minimization. In addition, they are compared to conven- tional solutions, which do not protect privacy. Our experiments indicate that location data protection constraints can be taken into account in ridesharing services without degrading their performance.

Mots-Clés / Keywords
Privacy; Ridesharing; Privacy enhancing technologies; Vie privée; Covoiturage; Technologies renforçant la vie privée;

142777
17471
26/12/2017

Algorithm for the power control and distribution unit - PCDU Nanosat

E.HEBRARD, C.ARTIGUES

ROC

Rapport de Contrat : EREMS Contract 67696 - Final report, Décembre 2017, 27p. , N° 17471

Non diffusable

141915
17126
06/12/2017

Complexity results and algorithms for an integrated single machine scheduling and outbound delivery problem with fixed sequence

A.CHEREF, A.AGNETIS, C.ARTIGUES, J.C.BILLAUT

ROC, UNISI, LI

Revue Scientifique : Journal of Scheduling, Vol.20, N°6, pp.681-693, Décembre 2017 , N° 17126

Lien : https://hal.archives-ouvertes.fr/hal-01529299

Diffusable

Plus d'informations

Abstract

In this paper, we consider an integrated production and outbound delivery scheduling problem. In particular, we address the situation in which the scheduling sequence and the delivery sequence are the same and predefined. A set of jobs are processed on a single machine and finished jobs are delivered to the customers by a single capacitated vehicle. Each job has a processing time and transportation times between customers are taken into account. Since the sequence is given, the problem consists to form batches of jobs and our objective is to minimize the sum of the delivery times or general functions of the delivery times. The NP-hardness of the general problem is established and a pseudopolynomial time dynamic programming algorithm is given. Some particular cases are treated, for which NP-hardness proofs and polynomial time algorithms are given. Finally, a fixed-parameter tractability result is given.

141652
17419
05/12/2017

Robust basic cyclic scheduling problem

I.HAMAZ, L.HOUSSIN, S.CAFIERI

ROC, ENAC

Rapport LAAS N°17419, Décembre 2017, 21p.

Lien : https://hal.archives-ouvertes.fr/hal-01635856

Diffusable

Plus d'informations

Abstract

This paper addresses the Basic Cyclic Scheduling Problem where the processing times are affected by uncertainties. We formulate the problem as a two-stage robust optimization problem with polyhedral uncertainty set. We propose three exact algorithms for solving the problem. Two of them use a negative circuit detection algorithm as a subroutine and the last one is an Howard's algorithm adaptation. Results of numerical experiments on randomly generated instances show that the Howard's algorithm adaptation yields efficient results and opens perspectives on more difficult robust cyclic scheduling problems.

141640
17434
04/12/2017

Inventory routing problems with explicit energy consideration

Y.HE

ROC

Doctorat : Université de Toulouse III - Paul Sabatier, 4 Décembre 2017, 188p., Président: , Rapporteurs: M.G.SPERANZA, F.SEMET, Examinateurs: N.ABSI, D.QUADRI, Directeurs de thèse: N.JOZEFOWIEZ, C.BRIAND , N° 17434

Lien : https://hal.laas.fr/tel-01675497

Diffusable

Plus d'informations

Résumé

Dans le problème de tournées avec gestion de stock ou “Inventory Routing Problem” (IRP), le fournisseur a pour mission de surveiller les niveaux de stock d’un ensemble de clients et gérer leur approvisionnement en prenant simultanément en compte les coûts de transport et de stockage. Etant données les nouvelles exigences de développement durable et de transport écologique, nous étudions l’IRP sous une perspective énergétique, peu de travaux s’étant intéressés à cet aspect. Plus précisément, la thèse identifie les facteurs principaux influençant la consommation d’énergie et évalue les gains potentiels qu’une meilleure planification des approvisionnements permet de réaliser. Un problème relatif à l’approvisionnement en composants de chaînes d’assemblage d’automobiles est tout d’abord considéré pour lequel la masse transportée, la dynamique du véhicule et la distance parcourue sont identifiés comme les principaux facteurs impactant la consommation énergétique. Ce résultat est étendu à l’IRP classique et les gains potentiels en termes d’énergie sont analysés. Un problème industriel de tournées avec gestion de stock est ensuite étudié et résolu, notamment à l’aide d’une méthode de génération de colonnes. Ce problème met en évidence les limitations du modèle IRP classique, ce qui nous a amené à définir un modèle d’IRP plus réaliste. Finalement, une méthode de décomposition basée sur la relaxation lagrangienne est développée pour la résolution de ce problème dans le but de minimiser la consommation énergétique.

Abstract

The thesis studies the Inventory Routing Problem (IRP) with explicit energy consideration. Under the Vendor Managed Inventory (VMI) model, the IRP is an integration of the inventory management and routing, where both inventory storage and transportation costs are taken into account. Under the new sustainability paradigm, green transport and logistics has become an emerging area of study, but few research focus on the ecological aspect of the classical IRP. Since the classical IRP concentrates solely on the economic benefits, it is worth studying under the energy perspective. The thesis gives an estimation of the energetic gain that a better supplying plan can provide. More specifically, this thesis integrates the energy consumption into the decision of the inventory replenishment and routing. It starts with a part supplying problem in car assembly lines, where the transported mass, the vehicle dynamics and the travelled distance are identified as main energy influencing factors. This result is extended to the classical IRP with energy objective to show the potential energy reduction that can be achieved. Then, an industrial challenge of IRP is presented and solved using a column generation approach. This problem put the limitations of the classical IRP model in evidence, which brings us to define a more realistic IRP model on a multigraph. Finally, a Lagrangian relaxation method is presented for solving this new model with the aim of energy minimization.

Mots-Clés / Keywords
Inventory routing problem; Logistics; Energy; Problème de tournées de véhicules avec gestion de stock; Logistique; Energie;

141693
17478
01/12/2017

Heuristics and lower bounds for minimizing fuel consumption in hybrid-electrical vehicles

S.U.NGUEVEU , S.CAUX, F.MESSINE, M.GUEMRI

ROC, LAPLACE

Revue Scientifique : 4OR: A Quarterly Journal of Operations Research, Vol.15, N°4, pp.407-430, Décembre 2017 , N° 17478

Lien : https://hal.archives-ouvertes.fr/hal-01671023

Diffusable

Plus d'informations

Abstract

In hybrid electric vehicles, the electrical powertrain system has multiple energy sources that it can gather power from to satisfy the propulsion power requested by the vehicle at each instant. This paper focusses on the minimization of the fuel consumption of such a vehicle, taking advantage of the different energy sources. Based on global optimization approaches, the proposed heuristics find solutions that best split the power requested between the multi-electrical sources available. A lower bounding procedure is introduced to validate the quality of the solutions. Computational results show a significant improvement over previous results from the literature in both the computing time and the quality of the solutions.

142053
Les informations recueillies font l’objet d’un traitement informatique destiné à des statistiques d'utilisation du formulaire de recherche dans la base de données des publications scientifiques. Les destinataires des données sont : le service de documentation du LAAS.Conformément à la loi « informatique et libertés » du 6 janvier 1978 modifiée en 2004, vous bénéficiez d’un droit d’accès et de rectification aux informations qui vous concernent, que vous pouvez exercer en vous adressant à
Pour recevoir une copie des documents, contacter doc@laas.fr en mentionnant le n° de rapport LAAS et votre adresse postale. Signalez tout problème de dysfonctionnement à sysadmin@laas.fr. http://www.laas.fr/pulman/pulman-isens/web/app.php/