Big Data application : UK Pubs Traveling Salesman Problem

Source: UK Pubs Traveling Salesman Problem



Nearly everyone in the UK knows by heart the best path to take them over to their favorite public house. But what about jotting down the shortest route to visit every pub in the country and return home safely? That is what we set out to do.

Okay, maybe every pub is overstating the goal. Pubs in the UK are closing shop or starting up, fresh and new, all of the time. Any route would be out-of-date by the time it was created. So we set a more modest goal: find the shortest route to visit some 24,727 stops found on the great Web site Pubs Galore – The UK Pub Guide.

This is a concrete target. But still an overstatement. Only a real local could possibly know every shortcut, slipping between buildings and along dark allies, to find the absolute best way to reach The Fiddler’s Elbow or The Bald Faced Stag. This is well out of reach for a humble team of mathematicians.

Here we rely on the fantastic service provided by Google Maps. Ask Google for the shortest way to walk from The Elbow over to The Stag and it will respond with excellent step-by-step directions. The level of detail covered by Google Maps is amazing.

So this is our challenge. Using geographic coordinates of 24,727 pubs provided by Pubs Galore and measuring the distance between any two pubs as the length of the route produced by Google Maps, what is the shortest possible tour that visits all 24,727 and returns to the starting point?

Well, almost. We need to make one final assumption. It sounds like something only a mathematician would consider, but we have to assume that the route Google suggests for walking between The Fiddler’s Elbow and The Bald Faced Stag is no shorter than the route a smart crow would fly. This makes it conceivable to solve the problem without actually asking Google for the distance to travel between each pair of pubs, an important consideration since there are 305,699,901 pairs and Google puts a cap of 2,500 distance requests per day.

This is the problem we have solved. The optimal tour has length 45,495,239 meters. To be clear, our main result is that there simply does not exist any pub tour that is even one meter shorter (measuring the length using the distances we obtained from Google) than the one produced by our computation. It is the solution to a 24,727-city traveling salesman problem (TSP).

The UK Pubs tour is easily the largest such road-distance TSP that has been solved to date, having over 100 times more stops than any road-distance example solved previously by other research groups.

The Big Picture

The work was carried out over the past two years. We, of course, did not have in mind to bring everything mathematics has to bear in order to improve the lot of a wandering pub aficionado. Rather, we use the UK pubs problem as a means for developing and testing general-purpose optimization methods. The world has limited resources and the aim of the applied mathematics fields of mathematical optimization and operations research is to create tools to help us to use these resources as efficiently as possible.

For general information on mathematical modeling and its impact on industry, commerce, medicine, and the environment, we point you to a number of societies that support mathematics research and education: American Mathematical Society, Mathematical Association of America, Mathematical Optimization Society, INFORMS (operations research),London Mathematical Society, and SIAM (applied mathematics).

Research Team

William Cook, Combinatorics and Optimization, University of Waterloo, Canada
Daniel Espinoza, Gurobi Optimization, USA
Marcos Goycoolea, School of Business, Universidad Adolfo Ibanez, Chile
Keld Helsgaun, Computer Science, Roskilde University, Denmark

The Tour

It is not easy to convey the structure and complexity of the optimal tour. A list of the 24,727 pubs, one after the other, in the correct order, resembles a good-sized phone book. Perhaps the best way to get a quick view is to look at a line drawing, where the solution is displayed without indicating the many destinations.

Small line image of tour
<figcaption=”figure-caption”>Click image for a larger view.

You see that we obviously cannot walk several of the indicated routes: to reach the Isle of Man, Northern Ireland, and the islands of Scotland, the tour uses scheduled passenger-ferry routes provided by Google’s direction services.

To show a detailed view, we make use of the Google Maps drawing tools to display an interactive version of the tour, where you can zoom in and pan from one region to another. The link is given below, but first a word of warning: the map contains a great deal of information and it can take a minute or so to load. We provide tips for using the map on the tour page.

Screen image of map
<figcaption=”figure-caption”>Click image for an interactive map.

If the map refuses to load for you, please have a look at the tour page for high-resolution screen shots, as well as further information about the route.


How do we know the tour is the shortest possible? Clearly we did not check every tour, one by one by one. Indeed, the first thing you learn about the TSP is that it is impossible to solve in this way. If you have N cities, then, starting from any point, you have N-1 possibilities for the second city. Then N-2 possibilities for the third city, and so on. The total number of tours is obtained by multiplying these values: N-1 x (N-2) x (N-3) x . . . x 3 x 2 x 1. Now this is a big number. For the pubs problem, it is roughly 1 followed by 100,000 zeroes. That is in an unimaginably large number of possibilities. Even for 50 cities, the world’s fastest supercomputer has no hope of going through the full count of tours one by one to pick out the shortest.

But this by itself does not mean we can’t possibility solve an example of the TSP. If you have 50 words to put into alphabetical order, you don’t worry about the 50 x 49 x 48 x … x 3 x2 x 1 possible lists you could create. You just sort the words from first to last and build the one correct list among the huge number of possibilities.

For the TSP we don’t know of any simple and fast solution method like we have for sorting words. And, for technical reasons, it is believed that there may be large, nasty TSP examples that no one can ever solve. (If you are interested in this and could use an extra $1,000,000 [≈ 1965 typical CEO pay], check out the P vs NP problem.) But if you need to plot a 50-point route for a holiday or to compute the order of 1,000 items on a DNA strand, then mathematics can help, even if you need the absolute shortest-possible solution.

The way to proceed is via a process known as the cutting-plane method. If you have twenty minutes to spare, there is a video explaining the method and how it is used to solve the TSP (in the pleasing voice of Siri). If you are in a hurry, here is how I try to describe the process in a short piece in Scientific American

