{"entities":{"Q1102209":{"pageid":1112961,"ns":120,"title":"Item:Q1102209","lastrevid":66296286,"modified":"2026-04-12T08:55:51Z","type":"item","id":"Q1102209","labels":{"en":{"language":"en","value":"Minimum cost-reliability ratio path problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4049419"}},"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":"Q1102209$78ABBC6D-FCA8-4AD6-9287-D98DD46C92DD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"57e5130caf7f84365372eed53065cb70c18c7e72","datavalue":{"value":{"text":"Minimum cost-reliability ratio path problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1102209$0C022A72-C990-4B01-9F0C-A2B00C219DED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cb93b8086c31e352d01522ac6df8274b9a9e573c","datavalue":{"value":"0643.90088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102209$EE59A69D-602C-42BB-AE2F-02960940A982","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1369b971c6cd1146da3fcbf336922d0d130d72a4","datavalue":{"value":"10.1016/0305-0548(88)90031-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102209$0C1ACDBF-A21E-4E76-8E47-A17C448C987C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e630590c5ca6e787c3c7b5e291898405495fea2b","datavalue":{"value":{"entity-type":"item","numeric-id":162215,"id":"Q162215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102209$3960F14E-9046-477F-BF2F-A27D9CAD53CB","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":"Q1102209$6BBBAFDC-51C8-438C-8799-772A81F880D7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3b39fef3bf8f8bcda0bd81f678ab16def952a4e9","datavalue":{"value":"Let \\(c_{ij}\\) denote the nonnegative cost of traversing an arc (i,j)\\(\\in A\\) in a directed network and \\(r_{ij}\\) \\((0<r_{ij}\\leq 1)\\) its reliability, then the minimum cost-reliability ratio path problem (MCRRPP) is to find a directed path from a source node s to a sink node t in this network with minimal ratio  \\[  \\sum_{(i,j)\\in P}c_{ij}/\\prod_{(i,j)\\in P}r_{ij}  \\]  among all such paths. The author shows that the optimum solution of this problem is an efficient extreme point of a bicriteria path problem. Thus the enumeration of all efficient extreme points of the two-parameter shortest path problem yields a first step to get the optimal solution. These paths can be enumerated by performing parametric analysis of the shortest path problem with arc lengths as \\(d_{ij}+\\mu c_{ij}\\) and increasing \\(\\mu\\) from 0 to a large number. As the efficient frontier of each solution is a piecewise linear convex function the author gives two criteria which allow to shorten the enumeration process.    The whole algorithm can be formulated very elegantly. The worst case computational complexity of the algorithm is of order O(mnD log m), where m and n denote the number of arcs respectively vertices of the network and \\(D=\\max_{i,j\\in A}\\{c_{ij}\\}\\). Some computational results on grid networks and random networks demonstrate that the algorithm can be used very well in real life network problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102209$E7350916-BE34-4632-A264-59137639DE61","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102209$AE99F712-5FF9-444F-9869-16BDA3CADA62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"82a006ec5bbbadf5f063bfdc770a07a4120063ab","datavalue":{"value":"90C31","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102209$823E475D-7AE0-4EF6-965E-DCA8D2E446A9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"152c1444338e59a49b9b65b3c44d8c61ff346525","datavalue":{"value":"4049419","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102209$E7FBE1E2-1C3F-422A-A784-342752E0941A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e87161621c6e16a6df001755ce396bde6c5ff489","datavalue":{"value":"special ratio path problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102209$AF6ACD32-ED26-48E5-B56A-838275CC1521","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d56f0960c0e2c0692f2de8022b55c98b398d61e9","datavalue":{"value":"multicriteria shortest paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102209$7AE4B71E-0C65-4320-B286-44D615ABAF12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c6cf2e93ad1c607effff7f16ec42271d5e35d3a","datavalue":{"value":"parametric shortest paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102209$2DAD3E8F-4E28-48FC-8785-3BAAD06FDC87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b227956c725d7b91412ea914475e752de7b8165","datavalue":{"value":"minimum cost-reliability ratio path problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102209$F2A083C8-E64E-46E9-8093-4F166E465068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88872228c5399d0c2cfe23264783effb18f879fd","datavalue":{"value":"efficient extreme point","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102209$198EB39E-3D88-485D-A85E-A314328B23F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ed2c9f4a182919df886910ebc4aa78f3fc294d2","datavalue":{"value":"two-parameter shortest path problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102209$A9B0C155-EC83-4B98-B5BC-1E8701741C3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3989d819d937a76f41d6483defa1cf0b89389b5e","datavalue":{"value":"worst case computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102209$705889ED-9E44-41E6-8105-F83B9214EFAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05c82f72c045d982e9593e7e10008041117b8229","datavalue":{"value":"grid networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102209$30A10C7D-FC13-4536-9460-8C5774BBEFBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a059cb67176d9ba7914fa7f2868b6f576596e08e","datavalue":{"value":"random networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102209$2327F0D7-6317-4E8E-9DE6-80F933077BF1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6c8d6efbe53de15b37aa08c687a2038707fe736f","datavalue":{"value":{"entity-type":"item","numeric-id":229626,"id":"Q229626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102209$5E64CA38-512C-48A6-AD7E-7C60B5D4D2FE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"111aa4d205b7adb5a8dca99e52744f61a537d2b5","datavalue":{"value":{"entity-type":"item","numeric-id":647398,"id":"Q647398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102209$FA3F58B9-8ABD-421F-AC3F-AEBA208C4E5E","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":"Q1102209$C4B87294-4056-4A87-BCBA-A83C16F69343","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c9929bfa946b157901f05aedcfd71fe768df706e","datavalue":{"value":"https://doi.org/10.1016/0305-0548(88)90031-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1102209$4D8E30EC-8D94-4240-91E9-6509083BF226","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0b01d4b9d337a54be31606f5911663b2354c78b0","datavalue":{"value":"W1984044902","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102209$D97EEB9F-9E1F-4998-9E9D-B5498E2C6F56","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a7ef877fc1f04c4ca02dfb519d959f8e1260de1","datavalue":{"value":{"entity-type":"item","numeric-id":4143188,"id":"Q4143188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102209$AE941497-88CC-441D-A676-12DFFF350A93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"117178b46bd4133cc1ac40b9e01f7800f42d50ab","datavalue":{"value":{"entity-type":"item","numeric-id":5583694,"id":"Q5583694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102209$D8D255D3-75F4-47F3-A84E-0FD3EAB71E71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5cd3cdd629cb21e3cafcd375ac9c9591b448acc8","datavalue":{"value":{"entity-type":"item","numeric-id":5593809,"id":"Q5593809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102209$9A18CB20-575C-494A-800C-AD6DBD08A511","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fb92d0c47be1223623b1854929572465a19ccea","datavalue":{"value":{"entity-type":"item","numeric-id":3861175,"id":"Q3861175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102209$2BCD9FFC-CE0E-4963-BF49-EE68D509388B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f05b7941374a78c5d2da1cc0e9b5e27632ea456","datavalue":{"value":{"entity-type":"item","numeric-id":3666614,"id":"Q3666614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102209$B5366890-DF7C-4977-9C85-F8C9E969FCE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102209$B985D21B-8A8B-4905-B74F-FA6364B044CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9063f5239a9b147b36ae7680657ab12b741e00f9","datavalue":{"value":{"entity-type":"item","numeric-id":3923967,"id":"Q3923967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102209$9D0769C7-12F4-4D28-AC2D-E37C69F97407","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56521ca1aac393e3b19010974acb1b4d652c78ce","datavalue":{"value":{"entity-type":"item","numeric-id":797504,"id":"Q797504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102209$EBE03E16-457C-432B-A635-223C7A84F368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4d8f0dbc1a83da59a75c8ee68b1cd92e83b44cc","datavalue":{"value":{"entity-type":"item","numeric-id":1225555,"id":"Q1225555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102209$2DCC91B1-B696-4517-969B-F7AD3FDDAC39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"021053b900ebc95dc2b0339a2af7bc110e3c219a","datavalue":{"value":{"entity-type":"item","numeric-id":4777082,"id":"Q4777082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102209$554807B3-2525-4F0D-8D0F-06001E21C58C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca402291ee35bbc1edf903b7ae6d09fb1a2435a5","datavalue":{"value":{"entity-type":"item","numeric-id":3693257,"id":"Q3693257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102209$CF2627D8-9BD5-4746-A8AF-B61D46163B1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6a6cbec12f8fa68c063d3e276b9c0c174fd44eb","datavalue":{"value":{"entity-type":"item","numeric-id":1266668,"id":"Q1266668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102209$12A79461-068F-4EEF-B84D-9011D1F4F7AE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"380dbe399776562fcc36013288e2f006efbdbcc0","datavalue":{"value":{"entity-type":"item","numeric-id":709122,"id":"Q709122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b68a757e068993ff5e4e8bd3ee8ebc497c5ec4f","datavalue":{"value":{"amount":"+0.8158215284347534","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":"Q1102209$297A95C6-285A-4FEC-B621-06B1B5AF1B3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9696ba1bfbf7657901f1bc6520a9a936089dea79","datavalue":{"value":{"entity-type":"item","numeric-id":373197,"id":"Q373197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74531cad458418ddac58f157e39327e8f2b21f1b","datavalue":{"value":{"amount":"+0.7758560180664062","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":"Q1102209$FDF7C02E-34A5-49AE-95C1-79F085767845","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"999693e386bf285dd3571fbc82b30686b6349083","datavalue":{"value":{"entity-type":"item","numeric-id":3351166,"id":"Q3351166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95560814411fc2fedb7a31ea7d7d389f8ae5fa48","datavalue":{"value":{"amount":"+0.7668214440345764","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":"Q1102209$15B25B34-6EF9-48A2-9052-B013DA1FFD5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39baa343b21d44081a5b7501ce502290b6461907","datavalue":{"value":{"entity-type":"item","numeric-id":2284640,"id":"Q2284640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65aebf4c0bfee301710d3450eeddf00351874826","datavalue":{"value":{"amount":"+0.7661778926849365","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":"Q1102209$D52A872A-FB71-474C-99A0-522C4D350054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6b63b6c0582433dd5a83393943e64fb1ed4fcc2","datavalue":{"value":{"entity-type":"item","numeric-id":4845159,"id":"Q4845159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d729810fa862388cfc257aef44e2773b1c10e1e9","datavalue":{"value":{"amount":"+0.7534395456314087","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":"Q1102209$FE08D013-8831-42DA-8EA2-2BD35CFBB34B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimum cost-reliability ratio path problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimum_cost-reliability_ratio_path_problem"}}}}}