Real-Time Spatial Optimization

Contents

List of Abbreviations

1 Introduction
1.1 Supply Chain Management
1.2 Wood Supply Chain
1.3 Spatial Optimization
1.4 Problems Addressed - Hypothesis
1.5 Relevant Literature
1.6 Organization of the thesis

I Theoretical Part

2 Geographic Information Science and Technology
2.1 Standardization in GIS
2.1.1 Interoperability
2.1.2 Standards
2.1.3 De facto Standards
2.1.4 De jure Standards
2.2 Service Oriented Architectures in GIS
2.3 Location Based Services
2.4 Conclusion

3 Graph Theory and Optimization Techniques
3.1 Graph Theory
3.1.1 Graphs
3.1.2 Paths, Walks and Connected Graphs
3.1.3 Digraphs
3.2 Vehicle Routing Problems
3.2.1 VRP with Time Windows
3.2.2 VRP with Backhauls
3.2.3 VRP with Pickup and Delivery
3.2.4 VRP with Pickup and Delivery and Time Windows
3.3 Exact Optimization Techniques
3.3.1 Branch and Bound
3.3.2 Branch and Cut
3.4 Heuristical Optimization Techniques
3.4.1 Construction Methods
3.4.2 Local Search Methods
3.4.3 Simulated Annealing
3.4.4 Adaptive Large Neighborhood Search
3.5 Rolling Schedule approach
3.6 Conclusion

4 Spatial Decision Support Systems
4.1 Definition, Components and brief history of SDSS
4.2 SDSS and GISc
4.3 Integration of Optimization Techniques
4.4 Conclusion

II Application and Results

5 System Architecture and Implementation of WSC Proto type
5.1 Overview of System Architecture
5.2 Database Management System
5.3 Tracking Engine
5.4 Web Mapping Engine
5.5 Decision Engine
5.5.1 Rolling Schedule for WSC optimization
5.5.2 Graph theory for WSC optimization
5.5.3 Object oriented design for handling of optimization data
5.5.4 Retrieval of an initial solution
5.5.5 ALNS for WSC optimization
5.6 Mobile Devices
5.6.1 Mobile Device for vehicles
5.6.2 Mobile Device for forest enterprise
5.7 Desktop System
5.8 Conclusion

6 Setup and Results
6.1 Experiment Setup
6.1.1 Hardware
6.1.2 Software
6.1.3 Spatial data and area of interest
6.1.4 Problem instances
6.2 Results
6.2.1 Work Expenditure
6.2.2 Results of ALNS applied to WSC
6.3 Conclusion

7 Discussion and Outlook
7.1 Evaluation of Alternative Architectures
7.1.1 User requirements
7.1.2 Quality Evaluation of System Architectures
7.1.3 Possible system architecture designs
7.1.4 Evaluation of System Architectures
7.2 Discussion of Results of ALNS applied to WSC
7.3 Implications of real-time spatial optimization on related fields
7.4 Future aspects
7.5 Concluding Remarks

Bibliography

III Appendix

Test Instance 1

Test Instance 2

List of Figures

1.1 An example of a Supply Chain consisting of a number of sup- pliers and customers (Spitter, 2005). A number of possible paths from supplier to customer exist, of which only one - the optimal (marked in blue) - is chosen, based on a number of criteria

1.2 Major working areas of a Supply Chain Management system (based on Wannenwetsch (2005))

1.3 Simplified illustration of the Wood Supply Chain

1.4 Information path and traditional shortcomings - here media disruptions marked with red exclamation marks - of the Wood Supply Chain based on von Bodelschwingh et al. (2003)

2.1 Graphical illustration of a network flow between origins and destinations - the square case. From Goodchild (1998)

2.2 Graphical illustration of a network flow between origins and destinations - the rectangular case. From Goodchild (1998)

2.3 Continuous spatial-temporal behavior of attribute a over time t (after Wang and Cheng (2001) and Renolen (2000))

2.4 Discrete spatial-temporal behavior of attribute a over time t (after Wang and Cheng (2001) and Renolen (2000))

2.5 Stepwise spatial-temporal behavior of attribute a over time t (after Wang and Cheng (2001) and Renolen (2000))

2.6 Illustration of a space-time path. These graphs are based on time geography (Hägerstrand, 1970). Graphic adopted from Yu (2006)

2.7 Space-time prism and potential path area. Graphic adopted from Yu (2006)

2.8 Simplified Service Oriented Architecture (SOA) architecture with web services (after Gisolfi (2001))

2.9 Simple web service architecture

2.10 Basic niche of Location Based Services (LBSs) (Brimicombe, 2002). NICTs are portable devices that are capable of gath- ering their position and incorporate wireless communication i.e. PDA’s with GPS (either built-in or connected via e.g. Bluetooth)

2.11 Basic LBS architecture

3.1 Classical optimization techniques, from Talbi (2009)

3.2 Taxonomy of optimization techniques, from Weise (2009)

3.3 A simple illustration of a digraph

3.4 The variants of the VRP and their connections, from Toth and Vigo (2002b). The abbreviations and terms are discussed section 3.2

3.5 Outline of the Branch and Bound approach (based on Zim mermann (2005))

3.6 Illustration of the sweep algorithm. Customers are assigned due to their membership to a sector of a circle (based on Ropke (2005))

3.7 Local Search utilizing the Steepest Descent strategy. The choice of an initial solution is crucial for the result of the optimization process

3.8 Metaheuristics for improving the Local Search - i.e. to over come being trapped in a local optimum - from (Talbi, 2009)

3.9 Comparison between VNS and ALNS, from Pisinger and Ropke (2005). The neighborhoods of ALNS and VNS are illustrated

3.10 Rolling Schedules approach illustration. The timeline is di vided into discrete time periods 1 , . . . , and a Planning Horizon - abbreviated ”Horizon” - defines the duration that the ”system” planes ahead. After 1 is over the Horizon is ”rolled” forward by one time period

4.1 Degree of decision problems and intended problem solving environment, after Malczewski (1999)

4.2 MCDM Framework, based on Malczewski (1999)

4.3 SDSS functionality and corresponding decision phases. De veloped based on Herzig (2005), Makowski and Wierzbicki (2000), Malczewski (1999), Densham (1993)

4.4 Components of an SDSS, based on Malczewski (1999, 1997)

4.5 Technical levels in an DSS Framework, based on Sprague (1980)

4.6 Analogy between the technical DSS framework proposed by Sprague (1980) and the analogue counterparts of a recent SDSS approach using SOA. Based on Rinner (2003). The classical desktop approach defined by (Sprague, 1980) on the left side is replaced by a contemporary approach on the right side that utilizes SOA

4.7 Integration of GIS in a SDSS - distinguishing the extent of integration (Jun, 2000)

4.8 Integration of GIS in a SDSS - distinguishing the direction (Jun, 2000)

5.1 Overview of the system architecture for optimizing the WSC. The arrows are indicating the connections between the mod- ules - each connection with a number is explicitly explained in the text of section 5.1

5.2 ERD with entity groups according to a subgroup of the iden tified stakeholders of the WSC

5.3 ERD in the IDEF1X Notation

5.4 Vizualizing 0. . . 1:0. . . relations in ERD using IDEF1X no tation

5.5 Class Diagram of VRP classes. The classes Nodes and Vehi cles are collections of the classes Node and Vehicle respectively

5.6 Screenshots of mobile device for vehicles. In 5.6(a) the start screen of the application is visualized and in 5.6(b) the avail- able program features are displayed. In figure 5.6(c) the red lines indicate the road network and the gray areas show the settled areas. The red triangle marks the position of the mo bile device, i.e. the vehicle

5.7 Screenshot of the desktop application

6.1 Hardware overview for WSC optimization used in this thesis

6.2 Software overview for WSC optimization

6.3 The test area for WSC optimization marked with the blue box - the overview in 6.3(a) and the detailed map in 6.3(b)

6.4 Map with the entities present in test instance 1 - piles, saw mills and haulage companies. The administrative borders, rivers and populated places are displayed for a better orien tation

6.5 Map with the entities present in test instance 2 - piles, saw mills and haulage companies. The administrative borders, rivers and populated places are displayed for better orienta tion