The idea is to follow Yogi Berra’s advice “When you come to a fork in the road, take it.” A tool called linear programming allows us to do just this, assigning fractions to roads joining pairs of cities, rather than deciding immediately whether to use a road or not. It is perfectly fine, in this model, to send half a salesman along both branches of the fork.

The process begins with the requirement that, for every city, the fractions assigned to the arriving and departing roads each sum to one. Then, step-by-step, further restrictions are added, each involving sums of fractions assigned to roads. Linear programming eventually points us to the best decision for each road, and thus the shortest possible route.

Our pubs computation used a beefed-up version of the Concorde implementation of the TSP cutting-plane method. Even if you are in a hurry, you might want to see for yourself how the process solves smaller examples on an iPhone or iPad by downloading the free Concorde App.

In working with road data, we were faced with the additional challenge of finding the correct TSP solution even though we could not possibly ask Google for all 305,699,901 pub-to-pub distances. To handle this, we ran the cutting-plane method in tandem with a beefy variant of Keld Helsgaun’s LKH code.

LKH combines a powerful local-search technique with a genetic algorithm to produce a high-quality tour, say of length U. Along the way, LKH discovers pairs of pubs that look promising to include in any short tour, so for these pairs we ask Google for the correct walking distances.

While this is going on, Concorde’s cutting-plane method finds a fractional tour of value L. From the way this is constructed with linear programming, we know for sure that no TSP tour can have value less than L. During this process, Concorde also discovers pairs of pubs that look promising, in this case for fractional solutions, so we ask Google also for these distances.

Any new data obtained from Google is shared between LKH and Concorde, while both codes continue to look for better results. That is, we aim to decrease the value of U by finding better tours, and we aim to increase the value of L by adding further restrictions to the fractional linear-programming model. At any point, we know the optimal tour length is trapped between L and U, that is, we know the difference between the length of our tour and the length of an optimal tour is at most UL. The name of the game is to reduce this gap UL as quickly as we can.

Eventually, in the pubs computation, the algorithms inside LKH and Concorde became satisfied that they had an adequate collection of Google distances, LKH could find no further improvements in its tour, and the cutting-plane method in Concorde could only produce tiny improvements in the value of its fractional tour. At this point, we had L = 45,492,247 andU = 45,495,239, and thus a gap of 2,992 meters.

To finish off the problem, we then turned to Concorde’s branch-and-bound search procedure. In this process, the collection of tours is repeatedly subdivided and the cutting-plane method is applied to the resulting TSP subproblems. The simplest form of the division is to select a pair of pubs, say The Black Dog and The Duke of Cornwall in Weymouth, and consider first only tours where the two pubs are visited consecutively, then consider only tours where, between the stops at The Dog and The Duke, we drop in on at least one other pub along the way. This selection divides the set of all tours neatly into two subsets.

In this this final phase of the computation, we processed a large, but manageable, collection of 4,231 subproblems. The total amount of computer time was 305.2 days on a single processor core of a Linux server. We didn’t actually have to wait the full 10 months for the results, since we ran the search in parallel on up to 48 cores.

Click here to see a drawing of the search tree, where the position of a subproblem corresponds to the value of its fractional tour. For a closer look, here is a pdf file for the tree.

The computing time was reasonable enough to allow us to run the branch-and-bound phase a second time, using different settings to test the selection rule for the subdivisions. This second run processed a total of 5,687 subproblems in a total of 1381.1 days. Of course, it again produced the same optimal value of 45,495,239 meters.


If you are interested in creating your own local pub tour, the best bet for data is to go back to the original sources, Pubs Galore for locations and Google Maps for up-to-date walking distances. But the information provided by these sources changes over time. Therefore, to document the 24,727-stop TSP instance we have solved, we provide the raw data needed to reproduce the travel distances on the data page.

Tour-Finding History

Early computational studies focused on the most natural class of salesman problems: select an interesting group of cities, look up the point-to-point distances in a road atlas, and have a go at finding the shortest tour. Record-setting solutions were found by legendary figures in applied mathematics and computer science.

The first reference, in particular, is widely viewed as the most important paper in the history of the broad fields of discrete optimization and integer programming. The links are to technical research papers. For lighter viewing, have a quick look at a slide show of these record-breaking results.In the late 1970s, the focus switched to geometric examples of the TSP, where cities are points drawn on a sheet of paper and travel is measured by straight-line distances. The reasons were twofold. First, with over 100 stops it became difficult to obtain driving distances along road networks: printed road atlases included distances only for major cities. Second, there were classes of industrial problems that neatly fit into the geometric TSP setting. Indeed, the next world record, set in 1980 by Harlan Crowder and Manfred Padberg, consisted of locations of 318 holes that had to be drilled into a printed-circuit board.

Geometric TSP instances, arising in applications or from geographic locations, were gathered together in the TSPLIB by Gerhard Reinelt. This collection became the standard testbed for researchers. The largest of the instances, having 85,900 points arising in a VLSI application, was solved by Applegate et al. in 2006.

The geometric data sets are worthy adversaries, but the large industrial instances have points clustered into straight lines. These examples are punching below their weight, likely missing aspects of the complexity of the road TSP problems.

pla85990 zoom

So, why not take advantage of the modern day atlas provided by Google Maps? One of the first people to put together a TSP challenge instance with Google data was Randal Olson, who found a good tour to visit 50 USA landmarks. His tour was the subject of one of the most heavily reported math stories in 2015, including an article in the Washington Post and aradio interview on NPR’s Weekend Edition. See our discussion of the 50 landmarks problem.

Following Olson’s work, a number of people created similar touring problems in the US and abroad. The largest of these was a route through the 200 Tesla Superchargers in the United States. When I wrote that the UK pubs problem was a factor of 100 larger than previously solved road-TSP examples, it was in reference to this work by Mortada Mehyar.

