Modeling Width in Spatial Optimization in Raster Space

QC 20230109

Abstract

Med tanke på ett rutnät av celler, som var och en tilldelas ett numeriskt värde som kvantifierar dess användbarhet (eller kostnad) för en viss användning, är en populär typ av problem inom geografisk informationsvetenskap (GIS) rasterbaserad rumslig optimering. Sådana problem försöker vanligtvis hitta en uppsättning celler som maximerar (eller minimerar) den nyttan (eller kostnaden) samtidigt som de följer en given uppsättning begränsningar. Om problemet gäller valet av en region, d.v.s. en ansluten uppsättning celler, är det särskilt användbart i en rad planeringsfält som förlitar sig på GIS. Med den ökande tillgängligheten av högupplösta data på jordens yta kanske det inte längre är tillräckligt att uteslutande modellera sådana rasterbaserade optimeringsproblem på cell-för-cell-basis. Istället kan det explicita övervägandet av bredd och efterföljande modellering av rumsliga optimeringsproblem övervägas.

Det övergripande syftet med denna avhandling är att integrera "grannskaps"-metoden för modellering för bredd i rasternät i relevanta rumsliga optimeringsproblem. Studierna som presenteras i denna avhandling fokuserar på två vanliga rasterbaserade rumsliga optimeringsproblem, maximivärdesregionproblemet och minstakostnadsvägproblemet. Varje studie modellerar sedan varianter av de problem som innehåller en bredd som är större än en cell, och designar, implementerar och testar lösningsmetoder enligt följande.

Det rasterbaserade maximivärdesregionproblemet involverar valet av en ansluten uppsättning celler, d.v.s. en region, med en specificerad storlek som maximerar (eller minimerar) summan av alla deras värden. Denna uppgift kan gjutas som ett kombinatoriskt optimeringsproblem, och det finns exakta och heuristiska metoder för att lösa det. Även om lösningar som genereras av dessa metoder garanterat är genomförbara (om de inte är optimala), kanske de inte är önskvärda för praktisk användning om de innehåller för smala segment (som kan vara lika smala som bredden på en enda cell). En ny variant av maximivärdesregionproblemet – här kallat maximivärdesbredregionproblemet – presenteras som kräver att en region är minst lika bred som en specificerad bredd. En heuristisk metod för dess lösning introduceras och dess prestanda testas genom beräkningsexperiment med slumpmässigt genererade artificiella landskapsdata. Resultaten visar att metoden genererar bra genomförbara lösningar när det gäller all koppling, storlek, bredd och värde, men kräver mer beräkningstid - som i teorin växer linjärt med rutnätsstorleken och kvadratiskt med regionstorlek och regionbredd - än andra metoder för regioner med maximalt värde utan krav på minsta bredd.

Det rasterbaserade minsta kostnadsvägproblemet involverar valet av en region som förbinder två specificerade celler, en källa och destination, och som minimerar summan av alla deras värden. Det är ett av de mest studerade problemen i GIS, och i sig är det en variant av det optimala routingproblemet. I förhållande till bredd är optimal routing av en bana med konstant bredd, det vill säga en korridor, i ett tvådimensionellt (2D) rutnät av kostnadsviktade kvadratceller en ny förlängning av problemet med minsta kostnadsväg, och modeller och lösningar är tillgängliga och redo att integreras i rasterbaserade geografiska informationssystem. Dessa lösningar är dock beroende av kostnadsytan som de är modellerade på, vilket har begränsningar i vissa situationer, inklusive 1) ett beroende av antagandet att kostnaden (per längdenhet) mäts på en kvantitativ skala, 2) en uppmätt distorsion när kostnadsytan är konstant, och 3) de är begränsade till optimal routing av vägar i 2D.

I förhållande till den första begränsningen föreslås ytterligare en modell som kännetecknar en lägsta kostnadskorridor på en ordinärt skalad rasterkostnadsyta – eller kort och gott en minst ordinärt skalad kostnadskorridor – och visar att den kan omvandlas till en instans av ett multiobjektivt optimeringsproblem känt som det föredragna vägproblemet med en lexikografisk preferensrelation och löst i enlighet därmed. Modellen testas genom beräkningsexperiment med slumpmässigt genererade artificiella landskapsdata såväl som verkliga data. Resultaten visar att kostnadskorridorer med minst ordinär skala garanterat innehåller mindre ytor med högre kostnad än konventionella minsta kostnadskorridorer på bekostnad av mer långsträckta och slingrande former. Det minst ordinala kostnadskorridorproblemet har en beräkningskomplexitet på O(n2.5) i värsta fall, vilket resulterar i en längre beräkningstid än lägsta kostnadskorridorer. Denna skillnad är dock mindre i praktiken.

I förhållande till den andra begränsningen, som är fallet med konventionella rasterbaserade lägsta kostnadsvägar, är de inkrementella orienteringarna begränsade till ett fast antal (typiskt åtta kardinal) riktningar, och därför, oavsett nätupplösning, lägsta kostnad korridorer tenderar att avvika från de tänkbara på det euklidiska planet. En metod föreslås för att lösa det rasterbaserade lägsta kostnadskorridorproblemet med reducerad distorsion genom att anpassa en distorsionsreduktionsteknik som ursprungligen utformades för lägsta kostnadsvägar och tillämpa den på en effektiv men distorsionsbenägen lägstakostnadskorridoralgoritm. Den föreslagna metoden är, i teorin, garanterad att generera inte mindre exakta lösningar än den befintliga i polynomtid och förväntas i praktiken generera mer exakta lösningar, vilket demonstrerats experimentellt med hjälp av syntetiska och verkliga data.

I förhållande till 2D-begränsningen, med den ökade tillgängligheten av 3D-data, skulle man kunna överväga ytterligare ett rumsligt optimeringsproblem i ett tredimensionellt rutnät av kostnadsviktade kubiska celler eller voxels, vilket är att hitta ett rörformigt område av voxlar med en konstant bredd, här kallad "3D-korridor", som förbinder två terminaler samtidigt som den ackumulerar minsta kostnad. En 3D-korridor är modellerad som en sekvens av uppsättningar av voxlar, kallade "kvarter", som är arrangerade i en 26-hedrisk form, en heuristisk metod är utformad för att hitta en sekvens av sådana stadsdelar som sveper den minsta kostnadsviktade volymen, och dess prestanda testas med datorgenererade slumpmässiga data. Resultat visar att metoden hittar en lågkostnads, om inte minst kostnadseffektiv, korridor med en specificerad bredd i ett tredimensionellt kostnadsnät och har en rimlig effektivitet då dess komplexitet är O(n2) där n är antalet voxlar i insatskostnadsnätet och är oberoende av korridorbredden. En stor nackdel är att korridoren som hittas kan skära sig själv, vilket ofta inte bara är en oönskad kvalitet utan gör uppskattningen av dess kostnadsviktade volym inexakt.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-322780