6.6 Amount of work in hours invested in the development of the WSC prototype, separated by modules. The position ”System Architecture” stands for the overall conceptual planning of the system itself

6.7 Amount of work in hours separated by modules by each month

6.8 Result of ALNS applied to test instance 1 (test run 1)

The value of the objective function is displayed on the y-axis and the corresponding iteration number on the x-axis. The value of the best solution is in blue, the actual accepted (the one the ALNS algorithm works with), which is denoted as the actual solution, is colored in red and the new solution in yellow. The value of the initial solution is marked with a dotted line

6.9 Result of ALNS applied to test instance 1 (test run 1) here the first 2000 iterations of an algorithm run are dis- played. The value of the objective function is displayed on the y-axis and the corresponding iteration number on the x-axis. The value of the best solution is in blue and the actual ac- cepted (the one the ALNS algorithm works with), which is denoted as the actual solution, is colored in red. The value of the initial solution is marked with a dotted line

6.10 Result of ALNS applied to test instance 1 (test run 1) here the first 11300 iterations of an algorithm run are dis- played. The value of the objective function is displayed on the y-axis and the corresponding iteration number on the x-axis. The value of the best solution is in blue and the actual ac- cepted (the one the ALNS algorithm works with), which is denoted as the actual solution, is colored in red. The value of the initial solution is marked with a dotted line

6.11 Result of ALNS applied to test instance 1 (test run 2) here all 25000 iterations are displayed. The value of the objec- tive function is displayed on the y-axis and the corresponding iteration number on the x-axis. The value of the best solution is in blue and the actual accepted (the one the ALNS al- gorithm works with), which is denoted as the actual solution, is colored in red. The value of the initial solution is marked with a dotted line

6.12 Result of ALNS applied to test instance 1 (test run 2) here the first 1000 iterations are displayed. The value of the objective function is displayed on the y-axis and the corres- ponding iteration number on the x-axis. The value of the best solution is in blue, the actual accepted (the one the ALNS algorithm works with), which is denoted as the actual solu- tion, is colored in red and the new solution in yellow. The value of the initial solution is marked with a dotted line

6.13 Result of ALNS applied to test instance 1 (test run 2) here the first 500 iterations are displayed. The value of the objective function is displayed on the y-axis and the corres- ponding iteration number on the x-axis. The value of the best solution is in blue, the actual accepted (the one the ALNS algorithm works with), which is denoted as the actual solu- tion, is colored in red and the new solution in yellow. The value of the initial solution is marked with a dotted line

6.14 Result of ALNS applied to test instance 1 (test run 2) - here the first 200 iterations are displayed. The value of the objective function is displayed on the y-axis and the corres- ponding iteration number on the x-axis. The value of the best solution is in blue, the actual accepted (the one the ALNS algorithm works with), which is denoted as the actual solu- tion, is colored in red and the new solution in yellow. The value of the initial solution is marked with a dotted line

6.15 Result of ALNS applied to test instance 1 (test run 3) after 5000 iterations. The value of the objective function is displayed on the y-axis and the corresponding iteration num- ber on the x-axis. The value of the objective function is dis- played on the y-axis and the corresponding iteration number on the x-axis. The value of the best solution is in blue and the actual accepted (the one the ALNS algorithm works with), which is denoted as the actual solution, is colored in red. The value of the initial solution is marked with a dotted line

6.16 Result of ALNS applied to test instance 1 (test run 3) after 1000 iterations. The value of the objective function is displayed on the y-axis and the corresponding iteration num- ber on the x-axis. The value of the objective function is dis- played on the y-axis and the corresponding iteration number on the x-axis. The value of the best solution is in blue, the ac- tual accepted (the one the ALNS algorithm works with), which is denoted as the actual solution, is colored in red and the new solution in yellow. The value of the initial solution is marked with a dotted line

6.17 Result of ALNS applied to test instance 1 (test run 3) after 750 iterations. The value of the objective function is dis- played on the y-axis and the corresponding iteration number on the x-axis. The value of the objective function is displayed on the y-axis and the corresponding iteration number on the x-axis. The value of the best solution is in blue, the actual ac- cepted (the one the ALNS algorithm works with), which is denoted as the actual solution, is colored in red and the new solution in yellow. The value of the initial solution is marked with a dotted line

6.18 Result of ALNS applied to test instance 1 (test run 4) after 5000 iterations. The value of the objective function is displayed on the y-axis and the corresponding iteration num- ber on the x-axis. The value of the objective function is dis- played on the y-axis and the corresponding iteration number on the x-axis. The value of the best solution is in blue and the actual accepted (the one the ALNS algorithm works with), which is denoted as the actual solution, is colored in red. The value of the initial solution is marked with a dotted line

6.19 Result of ALNS applied to test instance 1 (test run 4) after 1000 iterations. The value of the objective function is displayed on the y-axis and the corresponding iteration num- ber on the x-axis. The value of the best solution is in blue, the actual accepted (the one the ALNS algorithm works with), which is denoted as the actual solution, is colored in red and the new solution in yellow. The value of the initial solution is marked with a dotted line

6.20 Result of ALNS applied to test instance 1 (test run 4) after 300 iterations

6.21 Result of ALNS applied to test instance 2 (test run 1) after 25000 iterations. The value of the objective function is displayed on the y-axis and the corresponding iteration num- ber on the x-axis. The value of the objective function is dis- played on the y-axis and the corresponding iteration number on the x-axis. The value of the best solution is in blue and the actual accepted (the one the ALNS algorithm works with), which is denoted as the actual solution, is colored in red. The value of the initial solution is marked with a dotted line

6.22 Result of ALNS applied to test instance 2 (test run 1) showing the last 2500 iterations. The value of the objective function is displayed on the y-axis and the corresponding it- eration number on the x-axis. The value of the best solution is in blue, the actual accepted (the one the ALNS algo- rithm works with), which is denoted as the actual solution, is colored in red and the new solution in yellow. The value of the initial solution is marked with a dotted line

6.23 Result of ALNS applied to test instance 2 (test run 1). Here the first 3500 iterations are visualized

6.24 Result of ALNS applied to test instance 2 (test run 2) after 20000 iterations. The value of the objective function is displayed on the y-axis and the corresponding iteration num- ber on the x-axis. The value of the objective function is dis- played on the y-axis and the corresponding iteration number on the x-axis. The value of the best solution is in blue and the actual accepted (the one the ALNS algorithm works with), which is denoted as the actual solution, is colored in red. The value of the initial solution is marked with a dotted line

6.25 Result of ALNS applied to test instance 2 (test run 2) the first 5000 iterations are visualized. The value of the objec- tive function is displayed on the y-axis and the corresponding iteration number on the x-axis. The value of the best solution is in blue and the actual accepted (the one the ALNS al- gorithm works with), which is denoted as the actual solution, is colored in red. The value of the initial solution is marked with a dotted line

6.26 Result of ALNS applied to test instance 2 (test run 2). Here the first 1000 iterations are visualized. The value of the objective function is displayed on the y-axis and the corres- ponding iteration number on the x-axis. The value of the best solution is in blue, the actual accepted (the one the ALNS algorithm works with), which is denoted as the actual solu- tion, is colored in red and the new solution in yellow. The value of the initial solution is marked with a dotted line

7.1 A typical monolithic architecture (Zalesky, 2003)

7.2 Monolithic architecture option A for Wood Supply Chain (WSC) optimization

7.3 Monolithic architecture option B for WSC optimization

List of Algorithms

3.1 Greedy Algorithm Template, from Talbi (2009, p. 26)

3.2 Local Search algorithm template, from Talbi (2009, p. 122) and Ropke (2005, p.28)

3.3 Steepest descent algorithm

3.4 Basic Variable Neighborhood Search, based on Mlacenovic and Hansen (1997)

3.5 Simulated annealing algorithm, adapted from Kirkpatrick et al. (1983)

3.6 Large Neighborhood Search for VRPPDTW, from Ropke and Pisinger (2006)

3.7 ALNS pseudocode, from Pisinger and Ropke (2005)

3.8 Shaw Removal, from Pisinger and Ropke (2005)

3.9 Worst Removal, from Pisinger and Ropke (2005)

5.1 Pseudocode for the Decision Engine