Okay, the factor of 100 is not really true. While building up the expertise, algorithms, and software to tackle the UK pubs example, we solved a number of smaller instances along the way. The largest of these has 3,100 points in the US. But these were solved with the bigger target in mind.

Our final goal is even larger: a shortest-possible walking tour through 50,000 stops from the US National Register of Historic Places. This problem is quite a beast. We currently have a tour of length 350,201,525 meters [≈ Moon’s orbital distance from Earth]. That is a little less than the distance to the moon. But we don’t know if this is actually the shortest tour. All we can say at this point (October 19, 2016) is that there you definitely have to walk at least 350,201,329 meters [≈ Moon’s orbital distance from Earth] to reach all 50,000 stops. So there might possibly be a tour that is 196 meters shorter than our tour. Ouch! Close is just not good enough.


Google Maps provided the interface between the real world and the abstract mathematical model of the TSP. The engineers at Google do all of the heavy lifting in dealing with paths, roads, traffic circles, construction sites, closures, detours, and on and on.

Pubs Galore – The UK Pub Guide is the source for the locations of the stops on our TSP tour. No matter where you are in the UK, the Pubs Galore site will help you find a cozy place for a meal and a drink.

The huge number of linear-programming models that arose in the computation were solved with the IBM CPLEX Optimizer. Many thanks to IBM for making their great software freely available for academic research.

Is A.I. the 4th industrial revolution ?

Ubiquitous, mobile supercomputing. Artificially-intelligent robots. Self-driving cars. Neuro-technological brain enhancements. Genetic editing. The evidence of dramatic change is all around us and it’s happening at exponential speed.

Previous industrial revolutions liberated humankind from animal power, made mass production possible and brought digital capabilities to billions of people. This Fourth Industrial Revolution is, however, fundamentally different. It is characterized by a range of new technologies that are fusing the physical, digital and biological worlds, impacting all disciplines, economies and industries, and even challenging ideas about what it means to be human.

Algorithmes prédictifs : la nouvelle force de vente

Anticiper les attentes du consommateur et lui proposer d’emblée le produit ou le service qu’il recherche. C’est ce que permet le marketing prédictif en exploitant toutes les données clients. Au menu : fidélisation, amélioration du taux de conversion et ventes additionnelles, en ligne comme dans les réseaux physiques. Décryptage et illustrations avec les hôtels Hyatt, Menlook, la Fnac, le Crédit Mutuel Arkéa, Voyage Privé, etc. Le marketing prédictif pour retrouver en ligne le niveau de conseil en (…)

Source: Les 3 parties du dossier – /le hub de La Poste, tendances du marketing relationnel

Le marketing prédictif pour retrouver en ligne le niveau de conseil en magasin

« La fête est finie ! » L’avertissement est lancé par Marc Ménasé, fondateur de Menlook, site spécialisé dans la mode en ligne qui enregistre plus de 4 millions de visites par mois. S’exprimant lors d’une manifestation organisée par l’EBG, un think-tank français dédié à l’innovation digitale, il explique : « Le e-commerce a connu des années exceptionnelles, mais la concurrence est aujourd’hui extrêmement brutale, et le consommateur a gagné en maturité. Se contenter de mettre des produits sur un site pour les vendre en achetant des mots-clés sponsorisés sur Google, c’est terminé. Particulièrement avec l’arrivée du mobile. »

« En e-commerce, le marketing prédictif améliore la conversion »

À l’instar de la plupart des sites de e-commerce, Menlook est confronté à un double phénomène. D’un côté, l’écran de ses clients devient plus petit : la moitié de son trafic s’opère désormais sur smartphone.« Sur le mobile, on doit aller à l’essentiel », pointe Marc Ménasé. Et de l’autre, son offre explose : avec sa place de marché, Menlook accueille maintenant 1 600 marques, comprenant à la fois des articles haut de gamme et d’autres plus basiques. C’est ici qu’entre en jeu le marketing prédictif. Objectif : proposer d’emblée à l’internaute les produits qu’il est le plus susceptible d’acheter. Sinon, il risque de se perdre dans l’offre et de zapper sur un autre site.

- Pour le patron de Menlook, les entreprises qui ont le mieux compris les enjeux actuels sont Amazon et Netflix : « À chaque étage de la fusée et à chaque interaction avec le client, ils mettent en œuvre le plus de solutions techno et marketing possibles pour pouvoir servir au client ce dont il a envie. » 35 % des ventes sur Amazon seraient ainsi générées par des suggestions de produits en fonction de la navigation des clients. Netflix doit lui aussi une grande part de sa réussite à son algorithme de recommandation : face à l’hyperchoix en matière de séries et de films, l’entreprise a développé un logiciel qui donne à ses abonnés des conseils très précis de programmes à regarder en fonction de ce qu’ils ont déjà vu et apprécié.

- « En e-commerce, le marketing prédictif permet d’améliorer la conversion », résume Laetitia Comès-Bancaud, cofondatrice d’Early Birds, qui édite une plateforme de marketing prédictif permettant de personnaliser l’expérience client. Pour elle, l’ambition est de retrouver en ligne le niveau de conseil personnalisé qu’un client trouverait dans un magasin physique. « En boutique, sur le point de vente, c’est très facile de sonder une personne. En ligne, c’est plus compliqué. On est obligé de se baser sur les signaux qu’elle nous envoie », explique Laetitia Comès-Bancaud.

Plus d’infos :
- La table ronde organisée par Early Birds : « L’efficacité réelle du marketing prédictif »

Comment ça marche ?

