{"entities":{"Q1083379":{"pageid":1094131,"ns":120,"title":"Item:Q1083379","lastrevid":48987844,"modified":"2026-01-06T10:09:20Z","type":"item","id":"Q1083379","labels":{"en":{"language":"en","value":"The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3974767"}},"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":"Q1083379$0B051599-6AE4-4445-8EEA-511412573184","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"30eaea9d50e617bef92d4e6d74165ccc80acad26","datavalue":{"value":{"text":"The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1083379$3589299A-70F2-4E44-9A06-408CDFF8EB22","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"49d8a7f8e5660ead140fb211277fdad6471b0fe7","datavalue":{"value":"0603.90132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083379$056ECB1D-4C79-45C2-A184-21852E1E898C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e3c199d4aaf0aff0db828f6f10753d7d7500fc31","datavalue":{"value":"10.1016/0166-218X(86)90087-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083379$D82E4ECD-6AD3-4995-8019-45D529C3E009","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f8da75ed8378ab8989ef128712f7e53d2d633f97","datavalue":{"value":{"entity-type":"item","numeric-id":1066817,"id":"Q1066817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083379$B9269E49-D50F-40DD-AC2D-B737A6CE47DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"21fe465e77678045f79e6432c4c08366e464b477","datavalue":{"value":{"entity-type":"item","numeric-id":684329,"id":"Q684329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083379$473CEBEA-AAFE-40F7-9306-91A4C6A304AB","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":"Q1083379$E8E6C15F-D3C7-40B3-B269-30E4C0B3BA53","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1083379$FD2312CF-6E30-4839-A9EC-2B30F9662BC5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8e292e99271843af4578cdd9a04e828bd6b80c91","datavalue":{"value":"An algorithm of Held and Karp for the ordinary TSP is extended to the following situation: Given n cities and m salesmen, find m tours, all starting at the same given city, so that no city is visited twice and total distance travelled is minimum.    The algorithm employs a Lagrangean relaxation, a subgradient procedure to solve the dual and a greedy algorithm to obtain minimal m-trees. For up to \\(n=50\\) cities, solutions can be routinely obtained; computational experience with \\(n=100\\) is documented, too. Alternatively, the problem can be transformed into an equivalent ordinary TSP with \\(n+m-1\\) cities. Whether the approach given here is more efficient than solving the transformed problem remains to be an open question.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083379$2ADC4975-4341-4B63-981A-FC52EE11C5D9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083379$77BB60AF-78BF-4C6F-928B-A0E4F7823F44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083379$9195EFA4-906C-494B-9258-10AA80AA9F3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083379$55C72909-A49C-4F3E-B003-322D9982EB2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083379$A50042F2-CFC5-4547-AA11-A7DB3429B106","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6b6daa52fdc5961fdebfbcae6ef520752994d1b1","datavalue":{"value":"3974767","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083379$FDB977FA-CDC8-445F-BB0F-02C6C0F9B881","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"98e9d0f2b32d69050a8c6b3190131f67b9330cdb","datavalue":{"value":"multiple travelling salesman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083379$2988A33E-FB57-4052-95F1-02EF567A261D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"930816699e323987bf987f4de63664e42a9aab61","datavalue":{"value":"minimum spanning trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083379$D2C147E7-5C4A-4C20-A168-9EE0F2BE3D36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"468a9760790c50a8f14ee210166e4f56f71c3ca9","datavalue":{"value":"Lagrangean relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083379$733F1E76-1B99-4B5B-B6D4-456D1AB5C061","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"33c652f83343364d928c1e64040f570db4d9e2ec","datavalue":{"value":"subgradient procedure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083379$9CEDAA41-56BE-49E1-9A8E-8802F1D747C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083379$21CDE02F-D8ED-44CB-8DA9-F07963314E10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2547fe05fc38d862a3c0fa5dd3d72d33319bce3","datavalue":{"value":"computational experience","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083379$B849BC77-D6E2-4B4E-BD79-048E36DB0ABF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7ce2e58fadab72e48061115ef741265ae9f57522","datavalue":{"value":{"entity-type":"item","numeric-id":1224948,"id":"Q1224948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083379$711E1513-A54F-4E87-B942-30BAA8A3FDBA","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":"Q1083379$A28C6FA6-2825-4818-B3E5-7E133464FF93","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d00c31d54eadcb2bb7c1724e272878d138fea19a","datavalue":{"value":{"entity-type":"item","numeric-id":4156164,"id":"Q4156164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083379$8E3272FF-5207-452F-9805-8EB217ABAF1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fd2865c347636a0d54c9d361e775f17ea6bdafc","datavalue":{"value":{"entity-type":"item","numeric-id":3932576,"id":"Q3932576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083379$FD3132F3-5630-464C-88BE-C92ADDAA947E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e51e837fb3fab405d5f98f757bf2c4a81d6e88f5","datavalue":{"value":{"entity-type":"item","numeric-id":4770207,"id":"Q4770207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083379$90C0A780-BFE1-4A3A-BCB0-56A7E40ADF83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4042a6a8925d33e7ac25ffe3a11c3e8654542cc4","datavalue":{"value":{"entity-type":"item","numeric-id":5668601,"id":"Q5668601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083379$FD6824DF-A25D-4F0C-9207-3B89DB277699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bea7828a4f88474614a0a37a4be80d1ae17b020","datavalue":{"value":{"entity-type":"item","numeric-id":5641019,"id":"Q5641019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083379$1F9D76FF-F108-420C-82A8-ACDAE61C5F90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a03ba2c3dd778b77f2bbe2eaa0b2a279110f513","datavalue":{"value":{"entity-type":"item","numeric-id":5650509,"id":"Q5650509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083379$FE1C85D9-62C3-42D0-9055-680773451601","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f57cb52d5b46d9b84e5c5fdecf79231c1f4f0138","datavalue":{"value":{"entity-type":"item","numeric-id":4178782,"id":"Q4178782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083379$B67E3F9A-C6A5-4691-A54D-0A6DB81E1137","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95ac60093948df00a6d95c2fbc5d8b2ff34bd5d6","datavalue":{"value":{"entity-type":"item","numeric-id":4178800,"id":"Q4178800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083379$624E106B-5651-4FD0-8182-4E223B97C614","rank":"normal"},{"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":"Q1083379$F0F4C1DD-9131-4EE7-9F0E-DEF1C95600FB","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":"Q1083379$442E77D3-BF27-4BEF-8F71-96DA0C1C6EBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8634671064abab94a7b8dbe7f85bfc42274b7db2","datavalue":{"value":{"entity-type":"item","numeric-id":4770776,"id":"Q4770776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083379$EC2CDB7E-F5D0-4BAE-BF12-1757F80D97DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"731e99376e8702c5d355c7d2ba0ddb139c20b787","datavalue":{"value":{"entity-type":"item","numeric-id":3899825,"id":"Q3899825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083379$C5871788-5DEB-4019-8FC3-19735A190C03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cdc8ab92d92234a6c60e69beca185042cc554d5","datavalue":{"value":{"entity-type":"item","numeric-id":3281501,"id":"Q3281501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083379$F6E46F2A-A627-4FAF-8F08-EB53002C5995","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63866871df3885e792a8232ec44df46998355118","datavalue":{"value":{"entity-type":"item","numeric-id":5670445,"id":"Q5670445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083379$BF5E7C16-32F4-4670-AA40-DF850D62E476","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e704d67d9c33080bbbbb93473407f9b2afff542","datavalue":{"value":{"entity-type":"item","numeric-id":3770307,"id":"Q3770307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03c021c60be2e191cf9906fc8cec387f41ef71b6","datavalue":{"value":{"amount":"+0.8459765911102295","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":"Q1083379$BD860D3E-430F-41EE-9994-98F0B2575179","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ec2769b9c70ff03522675024edcb60a09806927","datavalue":{"value":{"entity-type":"item","numeric-id":3753823,"id":"Q3753823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8cfc27a5511e3d03dcf98e8442c0a82e32b4360b","datavalue":{"value":{"amount":"+0.8201996088027954","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":"Q1083379$65D3FB9B-192C-4A35-AF89-0A67DC0AB774","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":"d12fffa58f4b32922ce482099d4d683ecdf52504","datavalue":{"value":{"amount":"+0.8182418942451477","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":"Q1083379$D67C59B6-DA25-486F-8471-DB278845D7B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c53f67e79b769ee6a27ad6e0589f54bae1c887a","datavalue":{"value":{"entity-type":"item","numeric-id":4371607,"id":"Q4371607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd13831c68ad9d3e0eac3e4f971c88d0a8b0e18d","datavalue":{"value":{"amount":"+0.8156920671463013","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":"Q1083379$A2E4BF12-321F-4293-AF06-3F04E4F3BF4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"421a44ea561d12439ee43f24359b2ee644067542","datavalue":{"value":{"entity-type":"item","numeric-id":1671016,"id":"Q1671016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"511b8ff5d01193289808587fa760f96ff24ca7e1","datavalue":{"value":{"amount":"+0.8150576949119568","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":"Q1083379$E79DD044-CA5F-4855-9E5C-7FAE9051C7EE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1083379","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1083379"}}}}}