{"entities":{"Q918861":{"pageid":920709,"ns":120,"title":"Item:Q918861","lastrevid":42762784,"modified":"2025-07-10T12:42:23Z","type":"item","id":"Q918861","labels":{"en":{"language":"en","value":"The Hamiltonian p-median problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4160458"}},"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":"Q918861$D38756B1-22A9-41CB-9A34-659CEB27C18A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"195acfa9832f64590c8c1a997d23d215214e7c24","datavalue":{"value":{"text":"The Hamiltonian p-median problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q918861$BEABAD4F-CA9B-425B-AEE7-326D6DABB3F7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8d702d8b0cd9bd61c013dac03bdbb70445ce25af","datavalue":{"value":"0706.90039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918861$F2B80C18-4B8C-4481-828A-E50B24880C7C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4c0fbc7096577e111e1a2ca5be323c90dff800b6","datavalue":{"value":"10.1016/0377-2217(90)90092-P","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918861$BD2A6EC4-2299-45A9-AF15-A915190BA4C3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3d56612cb84f7069100c4cabafc4cc7f11973342","datavalue":{"value":{"entity-type":"item","numeric-id":914554,"id":"Q914554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918861$AF429213-FFAB-4210-B83B-8D71717E7121","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":"Q918861$CCCBEFB6-C053-45F2-A46F-2494CCB37B88","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q918861$9EA600EF-CC86-4B62-A69E-5B15DB5C9BAC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2da1245c4f394020813f1cf2ff04f0034ac730ca","datavalue":{"value":"The Hamiltonian p-median problem is to locate p depots to serve a given set of customers through p distinct Hamiltonian cycles at minimal total distribution cost. This may be modeled as a set partitioning problem with cost of a subset equal to the length of a shortest circuit of the subset.    The paper describes several heuristic solution procedures: a clustering method which builds a solution, a 3-optimal improvement method, a solution building method based on the 2-matching relaxation, and a modification of the spanning walk heuristic for the travelling salesman problem, applicable only to planar problems. These methods are tested on several random test problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q918861$73B6908C-F9EA-4CB4-BBFA-39E7139B05F7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ad37711539483f94ecc5e7c9236f6acd7c19a03","datavalue":{"value":"90B80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918861$C5720B6E-3424-4807-8725-C92FC17CBC9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918861$389A0E42-4937-4D51-A611-B57584A64DBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918861$CFADFBA2-FDE3-4A04-9A1B-DE1FFB7105DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918861$DEBB30D1-89CE-47C6-8AB5-B33F1B357964","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7530ae852489b120b1b979fe5df373da24dc8e97","datavalue":{"value":"91C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918861$BB47FFE9-7FB6-409E-AB71-9040E0648D82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918861$F5AB71A1-CB22-47D7-B1B8-EDF0700371C5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"45a7c133a59e32b1c8ecd20b4fddb93fe63e7179","datavalue":{"value":"4160458","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918861$BE345E23-BE21-4B0E-8DE3-B26EE1A9F362","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be9847b5080561732e2df3fe2a5afade2166808c","datavalue":{"value":"routing","type":"string"},"datatype":"string"},"type":"statement","id":"Q918861$7315EF15-3924-423A-B0C5-BC4654A83E0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a116936c38a51a0522ce224ce891c6b8039ba236","datavalue":{"value":"Hamiltonian p-median","type":"string"},"datatype":"string"},"type":"statement","id":"Q918861$FCC238D5-72A9-471A-AD4D-D91028F69869","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52de5883751daf770e52b335cde888ca59e1a57c","datavalue":{"value":"set partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q918861$52983154-BBEA-4938-93EB-F9E767D88DF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f641bd239fe6f0d5fb2cc0d2b3f89cbc609bab87","datavalue":{"value":"heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q918861$C13DD36D-D7AC-409E-901D-78915EB3B327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2786e1ba642e3cbcd7e642edf6ab834e2e798a22","datavalue":{"value":"2-matching relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q918861$CDA17240-03D8-4A7F-B448-E8C1F7F27048","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b76c57478e7480f586895f73fe9158887c3cad6c","datavalue":{"value":"travelling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q918861$12577951-1D4C-454A-AF14-67C840706047","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5e09f3da1a7483864918926ab5885138a8f45aaa","datavalue":{"value":{"entity-type":"item","numeric-id":166210,"id":"Q166210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918861$78F9BC79-679A-4C5A-99DB-DC8D2BF700BB","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":"Q918861$23D8AA2F-07E2-40B2-8D6B-1593BB5E6086","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"762a4bf1c211653d191d565d27fcf0d3c0c6e41b","datavalue":{"value":{"entity-type":"item","numeric-id":918861,"id":"Q918861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918861$40386F8A-726C-4082-803B-7FE8A4781C18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"363f53eceaf2008d406e761c580f5afbbf2a864f","datavalue":{"value":{"entity-type":"item","numeric-id":3329224,"id":"Q3329224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918861$C030B484-9C8D-4EEA-8414-71D9F52BC32D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10b0c899a42f8ecee4775cc6824aa426fbe4b13b","datavalue":{"value":{"entity-type":"item","numeric-id":3703612,"id":"Q3703612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918861$8A5AFD50-EDA0-4166-A0CD-A04483DA9A20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e4b98677b3421a2bf46a6615f8da739f8485480","datavalue":{"value":{"entity-type":"item","numeric-id":5677061,"id":"Q5677061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918861$5BF883B7-89F2-4AC9-B568-DB580F79319E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbc5f443e1da82c56df0b2fdf8a86f5f1c7d2ab1","datavalue":{"value":{"entity-type":"item","numeric-id":1143306,"id":"Q1143306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918861$CA954C70-1747-4B9B-9487-BBCFCE81569D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2105ff279dc4d548bf5fd676a1cf44ea440124ae","datavalue":{"value":{"entity-type":"item","numeric-id":4173216,"id":"Q4173216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918861$FDC1C683-8955-49D8-AE72-9F9A88E85711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e524f80f1cad4115199cf4e200cbac9ac306c7fa","datavalue":{"value":{"entity-type":"item","numeric-id":1148218,"id":"Q1148218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918861$BF65D557-FF76-46FD-8421-4CBD402C4D40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44f52a4c1e589b94e4d72a9050e571e8475832cb","datavalue":{"value":{"entity-type":"item","numeric-id":1173005,"id":"Q1173005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918861$F1A731D0-E8B3-4569-BD7D-8D7C02E653A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c85ad1c11b4c2c66512da23bc9ecc32c36b4a62","datavalue":{"value":{"entity-type":"item","numeric-id":5510390,"id":"Q5510390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918861$FD9EFBD6-68BF-495C-AD82-B6515586563E","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":"Q918861$5EEB0613-1894-4C3A-8D1C-99A4C7288B71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59e6892aa2c3225a728611515ad6c78734dbd590","datavalue":{"value":{"entity-type":"item","numeric-id":1148213,"id":"Q1148213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918861$7D59A531-29C6-4DE9-A23D-48A98963972A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3c15096ab3c6c7cf0997a36ff264315f46cfddce","datavalue":{"value":"https://doi.org/10.1016/0377-2217(90)90092-p","type":"string"},"datatype":"url"},"type":"statement","id":"Q918861$3D773134-DBF1-4B24-9976-0D270F42524A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5871f01e6d5eb17b22b8e55d979eee32e8263f1d","datavalue":{"value":"W2011702214","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918861$4FEA9E07-8ACE-4F35-B754-E1CFAC5E7589","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6ca41de06a2eaee6ca96e0dfe8f6542ef558d09","datavalue":{"value":{"entity-type":"item","numeric-id":1578475,"id":"Q1578475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"caa6b53907240414ef19af4c0e9638f41152105b","datavalue":{"value":{"amount":"+0.99196273","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q918861$2266D196-9FFF-4F7D-BED5-F0BB9559EED3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7eb0db4185c48a45c8aec3dd9c2480158b94370e","datavalue":{"value":{"entity-type":"item","numeric-id":323162,"id":"Q323162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c837c841dcb923e63c95b78c176947ecf9934cc3","datavalue":{"value":{"amount":"+0.93173975","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q918861$57D63A4C-DA8C-4F17-B873-A41F0511CA39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6f65a44bc1ac62a52beb9b253e9fe915da69c72","datavalue":{"value":{"entity-type":"item","numeric-id":5422825,"id":"Q5422825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77e3b90951651b21aab205b1fea9eeaad88cfe3f","datavalue":{"value":{"amount":"+0.9301722","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q918861$99C47922-3185-44A5-8D9C-F5057945C861","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1388ab20489d237d7979cd1040ce1b265b5ccceb","datavalue":{"value":{"entity-type":"item","numeric-id":3358523,"id":"Q3358523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c2b204d45b3e34669a7b7e508bfcca0b9cbe51a","datavalue":{"value":{"amount":"+0.90671253","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q918861$6E7DC501-458F-448F-85FA-0BF4D668336F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"902539f481455c5d4bb1cad906d11571e3a07c60","datavalue":{"value":{"entity-type":"item","numeric-id":4672943,"id":"Q4672943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc02e8d3433b4fd448488599769ea051513910b6","datavalue":{"value":{"amount":"+0.8982084","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q918861$980DCADD-A4E1-40A1-BE2B-F9FABD23D110","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df14b550a5dc39cc1425b24f8fea6c35ec4b3917","datavalue":{"value":{"entity-type":"item","numeric-id":2960363,"id":"Q2960363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1124c338fbd9a9eda188407c59d94f800188aac","datavalue":{"value":{"amount":"+0.8943286","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q918861$1EC2E68D-0264-4973-9A49-CEDC3FB6DDBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b20f244837b82b04ce9805eb543fba0e6d038111","datavalue":{"value":{"entity-type":"item","numeric-id":4642484,"id":"Q4642484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44f4cbe226f40913b91895ff1bbd30bcbec58d9d","datavalue":{"value":{"amount":"+0.88972145","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q918861$9642B14D-A748-42C5-ACEB-6E7E98C9B16B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f8f4558bba3979d12e8887d5e0d6e32bd190517","datavalue":{"value":{"entity-type":"item","numeric-id":3091521,"id":"Q3091521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f87301417a782cddf0d0f7ea8f4c693b122e12a3","datavalue":{"value":{"amount":"+0.88727313","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q918861$893938EC-7EFE-468C-834E-D631324E5BE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d9341ac04fba3a59641331043402177b830e977","datavalue":{"value":{"entity-type":"item","numeric-id":5365103,"id":"Q5365103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f82f6571b9cfc62e0bc3b7c2212336aef2d52d4","datavalue":{"value":{"amount":"+0.88041615","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q918861$C42FD84B-9FC4-4EFF-8D51-5E20DFA9B3D8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:918861","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:918861"}}}}}