Avez-vous déjà accepté la proposition d’un site de vous connecter à ses services grâce à votre compte Facebook ? Cela simplifie la procédure d’identification, mais cela permet également au site de recevoir de nombreuses informations à votre sujet. Il peut connaître vos centres d’intérêt, les marques avec lesquelles vous interagissez, les voyages que vous avez effectués, etc. De quoi nourrir un algorithme de recommandation.

- Mais le module Facebook Connect n’est qu’une des sources d’alimentation du marketing prédictif. La collecte de data commence par les données de navigation via les cookies déposés sur l’ordinateur de l’internaute. Viennent aussi les données du CRM pour les personnes déjà clientes. « Nous regardons aussi tous les signaux faibles, ajoute Laetitia Comès-Bancaud. Combien de temps une personne passe sur une page, comment elle va agir avec sa souris, quelles sont les activités qu’elle va avoir sur le site, le fait de mettre un produit en panier, une vue sur un produit, un achat, un like, etc. Ce sont toutes ces activités que nous ‘trackons’ et qui ensuite vont avoir un poids dans nos algorithmes, et qui vont permettre de bien sélectionner les produits. » Les algorithmes sont par ailleurs désormais très souvent « auto-apprenant ». On parle de machine learning : ils affinent leurs recommandations en fonction du comportement des internautes suite à leurs propositions initiales.

Plus d’infos :
- Cofidis retail

Big brother ou nouveau service pour le client ?

Le recours au marketing prédictif se développe notamment car l’accès aux technologies se démocratise. Plusieurs startups ont lancé des solutions plus facilement implémentables, avec des logiciels qui peuvent être disponibles en mode Saas (Software as a service : ils sont hébergés sur un serveur distant et proposés sur abonnement). Et de fait, le marketing prédictif gagne tous les canaux de la relation, permettant de personnaliser les contenus, de mieux cibler les campagnes d’emailing et même d’individualiser l’envoi de catalogues papier (lire 3 exemples de personnalisation de la relation client).

- Il devient aussi possible de générer des argumentaires personnalisés à l’attention des conseillers dans le réseau physique, en boutique ou au téléphone : ils peuvent ainsi disposer de la liste des produits ou services qu’un client est le plus susceptible d’acheter (lire Quand algorithmes et vendeurs humains coopèrent).

- Ces pratiques peuvent toutefois inquiéter. Même s’il n’est question que d’identifier les produits avec lesquels un internaute a le plus d’appétence, des questions émergent sur la protection de la vie privée. Des questions que la Fnac s’est posée, avant de se décider néanmoins à franchir le pas du marketing prédictif cet été. C’est ce qu’explique au magazine LSA Delphine Jamain, responsable de l’expérience client sur : « Nous nous freinions car nous redoutions de paraître trop intrusifs. [Toutefois] nos études ont montré que nos clients attendaient qu’on les reconnaisse finement, qu’on sache leur proposer ce qu’ils aiment, mais aussi ne pas afficher ce qui ne les intéresse pas. » Le marketing prédictif apparaît ainsi comme un service permettant de gagner du temps, tout en resserrant les liens avec l’enseigne ou la marque, le client se sentant en affinité avec un site qui met en avant ce qu’il apprécie.

Plus d’infos :

3 exemples de personnalisation de la relation client

Voyage Privé cible ses offres en prédisant les envies de vacances de ses membres

Avec 500 millions de chiffre d’affaires et 400 employés, Voyage Privé se présente comme le premier groupe indépendant d’e-tourisme en Europe. Son concept : proposer à ses 11,5 millions de membres des voyages de rêve à prix réduits durant un temps limité. Et elle est confrontée à un enjeu classique du marketing : réussir à envoyer la bonne offre, à la bonne personne, au bon moment ! Le site veut aller jusqu’à proposer les séjours les plus pertinents possibles « avant même que le client ne sache vraiment ce qu’il cherche ».

- Fin 2014, Voyage Privé s’est tourné vers Dataiku, une start-up proposant une solution big data permettant l’analyse prédictive. Comme les clients doivent d’abord s’enregistrer pour accéder aux offres, le voyagiste dispose de nombreuses données : leurs parcours, leurs clics, leurs précédents achats, etc. Ces datas sont passées à la moulinette d’un logiciel auto-apprenant (machine learning), et il en ressort une sélection personnalisée de voyages en fonction des comportements des clients.

- Le système mis en place par Voyage Privé permet aussi d’individualiser la pression publicitaire internaute par internaute, en décidant comment s’adresser à chaque client, à quel moment, et sur quel type de support (emailing, display…). Résultat : un taux moyen d’ouverture supérieur à 35 % pour l’email relationnel. Et au final un panier moyen en hausse de 6 % au bout d’un an de fonctionnement.

Plus d’infos :

Showroomprivé détecte les « churners »

Comme Voyage Privé, Showroomprivé s’adresse à une communauté de membres enregistrés. Les clients doivent s’identifier pour profiter de ses offres de déstockage. Ce qui facilite la collecte de données et la connaissance client. Le site a développé en interne une solution d’analyse prédictive autour d’un enjeu : la fidélisation. Ou plus précisément la réduction de l’attrition. L’algorithme de Showroomprivé détecte ainsi les « churners », autrement dit les clients susceptibles de ne pas refaire d’achat sur le site. Il détermine également la valeur potentielle de chacun de ces clients. S’ils devaient commander à nouveau, peut-on s’attendre à ce qu’ils fassent des achats importants ?

- Showroomprivé estime identifier les churners potentiels avec 77 % de précision. Ce qui lui permet de déclencher des actions marketing très ciblées pour susciter de nouvelles commandes auprès des membres inactifs et améliorer son taux de rétention. « Aujourd’hui, nous sommes capables de prédire les actions futures de nos clients et d’agir en conséquence, en envoyant le bon message à la bonne personne », indique Damien Garzilli, Strategy and Business Intelligence Manager chez Showroomprivé.