5.2 Pseudocode for finding an initial solution

5.3 ALNS pseudocode, based on Pisinger and Ropke (2005)

List of Abbreviations

illustration not visible in this excerpt

Introduction

This chapter comprises preliminary definitions necessary to understand the contents of this thesis. The concept of a Supply Chain is explained, followed by a detailed description of the Wood Supply Chain. Spatial optimization, which is the central methodology used in this dissertation, is introduced before the problems addressed in this thesis are mentioned. Finally, sections on the relevant literature and the organization of the thesis itself complete this chapter.

1.1 Supply Chain Management

In the last decades Supply Chain Management (SCM) emerged as a buzz- word in business operations planning. Generally speaking, this concept does assume that stakeholders are not isolated islands in the market. If the market is considered as an ocean and the participating enterprises as islands that get and deliver something from/to the ocean, the market would not work as well as it does. If nobody in the ocean knows anything about the others needs, it would be hard to develop and produce goods that are really demanded. Thus, a great amount of resources is wasted due to the lack of target-oriented production and development.

The definition of the term SCM comprises the linkage between all stakeholders during the lifecycle of a product (Wannenwetsch, 2005). Generally speaking, the Supply Chain (SC) starts with the production of the raw materials and ends at the consumer. Thus, all participating institutions, enterprises or people are part of the SC (see figure 1.1). Based on this definition, also the transportation process itself is part of the SC.

Supply Chain Planning (SCP) enables every company to plan within the SC based on the market situation. Thus several processes have to be included in the planning process, based on Wannenwetsch (2005):

- SC design
- sales and requirements planning 1

illustration not visible in this excerpt

Figure 1.1: An example of a Supply Chain consisting of a number of suppliers and customers (Spitter, 2005). A number of possible paths from supplier to customer exist, of which only one - the optimal (marked in blue) - is chosen, based on a number of criteria.

- production planning
- distribution planning
- available-to-promise: guarantees reliable delivery dates in real time.

To facilitate SCP informatics may be used. The term Supply Chain Management System (SCM-system) comprises all tools that are capable of supporting the processes mentioned above, including all planning, simulation and optimization operations. Moreover the flow of commodities, informa- tion and money has to be integrated into these systems. Based on a study by Forrester Research (2001) running a SCM-system can result in an im- provement of delivery reliability of 40%. At the same time the delivery time is reduced by 30% and the processing time is cut by 10%.

Generally speaking, a SCM-system is a software system that is capable of supporting business activities in four major areas/phases (see figure 1.2):

- Planning
- Execution
- Coordination
- Cooperation

A SCM-system may support planning activities by facilitating a proper SC design, as well as an exact requirements analysis. A well founded transport planning is possible due to this preliminary work which may include network design. In the course of the execution phase of the production cycle a SCM- system is capable of supporting controlling, stock-keeping, production and transportation. Through the coordination phase the systems monitor the processes and seek for savings capacities. In case of altering conditions the production process itself may be altered - which will be handled by the system by raising an alert. In case of minor changes in the conditions that affect the process a SCM-system may adjust the performance of e.g. machines in order to guarantee an optimal production process. Cooperation takes place by the people or organizations in the SC. Thus a platform for e.g. e-commerce, registering commodities to transport from A to B, is helpful to integrate more organizations in the SC and to let them cooperate more intensely.

illustration not visible in this excerpt

Figure 1.2: Major working areas of a Supply Chain Management system (based on Wannenwetsch (2005)).

Wannenwetsch (2005) states that Location Based Services (LBSs) help to intensify and optimize either the Business to Customer (B2C) as well as the Business to Business (B2B) relations. Typical fields of applications for LBS paired with mobile navigation in the B2B sector are according to Reichenbacher (2004):

- orientation and localization
- navigation
- search services - identification - event check

A description of the preceding list can be found in the following paragraph. Orientation and localization represents the position of a mobile device in relation to a reference frame (e.g. coordinate system). Route planning and guidance based on digital spatial data heavily relies on the existence of ac- curate position information of the mobile device. Search services provide a basic search functionality for spatial objects, i.e. ”Where is the next . . . ?”. The ability to get information on unknown spatial objects is of great impor- tance for navigating in unfamiliar areas, and is covered by the identification ability. A number of implemented triggers, either spatial, temporal or at- tributive can fire events on the mobile device or the service center. Typical examples would be: ”Turn left” call - in guidance; truck leaves planned route; truck has serviced all customer requests and is fully loaded; emergency but- ton was hit - security and emergency services.

The so-called ” Mobile Supply Chain Management ” (Wannenwetsch, 2005)

- the application of LBS in B2B SCM-systems - takes advantage of the combination of both fields of expertise.

1.2 Wood Supply Chain

The term Wood Supply Chain (WSC) comprises the logistics system from timber to final product that is delivered to a customer. This work will focus on the logistic operations from timber production to the first processing step usually taking place in a saw or paper mill.

Figure 1.3 shows a brief description of the WSC part that is subject of this dissertation. Saw mills have a demand for timber with a number of special constraints, like quality, quantity, due-date and a price per cubic meter the saw mill is willing to pay. Timber arriving from a forest enterprise must meet the criteria quality and due-date. The quantity may be met by a number of forest enterprises. It can be assumed that forest enterprises produce timber if a demand exists or if they are ”forced” to do so due to external conditions, like e.g. catastrophic wind breaks. Produced timber has several attributes: quality, quantity, completion date and a price per cubic meter the forest enterprise wants to receive. Haulage companies transport timber from various forest enterprises to saw mills and have the following criteria: price per driving unit, capacity constraints. The striking questions concerning the WSC are the following:

- WHAT should be transported? e.g. timber with quality class A, from forest enterprise 1
- WHO should transport? e.g. haulage company 1
- WHEN should it be transported? e.g. picked up tomorrow at 8.30 am - WHERE TO? e.g. saw mill 1

illustration not visible in this excerpt

Figure 1.3: Simplified illustration of the Wood Supply Chain.

To ensure an efficient transportation process, relevant information must be passed on throughout the whole process. Due to the great number of participants, and to a great variety of information media and devices within the WSC, media disruptions occur (Gronalt et al., 2005), see figure 1.4. Moreover the dispatchers hardly ever use information systems to maintain an overview of the situation. Thus, the uncoordinated handling of logistic operations is very likely. Concluding, the characteristics of the WSC are as follows:

- Great number of participants
- Bidirectional flow of products and information
- Voluminous and complex information has to be processed - Spatial in nature
- Problem is not entirely solvable by computers - human knowledge has to be involved in managing WSC operations

illustration not visible in this excerpt

Figure 1.4: Information path and traditional shortcomings - here media disruptions marked with red exclamation marks - of the Wood Supply Chain based on von Bodelschwingh et al. (2003).

The actual WSC works as follows: A forest enterprise and a saw mill sign a contract that regulates the amount, due date and quality of timber delivered by the forest enterprise. Usually the timber has to be hauled to the next forest road from where it is transported to the saw mill by a haulage company that both contracting parties agree on. Thus, the destination of the timber is fixed before the timber is even harvested. In addition, trucks are assigned to timber transports without knowledge of surrounding condi- tions, like other timber that should be transported from nearby locations. The location of timber piles and the information that timber is available to haul has to be given by the forest enterprises. In most cases, the location information consists of an oral description of the position, which is only us- able by truck drivers who are familiar with the particular area - although LBSs are introduced in this sector too. Hence, ”foreign” truck drivers are hardly ever able to find the timber to pick up.

To clarify where different components and concepts presented in this thesis will have an impact, two scenarios shall be used, which are outlined below. In both scenarios, a high degree of standardization as well as rich and well-documented geospatial data infrastructure are essential ingredients.

- Scenario 1 (long-term): A new saw mill, a new forest enterprise or new haulage company enters the market. All processes have to be revised and for this purpose, a multitude of geospatial datasets has to be taken into account. Standardized web services allow query, overlay and analysis of up-to-date data from different sources, also ad-hoc and on-demand, providing the necessary inputs for Spatial Decision Support Systems (SDSSs).
- Scenario 2 (short-term): Varying weather conditions, road construction, traffic incidents or saw mill breakdowns call for temporary revisions of strategies. LBSs being utilized in the field and being coupled with web services in the dispatching center will improve the quality of such strategy amendments.

