{"id":804,"date":"2017-11-08T08:27:48","date_gmt":"2017-11-08T07:27:48","guid":{"rendered":"https:\/\/www.hsu-hh.de\/logistik\/?page_id=804"},"modified":"2017-11-26T06:55:09","modified_gmt":"2017-11-26T05:55:09","slug":"disjoint-path-planning","status":"publish","type":"page","link":"https:\/\/www.hsu-hh.de\/logistik\/research\/projects\/disjoint-path-planning","title":{"rendered":"Disjoint Path Planning"},"content":{"rendered":"<figure id=\"attachment_803\" aria-describedby=\"caption-attachment-803\" style=\"width: 300px\" class=\"wp-caption alignright\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-803 size-full\" src=\"https:\/\/www.hsu-hh.de\/logistik\/wp-content\/uploads\/sites\/655\/2017\/11\/DisjointPathPlanning.jpg\" alt=\"Disjoint Path Planning\" width=\"300\" height=\"300\" srcset=\"https:\/\/www.hsu-hh.de\/logistik\/wp-content\/uploads\/sites\/655\/2017\/11\/DisjointPathPlanning.jpg 300w, https:\/\/www.hsu-hh.de\/logistik\/wp-content\/uploads\/sites\/655\/2017\/11\/DisjointPathPlanning-150x150.jpg 150w, https:\/\/www.hsu-hh.de\/logistik\/wp-content\/uploads\/sites\/655\/2017\/11\/DisjointPathPlanning-100x100.jpg 100w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><figcaption id=\"caption-attachment-803\" class=\"wp-caption-text\">Fig.: Example of two disjoint paths<\/figcaption><\/figure>\n<p>Some of our research activities are devoted to\u00a0disjoint path planning\u00a0(DPP). In DPP, a graph\u00a0G=(V,E)\u00a0is given, within which a set of disjoint paths\/routes has to be found such that some objective function, for example the maximum length of all constructed paths, is minimized. Applications of disjoint path planning problems are found in logistics, where several distinct vehicle routings have to be found. Here, disjoint paths\/ routes provide a degree of flexibility, and also ensure that vertices are not visited in the same order every day. Especially in security critical applications, such as the routing of security firms, this property can be of upmost importance.<\/p>\n<p>The figure on the left depicts two edge-disjoint paths within a graph\u00a0G. Obviously, each node is visited by the red and the blue path, while both paths do not share a common edge.<\/p>\n<p>A variant of the problem was introduced December 2012\u2013January 2013 in the Kaggle Competition on the <a href=\"http:\/\/www.kaggle.com\/c\/traveling-santa-problem\" target=\"_blank\" rel=\"noopener noreferrer\">&#8222;Traveling Santa Problem&#8220;<\/a>. In this setting, two edge-disjoint Hamiltonian paths had to be found for a graph consisting of 150,000 nodes, minimizing the length of the longer path.<br \/>\nOur algorithm\/ computer implementation ranked 19th in this international competition (out of 356 registered teams), with a final objective function value of 0.7% above the best-known solution.<br \/>\nThe following two figures illustrate the two computed paths for the 150,000 nodes-dataset. Although the look similar (in fact they are of similar length), they are edge-disjoint.<\/p>\n<figure id=\"attachment_1210\" aria-describedby=\"caption-attachment-1210\" style=\"width: 800px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1210 size-full\" src=\"https:\/\/www.hsu-hh.de\/logistik\/wp-content\/uploads\/sites\/655\/2017\/11\/DPP.jpg\" alt=\"DPP\" width=\"800\" height=\"376\" srcset=\"https:\/\/www.hsu-hh.de\/logistik\/wp-content\/uploads\/sites\/655\/2017\/11\/DPP.jpg 800w, https:\/\/www.hsu-hh.de\/logistik\/wp-content\/uploads\/sites\/655\/2017\/11\/DPP-300x141.jpg 300w, https:\/\/www.hsu-hh.de\/logistik\/wp-content\/uploads\/sites\/655\/2017\/11\/DPP-768x361.jpg 768w\" sizes=\"auto, (max-width: 800px) 100vw, 800px\" \/><figcaption id=\"caption-attachment-1210\" class=\"wp-caption-text\">Fig.: Two disjoint paths for the 150,000-node-instance<\/figcaption><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>Some of our research activities are devoted to\u00a0disjoint path planning\u00a0(DPP). In DPP, a graph\u00a0G=(V,E)\u00a0is given, within which a set of disjoint paths\/routes has to be found such that some objective [&hellip;]<\/p>\n","protected":false},"author":74,"featured_media":0,"parent":644,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"categories":[53],"tags":[],"class_list":["post-804","page","type-page","status-publish","hentry","category-research-project"],"_links":{"self":[{"href":"https:\/\/www.hsu-hh.de\/logistik\/wp-json\/wp\/v2\/pages\/804","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.hsu-hh.de\/logistik\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.hsu-hh.de\/logistik\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.hsu-hh.de\/logistik\/wp-json\/wp\/v2\/users\/74"}],"replies":[{"embeddable":true,"href":"https:\/\/www.hsu-hh.de\/logistik\/wp-json\/wp\/v2\/comments?post=804"}],"version-history":[{"count":8,"href":"https:\/\/www.hsu-hh.de\/logistik\/wp-json\/wp\/v2\/pages\/804\/revisions"}],"predecessor-version":[{"id":1211,"href":"https:\/\/www.hsu-hh.de\/logistik\/wp-json\/wp\/v2\/pages\/804\/revisions\/1211"}],"up":[{"embeddable":true,"href":"https:\/\/www.hsu-hh.de\/logistik\/wp-json\/wp\/v2\/pages\/644"}],"wp:attachment":[{"href":"https:\/\/www.hsu-hh.de\/logistik\/wp-json\/wp\/v2\/media?parent=804"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.hsu-hh.de\/logistik\/wp-json\/wp\/v2\/categories?post=804"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.hsu-hh.de\/logistik\/wp-json\/wp\/v2\/tags?post=804"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}