Plus d’infos :
- La Revue du digital

Cyrillus personnalise ses catalogues en fonction de la navigation des clients sur son site

Le marketing prédictif n’est pas l’apanage du marketing digital. En septembre dernier, les « Paris Retail Awards » ont distingué dans la catégorie CRM le projet Smartalog. Il est né de la collaboration entre Naos Publishing, spécialisé dans la production de catalogues, et Nuukik, qui propose une solution de recommandation et de personnalisation du parcours d’achat basée sur le marketing prédictif. Leur idée : proposer un catalogue papier personnalisé pour chaque client en fonction de son comportement en ligne, de ses précédents achats, des produits qu’il a consultés sur le site, etc. Autrement dit, utiliser les technologies prédictives au service du papier et des courriers adressés.

- « Smartalog vise à repositionner le catalogue papier au sein des différents canaux digitaux existants en développant une solution de communication supplémentaire et industrialisée », indique Nuukik. L’enseigne de mode Cyrillus s’est associée à l’initiative pour envoyer à ses clients des catalogues personnalisés.

Plus d’infos :
- Nuukik

Quand algorithmes et humains coopèrent

Les hôtels Hyatt fournissent aux réceptionnistes des préconisations personnalisées selon les données du client

Un client qui se rend dans un hôtel Hyatt peut avoir le sentiment que la personne à la réception est vraiment très intuitive. Il peut se voir proposer une promotion de dernière minute pour bénéficier d’une chambre avec vue, alors que c’est justement ce dont il rêvait. Le réceptionniste peut aussi lui suggérer un package pour profiter des services du spa, une activité dont il raffole, ou encore lui proposer de se faire livrer à manger dans sa chambre, ce qu’il apprécie toujours… La chaîne d’hôtels est en fait en train de déployer dans l’ensemble de ses établissements un programme de recommandation personnalisée basé sur la collecte des données de ses clients.

- L’objectif du groupe Hyatt ? Améliorer les revenus générés par un client après sa réservation en ligne. Pour lui faire des offres adaptées, Hyatt prend en compte son profil, son historique lors de ses précédents séjours, ainsi que les données laissées lors de sa réservation en ligne (A-t-il consulté une chambre plus grande ? A-t-il regardé les horaires du spa ? etc.). Cela donne une série de suggestions qui est envoyée à la réception de l’hôtel et dont le personnel peut s’inspirer quand le client se présente.

- « Le personnel est libre de suivre ou non les préconisations de l’algorithme, précise Chris Brogan, Vice-président en charge de la stratégie de Hyatt Hotels. Mais nous leur demandons un feedback dans tous les cas de figure, pour que nos données restent ‘propres’. » Il s’agit de savoir si les recommandations ont été suivies par le client. L’algorithme peut ainsi mesurer la pertinence de ses prédictions, et s’améliorer, sur le principe du machine learning.

- La chaîne d’hôtels a testé ce programme en 2014, et a observé une hausse de 60 % des revenus post-réservations là où l’expérimentation était menée, indique Chris Brogan. Ce qui explique son déploiement dans l’ensemble des établissements du groupe.

Plus d’infos :
- Tnooz

Le Crédit Mutuel Arkéa utilise le marketing prédictif pour cibler les propositions commerciales dans ses agences et centres d’appels

Crédit Mutuel Arkéa, le groupe de bancassurance de l’Ouest de la France qui compte plus de 3,5 millions de clients et qui possède notamment Fortuneo, est un des leaders en France dans l’utilisation du marketing prédictif. La banque s’appuie sur un algorithme auto-apprenant qui analyse deux années d’historique de données clients. Cet algorithme fournit aux conseillers des suggestions de produits susceptibles de répondre aux attentes de chaque client.

- Un premier test a été mené fin 2014 dans les centres d’appels du Crédit Mutuel Arkéa, où travaillent une centaine de collaborateurs. « On demande à ces conseillers d’effectuer du rebond commercial lors des appels entrants de clients », explique Marc Chereau, directeur des études informatiques chez Crédit Mutuel Arkéa, dans un entretien au site L’essai a été concluant : les deux centres d’appels bénéficiant de la technologie ont affiché un taux de succès sur ces propositions de 30 % supérieur aux deux autres call centers « témoins ».

- Ces premiers pas encourageants ont incité la banque à expérimenter ce programme également en agence, auprès de 450 conseillers. Avec ici encore un très bon retour : les utilisateurs estiment que 60 % des propositions générées par cette technologie prédictive sont pertinentes. Fin 2015, la décision a été prise de généraliser ce programme à l’ensemble des agences et des centres d’appels du Crédit Mutuel Arkéa, soit au total 5 000 collaborateurs en contact avec les clients.

Plus d’infos :

Chez Stitch Fix, 2 800 stylistes et 80 data scientists travaillentensemble pour recommander des vêtements

Stitch Fix fait partie de ces entreprises inconnues de ce côté-ci de l’Atlantique, mais qui font figure desuccess story aux États-Unis, avec un chiffre d’affaires estimé à 250 million de dollars en 2015 et qui devrait croître de 50 % cette année. Principe de ce site : proposer à ses clientes une sélection personnalisée de cinq vêtements et accessoires. C’est le concept de la malle de vêtements, adapté en France par Chic Types, par exemple. Mais Stitch Fix a poussé la pertinence de la personnalisation a un tel point que le site fait payer son service de sélection 20 dollars (remboursés toutefois si la cliente conserve un des articles).