Geographic Information Systems (GISs) have emerged to a type of infor- mation systems that are capable of capturing, storing, checking, manipulat- ing, analyzing and displaying spatial data (Bartelme, 2005; Burrough and McDonnell, 1998; Longley et al., 1998; Worboys, 1995; Department of En- vironment, 1987). Due to the fact that analyzing data in different ways is a creative and innovative task, this is a field where new methodologies from other (related) fields might be applied. Thus, the introduction of related theory and methods in Geographic Information Sciences (GIScs) has and will always be of particular interest for further research.

The analysis of spatial data has also been done by geographers, who formed the term GeoComputation that comprises spatial analysis added with additional modeling and simulation capabilities. GIS seems not to be a mandatory ”equipment” for this field of research (Macmillan, 1997; Open- shaw and Abrahart, 1996). Nevertheless, in GeoComputation and also in the field of SDSSs the fact that ”external” theory and methods are necessary to advance the research field, are mentioned. Thus, a number of methodolo- gies from e.g. mathematics, statistics or hydrology were introduced in GIS, including genetic algorithms (e.g. Lei and Li, 2009), particle swarm algo- rithms (e.g. van Dijk et al., 2002) or kernel density estimation (e.g. Leitner and Staufer-Steinocher, 2001). With such ”external” methods, like the ones mentioned, it is possible to generate ”what-if” scenarios and sophisticated simulations within a GIS environment (e.g. GRASS Development Team, 2009).

For spatial optimization, simulation is of particular interest, as any opti- mization is related to it, because the ”best” alternative has to be determined based on a simulation. The term spatial optimization has been mostly linked to land distribution models yet - e.g. finding the best suitable location for [. . . ] or finding the best distribution of [. . . ] (e.g. Herzig, 2008; Ward et al., 2003; Guerra and Lewis, 2002). In this thesis this term is used in order to optimize the WSC - i.e. defining which vehicle brings timber from a par- ticular origin (a timber pile) to a saw mill. The prefix real-time denotes the ability of the system to a) gather data from all stakeholders and b) to provide assignments for each truck - i.e. where to pick up and deliver timber in (near) real-time.

1.4 Problems Addressed - Hypothesis

The problem addressed in this work is of interdisciplinary character, due to the involved research fields: GISc, Operations Research (OR), Computer Science, SDSSs and partly Forest Science. The research questions of this thesis are as follows:

- Firstly, the concept of spatial optimization is applied to the WSC in order to maximize the profit of the WSC - i.e. maximize turnover and minimize costs. By the use of an appropriate optimization methodology, an effective algorithm is formalized.
- Secondly, by the application of Service Oriented Architectures (SOAs) with regard to international standards (International Organization for Standardization (ISO) and Open Geospatial Consortium (OGC)) a system can be designed, that facilitates communication between different modules that together form the optimization system itself. By utilizing SOA, data can be collected and delivered to clients in realtime which in turn will eliminate media breaks.

Summarizing the points mentioned above the hypothesis of this dissertation is as follows:

” Real-time spatial optimization, which is in this context reflected as a combination of Geographic Information Science (GISc) and Operations Re search (OR) within a Spatial Decision Support System (SDSS), improves the profitability of the Wood Supply Chain (WSC). ”

Both research questions lead to an optimization of the WSC in the end, because media breaks result in increasing costs due to a planning process based on inaccurate data. The verification of this hypothesis is done by a proof of concept implementation, and the analysis of optimization results of two distinct problem instances - comparing the profit of the optimization result and the initial solution of each instance.

Additionally, the results of this thesis imply a re-use of the generated methodology in related fields of expertise and in similar spatial problems. The implications are discussed in chapter 7.3.

1.5 Relevant Literature

Basic resources in the field of GISc are the classical books of Burrough and McDonnell (1998), Longley et al. (1998) as well as the work of Bartelme (2005). These publications provide basic definitions and insights in the field of GISc which are very useful for developing the theoretical part of this work. A fundamental work in the field of Multi Criteria Decision Analysis (MCDA) and GIS is the book of Malczewski (1999). This book gives detailed insight in the process of decision making paired with GIS and certainly bridges the pretended gap between GISc and mathematics. Malczewski (1999) outlines the process and feedback loops that have to be implemented within a GIS in order to support decision making, which serve as building blocks for op- timizing the WSC. The foundations of SDSS are the works of Gorry and Scott-Morton (1971) using the results of Simon (1960) and Anthony (1965), who defined decision types that are still valid. The paper of Malczewski (2006) outlines the literature related to MCDA with GIS and outlines the coupling approaches of GIS and decision support. In addition, the following resources have to be mentioned when talking about coupling of GIS and decision support: Malczewski (2006); Ungerer and Goodchild (2002); Jun (2000); Fedra (1996); Jankowski (1995); Nyerges (1992). The coupling of various software components may be realized by service oriented technolo- gies. Thus, so-called SOAs and standardization play a vital role to generate interoperable systems. A detailed description of SOAs is given in (W3C, 2009b; Organization for the Advancement of Structured Information Stan- dards, 2006; Fielding, 2000), with specific implementations like Simple Ob- ject Access Protocol (SOAP) or Representational State Transfer (REST). Standardization issues are of great importance and are covered in the doc- uments provided by ISO (e.g. ISO, 2005b,c, 2004, 2003a,b) and OGC (e.g. OGC, 2009a, 2008b,d, 2006c, 2005).

A detailed look into mobile cartography and their possible methods and applications is done in Reichenbacher (2004) and Zipf (2004). Navi- gation is covered by the book of Hofmann-Wellenhof et al. (2003), which lays out basic positioning and navigation methods as well as an overview on selected problems and algorithms from Operations Research - namely Shortest Paths, Traveling Salesman Problems (TSPs) and Vehicle Routing Problems (VRPs). Publications by ISO and OGC (e.g. OGC, 2008c; ISO, 2007a) list possible services and applications in the LBS context. In addi tion, wireless communication networks are inevitable for data transfer (e.g. Krishnamurthy and Pahlavan, 2004; Umar, 2004; Schiller, 2003) and can also be used for the determination of the position - especially indoor (e.g. di Flora and Hermersdorf, 2008; Weimann, 2008; Hofmann-Wellenhof et al., 2003). Practically, satellite positioning systems, like the Global Position- ing System (GPS), are of higher importance for outdoor positioning. Thus, Global Navigation Satellite Systems (GNSS) are extensively used in this the- sis. A general introduction is found in Hofmann-Wellenhof et al. (2003) and a detailed accuracy analysis is published by the U.S. Department of Defense (2001).

VRPs are the problem class that has to be dealt with when optimizing the WSC. The VRP was first published by Dantzig and Ramser (1959), and a contemporary overview is given in the book of Toth and Vigo (2002b) and in Zimmermann (2005). Detailed descriptions of VRP subproblems as well as relevant solution techniques are published there. In order to get a general introduction in Graph Theory the book of Jungnickel (2005) is an excel- lent resource. To solve VRPs, heuristical techniques are discussed in litera- ture (e.g. Talbi, 2009; Bianchesini and Righini, 2005; Kytöjoki et al., 2005; Pisinger and Ropke, 2005; Bramel and Simchi-Levi, 1998; Mittenthal and Noon, 1992; Cloonan, 1966). Out of the available heuristics Adaptive Large Neighborhood Search (ALNS) (Pisinger and Ropke, 2005) is chosen because this method has promising results for VRPs with Pickup and Delivery. This heuristic relies on a number of concepts that have gained interest within the community, which are: Local Search and Simulated Annealing. Local Search is a heuristic that takes a solution as input and tries to modify the given solution based on a number of criteria. As a result a new - hopefully ”better” solution - is found (Funke et al., 2005; Laporte and Semet, 2002). Simulated Annealing is a technique that allows an optimization process that is similar to cooling metal. With this method is possible to overcome local optima, by accepting solutions that are worse than a given solution. Besides heuristical approaches, exact solution methods gained high attractiveness due to increasing computer power and are in depth discussed in literature (e.g. Cordeau et al., 2008; Azi et al., 2007; Ropke, 2005). Most publications solve the VRP using column generation methods, mostly Branch and Bound and Branch and Cut. The first articles concerning Branch and Bound were published by Dakin (1965) and Land and Doig (1960). A more historical overview of exact algorithms for the VRP is given in Laporte (1992). A number of important articles have been published that cover the optimiza- tion of VRPs with pickup and delivery and time windows (e.g. Ropke and Cordeau, iRev; Ropke et al., 2007). The Rolling Schedules approach is a rather old concept, first mentioned by Wagner and Whithin (1958) and fur- ther expanded and applied to real world problems by Teng et al. (2006) and Spitter (2005).

