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

577documents trouvés

15589
10/02/2017

The vehicle routing problem with transhipment facilities

R.BALDACCI, S.U.NGUEVEU , R.WOLFER CALVO

Bologne, ROC, LIPN

Revue Scientifique : Transportation Science, 47p., Février 2017, doi http://dx.doi.org/10.1287/trsc.2016.0711 , N° 15589

Diffusable

Plus d'informations

Abstract

This paper proposes an exact method for solving an optimization problem arising in several distribution networks where customers can be served directly, using vehicle routes from a central depot, or through transhipment facilities. The problem consists of optimizing the following inter-dependent decisions: selecting transhipment facilities, allocating customers to these facilities, and designing vehicle routes emanating from a central depot to minimize the total distribution cost. This problem is called the Vehicle Routing Problem with Transhipment Facilities (vrptf). The paper describes two integer-programming formulations for the vrptf, i.e., an edge-flow based formulation and a Set Partitioning (SP) based formulation. The LP-relaxation of the two formulations are further strengthened by the addition of different valid inequalities. We also describe two new route relaxations used by dual ascent heuristics to find near-optimal dual solutions of LP-relaxation of the SP model. The valid inequalities and the route relaxations are used in a branch-and-cut-and-price approach to solve the problem to optimality. The proposed method is tested on a large family of instances, including real-world examples. The computational results obtained indicate the effectiveness of the proposed method.

138955
17009
31/01/2017

Constraint programming for planning test campaigns of communications satellites

E.HEBRARD, M.J.HUGUET, D.VEYSSEIRE, L.SAUVAN, B.CABON

ROC, Airbus Defence & Sp

Revue Scientifique : Constraints, Vol.22, N°1, pp.73-89, Janvier 2017 , N° 17009

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

Diffusable

Plus d'informations

Abstract

The payload of communications satellites must go through a series of tests to assert their ability to survive in space. Each test involves some equipment of the payload to be active, which has an impact on the temperature of the payload. Sequencing these tests in a way that ensures the thermal stability of the payload and minimizes the overall duration of the test campaign is a very important objective for satellite manufacturers. The problem can be decomposed in two sub-problems corresponding to two objectives: First, the number of distinct configurations necessary to run the tests must be minimized. This can be modeled as packing the tests into configurations, and we introduce a set of implied constraints to improve the lower bound of the model. Second, tests must be sequenced so that the number of times an equipment unit has to be switched on or off is minimized. We model this aspect using the constraint Switch, where a buffer with limited capacity represents the currently active equipment units, and we introduce an improvement of the propagation algorithm for this constraint. We then introduce a search strategy in which we sequentially solve the sub-problems (packing and sequencing). Experiments conducted on real and random instances show the respective interest of our contributions.

138720
16393
01/01/2017

Finding a Nash Equilibrium and an optimal sharing policy for multi-agent network expansion game

N.CHAABANE, A.AGNETIS, C.BRIAND, M.J.HUGUET

ROC, UNISI

Revue Scientifique : Networks, Vol.69, N°1, pp.94-109, Janvier 2017 , N° 16393

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

Diffusable

Plus d'informations

Abstract

In this work, a multi-agent network flow problem is addressed , aiming at characterizing the properties of stable flows and allowing their computation. Two types of agents are considered: transportation-agents, that carry a flow of products on a given network and another agent, either a producer or a customer, who is willing to ship (receive, respectively) products. Every transportation-agent controls a set of arcs, each having a capacity that can be increased up to a certain point at a given cost. The other agent (i.e., the customer/producer) is interested in maximizing the flow transshipped through the network. To this aim, we assume it offers the transportation-agents a reward that is proportional to the realized flow value. This particular multi-agent framework is referred to as a Multi-Agent network expansion game. We characterize and find particular stable strategies (i.e., Nash equilibria) that are of interest for this game. We particularly focus on the problem of finding a Nash Equilibrium and a sharing policy that maximize the value of the total flow. We prove that this problem is NP-hard in the strong sense and show how such a strategy can be characterized considering paths in specific auxiliary graphs. We also provide a mixed integer linear programming (MILP) formulation to solve the problem. Computational experiments are provided to prove the effectiveness of our approach and derive some insights for practitioners.

138233
16232
31/12/2016

Approximation of the parallel machine scheduling problem with additional unit resources

E.HEBRARD, M.J.HUGUET, N.JOZEFOWIEZ, A.MAILLARD, C.PRALET, G.VERFAILLIE

ROC, ONERA

Revue Scientifique : Discrete Applied Mathematics, Vol.215, pp.126-135, Décembre 2016, doi 10.1016/j.dam.2016.07.003 , N° 16232

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