- Stitch Fix est un mélange de personal shoppers et de data intelligence. Le parcours d’une nouvelle cliente commence par un questionnaire en ligne portant sur ses préférences en matière de mode, son style de vie, sa profession, son lieu d’habitation… Environ 50 données sont ainsi captées pour être analysées par l’algorithme prédictif. Le code postal permet par exemple d’adapter la sélection au climat, la profession est utilisée pour affiner le style, etc. Stitch Fix demande aussi à sa cliente si elle possède un compte Pinterest, ce qui fournira d’autres données pour cibler ses goûts.

- « Tout est question d’expérience et de pertinence », explique Eric Colson, le Chief Algorithm Officer de Stitch Fix, qui travaillait auparavant chez Netflix où il a mis au point le logiciel de recommandation. « Nous n’avons pas d’exclusivité pour les vêtements que nous proposons. Nous ne les vendons pas au meilleur prix. Nous ne les livrons pas le plus rapidement. Nous devons juste être les plus pertinents. » Pour s’assurer de la qualité de la sélection, le site emploie 80 data scientists.

- Stitch Fix ne s’en remet pourtant pas uniquement à sa technologie prédictive : les recommandations opérées par l’algorithme sont transmises à l’une des 2 800 stylistes employées par le site, la plupart travaillant à temps partiel à domicile. Elle finalise le choix des cinq vêtements et accessoires envoyés. Pour que le procédé soit rentable, une cliente doit garder au moins deux des articles qu’elle reçoit.

- Le concept de Stitch Fix plaît, et fidélise. 80 % environ des clientes qui reçoivent une sélection de vêtements passent de nouveau commande dans les trois mois. 39 % dépenseraient même plus de la moitié de leur budget vêtements chez Stitch Fix. Forts de ces chiffres, le site vient de lancer sa version pour hommes.

Plus d’infos :
- Customer Insight Consulting
- Forbes

Les « BAT » meilleurs que les « GAFA » dans la fintech – Actualités Banque & Assurance

Source: Les « BAT » meilleurs que les « GAFA » dans la fintech – Actualités Banque & Assurance

A la a différence de l’Europe ou des Etats-Unis, la Chine a désormais largement dépassé le point de bascule dans la «disruption» des services financiers, estime Citi. Dans un rapport sur les perspectives de la fintech, la banque souligne la supériorité dans ce domaine des BAT (Baidu, Alibaba, Tencent) face aux GAFA (Google, Amazon, Facebook, Apple). Dans les services de paiement tiers (non bancaires), Alibaba et Tencent détiennent 33% et 10% de parts de marché respectivement, nettement au-dessus des 2% revendiqués par les GAFA pour les paiements non cash aux Etats-Unis.

Citi identifie plusieurs causes. Les géants chinois ont investi la sphère financière de longue date; Google s’est aventuré dans les paiements en 2011, sept ans après Alibaba avec Alipay. Deuxième élément, la puissance de l’e-commerce (40% du marché mondial) a accéléré le développement des services de paiement digitaux. Alipay a réalisé l’an dernier un volume total de paiements de 931 milliards de dollars, un montant plus de trois fois supérieur à celui de PayPal.

Brice 3 film complet VF : Gaumont casse les pirates sur Youtube,…

« Brice 3 film complet VF », c’était trop beau pour être vrai. À quelques jours de sa sortie dans les salles, Gaumont a posté cette vidéo Youtube d’1 h 19. Au début, on croirait le film, mais au bout de trois minutes, Jean Dujardin apparaît dans une chambre au fond blanc et se moque du téléspectateur dans un sketch qui dure  jusqu’à la fin de la vidéo. Aussi improbable que très drôle !

The Last Mile of IoT: Artificial Intelligence (AI) – OpenMind

IoT expert Ahmed Banafa analyzes the last mile of the Internet of Things

Source: The Last Mile of IoT: Artificial Intelligence (AI) – OpenMind

The possibilities that IoT brings to the table are endless. IoT continues its run as one of the most popular technology buzzwords of the year, and now the new phase of IoT is pushing everyone to ask hard questions about the data collected by all devices and sensors of IoT.

IoT will produce a tsunami of big data, with the rapid expansion of devices and sensors connected to the Internet of Things continues, the sheer volume of data being created by them will increase to an astronomical level. This data will hold extremely valuable insights into what’s working well or what’s not.



Also, IoT will point out conflicts that arise and provide high-value insight into new business risks and opportunities as correlations and associations are made.

Examples of such IoT data:

  • Data that helps cities predict accidents and crimes.
  • Data that gives doctors real-time insight into information from pacemakers or biochips.
  • Data that optimize productivity across industries through predictive maintenance on equipment and machinery.
  • Data that creates truly smart homes with connected appliances.
  • Data that provides critical communication between self-driving cars.

That’s the good news, but it’s simply impossible for humans to review and understand all of this data with traditional methods, even if they cut down the sample size, simply takes too much time. The big problem will be finding ways to analyze the deluge of performance data and information that all these devices create. Finding insights in terabytes of machine data is a real challenge, just ask a data scientist.

But in order for us to harvest the full benefits of IoT last mile (data), we need to improve:

  • Speed of big data analysis.
  • Accuracy of big data analysis.


The only way to keep up with this IoT-generated data and gain the hidden insights it holds is using AI (Artificial Intelligence) as the last mile of IoT.

Artificial intelligence (AI) and IoT

Artificial intelligence (AI) is the intelligence exhibited by machines or software. It is an academic field of study which generally studies the goal of emulating human-like intelligence. John McCarthy, who coined the term in 1955, defines it as “the science and engineering of making intelligent machines”

In an IoT situation, AI can help companies take the billions of data points they have and boil them down to what’s really meaningful. The general premise is the same as in the retail applications – review and analyze the data you’ve collected to find patterns or similaritiesthat can be learned from, so that better decisions can be made. To be able to call out potential problems, the data has to be analyzed in terms of what’s normal and what’s not. Similarities, correlations and abnormalities need to be quickly identified based on the real-time streams of data. The data collected, combined with AI, makes life easier with intelligent automation, predictive analytics and proactive intervention.