In order to get an overview on the WSC and the related problems the article by (von Bodelschwingh et al., 2003) is a good starting point. Küh- maier et al. (2007, p. 73 ff) list Decision Support Systems (DSSs) for the Wood Chip Supply Chain, and show that several companies have invested in an intelligent tool for decision support. Nevertheless, they lack of a broad approach, meaning that most of them have a navigation component as well as the possibility to monitor remaining timber located at the piles. Addi- tionally Kühmaier et al. (2007) mention, that the optimization of vehicle routes is not a standard feature in such software systems. Furthermore, it is not clear if these approaches incorporate international standards, at least to a certain level, so it has to be assumed that the solutions are a piece of proprietary software.

1.6 Organization of the thesis

This thesis is organized in three parts, a theoretical part, an application and results part that analyzes the obtained result and an appendix part. The theoretical part is divided into three sections which cover the topics: GISc, optimization techniques from OR and SDSS. The second part - application and results - deals with the WSC application and the experiment setup which is followed by the results and the discussion and outlook.

The theoretical part covers the topics of GISc that are relevant for the WSC and this thesis. GISc as a basis for SDSS and spatial optimization is outlined, followed by a subsection describing the relevant standards ap- plicable. Based on standards SOAs are possible - thus their role in GISc and in WSC will be analyzed. In order to facilitate (near) real-time in- formation sharing LBSs are of particular interest for tracking and tracing of the stakeholders of the WSC. A description of optimization techniques starts with fundamental Graph Theory as well as VRPs. The VRP is the central problem that has to be solved in order to optimize the WSC. This basic section is followed by the description of exact optimization techniques. A discussion of approximation techniques - Heuristics and Metaheuristics - shows advantages of these methods and a detailed description. The Rolling Schedule Approach (RSA) is a technique to cope with uncertainty in opti- mization environment is mentioned for this reason. The part covering SDSS elaborates on the genesis of SDSS and their components and the connec- tion to MCDA. In addition, the connection between GISc and SDSS is discussed. Furthermore, the role of optimization techniques in SDSSs is ex- plained. The different types of SDSSs are distinguished depending on the degree of integration in GIS or the integration of mathematical models in a GIS environment.

The application part shows a discussion of the experiment setup. The system architecture is layed out, that gives an overview of the application as such. Detailed description of the underlying Spatial Database Management System (SDBMS) and the modeling of the universe of discourse is given. Tracking and Tracing with LBS and reverse LBS as well as the seamless integration in the system follows consecutively. A description of the imple- mented LBS on mobile devices and the according service providers shows the capabilities of the system. The Decision Engine delivers optimization results based on the optimization methods described in the theoretical part. Heuristic methods are implemented in order to prove their applicability. This is followed by a section that highlights the setup for the evaluation of the WSC optimization - i.e. describes the problem instances at hand and the system on which the results are generated. In addition, the results are displayed in this chapter. There the focus lies on the work expenditure and the optimization results of the problem instances.

The discussion and outlook chapter is analyzing the results in a general way. First, alternative system architectures are highlighted, and a justifica- tion for the architecture used here is given, based on an evaluation utilizing standardized quality parameters. Secondly, the actual results of the opti- mization process are analyzed in detail, followed by the implications of this thesis on related fields of expertise and/or spatial problems.

Geographic Information Science and Technology

Geographic Information Science and Technology (GIS&T) is the domain of information technology that enables the researcher and technician to perform tasks that have a spatial dimension. Among them are data acquisition, stor- age and manipulation as well as visualization and analysis. The term GIS&T consists of two distinct parts: Geographic Information Science (GISc) and Geographic Information Technology (GIT). GIT comprises all technical tools that are necessary to build up and maintain a Geographic Information System (GIS) - and generate defined projects (e.g. cadastre). The evolution of GIS from a tool - reflected by GIT - to a legitimate scientific domain is documented by the emerging term GISc (Goodchild, 1992a). GISc was given a definition in Mark (2000):

” Geographic Information Science (GISc) is the basic research field that seeks to redefine geographic concepts and their use in the context of Geo- graphic Information System (GIS). GISc also examines the impacts of GIS on individuals and society, and the influences of society on GIS. GISc re- examines some of the most fundamental themes in traditional spatially ori- ented fields such as geography, cartography, and geodesy, while incorporating more recent developments in cognitive and information science. It also over- laps with and draws from more specialized research fields such as computer science, statistics, mathematics, and psychology, and contributes to progress in those fields. It supports research in political science and anthropology, and draws on those fields in studies of geographic information and society. ”

Goodchild (1992a) gives a list of items under the heading content of Geographic Information Science:

1. Data collection and measurement
2. Data capture
3. Spatial statistics
4. Data structures, algorithms and processes 15
16 Geographic Information Science and Technology
5. Display
6. Analytical tools
7. Institutional, managerial and ethical issues

In Goodchild et al. (1999) a number of open research questions are defined. Due to the technical formulation this condenses the term GISc. Among the mentioned research questions are:

- How to store, access and transform geographic concepts with minimal information loss?
- How can geographic phenomena be explained through applying methods and models of physical and human processes?

Moreover the University Consortium for Geographic Information Science (1996) presented a survey among their institutional members that identified the ten research topics of GISc, which reflect a number of relevant topics covered by this thesis (see table 2.1), e.g. spatial analysis, distributed and mobile computing as well as interoperability. Hence, the content of this thesis has relevance for GISc. This seems to be evident, when looking at the three distinct domains of GISc defined by Goodchild et al. (1999):

a) the decision maker
b) the system comprising digital GIT
c) the society with norms and standards

All three domains of GISc have relevance to this project - which will be explained in the following sections. The decision maker plays a vital role in any aspect connected with GISc. Especially for the case of Wood Sup- ply Chain (WSC) management a person supervises the process of assigning trucks and management by the system and may alter decisions of the system. Digital GIT is the basis for all intelligent systems dealing with spatial data. Hence, GIT is necessary for routing and guidance, tracking and tracing, as well as positioning and visualization of maps (see section 2.3). Norms and standards defined by ”GI-society” are the guidelines for developing a certain application. Moreover certain standards are explicitly designed for practical usage (e.g. Open Location Service (OGC, 2008b)). Thus, in most cases a reference implementation exists that reveals the potential of the standard. By building a project on standards, not each part of the planned GIT has

illustration not visible in this excerpt

Table 2.1: Ten Research Topics defined by University Consortium for Geographic Information Science (1996).

to be developed from scratch, which in turn saves development time. A detailed overview of the relevant standards and norms for WSC optimization is given in section 2.1.

Thill (2000) debates the nature of GIS and mentions Goodchild (1998, 1992b), who distinguishes three different classes of GIS models - having the transportation context in mind. The classes are:

- Field models, or a representation of continuous phenomena in space.
- Discrete models, that are related to discrete entities, like points, polygons or polylines.
- Network models, that represent topological connected linear entities, like roads, railways.

The three classes are not mutually exclusive, as a network consists of discrete entities - points and lines. It is obvious that the network models are most important in the domain of transportation planning - and in particular in WSC management. Due to the complex task of network modeling Goodchild (1998) proposed several data models for discrete network planning, which are based on network and discrete models, respectively. This is necessary, because network and discrete models cannot handle the complexity that transportation networks bear. Many features mentioned in this paper are not yet available, but enhance network planning (Thill, 2000; Goodchild, 1998). A number of important concepts are mentioned in the following paragraphs.