Diffusable

Plus d'informations

Abstract

We consider the problem of minimizing the makespan of a schedule on m parallel machines of n jobs, where each job requires exactly one of s additional unit resources. This problem collapses to P ||C max if every job requires a different resource. It is therefore NP-hard even if we fix the number of machines to 2 and strongly NP-hard in general. Although very basic, its approximability is not known, and more general cases, such as scheduling with conflicts, are often not approximable. We give a (2 − 2 /(m+1))-approximation algorithm for this problem, and show that when the deviation in jobs processing times is bounded by a ratio ρ, the same algorithm approximates the problem within a tight factor 1 + ρ (m−1)/n. This problem appears in the design of download plans for Earth observation satellites, when scheduling the transfer of the acquired data to ground stations. Within this context, it may be required to process jobs by batches standing for the set of files related to a single observation. We show that there exists a (2 − 1/m)-approximation algorithm respecting such batch sequences. Moreover, provided that the ratio ρ, between maximum and minimum processing time, is bounded by ⌊s−1/ m−1⌋, we show that the proposed algorithm approximates the optimal schedule within a factor 1 + (s−1)/n.

138652
16495
20/12/2016

Octal Games on Graphs: The game 0.33 on subdivided stars and bistars

L.BEAUDOU, P.COUPECHOUX, A.DAILLY, S.GRAVIER, J.MONCEL, A.PARREAU, E.SOPENA

UBP, ROC, LIRIS, UJF, LABRI

Rapport LAAS N°16495, Décembre 2016, 21p.

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

Diffusable

Plus d'informations

Abstract

Octal games are a well-defined family of two-player games played on heaps of counters, in which the players remove alternately a certain number of counters from a heap, sometimes being allowed to split a heap into two nonempty heaps, until no counter can be removed anymore. We extend the definition of octal games to play them on graphs: heaps are replaced by connected components and counters by vertices. Thus, an octal game on a path Pn is equivalent to playing the same octal game on a heap of n counters. We study one of the simplest octal games, called 0.33, in which the players can remove one vertex or two adjacent vertices without disconnecting the graph. We study this game on trees and give a complete resolution of this game on subdivided stars and bistars.

138679
16409
09/12/2016

A new glideslope guidance algorith for minimum-fuel fixed-time elliptic rendezvous using semidefinite programming

Y.ARIBA, D.ARZELIER, L.URBINA IGLESIAS, C.LOUEMBET

MAC, ROC

Rapport LAAS N°16409, Décembre 2016, 8p.

Diffusable

138289
16424
09/12/2016

Polyhedral results and valid inequalities for the continuous energy-constrained scheduling problem

M.NATTAF, T.KIS, C.ARTIGUES, P.LOPEZ

ROC, MTA

Rapport LAAS N°16424, Décembre 2016, 9p.

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

Diffusable

Plus d'informations

Abstract

This paper addresses a scheduling problem with a cumulative, continuously-divisible and renewable resource with limited capacity. During its processing, each task consumes a part of this resource, which lies between a minimum and a maximum requirement. A task is finished when a certain amount of energy is received by it within its time window. This energy is received via the resource and an amount of resource is converted into an amount of energy with a non-decreasing, continuous and linear efficiency function. The goal is to minimize the resource consumption. The paper focuses on an event based mixed integer linear program, providing several valid inequalities which are used to improve the performance of the model. Furthermore, we give a minimal description of the polytope of all feasible assignments to the on/off binary variable for a single activity along with a dedicated separation algorithm. Computational experiments are reported in order to show the effectiveness of the results.

138314
16478
07/12/2016

Harnessing tractability in constraint satisfaction problems

C.CARBONNEL

ROC

Doctorat : INP de Toulouse, 7 Décembre 2016, 138p., Président: N.CREIGNOU, Rapporteurs: S.SZEIDER, S.ZIVNY, Examinateurs: P.JEGOU, Directeurs de thèse: M.CCOPER, E.HEBRARD , N° 16478

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

Diffusable

Plus d'informations

Abstract

The Constraint Satisfaction Problem (CSP) is a fundamental NP-complete problem with many applications in artificial intelligence. This problem has enjoyed considerable scientific attention in the past decades due to its practical usefulness and the deep theoretical questions it relates to. However, there is a wide gap between practitioners, who develop solving techniques that are efficient for industrial instances but exponential in the worst case, and theorists who design sophisticated polynomial-time algorithms for restrictions of CSP defined by certain algebraic properties. In this thesis we attempt to bridge this gap by providing polynomial-time algorithms to test for membership in a selection of major tractable classes. Even if the instance does not belong to one of these classes, we investigate the possibility of decomposing efficiently a CSP instance into tractable subproblems through the lens of parameterized complexity. Finally, we propose a general framework to adapt the concept of kernelization, central to parameterized complexity but hitherto rarely used in practice, to the context of constraint reasoning. Preliminary experiments on this last contribution show promising results.

