{"entities":{"Q1123818":{"pageid":1134567,"ns":120,"title":"Item:Q1123818","lastrevid":66178728,"modified":"2026-04-12T08:04:34Z","type":"item","id":"Q1123818","labels":{"en":{"language":"en","value":"A reoptimization algorithm for the shortest path problem with time windows"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4110490"}},"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":"Q1123818$DFAE2C4D-5DC4-4A87-A678-B8D49A40C920","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2fac75cc87076e0e979ba83633b0eef391fb74ee","datavalue":{"value":{"text":"A reoptimization algorithm for the shortest path problem with time windows","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1123818$DF2FCEBB-616F-46D2-A47E-435D5CBD54B5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0ba28c618d2642470173098aa274310cb189b155","datavalue":{"value":"0677.90080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123818$D0B6EEA9-E01F-40E9-9FAB-314CB83F7345","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a312437cd0cd3610e311eb262323d1ec78443aad","datavalue":{"value":"10.1016/0377-2217(88)90034-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123818$7762E1B5-09EC-4E56-9240-D4F429CBEDC7","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":"Q1123818$D4B159C8-2340-452B-913F-2B1FC9737689","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1123818$C4292518-A837-4FD6-8932-2FBC5199C3B5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"21cec71d0b0e9d74229a28cd027324d16080d276","datavalue":{"value":"The shortest path problem with time windows (SPPTW) consists of finding the least cost route between two nodes in a network \\(G=(N,A)\\), while visiting each chosen node i within a specified time interval \\([a_ i,b_ i]\\). The problem of finding the set of disjoint paths, covering all the nodes of the network requires the solution of a sequence of SPPTWs, each one providing one path. After solving the k-th problem for a set of nodes \\(N^ k\\) (the authors propose a dynamic programming algorithm here), the nodes \\(S^ k\\) belonging to the optimal solution \\(X^ k\\) are removed from \\(N^ k\\) to form a set of nodes \\(N^{k+1}=(N^ k-S^ k)\\), used for the \\((k+1)th\\) problem.    In order to reduce the cost of repeatedly solving the SPPTW, a primal- dual reoptimization algorithm is proposed, reusing in the k-th problem part of the solution of the \\((k+1)th\\) problem. Implementation issues and the complexity of the reoptimization algorithm, running in pseudo- polynomial time, are discussed. Also numerical results are reported, including the efficiently solved example of a network with 2500 nodes and 250000 arcs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123818$AE8ABEF3-BCCD-4935-9DD3-F31D9961168C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123818$CD839538-BE6A-4CC9-A123-57C5CCEF762F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123818$D1FD43A0-5FFC-4DAF-B73C-EA6EB722EF98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123818$1265B9E4-4EA6-48B2-AF34-B585AEA7B703","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123818$01981CD9-B801-4884-9B61-7D8184889EAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123818$9714C248-2335-4180-A3E2-C92719E7A99F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"18d958e39e153a075e9c134a39a5ba1b1ce04ac2","datavalue":{"value":"4110490","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123818$98289277-2138-4080-9FBD-9078118972AE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f85e9f2721221f48af2e899508349c71e3faa29f","datavalue":{"value":"shortest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123818$B8081BAF-E8CA-4B6D-9778-67DD824A6857","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"668c727f1704bc4567b7b5eee09538faabe8115e","datavalue":{"value":"time windows","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123818$B5D3F6B0-5CCF-4F7D-9ADA-4D7E92E3C4EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1158d628f510dee867acc02e903f0fa17dd3833b","datavalue":{"value":"least cost route","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123818$8A96EBC4-4883-4277-9C1E-8CE2D16BB9BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18483549b1260233ac61cba056bdfdca500da59c","datavalue":{"value":"primal-dual reoptimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123818$D284A80D-4BEA-4890-86B8-F8565B78E2F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf56768d6b03a8bb6629a5b854586436247c3cd0","datavalue":{"value":"pseudo-polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123818$A863E356-B3D7-4568-8B0E-BF56917D6CA8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"622b16d11823b1525d20fd74b1b8ed7597116774","datavalue":{"value":{"entity-type":"item","numeric-id":1068006,"id":"Q1068006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123818$441E926B-AB1D-4DC5-8E8B-69F9DA442B15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"33fd9ca2317bf13b6f5b124a2b9103d0b54bc2ab","datavalue":{"value":{"entity-type":"item","numeric-id":319584,"id":"Q319584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123818$51788003-2B60-4D15-919C-1B6DD31BC280","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f044a93689ef39a8b6d0a9b2ab60fc8006dd98d6","datavalue":{"value":{"entity-type":"item","numeric-id":914544,"id":"Q914544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123818$DCBBD1D4-F642-4DC2-8B9D-02D0154FD25A","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":"Q1123818$D31271E9-ACF4-453D-A3D8-252968B57319","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e086a66ce7b420a6b883070e175982acb71de9d5","datavalue":{"value":"https://doi.org/10.1016/0377-2217(88)90034-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1123818$C20AC770-C0D1-438C-94F7-F870C24F23D0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"657e503180cf13f9a68185de995fcf7e1af05786","datavalue":{"value":"W2091020754","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123818$BE9F3853-FD38-44F3-B8C9-F3FC3DCF7FC5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"06ee523fdbdf81d701feb6cd2239973cf706f45a","datavalue":{"value":{"entity-type":"item","numeric-id":4173214,"id":"Q4173214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123818$9962001A-1D7A-4CC5-8981-8C3B12F5222E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c89c25dda4f672a4f7916c89b6d0324b925afbf","datavalue":{"value":{"entity-type":"item","numeric-id":3309472,"id":"Q3309472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123818$979CB811-6FC5-4FF4-83E3-46AA3BC36BD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e6a4e3723e1ca96af481175af5a2af3721526ff","datavalue":{"value":{"entity-type":"item","numeric-id":3688124,"id":"Q3688124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123818$617FC1E3-DD55-4E32-994A-AF259B781541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01dc7c089a6c3da17ca981c5bd0b1bb5a43d7b55","datavalue":{"value":{"entity-type":"item","numeric-id":4165179,"id":"Q4165179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123818$0156C253-F264-4681-BFA3-542EBE0F6EFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56a82cb99f377f33999364a98adc8eb30b4bf1d0","datavalue":{"value":{"entity-type":"item","numeric-id":3912036,"id":"Q3912036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123818$DB6414F5-B21B-4EF0-9083-CE3B723D3923","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8adc70e3679ceb3f96821715ddcd774dd9a67faa","datavalue":{"value":{"entity-type":"item","numeric-id":3657801,"id":"Q3657801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123818$F340E8B8-798E-4C36-87B2-6FE7198FB020","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b42608c02d472580d52a1f4d92e1e0112818f83","datavalue":{"value":{"entity-type":"item","numeric-id":4174636,"id":"Q4174636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123818$0F3DA614-41E8-43C7-9DF7-4AA860FB8E7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daf858f46db98710020faecfca241b9429463b93","datavalue":{"value":{"entity-type":"item","numeric-id":3951565,"id":"Q3951565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123818$49DED38B-4750-4DCD-A657-BD03DE5A24EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c1ebfa65d54544b8785011d2607cf3ffdb9a9d8","datavalue":{"value":{"entity-type":"item","numeric-id":4096696,"id":"Q4096696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123818$3D3D2F33-24FE-48D5-9A73-1446A07956EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"601e404f716a9ae129d1ae33ce03aab0de9a876c","datavalue":{"value":{"entity-type":"item","numeric-id":1394188,"id":"Q1394188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123818$06B6B593-3572-4937-B513-587C2FBC7663","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b6d9185fe63e47253765971cbfec2e931ba065d","datavalue":{"value":{"entity-type":"item","numeric-id":4088854,"id":"Q4088854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123818$51ED76C1-F83F-4B77-866C-BA6CC42724D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8635a293f0260693024421bcdf9d97cffc1890ad","datavalue":{"value":{"entity-type":"item","numeric-id":4010349,"id":"Q4010349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123818$DA718A0F-ABA6-4576-9CF6-2658337AA708","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9be4c52f96b8e644af07dc1c9155187956d3ca81","datavalue":{"value":{"entity-type":"item","numeric-id":4811408,"id":"Q4811408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc727321aa51fbf97e52c012b89cf9557fd854d1","datavalue":{"value":{"amount":"+0.8411016464233398","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":"Q1123818$74F41936-06F3-4A35-B092-F6E21D8C4F58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18428a869d97a1f5ab6bd9fb93582e2ec125b886","datavalue":{"value":{"entity-type":"item","numeric-id":4495163,"id":"Q4495163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74dc03458db78806537f3a63825ea358d1cb413b","datavalue":{"value":{"amount":"+0.826102614402771","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":"Q1123818$A96827AA-0AD9-4104-A70C-258C8C195E4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3990cb610cece98c556e43cc3d109aa41e7dc498","datavalue":{"value":{"entity-type":"item","numeric-id":2282822,"id":"Q2282822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74dc03458db78806537f3a63825ea358d1cb413b","datavalue":{"value":{"amount":"+0.826102614402771","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":"Q1123818$99CFC661-57B6-45E1-BA77-1B940668B05D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d0a42095d25572f772eab9e07809f6d25019af5","datavalue":{"value":{"entity-type":"item","numeric-id":4540047,"id":"Q4540047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8dcfeab4399eefca2798866bf7c3acc740585910","datavalue":{"value":{"amount":"+0.8254961371421814","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":"Q1123818$AA5DDC94-986B-4633-BA84-DF60091E37FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de0d98bcbf3e586a193c867f9e0d49a0849e80d2","datavalue":{"value":{"entity-type":"item","numeric-id":4395334,"id":"Q4395334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b10cb619479a36ce3a7008bda703af4881e1939","datavalue":{"value":{"amount":"+0.8189115524291992","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":"Q1123818$552451B5-7F34-4860-875E-6B8ED7746CBF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A reoptimization algorithm for the shortest path problem with time windows","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_reoptimization_algorithm_for_the_shortest_path_problem_with_time_windows"}}}}}