AI in IoT applications: 

  • Visual big data, for example – will allow computers to gain a deeper understanding of images on the screen, with new AI applications that understand the context of images.
  • Cognitive systems will create new recipes that appeal to the user’s sense of taste, creating optimized menus for each individual, and automatically adapting to local ingredients.
  • Newer sensors will allow computers to “hear,” gathering sonic information about the user’s environment.

These are just a few promising applications of Artificial Intelligence in IoT. The potential forhighly individualized services are endless and will dramatically change the way people live, for example helping Pandora to determine what other songs you may like, to suggest other books and movies to you and your doctor would receive notification if a certain condition was met – your heart rate increased to an unsafe level.


Challenges facing AI in IoT

  1. Compatibility.
  2. Complexity.
  3. Privacy/Security.
  4. Safety.
  5. Ethical and legal Issues.
  6. Artificial Stupidity.


What is next …?

Gartner predict that by 2018, 6 billion connected objects will be requesting support – meaning that strategies, technologies and processes will have to be in place to respond to them. It will become necessary to think of connected devices less as ‘things’, but more as customers and consumers of services in themselves – and as such in need of constant support. The need for AI will be more prominent at that stage under the pressure of the huge number of devices and sensors.

Brain belts: The many innovation centers that will take on Silicon Valley | VentureBeat | Entrepreneur | by Bert-Jan Woertman, High Tech Campus Eindhoven

Source: Brain belts: The many innovation centers that will take on Silicon Valley | VentureBeat | Entrepreneur | by Bert-Jan Woertman, High Tech Campus Eindhoven

To most high-tech enthusiasts, towns like Akron, Albany, Batesville, Malmö, and Eindhoven probably don’t hold much significance. Yet, while the world is busy watching Silicon Valley, these relatively obscure spots in the US and Europe are quietly building the infrastructure for innovation ecosystems that will drive the next technological revolutions.

BatesvilleBatesville, are you kidding? Nope. In2008 General Electric opened a state-of-the-art jet engine component factory in the small Mississippi town, followed by another one in Ellisville in 2013. The reason? Both towns are close to technical universities stocked with researchers that specialize in new materials for the next-generation ultralight and silent jet engines. This partnership is crucial for innovation. As GE CEO Jeff Immelt wrote in the Harvard Business Review, “By partnering with Mississippi State University, we have developed a highly sophisticated proprietary process for manufacturing components made of carbon-fiber composites.”

Albany’s story is even more impressive. New York state’s capital has grown intoone of the world’s leading producers of next-generation semiconductors. In Albany’s proud NanoTech Complex, companies like IBM, GlobalFoundries, Intel, Nikon, and Samsung are working together on developing the 450 millimeter silicon wafer, a breakthrough innovation in chip technology. Partnering with the University at Albany, the NanoTech Complex secured $4.4 billion ≈ net worth of Richard Branson, business magnate, 2011

“>[≈ Higher education annual book sales revenue, 2010] in investments to make it one of the leading chip innovation centers in the world.

Asia, move over

These new innovation ecosystems are part of an emerging trend. Antoine van Agtmael and Fred Bakker, authors of the recent book The Smartest Places on Earth, identified 83 of these “brain belts” all over the world (Silicon Valley beingone of them). Although some are located in Asia — Seoul, Singapore, and Hsinchu, for example — the majority are in Europe and the US. The authors visited 10 of these brain belts and concluded that, frankly, all cutting-edge research from biotechnology to robotics is happening in these new collaborative innovation centers. After interviewing CEOs and academics all over the world, the authors said that as market focus is shifting from cheap to smart, Asia’s decades long innovation advantage is nearing its end.

Albany NanoTech Complex

Above: Albany NanoTech Complex

Image Credit: Aerial Dimensions, 2011

Brain belts are quickly becoming a global benchmark for innovation. As Alain Kaloyeros, head of Albany’s NanoTech Complex said, “Building this infrastructure will ensure a competitive edge in technology.” GE’s Immelt remarked, “These partnerships [between tech companies and universities] are vital for developing tomorrow’s engineers, who are critical to America’s competitiveness.”

Clusters of excellence

So what do brain belts have in common? First, of all their physical components. Brain belts almost always consist of a handful of well-established tech companies with thriving R&D departments, a few dozen startups, and at leastone technical research university. The university supplies the research, knowledge, and talent. The big tech companies provide finances, research facilities, and market experience. The young, eager startups add innovative ideas and a risk-savvy entrepreneurial spirit to the mix.

The need to cluster together often arises because a town, region, or district has found an innovation niche, which naturally attracts the actors that later form the brain belt’s ecosystem. Akron, the US capital of tire manufacturing, has used its polymer knowledge base to find new innovative niches in medical appliances and steel coatings. In Eindhoven, home to Phillips, we used to be good at making silicon chips. When we lost that competitive edge, we found a new niche as a photonics chip innovator.

If the niche and the infrastructure are there, you have what I call a “cluster of excellence.” In Eindhoven we’ve built several of these clusters around areas like smart sensors, robotics, artificial intelligence, new materials and — the one we’re most proud of — photonics or “light on a chip.”

Centennial Campus, North Carolina

Above: Centennial Campus, North Carolina

Image Credit: NC State University

The Kremlin model

Secondly, the players within the ecosystem need to be willing to share ideas, knowledge, research, networks, and facilities. In today’s world, innovation is a team effort. The brilliant nerd starting the next tech revolution from his garage is, well, very 1980s. Companies also rarely innovate alone anymore. IBM now refers to its former innovation process as “the Kremlin model” for its autocratic and compartmentalized nature.