Résumé

Le problème de satisfaction de contraintes (CSP) est un problème NP-complet classique en intelligence artificielle qui a suscité un engouement important de la communauté scientifique grâce à la richesse de ses aspects pratiques et théoriques. Cependant, au fil des années un gouffre s’est creusé entre les praticiens, qui développent des méthodes exponentielles mais efficaces pour résoudre des instances industrielles, et les théoriciens qui conçoivent des algorithmes sophistiqués pour résoudre en temps polynomial certaines restrictions de CSP dont l’intérˆet pratique n’est pas avéré. Dans cette thèse nous tentons de réconcilier les deux communaut és en fournissant des méthodes polynomiales pour tester automatiquement l’appartenance d’une instance de CSP à une sélection de classes traitables majeures. Anticipant la possibilité que les instances réelles ne tombent que rarement dans ces classes traitables, nous analysons également de manière systématique la possibilité de décomposer efficacement une instance en sous-problèmes traitables en utilisant des méthodes de complexité paramétrée. Finalement, nous introduisons un cadre général pour exploiter dans les CSP les idées développées pour la kernelization, un concept fondamental de complexité paramétrée jusqu’ici peu utilisé en pratique. Ce dernier point est appuyé par des expérimentations prometteuses.

Mots-Clés / Keywords
Backdoor; Classe traitable; Complexité paramétrée; Kernelization; Polymorphisme; Problème de satisfaction de contraintes;

138577
16090
01/12/2016

Meeting points in ridesharing: a privacy-preserving approach

U.M.AIVODJI, S.GAMBS, M.J.HUGUET, M.O.KILLIJIAN

TSF, UQAM, ROC

Revue Scientifique : Transportation Research Part C: Emerging Technologies, Vol.72, pp.239-253, Décembre 2016 , N° 16090

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

Diffusable

Plus d'informations

Abstract

Nowadays, problems of congestion in urban areas due to the massive usage of cars, last-minute travel needs and progress in information and communication technologies have fostered the rise of new transportation modes such as ridesharing. In a ridesharing service, a car owner shares empty seats of his car with other travelers. Recent ridesharing approaches help to identify interesting meeting points to improve the efficiency of the ridesharing service (i.e., the best pickup and drop-off points so that the travel cost is competitive for both driver and rider). In particular, ridesharing services, such as Blablacar or Carma, have become a good mobility alternative for users in their daily life. However, this success has come at the cost of user privacy. Indeed in current's ridesharing services, users are not in control of their own data and have to trust the ridesharing operators with the management of their data. In this paper, we aim at developing a privacy-preserving service to compute meeting points in ridesharing, such that each user remains in control of his location data. More precisely, we propose a decentralized architecture that provides strong security and privacy guarantees without sacrificing the usability of ridesharing services. In particular, our approach protects the privacy of location data of users. Following the privacy-by-design principle, we have integrated existing privacy enhancing technologies and multimodal shortest path algorithms to privately compute mutually interesting meeting points for both drivers and riders in ridesharing. In addition, we have built a prototype implementation of the proposed approach. The experiments, conducted on a real transportation network, have demonstrated that it is possible to reach a trade-off in which both the privacy and utility levels are satisfactory.

138174
16373
17/11/2016

Calcul d'itinéraires multiples et de trajets synchronisés dans des réseaux de transport multimodaux

G.SCANO

ROC

Doctorat : INSA de Toulouse, Novembre 2016, 132p., Président: E.NERON, Rapporteurs: C.GUERET, A.OULAMARA, Examinateurs: N.EL FAOUZI, P.LACOMME, Directeurs de thèse: M.J.HUGUET, S.U.NGUEVEU , N° 16373

Non diffusable

Plus d'informations

Abstract