Planar and non-planar networks: Planar networks are datasets where a vertex is present at each intersection of a line, thus resulting in the cartographic and topologic representation to be equal. This results in a dataset that is hardly navigable, due to the fact that bridges or tunnels lead to obvious errors - e.g. traversal from a path to a motorway. In non-planar networks the cartographic and topological representation differs. Hence, the modeling of overpasses (e.g. bridges) is possible.

Turn tables: They model the turns between any pair of connected lines in a network. The attributes connected with a turn are binary when the allowed or forbidden maneuvers are modeled. Storing the delays, that are the result of a turn, result in cardinal numbers.

Dynamic segmentation: This offers the possibility to allow a variation of an attribute along an network element - i.e. vertex or edge. The original data structure is preserved, and no new vertices and edges are added. On top of this, discrete entities (0- and 1-dimensional) are placed at arbitrary positions of the network. These entities are stored in separate tables, and do not affect the original network. Dynamic segmentation is preferable when an attribute should vary over the network. An example would be speed limits or the modeling of traffic congestions.

Lanes: Due to the prior discussions, information about traversal is not stored in the data structure. Detailed data on the individual lanes reveals more potential, due to extra information on every single driving lane. With this concept it is possible to model complex street intersections in an ap- propriate manner, e.g. from which lane the highway exit ramp starts, or which lane is solely for turning left at a road intersection. Fohl et al. (1996) proposed a data model for storing lane based data, where a lane is a distinct entity that is connected with other lanes in a defined way, whereas all lanes of a road share the geometry of the road itself - i.e. an edge. Hence, there is no need to determine the absolute and relative positions of the lanes, but within the model the topology is stored, which is of particular importance. Furthermore, the topological relations of lanes, such as adjacency, can be extracted.

Flows: In order to represent ”real” traffic situations the number of vehi- cles traveling or quantities of goods transported on an edge are of interest. Hence, network flows are discussed in literature by Fohl et al. (1996) and Ahuja et al. (1993). Goodchild (1998) distinguished three types of flows:

a) flows allocated to the data model, b) flows between origins and destina- tions where flows exist between two places in both directions (square case) - see figure 2.1 - and c) flows between origins and destinations similar to the square case, but where the set of origins is different than the set of des- tinations (rectangular case) - see figure 2.2. The first type describes the mapping of e.g. measurement or traffic data on the edges and vertices of the network. Some constraints can be attached like skew symmetry and flow conservation which guarantee a ”correct” flow. These concepts are well implemented in the field of mathematics and got incorporated in a number of GIS. For the second and third type the data structure and entities to support this flow have to be created first, in order to map the network flow accordingly. So far no GIS supports the last two types of network flows from scratch.

illustration not visible in this excerpt

Figure 2.1: Graphical illustration of a network flow between origins and destinations - the square case. From Goodchild (1998).

illustration not visible in this excerpt

Figure 2.2: Graphical illustration of a network flow between origins and destinations - the rectangular case. From Goodchild (1998).

Temporal dimension: Common GIS and database models do not sup- port the temporal dimension that navigation and transportation datasets have. For WSC optimization time is of crucial importance, thus, it has to be a prominent part of the data model. Hence, here is a brief look at time in GIS. Goodchild et al. (1993) define two distinct ways to represent time behavior:

1. Activity events: Time periods where any individual is connected with an activity - an event. Each event is associated with two locations (start and stop), which coincide if it is a static event. Considering the changes of entities attributes in the course of an activity, spatial attributes, such as location (position), boundary and shape, may be modified too. Based on these changes, three types of spatial-temporal behavior can be distinguished (Hornsby and Egenhofer, 2000; Renolen, 2000; Tryfonia and Jensen, 1999):

Continuous change: Entities of this type are changing constantly, like a weather system or an avalanche (see figure 2.3). There the spatial behavior, the shape and the properties are in an unsteady state.

Discrete change: Entities are in a static state and change directly through an event (see figure 2.4). An example is real estate whose owner changes immediately after an acquisition, or change in shape through partitioning the real estate into small parcels.

Stepwise change: entities have either a static state, but do change through an event (see figure 2.5). An example are vehicles movements over time, where the position is changed but the shape remains con- stant.

illustration not visible in this excerpt

Figure 2.3: Continuous spatial-temporal behavior of attribute a over time t (after Wang and Cheng (2001) and Renolen (2000)).

illustration not visible in this excerpt

Figure 2.4: Discrete spatial-temporal behavior of attribute a over time t (after Wang and Cheng (2001) and Renolen (2000)).

2. Space time matrices: By the assignment of activity events to spa- tial entities 3D-matrices can be created consisting of three axis: time, activity and position. This allows a three dimensional analysis to iden- tify spatial-temporal behavior, which is crucial for WSC management. Each spatial temporal movement can be evaluated using time geogra- phy (Hägerstrand, 1970). This allows the creation of space-time paths, which form a trajectory of an individual’s movements in physical space

illustration not visible in this excerpt

Figure 2.5: Stepwise spatial-temporal behavior of attribute a over time t (after Wang and Cheng (2001) and Renolen (2000)).

over time (see figure 2.6). The concept was enhanced by Lenntorp (1976), who incorporated the idea of transportation. Thus, it is possi- ble to model e.g. a person’s potential area that she can reach in a given amount of time starting from their actual position. This continuous space in the space-time coordinate system is named space-time prism. When projected onto a two-dimensional space the resulting region is called potential path area (see figure 2.7). According to Yu (2006), the space-time path represents historical data, while the space-time prism and potential path area allow an outlook of possible future movements by any actors - e.g. trucks participating in the WSC.

illustration not visible in this excerpt

Figure 2.6: Illustration of a space-time path. These graphs are based on time geography (Hägerstrand, 1970). Graphic adopted from Yu (2006).

At the junction of temporal dimension and transportation in GIS ten functional requirements were defined by Adams et al. (2000) and mentioned in Koncz and Adams (2002) that reflect the needs of GISc in transportation. All of them have a direct or indirect link to time. To give an impression of the requirements, the most important for WSC optimization are: spatial

illustration not visible in this excerpt

Figure 2.7: Space-time prism and potential path area. Graphic adopted from Yu (2006).

and temporal referencing methods, temporal referencing system, temporal topology, dynamics, historical databases, resolution (temporal and spatial dimension). Moreover the research activities defined by Pas (1985) support the finding, that GISc is a vital expertise in WSC management. Among the defined major areas of investigation in the field of spatial-temporal modeling Pas (1985) mentions:

- activity scheduling in time and space
- spatial-temporal, interpersonal, and other constraints - interactions in travel decisions over time

Although the findings are related to human travel decisions, one can easily identify the correlation between the points above and WSC management, as defined in section 1.2. There activity scheduling is a vital part, due to the fact that vehicles have to pick up timber at several locations dispersed over space and deliver that to saw mills. In addition, a number of constraints are applicable to the whole problem that are mentioned in section 1.2, e.g. truck capacity or working time limits. Travel decisions of individual vehi- cles during a scheduled assignment are inevitable, due to changing weather conditions that result in impassable road segments. Thus, the assignment may be altered in real time, and other assignment of the vehicle have to be changed too.

The theory explained in the preceding paragraphs describes data mod- els and additional features that are necessary for transportation modeling with GIS&T. This is of importance for the storage of spatial-temporal in- formation, navigation issues, and creation of accurate maps with real-time data. For these tasks a GIS - in which form ever, e.g. spatial database - is used. Goodchild (1998) mentions five application paradigms, which are also encountered in Bartelme (2005):

- digital map production
- inventory and management - integration of data
- spatial analysis
- dynamic modeling

All listed items are of particular importance for WSC optimization, which is described in this paragraph. Digital map production is of major importance both for a logistics central office and for mobile devices, both for planning and for monitoring (”Where are the trucks now?” or ”Where are the tim- ber piles to be picked up?”) and thus has a direct link to inventory and management paradigm. Data integration is of vital interest, due to emerg- ing Spatial Data Infrastructures (SDIs) and other external datasets that have to be seamlessly incorporated into an WSC management application. The capability to review and analyze past activities is delivered by spatial analysis functionality. In this context the books of Bartelme (2005), Fother- ingham et al. (2000), Burrough and McDonnell (1998), Bailey and Gatrell (1995) and Worboys (1995) are mentioned, that provide an introduction into spatial analysis. Dynamic modeling is one of the most important and inno- vative concepts concerning WSC optimization. Due to the uncertain nature of the problem itself (see chapters 3.5 and 1.2) the WSC optimization cannot deliver solutions that are valid for a long time period - e.g. one month - and has to react to changing external conditions. Thus, automatic forecasting, scheduling, as well as the evaluation of different scenarios has to be possible. In addition, the visualization of dynamic modeling results is of particular interest for stakeholders of WSC management.