Agile companies know they don’t have the funds, time, or capacity to achieve success fast enough on their own. Strategic alliances are the way of cutting development costs and accelerating time to market. In Eindhoven we’ve learned to tap into trusted local networks first to see what’s possible. We’ve made our suppliers part of the innovation process by consulting them in the R&D phase so manufacturing can be made smarter. We call it a value chain instead of just a supply chain.

Managed serendipity

A third thing brain belts have in common is their reliance on physical proximity. As the Allen Curve teaches us, there’s a tight correlation between personal interactions, performance, and innovation. The Eindhoven High Tech Campus is located on a single square kilometer with 150 companies all within five-minutes’ walking distance. We included a main street called The Strip with restaurants, a conference center, and convenience services. It allows for natural networking and managed serendipity as people from different companies working on various projects visit these amenities several times a day.

Gateway to the Ideon Science Park in Lund, Sweden

Above: Gateway to the Ideon Science Park in Lund, Sweden

Image Credit:

It’s a concept Google, Facebook and others are discovering as well. The city center of St. Louis houses five different innovation hubs, all within five-minutes’ walking distance. Centennial Campus, North Carolina State University’s innovation hub in Raleigh, houses university buildings, companies, a startup incubator, and research facilities all in a single location. In Lund, Sweden, two science parks and a university, located less than a mile from each other, have joined hands and brains to push innovations in life sciences, telecommunication, and new materials. It recently resulted in a state-of-the-art particle accelerator.

This connectivity is fundamental to continued success in innovation. When people from different sectors are mixing, talking, sharing, and discovering, knowledge barriers are broken and breakthroughs can happen.

4 patents a day

Rome wasn’t built in one day. Neither is a brain belt. If there is one thing we’ve learned in Eindhoven, it’s that a successful innovation ecosystem takes years to develop. Founded in 2003, our High Tech Campus has been an early adopter. Although many people then viewed our open innovation’ model with suspicion, 13 years down the line we are seeing the success of those early investments. Nowadays, the High Tech Campus submits four patents a day, more than half of all patent applications in The Netherlands.

Eindhoven campus

We have also learned that innovation has many faces. According to Henk Volberda, a Dutch professor of strategic management, only 25 percent of innovation success depends on investments in IT and related technologies. A whopping 75 percent comes from “social innovation” — such as removing hierarchical pyramids, maximizing investment in human capital, and co-creation with partners. Understanding the local social dynamics is just as important to a brain belt as building top-quality test facilities, if not more.

Shoulders of giants

Although brain belts are great at making local and regional connections, I’d like to see them connect globally as well. Innovation centers can strengthen themselves by operating in global partnerships. What we need is an ongoing conversation between development managers from different innovation centers. If we work together, we can truly stand on the shoulders of giants.

So let Silicon Valley be the Goliath standing in the limelight. In the meantime, the other 80+ brain belts will be the Davids quietly working on technology that will impact the world in ways we cannot yet imagine.

Bert-Jan Woertman is director of marketing and communications at High Tech Campus Eindhoven, a business hub where 140 tech companies are working on developing future technologies and products.

Étude : l’importance de la transformation digitale – Blog du Modérateur

Mot clé de l’année, la transformation digitale est une préoccupation majeure de nombreuses entreprises. Ce processus complexe à mettre en œuvre peut apport

Source: Étude : l’importance de la transformation digitale – Blog du Modérateur

Pour en savoir plus sur l’état de la transformation digitale dans le monde, et les opportunités de ce process, CA Technologies et Coleman Parkes Research ont réalisé une étude sur le sujet auprès de 1770 dirigeants d’entreprises et responsables IT dans le monde et sur tous les secteurs. Voici les principales données de l’enquête.

Des efforts pour la digitalisation

Lorsqu’on demande aux dirigeants d’entreprise s’ils investissent sur les bons talents, ils sont 84% à répondre que c’est le cas. Cet aspect RH est vu comme une priorité pour la transformation digitale. 82% affirment se digitaliser pour changer la façon dont ils dirigent leur business et 79% mettent en place des méthodes agile.


Les KPI de la digitalisation

Il est facile de parler de transformation digitale sans avoir d’outil pour la mesurer. L’étude se penche sur cet aspect en proposent 4 grands KPIs pour mesurer la transformation digitale :

  • Agilité business
  • Croissance business
  • Expérience client
  • Efficacité opérationnelle.


À partir de ces 14 KPIs principaux, il est possible de faire une échelle de la digitalisation et des ses bénéfices économiques. Cette échelle sur 100 montre un score moyen de 53. Les pays qui ont le plus d’impact de leur digitalisation sont, sans trop de surprises, de nombreux pays asiatiques : Inde (79), Thaïlande (71), Indonésie (66)  et Malaisie (64). Le Brésil est 3ème avec un score de 69. Tous ces pays ont su tirer le meilleur parti des outils digitaux et notamment du mobile pour transformer leur économie.


Les secteurs les plus impactés par ce processus sont : les telecoms, la banque et la finance, le secteur public et le retail.


Les bénéfices de la digitalisation

Quand les auteurs de l’étude demandent aux dirigeants ce qu’offre la digitalisation, 76% affirment que cela augmente leur « digital reach », ou leur capacité à toucher les consommateurs sur les canaux digitaux. 69% trouvent que cela apporte un avantage concurrentiel et 37% que cela apporte une croissance des revenus ou de nouvelles sources de revenus.


Le consommateur : un enjeu important

Autre enjeu important de la digitalisation : le consommateur. Selon l’étude, 74% des dirigeants pensent que la digitalisation permet une meilleure expérience client. 40% trouvent que cela offre une meilleure satisfaction client, et 38% une meilleure rétention client.