Efficiency and simplicity are two conditions upon which the use of a transportation system is relevant. May it be intentional or imposed, an increasing mobility triggers the need to enhance the transportation offer. In turn, such a response encourages an even more demanding mobility in a constantly adapting cycle. In parallel, new and forthcoming means of transportation emerge from time to time with unknown practices and renewed actors : exactly like what carpooling is stirring at the moment. Passenger information systems can technically deal with such evolutions thanks to improved technologies but they still struggle to keep up with constantly changing usage expectations. From this perspective the computation of several paths from an origin to a destination becomes increasingly relevant. This issue is even more crucial in dense transportation networks in which many modes and lines of transportation are combined. Indeed, giving some travelling choices to the end user reduces the feeling of exclusion, anxiety and the lack of understanding which may arise when facing arbitrary decisions dictated by a software or an internet application. It is also helpful to estimate the quality of the transportation offer since the more paths exist to go from point A to point B within a fixed time window, the better the service is. This thesis focuses on the computation of such alternatives by the gradually increasing enumeration of paths between two points. Given this input, the pruning necessary to obtain such a diverse selection is assumed not to be known in advance. It is left up to transportation professionals who may choose a fitted solution based on their specific knowledge and objectives. Another subject studied in this thesis concerns the itinerary synchronisation of several users for various social uses such as shared travels. It is here seen from the perspective of carpooling. Considering only two users, the problem is to minimise the travelling cost of the users under the constraint that they must share some part of their respective trips with one another. Solving this problem is equivalent to finding a pick up point and a drop off location between which both paths overlap. Multiple corner cases concerning the transportation conditions of each user as well as the special cases of shared origins or destinations are studied. The constraints on the arrival and/or departure times may also vary. Last but not least and since the driver is often penalized when giving up a lift, the restriction to a maximal detour the driver accepts, compared to his shortest path, is analysed with respect to the benefits such a limitation generates. This thesis was funded by the MobiGIS company under the CIFRE (Industrial Agreement of Training through Research) researching context. The related work consisted in the practical implementation of mobility solutions within the framework of the company as well as the experimental performances evaluation of the algorithms proposed to solve them.

Résumé

L’utilisation des réseaux de transport est conditionnée par l’efficacité et la simplicité de leur utilisation. En réponse à une mobilité exacerbée, volontaire ou subie, l’offre de transport se développe et motive tout à la fois, en un cycle continu, des déplacements encore plus exigeants. De manière complémentaire, la mobilité est bousculée par l’arrivée de nouvelles modalités de transport pouvant faire émerger, comme dans le cadre du covoiturage, des acteurs ou des pratiques jusqu’alors inexistants. Si la technologie permet de suivre cette évolution dans les services d’information aux voyageurs, il reste toujours à satisfaire des attentes déterminées par des usages en constante évolution. C’est de ce point de vue que l’obtention de chemins multiples pour relier une origine à une destination est un facteur qui n’est plus à négliger, surtout dans des réseaux de transport denses et comportant de nombreux modes et lignes de transport. Une liberté dans le choix laissé à l’utilisateur du réseau réduit les sentiments d’exclusion, d’incompréhension ou d’anxiété qui peuvent survenir face à une application logicielle ou sur internet et qui effectuent des choix arbitraires de façon autoritaire. De plus, cela permet de vérifier la qualité de l’offre de transport, car plus il existe de moyens différents pour effectuer un trajet dans un intervalle de temps donné, meilleur est le service. Cette thèse s’intéresse au calcul de telles alternatives par le biais de l’énumération par coût croissant des chemins entre deux points, puis par le filtrage de ceux-ci suivant des critères, supposés quelconques et laissés à l’appréciation des professionnels de transport qui peuvent ainsi faire varier les angles d’analyses de leurs offres. Par ailleurs, la synchronisation de trajets de plusieurs utilisateurs, en vue d’usages sociaux ou de déplacements mutualisés, est étudiée dans ce manuscrit sous l’angle du covoiturage. En ne considérant que deux usagers, l’objectif est de minimiser le temps de trajet global des participants sous la contrainte qu’ils partagent une partie de leur chemin entre un point de rencontre et un point de séparation qu’il faut alors déterminer. Sont également étudiées les variantes associées au changement des conditions de transport de chacun des participants comme l’établissement d’une origine ou d’une destination commune parallèlement à des contraintes sur les heures de départ ou d’arrivée des usagers. Enfin, puisque la voiture est très souvent pénalisée par la prise en charge d’un piéton, il convient d’étudier comment ce détour peut être contraint et les impacts sur les gains que cette limitation engendre. Cette thèse a été réalisée dans un contexte CIFRE pour la société MobiGIS. Les travaux qui s’y rapportent ont fait l’objet de réalisations pratiques tant pour fournir des solutions de mobilité dans le cadre des activités de l’entreprise que pour évaluer expérimentalement les performances des algorithmes proposés pour les résoudre.

Mots-Clés / Keywords
Itinéraires alternatifs; Itinéraires synchronisés; Réseaux de transport multimodaux; Alternative itineraries; Multimodal transportatin network; Synchronised itineraries;

138014
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/