2.1 Standardization in GIS

Standardization is one of the key issues of SDIs and distributed systems. Standards are inevitable in projects with a great number of participants and high data transfer rates, in order to share information between them. In addition, the intra- and interorganizational communication and coordination is possible. In the course of this chapter a brief look at interoperability is given, the term standard is defined followed by a number of standards that have direct influence on the thesis.

2.1.1 Interoperability

Due to the fact that in the course of this research, data are transmitted in an extensive way by various devices, the term interoperability is discussed first, because one set of (spatial) data has to be used by all participants of the WSC. The IEEE (1990) defines interoperability as follows:

” The ability of two or more systems or components to ex- change information and to use the information that has been exchanged. ”

The Dublin Core Metadata Initiative (2009) defines the term in a similar, but enhanced way:

” The ability of different types of computers, networks, operat ing systems, and applications to work together effectively, with out prior communication, in order to exchange information in a useful and meaningful manner. There are three aspects of interoperability: semantic, structural and syntactical. ”

This definition comprises different levels of interoperability that are im- portant to GIS&T, and stresses the fact, that standards have to be defined beforehand in order to get two systems ”talking”. The following elaboration on interoperability levels is based on Friis-Christensen et al. (2005), Stuck- enschmidt (2003) and Bishr (1998). Syntactical interoperability is related to the encoding of data, e.g. different formats that have to be harmonized. The mapping of data schemas - the logical data description (Denkers, 1992), which can be carried out in e.g. XML - is provided by structural interoper- ability. Thus, the conversion of a source into a target schema is possible at a very basic level, by resolving e.g. differences in attributes. Semantic inter- operability is related to the meaning of a term, often in correlation with the specific context. Hence, not only technical issues are affected but also the social context has to be considered. Classical examples are extensively dis- cussed in Harvey et al. (1999). There the case studies show the importance and practical problems that arise when data should be shared considering semantics. Semantics rely on ontologies, that are defined as ” formal, explicit specification of a conceptualization ” (Gruber, 1993). The result is a vocab- ulary for a specific knowledge domain as well as the meaning and relations between them (Yue et al., 2008). To represent an ontology the Web Ontol- ogy Language (OWL) (W3C, 2009a) is one possibility besides e.g. XML. OWL is a standard in this field proposed by World Wide Web Consortium (W3C).

The first two levels of interoperability are frequently summarized as tech- nical interoperability, due to their nature and the fact that these issues can be handled by software accurately. In contrast semantic interoperability is still a vital research topic and has not been solved entirely. So far a number of examples and basic initiatives have been carried out that extend capa- bilities of GIS&T in that direction. For Web 3.0 a number of tools exist that exploit the concept of serendipity (Ertzscheid and Gallezot, 2004), e.g. Wilbur Semantic Web Toolkit (Lassila, 2007). In addition, the Semantic Web - a part of Web 3.0 - is in development right now, which utilizes the meaning of information in the WWW (Berners-Lee, 2000). This technol- ogy will have great impact on interoperability in the field of GIS&T, due to the concept of serendipity and minimized losses in information sharing and distribution.

To come up with ”fully” interoperable GISs, with respect to the three levels mentioned in the prior paragraphs, standards are inevitable. So far they provide a valuable fundament for technical and partly semantic interop- erability. Thus, in the next section the standards that are of importance for real-time spatial optimization and in turn WSC optimization, are discussed.

2.1.2 Standards

Prior sections show the necessity of standards. The British Standards Institute (2009) defines a standard as follows:

” A standard is an agreed, repeatable way of doing something. It is a published document that contains a technical specification or other precise criteria designed to be used consistently as a rule, guideline, or definition. Standards help to make life simpler and to increase the reliability and the effectiveness of many goods and services used. Standards are created by bringing together the experience and expertise of all interested parties such as the producers, sellers, buyers, users and regulators of a particular material, product, process or service. ”

Here a separation of the term ”standard” itself is conducted. Considering the legal basis there are two classes of standards:

a) de facto standards

b) de jure standards

De facto standards are not created by a standards organization, like International Organization for Standardization (ISO) or Comité Européen de Normalisation (CEN), and thus are not legally binding. In the scope of this work all standards not created by a standards organization are summarized as de facto standards, although they may have become de jure standards later on. One major organization that creates and publishes de facto standards in the field of GIS&T is the Open Geospatial Consortium (OGC), whose members are companies of the GIS industry.

De jure standards are under special circumstances legally binding, which is outlined here. Globally speaking international standard organizations like ISO or CEN as well as national organizations such as the Austrian Standards Institute (ON) exist. Standards, which originate from ISO don’t automatically become national standards. Even national standards may be in some points contradictory to an ISO standard. Nevertheless, a CEN standard is also a national standard if the national standards organization is a member of CEN - which is the case for ON. If an ISO standard is accepted as CEN standard then the ISO standard has to be accepted by the national CEN member organizations - which can be regarded as legally binding standards.

Such standards have to undergo an intense procedure of testing and revising through various instances before it is signed by all members and published. Thus, a de jure standard reflects recent technical terminology and actual technical rules for a specific field of expertise. Therefore, de jure standards are a valuable source of technical ”know-how” due to their technical maturity and no industry driven development.

2.1.3 De facto Standards

In the following paragraphs the standards published by OGC that are strong- ly related to this thesis are explained. Among them there are: Web Map- ping Service (WMS), Web Feature Service (WFS), Open Location Service (OpenLS), Geography Markup Language (GML), OpenGIS® Simple Fea- tures Interface Standard (SFS). Most of these standards have been - or are

- in the process of being adopted by ISO and CEN.

WMS provides an HTTP interface to get georeferenced maps - images

- from one or more spatial databases (located on distributed servers). The request specification comprises the layer(s) and the area of interest. The server responds with georeferenced map(s) in a defined format (e.g. JPEG, GIF, PNG) that can be displayed in any browser or geoportal application - e.g. Mapbender. For more details refer to OGC (2006c).

In order to directly access distinct features of spatial datasets the WFS interface was created. This service enables clients to send platform inde- pendent requests via HTTP, that fulfill the specifications of interfaces that are capable of manipulating and accessing spatial features. An extension to WFS specification is the Web Feature Service-transactional (WFS-T) which adds functionality to the basic WFS. Among the functionalities of WFS and WFS-T are:

- access spatial features based on constraints (spatial and non-spatial) - create new features
- delete features
- manipulate features - lock features

This standard requires data to be sent from spatial databases to clients. WFS data transmission utilizes another feature encoding standard, namely GML, that will be discussed in the following paragraphs. For more information concerning WFS refer to OGC (2005).

OpenLS is an umbrella for a number of standardized services in the field of Location Based Service (LBS), that have a great impact on this thesis and will be discussed in detail in chapter 2.3. The core services defined in OGC (2008d), OGC (2008c) and OGC (2008b) define a number of interfaces that are summarized in the so-called GeoMobility Server:

- Directory Service: provides a functionality to find e.g. the nearest place or service (i.e. POI’s).
- Gateway Service: An interface between the GeoMobility Server and a spatial data server that contains locations of mobile users. This service enables a client to get another actual user’s position.
- Location Utility Service (Geocode - getting the position out of e.g. an address - and Reverse Geocode - determining the e.g. address using the actual position)
- Presentation Service - Route Service
- Navigation Service - Tracking Service The modularity of the services mentioned in the preceding list allows companies to link up with services and provide a special application on top of the standard. Well known examples are: emergency services, traffic information systems or any routing system. Thus, OpenLS has great impact on the WSC optimization, due to the fact that mobile units have to e.g. be tracked, navigate to the timber piles, and they have to send information to the logistics center.

