{"entities":{"Q759661":{"pageid":761510,"ns":120,"title":"Item:Q759661","lastrevid":48765937,"modified":"2026-01-05T19:46:30Z","type":"item","id":"Q759661","labels":{"en":{"language":"en","value":"The symmetric clustered traveling salesman problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3882229"}},"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":"Q759661$BD9CBA53-776A-4E1D-B899-0B12B66F0331","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b442f391224d12c5db92379addca37421e460698","datavalue":{"value":{"text":"The symmetric clustered traveling salesman problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q759661$EF73624E-CD49-42E1-AE2C-645FFE0EE738","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bc00b3c3ff9273f5a3d65faac42b2a054cae77f6","datavalue":{"value":"0553.90100","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759661$4DE00FA1-B4CB-48F6-8222-D6DB25949534","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ced19a9fd75179ebc2156d587c863e459b0f1327","datavalue":{"value":"10.1016/0377-2217(85)90309-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759661$48228782-26DF-4AE9-A963-9F7D5FD6E2A9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a403af299549408e1e19f14d7aa459238721452","datavalue":{"value":{"entity-type":"item","numeric-id":759659,"id":"Q759659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759661$77D79078-E04A-467D-AC6D-6C039BF37390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2a981753343b2f01f33403fe406af396c6839ce8","datavalue":{"value":{"entity-type":"item","numeric-id":759660,"id":"Q759660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759661$F2905000-296E-4D50-A60E-B8013FD7D4BB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759661$A4AD20E9-5385-4A74-9623-BC176665CFCE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q759661$000B6A73-0A50-4E57-86D4-9A7F4725ECC9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"63df68e68c9775e425791452b52a78dbc67afa89","datavalue":{"value":"A travelling salesman problem (TSP) with n cities and symmetric cost matrix C is considered. The cities are partitioned into m groups called clusters and there is an additional constraint that all cities in each cluster must be visited contiguously. This constrained problem is called the clustered TSP (CTSP). Let C' be the matrix obtained by adding a large positive number H to \\(C_{ij}\\) whenever cities i and j are not in the same cluster. Any optimal tour for TSP with C' as the cost matrix is an optimal tour for CTSP with C as the cost matrix. However, the usual branch and bound algorithm performs poorly with the cost matrix C'. A bounding approach based on an adaptation of the Lagrangean relaxation approach with the 1-tree relaxation for the CTSP, and by introducting a new multiplier corresponding to the constraint that every feasible tour for the CTSP must have m edges (i,j) with cities i and j belonding to different clusters, is described. Heuristics are developed for finding upper bounds, and some techniques are discussed to detect and eliminate nonoptimal edges. With these changes, the branch and bound approach turns out to be satisfactory for the CTSP, as illustrated by computational results on problems involving up to 150 cities.","type":"string"},"datatype":"string"},"type":"statement","id":"Q759661$3EA84A57-DB3C-4835-9927-548B6CD0F8E7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759661$F0E159B9-6B37-4486-80B1-1EDF98EEFD6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759661$C2672CD7-9270-493A-A23D-76A29BEB720D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759661$3880A5EC-DA92-412D-8C99-5E260B9D9F0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759661$34FBA51E-04FE-4BF8-922F-B82E2F13E2D3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e0115a0afb298acbd49e208dedb77d69fcc74499","datavalue":{"value":"3882229","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759661$F3069503-2C8F-443C-BEF8-20C84C86D9AD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"028f60854abcdee8ddb221f3ec176a3951acf23d","datavalue":{"value":"grouped cities","type":"string"},"datatype":"string"},"type":"statement","id":"Q759661$FEBDA496-D208-41D6-8CD9-63CF75174D12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b76c57478e7480f586895f73fe9158887c3cad6c","datavalue":{"value":"travelling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q759661$9628B709-70A0-43A2-8B66-D97BF223576F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"acc60f184a27332256ed05ca8011bb981a711524","datavalue":{"value":"symmetric cost matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q759661$2443CFEA-A638-4DBD-8C40-5E1189764CCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec925930cd5cb92d73c0f9b0b994159f9e248e79","datavalue":{"value":"clusters","type":"string"},"datatype":"string"},"type":"statement","id":"Q759661$3B6D17B1-0F08-4A39-8C42-AC90049064C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08d1da0f8d015377f197bbae3a9703b0be9cb830","datavalue":{"value":"bounding approach","type":"string"},"datatype":"string"},"type":"statement","id":"Q759661$29F36CCA-575A-4E17-A478-36FCA5E9F400","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8799b7912a65618313e794ea0d0ce0d6a1e22e46","datavalue":{"value":"Heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q759661$7A2B096A-7A70-43EE-AD94-71E250C801A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdc6164cf25ab131dbb818bbd16bab28b6f9d095","datavalue":{"value":"branch and bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q759661$82AD1FED-2D00-4982-9151-9046D211DBB1","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":"Q759661$B0423DEA-C6C3-425C-B08F-1B2BF914D62B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"90a5505696f03602b336cda3c96a9713df1b5441","datavalue":{"value":"https://doi.org/10.1016/0377-2217(85)90309-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q759661$DBDA1F3F-84CE-4ADB-9832-C8D5EDF33623","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"834cea0e3b6872bce8873ab05515696ce186a246","datavalue":{"value":"W2080894457","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q759661$A3E636EC-6ACF-494C-BB6D-2BFA67EDDD1E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f73eb84a543b338a4a079febb7b97c03a91da92f","datavalue":{"value":{"entity-type":"item","numeric-id":5633847,"id":"Q5633847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759661$C6D37D52-5919-48EA-BBB8-F129A8DB35DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b5b903864765fb40a5b80f7f222eabf61ff3f0c","datavalue":{"value":{"entity-type":"item","numeric-id":5641007,"id":"Q5641007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759661$0ADD4B22-7882-4666-96E6-122C304F41D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2ff200c2711738a4abc27ef63aba660063d9950","datavalue":{"value":{"entity-type":"item","numeric-id":3337972,"id":"Q3337972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759661$7833294E-5548-451C-9D4F-EC1589C3277B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d1e8cd6eb2e0a5b1dbc86fe07f978d07189e52c","datavalue":{"value":{"entity-type":"item","numeric-id":5543949,"id":"Q5543949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759661$064C757C-AF79-4680-ABA3-B74F6C88C50A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d819776f7e9a51fdd430a0d73abdc1717b13fa7","datavalue":{"value":{"entity-type":"item","numeric-id":1253617,"id":"Q1253617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759661$6A8C0090-DA05-4312-882D-8C8851D4DDE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9586825a9df16830137e7d33acb174b1d38d8c12","datavalue":{"value":{"entity-type":"item","numeric-id":1158108,"id":"Q1158108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759661$25D4930D-6EF5-4B18-B40B-A2A33C676AEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f85f1bb9a2b42e8fd917505f47354b45d357319","datavalue":{"value":{"entity-type":"item","numeric-id":1170119,"id":"Q1170119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q759661$407A8B13-3825-43CB-9042-F89210F99CF4","rank":"normal"}],"P1643":[{"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":"ad07e2cd979a215021bf49494e0980fb814d8041","datavalue":{"value":{"amount":"+0.8530155420303345","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":"Q759661$45A896F8-02E0-4EB5-A8E6-950747D97511","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cefd393b7f582ce010454fc77e44350a5b635b10","datavalue":{"value":{"entity-type":"item","numeric-id":4703656,"id":"Q4703656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"038052c8307e2cdcdd90693e95d2c44f9f7a747a","datavalue":{"value":{"amount":"+0.8361167311668396","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":"Q759661$7C12394D-4633-4D83-B01A-B24487BF44D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d5a99d88cac0465d66835244fea32dca3b598ca","datavalue":{"value":{"entity-type":"item","numeric-id":3297279,"id":"Q3297279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbb9d82bd247588a5e8d0406710c87271843a690","datavalue":{"value":{"amount":"+0.8319724202156067","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":"Q759661$CB93EB15-6D56-42B7-AC3B-EBECB5A78A0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae61a2d7a0ca45bfc1790cd0cddf5ab15c045a73","datavalue":{"value":{"entity-type":"item","numeric-id":1806732,"id":"Q1806732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"767ebc912b40d1038e233e1298b42f7ede94917e","datavalue":{"value":{"amount":"+0.8218192458152771","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":"Q759661$41DB61A3-87C8-4D55-B8E9-554379A826F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1853522516c288ae4387dc51ba0aeeb23b4d44e1","datavalue":{"value":{"entity-type":"item","numeric-id":5133137,"id":"Q5133137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b05aba047ffce14a4886853977a0b9694433bb5","datavalue":{"value":{"amount":"+0.821819007396698","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":"Q759661$740F7D19-4DE9-4302-BDC5-61BF9B2422DF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:759661","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:759661"}}}}}