{"id":2107,"date":"2011-04-08T20:30:02","date_gmt":"2011-04-08T18:30:02","guid":{"rendered":"http:\/\/blogs.wittwer.fr\/whiler\/?p=2107"},"modified":"2012-03-03T04:24:43","modified_gmt":"2012-03-03T03:24:43","slug":"probleme-du-voyageur-de-commerce-wtsp","status":"publish","type":"post","link":"https:\/\/blogs.wittwer.fr\/whiler\/2011\/04\/08\/probleme-du-voyageur-de-commerce-wtsp\/","title":{"rendered":"Probl\u00e8me du voyageur de commerce &#8211; wTSP"},"content":{"rendered":"<p>Apr\u00e8s avoir r\u00e9ussi \u00e0 <a href=\"\/whiler\/2011\/04\/06\/wlatitude\/\">modifier mes coordonn\u00e9es dans Google Latitude<\/a>, j&rsquo;ai eu envie de voir comment on pouvait optimiser un trajet entre plusieurs points&#8230;<\/p>\n<p>Le probl\u00e8me me semblait complexe, mais je n&rsquo;imaginais pas encore \u00e0 quel point  <img src=\"https:\/\/blogs.wittwer.fr\/whiler\/wp-includes\/images\/smilies\/skype\/\/happy.gif\" alt=\"(lol)\" class=\"wp-smiley\" style=\"height: 1em; max-height: 1em;\" \/><\/p>\n<p>Heureusement, j&rsquo;ai tr\u00e8s rapidement trouv\u00e9 de la documentation concernant ce classique probl\u00e8me, plus commun\u00e9ment appel\u00e9&nbsp;: <a href=\"http:\/\/fr.wikipedia.org\/wiki\/probl\u00e8me_du_voyageur_de_commerce\" rel=\"glossary\" target=\"_blank\" title=\"Wikipedia, D&eacute;finition de&nbsp;: probl\u00e8me du voyageur de commerce\" style=\"\" >probl\u00e8me du voyageur de commerce<\/a><sup style=\"font-family: Georgia, Times New Roman, Serif; font-weight: bold; color: #AAAAAA\" ><em>W<\/em><\/sup>.<\/p>\n<p>J&rsquo;ai \u00e9galement trouv\u00e9 <a href=\"https:\/\/subsimple.com\/delphi.asp\" target=\"_blank\">un projet<\/a> d\u00e9j\u00e0 \u00e9crit en <a href=\"https:\/\/www.embarcadero.com\/fr\/products\/delphi\" target=\"_blank\">Delphi<\/a> qui m&rsquo;a permis de l&rsquo;impl\u00e9menter sans finalement, vraiment comprendre tout ce qui se passait&#8230; les algorithmes g\u00e9n\u00e9tiques n&rsquo;\u00e9tant clairement pas ma tasse de caf\u00e9&#8230;. Vous pouvez visiter le site Web de l&rsquo;auteur sur <a href=\"https:\/\/subsimple.com\/genealgo.asp\" target=\"_blank\">cette page<\/a>.<\/p>\n<p>L&rsquo;application que j&rsquo;ai faite me permet de charger un fichier <a href=\"http:\/\/fr.wikipedia.org\/wiki\/Google_Earth\" rel=\"glossary\" target=\"_blank\" title=\"Wikipedia, D&eacute;finition de&nbsp;: KML\" style=\"\" >KML<\/a><sup style=\"font-family: Georgia, Times New Roman, Serif; font-weight: bold; color: #AAAAAA\" ><em>W<\/em><\/sup>, g\u00e9n\u00e9r\u00e9 avec <a target=\"_blank\" href=\"https:\/\/earth.google.com\/\">Google Earth<\/a> ayant la structure suivante&nbsp;:<\/p>\n<ul>\n<li>Un r\u00e9pertoire qui contient&nbsp;:\n<ul>\n<li>des rep\u00e8res<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p><center><div id=\"attachment_2155\" style=\"width: 310px\" class=\"wp-caption aligncenter\"><a href=\"\/whiler\/wp-content\/uploads\/2011\/04\/tsp_before.jpg\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-2155\" src=\"\/whiler\/wp-content\/uploads\/2011\/04\/tsp_before-300x281.jpg\" alt=\"wTSP\" title=\"wTSP\" width=\"300\" height=\"281\" class=\"size-medium wp-image-2155\" srcset=\"https:\/\/blogs.wittwer.fr\/whiler\/wp-content\/uploads\/2011\/04\/tsp_before-300x281.jpg 300w, https:\/\/blogs.wittwer.fr\/whiler\/wp-content\/uploads\/2011\/04\/tsp_before.jpg 426w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><p id=\"caption-attachment-2155\" class=\"wp-caption-text\">wTSP<\/p><\/div><\/center><\/p>\n<p><!--more-->Je charge alors le fichier KML en r\u00e9cup\u00e9rant le nom, les coordonn\u00e9es GPS et l&rsquo;altitude de chaque rep\u00e8re dans une liste (l&rsquo;altitude n&rsquo;est pas utilis\u00e9e pour le calcul des distances).<\/p>\n<p>Je calcule ensuite les distances entre chaque position. Chaque distance correspond \u00e0 l&rsquo;\u00e9cart entre la ligne qui l&rsquo;affiche et la position pr\u00e9c\u00e9dente. La premi\u00e8re ligne est calcul\u00e9 en utilisant la derni\u00e8re position.<\/p>\n<p>Ce calcul est effectu\u00e9 en prenant une valeur constante pour le rayon \u00e9quatorial&nbsp;:<\/p>\n<div class=\"codecolorer-container delphi dawn\" style=\"overflow:auto;white-space:nowrap;width:480px;height:300px;\"><table cellspacing=\"0\" cellpadding=\"0\"><tbody><tr><td class=\"line-numbers\"><div>1<br \/>2<br \/>3<br \/>4<br \/>5<br \/>6<br \/>7<br \/>8<br \/>9<br \/>10<br \/>11<br \/>12<br \/>13<br \/>14<br \/>15<br \/>16<br \/>17<br \/>18<br \/>19<br \/>20<br \/>21<br \/>22<br \/>23<br \/>24<br \/>25<br \/>26<br \/><\/div><\/td><td><div class=\"delphi codecolorer\"><span class=\"kw1\">function<\/span> CalculateDistance<span class=\"br0\">&#40;<\/span>dFromLatitude<span class=\"sy1\">,<\/span> dFromLongitude<span class=\"sy1\">,<\/span> dToLatitude<span class=\"sy1\">,<\/span> dToLongitude<span class=\"sy1\">:<\/span> <span class=\"kw4\">Double<\/span><span class=\"br0\">&#41;<\/span><span class=\"sy1\">:<\/span> <span class=\"kw4\">Double<\/span><span class=\"sy1\">;<\/span><br \/>\n<span class=\"kw1\">const<\/span><br \/>\n&nbsp; EARTH_RADIUS <span class=\"sy3\">=<\/span> <span class=\"nu0\">6378<\/span><span class=\"sy1\">;<\/span> <span class=\"co1\">\/\/ Rayon \u00e9quatorial : 6 378,137<\/span><br \/>\n<br \/>\n&nbsp; <span class=\"kw1\">function<\/span> ArcCosWithZero<span class=\"br0\">&#40;<\/span>dValue<span class=\"sy1\">:<\/span> <span class=\"kw4\">Double<\/span><span class=\"br0\">&#41;<\/span><span class=\"sy1\">:<\/span> <span class=\"kw4\">Double<\/span><span class=\"sy1\">;<\/span><br \/>\n&nbsp; <span class=\"kw1\">var<\/span><br \/>\n&nbsp; &nbsp; dCheck<span class=\"sy1\">:<\/span> <span class=\"kw4\">Double<\/span><span class=\"sy1\">;<\/span><br \/>\n&nbsp; <span class=\"kw1\">begin<\/span><br \/>\n&nbsp; &nbsp; dCheck <span class=\"sy1\">:<\/span><span class=\"sy3\">=<\/span> <span class=\"kw3\">sqrt<\/span><span class=\"br0\">&#40;<\/span><span class=\"sy3\">-<\/span>dValue<span class=\"sy3\">*<\/span>dValue<span class=\"sy3\">+<\/span><span class=\"nu0\">1<\/span><span class=\"br0\">&#41;<\/span><span class=\"sy1\">;<\/span><br \/>\n&nbsp; &nbsp; <span class=\"kw1\">if<\/span> <span class=\"br0\">&#40;<\/span>dCheck <span class=\"sy3\">=<\/span> <span class=\"nu0\">0<\/span><span class=\"br0\">&#41;<\/span> <span class=\"kw1\">then<\/span><br \/>\n&nbsp; &nbsp; &nbsp; dCheck <span class=\"sy1\">:<\/span><span class=\"sy3\">=<\/span> <span class=\"nu0\">0.0000000001<\/span><span class=\"sy1\">;<\/span><br \/>\n<br \/>\n&nbsp; &nbsp; Result <span class=\"sy1\">:<\/span><span class=\"sy3\">=<\/span> <span class=\"sy3\">-<\/span><span class=\"kw3\">ArcTan<\/span><span class=\"br0\">&#40;<\/span>dValue <span class=\"sy3\">\/<\/span> dCheck<span class=\"br0\">&#41;<\/span> <span class=\"sy3\">+<\/span> <span class=\"br0\">&#40;<\/span>Pi <span class=\"sy3\">\/<\/span> <span class=\"nu0\">2<\/span><span class=\"br0\">&#41;<\/span><span class=\"sy1\">;<\/span><br \/>\n&nbsp; <span class=\"kw1\">end<\/span><span class=\"sy1\">;<\/span><br \/>\n<br \/>\n<span class=\"kw1\">begin<\/span><br \/>\n&nbsp; <span class=\"co1\">\/\/ Degr\u00e9s en radians<\/span><br \/>\n&nbsp; dFromLatitude &nbsp;<span class=\"sy1\">:<\/span><span class=\"sy3\">=<\/span> dFromLatitude &nbsp;<span class=\"sy3\">\/<\/span> <span class=\"nu0\">180<\/span> <span class=\"sy3\">*<\/span> Pi<span class=\"sy1\">;<\/span><br \/>\n&nbsp; dFromLongitude <span class=\"sy1\">:<\/span><span class=\"sy3\">=<\/span> dFromLongitude <span class=\"sy3\">\/<\/span> <span class=\"nu0\">180<\/span> <span class=\"sy3\">*<\/span> Pi<span class=\"sy1\">;<\/span><br \/>\n&nbsp; dToLatitude &nbsp; &nbsp;<span class=\"sy1\">:<\/span><span class=\"sy3\">=<\/span> dToLatitude &nbsp; &nbsp;<span class=\"sy3\">\/<\/span> <span class=\"nu0\">180<\/span> <span class=\"sy3\">*<\/span> Pi<span class=\"sy1\">;<\/span><br \/>\n&nbsp; dToLongitude &nbsp; <span class=\"sy1\">:<\/span><span class=\"sy3\">=<\/span> dToLongitude &nbsp; <span class=\"sy3\">\/<\/span> <span class=\"nu0\">180<\/span> <span class=\"sy3\">*<\/span> Pi<span class=\"sy1\">;<\/span><br \/>\n<br \/>\n&nbsp; <span class=\"co1\">\/\/Distance = Rayon * | arccos[ sin(LatA).sin(LatB)+cos(LatA).cos(LatB).cos(LonA-LonB) ] |<\/span><br \/>\n&nbsp; <span class=\"co1\">\/\/ Rayon \u00e9quatorial : 6 378,137<\/span><br \/>\n&nbsp; Result <span class=\"sy1\">:<\/span><span class=\"sy3\">=<\/span> EARTH_RADIUS <span class=\"sy3\">*<\/span> ArcCosWithZero<span class=\"br0\">&#40;<\/span><span class=\"kw3\">Sin<\/span><span class=\"br0\">&#40;<\/span>dFromLatitude<span class=\"br0\">&#41;<\/span><span class=\"sy3\">*<\/span><span class=\"kw3\">Sin<\/span><span class=\"br0\">&#40;<\/span>dToLatitude<span class=\"br0\">&#41;<\/span><span class=\"sy3\">+<\/span><span class=\"kw3\">Cos<\/span><span class=\"br0\">&#40;<\/span>dFromLatitude<span class=\"br0\">&#41;<\/span><span class=\"sy3\">*<\/span><span class=\"kw3\">Cos<\/span><span class=\"br0\">&#40;<\/span>dToLatitude<span class=\"br0\">&#41;<\/span><span class=\"sy3\">*<\/span><span class=\"kw3\">Cos<\/span><span class=\"br0\">&#40;<\/span>dFromLongitude <span class=\"sy3\">-<\/span> dToLongitude<span class=\"br0\">&#41;<\/span><span class=\"br0\">&#41;<\/span><span class=\"sy1\">;<\/span><br \/>\n<span class=\"kw1\">end<\/span><span class=\"sy1\">;<\/span><\/div><\/td><\/tr><\/tbody><\/table><\/div>\n<p>Ensuite, gr\u00e2ce \u00e0 l&rsquo;algorithme et au code source de l&rsquo;application de <a target=\"_blank\" href=\"https:\/\/subsimple.com\/aboutme.asp\">Troels<\/a>, j&rsquo;optimise les distances entre les diff\u00e9rents rep\u00e8res&nbsp;:<br \/>\n<center><div id=\"attachment_2156\" style=\"width: 310px\" class=\"wp-caption aligncenter\"><a href=\"\/whiler\/wp-content\/uploads\/2011\/04\/tsp_calculate.jpg\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-2156\" src=\"\/whiler\/wp-content\/uploads\/2011\/04\/tsp_calculate-300x275.jpg\" alt=\"Calcul du chemin le plus court\" title=\"Calcul du chemin le plus court\" width=\"300\" height=\"275\" class=\"size-medium wp-image-2156\" srcset=\"https:\/\/blogs.wittwer.fr\/whiler\/wp-content\/uploads\/2011\/04\/tsp_calculate-300x275.jpg 300w, https:\/\/blogs.wittwer.fr\/whiler\/wp-content\/uploads\/2011\/04\/tsp_calculate.jpg 538w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><p id=\"caption-attachment-2156\" class=\"wp-caption-text\">Calcul du chemin le plus court<\/p><\/div><\/center><\/p>\n<p>Pour finalement r\u00e9afficher la liste dans l&rsquo;ordre trouv\u00e9&nbsp;:<br \/>\n<center><div id=\"attachment_2157\" style=\"width: 310px\" class=\"wp-caption aligncenter\"><a href=\"\/whiler\/wp-content\/uploads\/2011\/04\/tsp_after.jpg\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-2157\" src=\"\/whiler\/wp-content\/uploads\/2011\/04\/tsp_after-300x281.jpg\" alt=\"R\u00e9sultats wTSP\" title=\"R\u00e9sultats wTSP\" width=\"300\" height=\"281\" class=\"size-medium wp-image-2157\" srcset=\"https:\/\/blogs.wittwer.fr\/whiler\/wp-content\/uploads\/2011\/04\/tsp_after-300x281.jpg 300w, https:\/\/blogs.wittwer.fr\/whiler\/wp-content\/uploads\/2011\/04\/tsp_after.jpg 426w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><p id=\"caption-attachment-2157\" class=\"wp-caption-text\">R\u00e9sultats wTSP<\/p><\/div><\/center><\/p>\n<p>Si cette application vous int\u00e9resse, vous pouvez la <a href=\"https:\/\/www.whiler.com\/freewares\/download?wtsp.exe\">t\u00e9l\u00e9charger depuis ce lien<\/a>. Vous pouvez \u00e9galement trouver <a href=\"\/whiler\/wp-content\/uploads\/2011\/04\/tour-de-france.zip\">un exemple du type de fichier KML<\/a> attendu par l&rsquo;application.<\/p>\n<p>&nbsp;<\/p>\n<blockquote><p>Cette application est d\u00e9velopp\u00e9e avec <a target=\"_blank\" href=\"https:\/\/www.embarcadero.com\/fr\/products\/delphi\">Embarcadero Delphi XE<\/a>.<\/p><\/blockquote>\n<p><center><a href=\"\/whiler\/category\/computer\/delphi\/\" title=\"Articles concernant Delphi\"><img loading=\"lazy\" decoding=\"async\" src=\"\/whiler\/wp-content\/uploads\/2009\/10\/built_with_delphi.png\" alt=\"D\u00e9velopp\u00e9 en Delphi\" title=\"D\u00e9velopp\u00e9 en Delphi\" width=\"125\" height=\"51\" class=\"size-full wp-image-2721\" \/><\/a><\/center><\/p>\n<div class=\"thanks_button_div\" \n                  style=\"float: right; margin-right: 10px; margin-top:10px;\"><div id=\"thanksButtonDiv_2107_1\" style=\"background-image:url(https:\/\/blogs.wittwer.fr\/whiler\/wp-content\/plugins\/thanks-you-counter-button\/images\/thanks_compact_brown1.png); background-repeat:no-repeat; float: left; display: inline;\"\n                onmouseover=\"javascript:thankYouChangeButtonImage('thanksButtonDiv_2107_1', true);\" \n                onmouseout=\"javascript:thankYouChangeButtonImage('thanksButtonDiv_2107_1', false);\"\n                onclick=\"javascript:thankYouChangeButtonImage('thanksButtonDiv_2107_1', false);\" >\n                <input type=\"button\" onclick=\"thankYouButtonClick(2107, 'You left &ldquo;Thanks&rdquo; already for this post')\" value=\"Merci\u00a0 2\"\n                  class=\"thanks_button thanks_compact thanks_brown1\"\n                  style=\"  font-family: Verdana, Arial, Sans-Serif; font-size: 14px; font-weight: normal;; color:#00f;\"\n                  id=\"thanksButton_2107_1\" title=\"Click to leave &ldquo;Thanks&rdquo; for this post\"\/>\n             <\/div><div id=\"ajax_loader_2107_1\" style=\"display:inline;visibility: hidden;\"><img decoding=\"async\" alt=\"ajax loader\" src=\"https:\/\/blogs.wittwer.fr\/whiler\/wp-content\/plugins\/thanks-you-counter-button\/images\/ajax-loader.gif\" \/><\/div><\/div>","protected":false},"excerpt":{"rendered":"<p>Apr\u00e8s avoir r\u00e9ussi \u00e0 modifier mes coordonn\u00e9es dans Google Latitude, j\u2019ai eu envie de voir comment on pouvait optimiser un trajet entre plusieurs points\u2026<\/p>\n<p>Le probl\u00e8me me semblait complexe, mais je n\u2019imaginais pas encore \u00e0 quel point&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","_links_to":"","_links_to_target":""},"categories":[7,6],"tags":[27,154,43,44,93,120,108],"class_list":["post-2107","post","type-post","status-publish","format-standard","hentry","category-delphi","category-dev","tag-coloration-syntaxique","tag-delphi","tag-donnees","tag-embarcadero","tag-freeware","tag-localisation","tag-script"],"_links":{"self":[{"href":"https:\/\/blogs.wittwer.fr\/whiler\/wp-json\/wp\/v2\/posts\/2107","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.wittwer.fr\/whiler\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.wittwer.fr\/whiler\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.wittwer.fr\/whiler\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.wittwer.fr\/whiler\/wp-json\/wp\/v2\/comments?post=2107"}],"version-history":[{"count":0,"href":"https:\/\/blogs.wittwer.fr\/whiler\/wp-json\/wp\/v2\/posts\/2107\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.wittwer.fr\/whiler\/wp-json\/wp\/v2\/media?parent=2107"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.wittwer.fr\/whiler\/wp-json\/wp\/v2\/categories?post=2107"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.wittwer.fr\/whiler\/wp-json\/wp\/v2\/tags?post=2107"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}