GML is an Extensible Markup Language (XML) grammar that is capa- ble of representing spatial features. Due to its enormous acceptance within the Geographic Information (GI)-community it has become a versatile mod- eling language for GIS as well as data exchange format - especially over the internet. Like almost every XML grammar, GML consists of two distinct parts: a) the schema file, that describes the document and b) the instance document with the spatial data. GML supports a set of primitives, that are the basis for the development of XML schemas, such as:

- Feature: represents a physical entity, but must not necessarily have spatial properties. E.g. a building may be a feature object with the position stored as geometry object - a point.
- Geometry: strictly stores geometry primitives - Coordinate Reference System
- Topology
- Time
- Unit of measure - Observations

These primitives are important for the development of application schemas, that support data exchange within a community. Such schemas consist of an XML schema file that contains relevant object classes that are of interest for a certain group of experts. Examples are CityGML (OGC, 2008a), which became a standard recently, SensorML (OGC, 2007c) or LandGML (LandXML.org Industry Consortium, 2009). More information is available in the Implementation Specification by OGC (2007a).

Simple Features Interface Standard (SFS) is a standard to ”work” with spatial data in a common and well-defined way. It facilitates object-rela- tional databases, and thus provides an architecture for storage and retrieval of geodata and provides a number of spatial operators to manipulate data. It supports the following geometrical primitives: point, line (LineString), polygon, 1 − points in one geometry (MultiPoint), 1 − lines in one geometry (MultiLineString), 1 − polygons in one geometry (Multipolygon), collection of geometries (GeometryCollection). Operators that are able to manipulate spatial data can be grouped into three classes:

- Basic Operators: e.g. retrieval of geometry type, envelope.
- Spatial Relations Operators: e.g. do two features touch, or are they equal.
- Spatial Analysis Operators: e.g. buffering, difference, union.

This standard is especially interesting for real-time spatial and WSC optimization, due to the database driven system architecture, that will be discussed later. The project, that is part of this thesis, solely works with spatial data that are stored in a spatial database that supports SFS. More information on this popular standard can be found in OGC (2006a).

2.1.4 De jure Standards

Basically de jure standards are described in section 2.1.2. Here ISO stan- dards are described that are of real importance for this thesis. In addition the OGC standards that have become ISO standards recently are mentioned here.

The Geography Markup Language (GML) as specified in ISO (2007c) is an XML dialect for the transmission and storage of geographic information. This standard is compliant with ISO 19118 (ISO, 2005a) and is equal to the OGC GML standard in the version 3.2.1.

ISO 19912 ”GI - Spatial referencing by geographic identifiers” (ISO, 2003a) defines a model for spatial referencing using geographic identifiers. It also defines the components of a spatial reference system and develops components of a gazetteer. Thus it fosters the understanding of spatial references used in datasets.

ISO 19115 ”Metadata” (ISO, 2003b) defines the schema for describing geographic information and services in the form of structured metadata. Hence, building a metadata catalogue based on the standard, results in information about the identification, the extent, the quality, the spatial and temporal schema, spatial reference and distribution of spatial data. It defines metadata information that are mandatory or optional, and highlights the minimal set of metadata necessary for metadata applications.

ISO 19119 ”Geographic Information - Services” (ISO, 2005b), which is identical with OGC Abstract Specification - Topic 12: ”The OpenGIS Ser- vice Architecture”, describes the general architecture for geospatial services, that are capable of accessing and processing spatial data from distributed data sources. In addition, this standard provides the following:

- abstract framework for a service oriented architecture
- standardized interfaces which allow the development of interoperable services
- support for a service catalogue by catalogue metadata - the usage of distributed data sources

The service architecture defined in ISO 19119 is described through four view- points: a) computational viewpoint, b) information viewpoint, c) engineer- ing viewpoint and d) technology viewpoint. The computational viewpoint contains the interaction between systems through interfaces, and defines the terms service, interface and operation. Through the explanations, trans- parent service chaining is possible. The information viewpoint describes the semantics of information processing and information itself, and distinguishes six classes of services in the geospatial context - see table 2.2. In order to provide a proper distribution of data with services the engineering view- point documents distribution oriented aspects. The specific implementation is elaborated in the technology viewpoint. For details refer to ISO (2005b).

illustration not visible in this excerpt

Table 2.2: Geographic Services as defined by ISO (2005b).

ISO 19125 Geographic Information - Simple Feature Access - Part 2: SQL Option the 2 part of ISO 19125, ”Simple Feature Access”, (ISO, 2004) defines an SQL schema that supports storage, retrieval, query and update of simple spatial features. In addition, this part of ISO 19125 describes a set of SQL Geometry Types together with SQL functions on those types, equal to OGC SFS mentioned the de facto standards section (see section 2.1.3). For details refer to paragraph containing OGC SFS.

ISO 19128, ”Web map server interface”, (ISO, 2005c) specifies a service that produces spatially referenced maps dynamically from geographic information, equal to OGC WMS described in section 2.1.3.

ISO 19132, ”Location-based services - Reference Model”, (ISO, 2007a) specifies a reference model and a conceptual framework for LBSs. In addition it describes the principles and interactions between systems, which are mentioned in chapter 2.3. Typical services of LBS are discussed in detail. General principles for mobile and fixed clients are explained as well as the interactions with other ISO standards in the field of GI.

ISO 19133, ”Tracking and Navigation”, (ISO, 2005d) describes operations and data types for the development of tracking and navigation services. It aims to web services that are available to wireless devices.

Data types and operations for the implementation of multimodal loca- tion-based services for routing and navigation are defined in ISO 19134, ”Multimodal routing and navigation”, (ISO, 2007b). Like ISO 19133, its goal is to develop web services that are usable by wireless devices.

De jure standards are of particular interest for the thesis by providing the nomenclature for LBS as well as tracking and navigation, and a number of terms in the field of GI. Together with the mentioned de facto standards they form a strong set of technical fundaments this thesis relies on. Without the formulation of standards every single piece of technology would have to be ”invented” or at least re-engineered (even) for the purpose of research.

2.2 Service Oriented Architectures in GIS

The term Service Oriented Architecture (SOA) is a paradigm for distributed digital capabilities able to solve a specified task (Organization for the Ad- vancement of Structured Information Standards, 2006). Benatallah and Mo- tahari Nezhad (2008), Papazoglou and van den Heuvel (2007) and Alonso et al. (2004) state that SOAs provide an architectural paradigm and abstrac- tions that simplify the integration of various types of software within one project. Thus, software functionalities are packaged in well defined modules and exposed to externals as services and service interfaces that are inde- pendent of the state and context of neighboring services. The overall goal of SOA is the elimination of barriers of legacy systems, proprietary formats, protocols, platforms and data transmission so that various applications can be integrated and run seamlessly. Holley et al. (2003) state that services in a SOA should meet the following criteria, listed here: - All functions are defined as services.

- All services are autonomous, so that they run on an opaque level. External services do not care about the actual implementation or how results are achieved. The only thing that is visible to externals is the published service interface.
- Generally speaking, services are invocable. Hence, the protocol or infrastructure component to establish the connection are irrelevant.

If developing a SOA an architect can rely on benefits of this concept. A SOA provides a simple and scalable paradigm for systems that need inter- operability. The scalability is a result of the network assumptions of SOA as they are very low. Due to the flexibility it is easy to integrate new systems or functionalities into a grown architecture. Thus this architecture ensures a flexible and agile adaption of a system according to the user needs.

To realize SOAs a number of technologies exist. Three technologies, listed below, have gained great interest within the community. They are discussed in detail in the following paragraphs.

- Web Services - which are abbreviated as WS
- Services following the Representational State Transfer (REST) architecture (Fielding, 2000)
- Simple Object Access Protocol (SOAP) (W3C, 2009b)

WSs have gained popularity because of interoperability and standardization, due to their availability over standard Internet protocols independent of the underlying platform. Thus, they facilitate loosely coupled and decentralized applications. Web Services (WSs) heavily rely on standards, in order to ensure data transfer between two applications/computers without prior communication. Within a SOA an application/computer - generally, actor in a SOA - can have one or both states (Gisolfi, 2001):

- Service provider, that provides a Web Service with given specifications and functionalities. The implementor of a service provider has to reg- ister the service at a specific service broker. The service broker serves as clearing house or ”yellowpages” for published services (see figure 2.8).

[...]