{"entities":{"Q1096550":{"pageid":1107302,"ns":120,"title":"Item:Q1096550","lastrevid":77752274,"modified":"2026-05-06T09:58:49Z","type":"item","id":"Q1096550","labels":{"en":{"language":"en","value":"Generalized travelling salesman problem through n sets of nodes: The asymmetrical case"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4031434"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096550$699DFC2E-3F44-47FC-A323-A9A726A02BC8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"52569bda601761a2aa845213a7cd6f5c2d74fc50","datavalue":{"value":{"text":"Generalized travelling salesman problem through n sets of nodes: The asymmetrical case","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1096550$46838870-11FC-4064-A3BA-4A8D200B0FAD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7cd9ea4038bd722b4d9484cce1311dabb4253215","datavalue":{"value":"0633.90087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096550$6FC3A2AC-7ED3-46CB-BCE1-C32DE38AA148","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f05c69509b9740db0bc5aa66f451229b45916f53","datavalue":{"value":"10.1016/0166-218X(87)90020-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096550$38439775-A1FC-45B9-932A-1EBEFD165D3C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9bb4124699c1f5367e8eff90a7046d28f42f9fac","datavalue":{"value":{"entity-type":"item","numeric-id":203167,"id":"Q203167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096550$D0D0815A-F3F7-4ACD-9494-B995E7A250E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce2c6fb0ffbcd8c5669db3973d1f480fa18f1430","datavalue":{"value":{"entity-type":"item","numeric-id":1096548,"id":"Q1096548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096550$6B115191-389E-482D-B33B-D16AA47AA755","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fbe9f7fb37828186e04ddcd36a3bc70db0ecde3e","datavalue":{"value":{"entity-type":"item","numeric-id":1096549,"id":"Q1096549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096550$697FE437-9F24-4F35-AB76-07FEE9FF78F3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096550$2C501086-6067-4B29-A6D5-81290D48C1FF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1096550$D75CD569-FDA8-4A20-8A56-149089C64779","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"220187c729cc5959c079300a1c2876088abf335f","datavalue":{"value":"This paper presents an exact algorithm for a generalized version of the Travelling Salesman Problem which consists of finding the shortest Hamiltonian circuit through n clusters of nodes, in the case where the distance matrix is asymmetrical. The problem is formulated as an integer linear program. The program is then relaxed and solved by a branch and bound algorithm. Computational results are reported for problems involving up to 100 nodes and 8 clusters.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096550$5A289410-F757-486A-9970-2407E2ED1B11","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096550$6C118C02-5F66-4B4B-AE97-E9D354FAB69A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096550$8205CBF6-126B-44E4-ACD3-DF6660CD6B46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096550$3EB26609-27CB-484F-B2DA-B98DD119121E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096550$BE137791-8E98-4F7A-842D-7B700943300E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096550$A485756B-0D65-4F72-8C62-BFB23FF71BF8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fac12c1f9f75162e66c166aa46b2bc054b8183a4","datavalue":{"value":"4031434","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096550$6BBF38E3-3C94-49AE-AEDB-F42B08D636BD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4b07e69d587bbe6e4055930d91a959b7887a6b5","datavalue":{"value":"asymmetrical case","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096550$E5822E55-AA51-4CCA-9973-31CD21BD4DFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56c22d5775221423046cc5c67c2b493cdcf52842","datavalue":{"value":"exact algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096550$2EA21B77-BD1E-409C-9AC5-ED771D4D3551","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b001d45d1656d97cb123bf535f2d6c67262c445","datavalue":{"value":"generalized version","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096550$CA9F8594-0424-498B-AFE8-B4BC3FD2479D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51402386d26c3901f9b932d78a2b6e15c1efc9c9","datavalue":{"value":"Travelling Salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096550$DF76EA37-E0CB-451C-A804-51BFAE50C65C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6983b385b76a7803ef15dc6a8c241a11f21dc2b6","datavalue":{"value":"shortest Hamiltonian circuit","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096550$FCC6DE13-FABA-43C3-8E42-69D62BAE68B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdc6164cf25ab131dbb818bbd16bab28b6f9d095","datavalue":{"value":"branch and bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096550$822623C6-54BE-4382-92EA-87F0E83FB7C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2661a0360bf1e96bc1f5b465a8070ac88ffa8a5b","datavalue":{"value":"Computational results","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096550$86322D92-94E0-46FF-BD2E-0594862002C3","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096550$1F051DD7-9BE5-4162-BB90-3BB46BCD4F11","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"232e19869ad1b77fc4b60187193e57bf7361853f","datavalue":{"value":{"entity-type":"item","numeric-id":3890444,"id":"Q3890444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096550$2F4C3EF4-E976-4E21-B4A7-62ECD72A0CA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec543139c5c450ba40e3b2aaaa64e9cbe50decd6","datavalue":{"value":{"entity-type":"item","numeric-id":5665016,"id":"Q5665016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096550$8F7229E2-F6A8-4E1A-BADB-925681AD00EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5fe003e8a37b9afbc7a45b7f8f19aac5670baa6","datavalue":{"value":{"entity-type":"item","numeric-id":5578578,"id":"Q5578578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096550$A47B67AE-497A-406F-89DE-8C00AD4E2827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"173a152b7bef310bc7cb51fe184d1e6d3346ac20","datavalue":{"value":{"entity-type":"item","numeric-id":3037137,"id":"Q3037137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096550$4216C6B9-C3B0-4C2B-AFB1-F94702A12458","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f5b41a30d26b4b1c8759e73ad3eb0fa58b91128","datavalue":{"value":{"entity-type":"item","numeric-id":5184697,"id":"Q5184697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096550$6BB7F7C7-7DF0-4AEF-A196-FB941F40066F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f79a1d18ea44fbafe3e9cf6e7e0dd36e7e68f06","datavalue":{"value":{"entity-type":"item","numeric-id":3762096,"id":"Q3762096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096550$662746B3-593C-4C31-9609-A791A2E86AC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d64e4c37be7ab17f731de955cf6e36e6ff1a42c","datavalue":{"value":{"entity-type":"item","numeric-id":3206662,"id":"Q3206662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096550$E53F9707-253E-4E87-922D-438965AE3AE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0930d57b126d4670b8351b41154baa4cb1f96e2","datavalue":{"value":{"entity-type":"item","numeric-id":5671788,"id":"Q5671788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096550$A1698783-F134-43ED-9C48-69C068DC92B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db3e78d1140188a7cc5b2a78aad0e0f451936237","datavalue":{"value":{"entity-type":"item","numeric-id":5613007,"id":"Q5613007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096550$C7BD49D2-2E1C-4698-BF05-2B8F9F961B36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0691e75528fafe118d25c8f1f2da5ff28d3c3d76","datavalue":{"value":{"entity-type":"item","numeric-id":5563210,"id":"Q5563210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096550$B4E14543-4371-46A5-820A-5CFADF5F049B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"149de7420c61b089581cb1824380bc9d41ca8783","datavalue":{"value":{"entity-type":"item","numeric-id":3762096,"id":"Q3762096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86884035888034ebb1e091626b86357c5e7db074","datavalue":{"value":{"amount":"+0.8493146896362305","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1096550$BA257A54-CB75-469D-91FC-70A437F26B47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7cdf9946d1a4d8fb5fc418d8c7b8c4b5320dd45c","datavalue":{"value":{"entity-type":"item","numeric-id":3980516,"id":"Q3980516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"632815534d5840ac8b52cf1d8c5c804e17f21409","datavalue":{"value":{"amount":"+0.8463484048843384","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1096550$12D66BB0-85F4-458D-8609-F95DE414F55E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0980162b558068dd02153877f837973f46613103","datavalue":{"value":{"entity-type":"item","numeric-id":505157,"id":"Q505157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87c05f517dc171bc83c45b6ce709e2a0a8986ec6","datavalue":{"value":{"amount":"+0.8463108539581299","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1096550$243BB692-8FE4-4A2D-8979-9A87F72EC053","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ad37504be5973a448880a412fa0922d56f15130","datavalue":{"value":{"entity-type":"item","numeric-id":3786261,"id":"Q3786261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bb1c577619478c7ff4e9c31740df750b30044ec","datavalue":{"value":{"amount":"+0.8300920724868774","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1096550$711441D6-E0CA-44AA-98F7-A8CE95229041","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49f1190886c70fc2ba8045ca295b9a806c45dc07","datavalue":{"value":{"entity-type":"item","numeric-id":4018534,"id":"Q4018534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82d87eca4866b3dfb1b0eb1ee015950083d80b81","datavalue":{"value":{"amount":"+0.8251705765724182","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1096550$A51D3365-5F62-430E-9F29-5F2BF7F2E7B7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generalized travelling salesman problem through n sets of nodes: The asymmetrical case","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Generalized_travelling_salesman_problem_through_n_sets_of_nodes:_The_asymmetrical_case"}}}}}