{"entities":{"Q2783791":{"pageid":2794529,"ns":120,"title":"Item:Q2783791","lastrevid":42009686,"modified":"2025-05-22T09:26:02Z","type":"item","id":"Q2783791","labels":{"en":{"language":"en","value":"An exact constraint logic programming algorithm for the traveling salesman problem with time windows"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1730763"}},"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":"Q2783791$52AF4FF1-A510-46E3-83E1-990877856835","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2826d64d86441ad1d8fb7c4aa29b8312402aee01","datavalue":{"value":"0987.90086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783791$B35ED6A8-D53E-47E8-8CD1-0C6AC1A0D55A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4cb42fe85e5b74aa2a5f43224d7349a607e89b65","datavalue":{"value":{"entity-type":"item","numeric-id":239561,"id":"Q239561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2783791$C34D040B-6A61-4791-941C-997191664082","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c1b1daef8f6648b31bd9c365da99db923f5676ee","datavalue":{"value":{"entity-type":"item","numeric-id":203166,"id":"Q203166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2783791$D064F824-2D3E-4E44-BD4D-09BC09F7DCC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d4eb34492241d1703c012bfd9f7459435e92f7d0","datavalue":{"value":{"entity-type":"item","numeric-id":227994,"id":"Q227994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2783791$3ADFE2D3-7671-4E26-923A-822ACAEC87CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"160e47863dce07c62ad65c4271a97d4b296c3835","datavalue":{"value":{"entity-type":"item","numeric-id":794930,"id":"Q794930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2783791$87A66186-7D17-4F68-9CA3-598C75721844","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4dcafa569b26f35e2ed2e5c8c4c4caae0cf19841","datavalue":{"value":{"entity-type":"item","numeric-id":86630,"id":"Q86630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2783791$32960054-619D-42BD-BEED-C4458F53C27E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6863e602815acb5f8df8b9dde489285ae2aa87d0","datavalue":{"value":{"time":"+2002-04-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2783791$4848BC74-0C34-442D-85EB-9ECC09358CA7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7402f526c1cbcb2cc261953135150c7cc8fd4a8c","datavalue":{"value":"https://semanticscholar.org/paper/e14ad53dd65244bccff68fbce31e5e9301c12981","type":"string"},"datatype":"url"},"type":"statement","id":"Q2783791$E51661BA-6C0D-4094-A058-0C4FB5EF9347","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783791$FFEDEDA3-2849-4B51-9835-1610860EEB31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"63b70ec5cb69f5c5c9550409918141ca28bfae61","datavalue":{"value":"90C08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783791$1F605366-7A38-4F61-A53B-A62FFF2E8CCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783791$C82B6250-0E2D-4421-9B3A-428A91D16D63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b492f281b8f52c724f2bc547e7e570cccf4bd5e0","datavalue":{"value":"68N17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783791$55A81D66-276D-4297-BBF4-5D9C47230BA1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f84c7d604000732699dfa2679befc419eaa8edc4","datavalue":{"value":"1730763","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783791$6DAA7F01-8743-4E0A-8335-F379558537DE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32b70193b15cfa9820eaa83513ddb2267d9b694a","datavalue":{"value":"branch-and-bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q2783791$EB050BE8-0258-48D6-B105-89332D52362C","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":"Q2783791$346A0688-541C-49F0-9457-5EF86AF4025F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"10075e13e2f74ff38c5ddc1033761428d0cf7ddd","datavalue":{"value":"W2135644739","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783791$EDB19B88-D1D0-4005-8ED0-D60B2D970AFA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c1fe2a5f05ff01c50946e84f941ecbd5ae8cfa18","datavalue":{"value":"10.1287/TRSC.32.1.12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783791$4600CA92-353D-42C5-B141-A3B8FADE9968","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c96e81a5cdf017f19fdf22e33b9c99c76ce7205","datavalue":{"value":{"entity-type":"item","numeric-id":6096613,"id":"Q6096613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dbacc335916ac6ad178cc9adf46df56c21f14f78","datavalue":{"value":{"amount":"+0.9067","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":"Q2783791$08E2A5A9-DE07-4672-8DE9-1A6BFC1DE355","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b391029a23dcbf3f4482ffa9fa20e325a4a002a","datavalue":{"value":{"entity-type":"item","numeric-id":3342216,"id":"Q3342216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec98f53ea36b24ecd51951e4bdde3fb0e1ae1cad","datavalue":{"value":{"amount":"+0.90609384","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":"Q2783791$BFCCBC99-5AD2-4F9F-87BD-0912C961A956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68469d2ba8d7b5d946862b3486ec35643d75fef6","datavalue":{"value":{"entity-type":"item","numeric-id":2174903,"id":"Q2174903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ae3fa2600766b500a0665c5e4c30ccf5597d79a","datavalue":{"value":{"amount":"+0.90447927","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":"Q2783791$02F4B253-7DDD-432E-9139-976C33F4DF2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca4bf98030e9736ef72e686a1738a3c05bce663d","datavalue":{"value":{"entity-type":"item","numeric-id":4849335,"id":"Q4849335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1869b327d6145fbc056512468073ba71fb1ac26","datavalue":{"value":{"amount":"+0.9007829","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":"Q2783791$980DEBC2-3547-4C8E-9082-9141CA106BBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebb97781aba356fea5d81fa68174eba7dec48c9c","datavalue":{"value":{"entity-type":"item","numeric-id":1651554,"id":"Q1651554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0764bd6831b307ef020a43b01d037b99691ec32","datavalue":{"value":{"amount":"+0.8933934","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":"Q2783791$956A6AAA-E7DC-4D23-85AF-60CC135DED12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"faa1f01467735d948f96144afe431ead0034e40b","datavalue":{"value":{"entity-type":"item","numeric-id":1847167,"id":"Q1847167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7607a17dab754297611e4b3a662814d0bf5934fc","datavalue":{"value":{"amount":"+0.8899541","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":"Q2783791$965348F4-D777-4C87-902D-26CD21CBCEF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d5fe255803689f761f562a7f8787865e30ac9a2","datavalue":{"value":{"entity-type":"item","numeric-id":2815434,"id":"Q2815434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96b9cbe5bab6c3444cf027f2983230ba726a29b6","datavalue":{"value":{"amount":"+0.8873186","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":"Q2783791$5A141E1D-D410-4944-8584-F200BF28A0F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c271d170b8a84ff0f3fb0c999f550c8ad6b8cf2f","datavalue":{"value":{"entity-type":"item","numeric-id":5060801,"id":"Q5060801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75fcb366f4a0b6af9c646823d2f23d5c25f89208","datavalue":{"value":{"amount":"+0.88500345","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":"Q2783791$24010DA0-1602-49A2-B4B4-759B05A7512F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd9efdf9b30d601aab369c3eb156c640153b0770","datavalue":{"value":{"entity-type":"item","numeric-id":4715981,"id":"Q4715981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd0ec8da34c98fca67a152513f5fd10a2a774e88","datavalue":{"value":{"amount":"+0.8847547","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":"Q2783791$DF0A1599-655E-4FD8-AE8A-2E554951E404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a38190d73d8583b6cd0a413c15e0e5928253050c","datavalue":{"value":{"entity-type":"item","numeric-id":4367231,"id":"Q4367231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9daf08fc88d4725b3a0b5a08470050ea0f1e8c6f","datavalue":{"value":{"amount":"+0.88411176","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":"Q2783791$DF3ABBD0-8DEB-49F9-8B61-4489DCC350F1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bfef41326302988f0b57394dc44d639f917a1ed7","datavalue":{"value":{"text":"An exact constraint logic programming algorithm for the traveling salesman problem with time windows","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2783791$F11D07B8-7E74-4599-BB15-C561BD4B9ACB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b7a0c39bf1841a7f4e7fcf8ae63242abbe0f50ad","datavalue":{"value":"This paper presents a constraint logic programming model for the traveling salesman problem with time windows which yields an exact branch-and-bound optimization algorithm without any restrictive assumption on the time windows. Unlike dynamic programming approaches whose performance relies heavily on the degree of discretization applied to the data, our algorithm does not suffer from such space-complexity issues. The data-driven mechanism at its core more fully exploits pruning rules developed in operations research by using them not only a priori but also dynamically during the search. Computational results are reported and comparisons are made with both exact and heuristical algorithms. On Solomon's well-known test bed, our algorithm is instrumental in achieving new best solutions for some of the problems in set RC2 and strengthens the presumption of optimality for the best known solutions to the problems in set C2.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2783791$E8F1F965-38E8-4439-A696-7B855E4FD8E7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2783791","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2783791"}}}}}