Multi User Context-Aware Service Selection for Mobile Environments

Abstract

Modern service systems build on top of service dominant designs which encompass contextualization (value-in-context) and collaboration (value-in-use) between users and service providers. Processes in this domain often require the consideration of both context information (e.g., location or time of day) and multiple participating users where each user probably has its own preferences and constraints (e.g., restricted overall budget). However, selecting a suitable service provider for each action of a process, especially when some of these actions are conducted together by several users, can be a complex decision problem in multi user context-aware service systems. Consequently, exact approaches are not fit to solve such a service selection problem in appropriate time. Thus, the paper proposes a heuristic technique applying a decomposition of the users’ global constraints and a local service selection. In this way, the aim is to determine a feasible service composition for each participating user while taking the users’ individual preferences and constraints as well as context information into account. The evaluation of the heuristic technique shows, based on a real-world scenario in the tourism domain, that the proposed approach is able to achieve close-to-optimal solutions while efficiently scaling with problem size and therefore can support decision makers in multi user context-aware service systems.

1 Introduction

Based on a progressive development of new mobile technologies (e.g., smartphone, tablet), applications and services, mobile business has gained in importance during the last decade (Statista 2017a, b). Businesses started capitalizing on this development to deliver their goods and services tailored to a new mobile lifestyle (Kabir and Akhtar Hasin 2011). The development also supports the construction of service systems (cf. Alter 2012) in form of a context-aware interplay of stationary and mobile devices, services and users (Zaplata et al. 2009). Thus, individual and professional processes conducted by multiple users jointly using services accessible anywhere and anytime are enabled (Zaplata et al. 2009; Deng et al. 2016). In this regard, context information such as location, time of day or temperature that can be gathered via the sensory capabilities of modern mobile devices play a vital role as they allow for a high degree of individualization (cf. Zhang et al. 2009; Böhmann et al. 2014; Amin et al. 2016). In general, context information can be defined as “any information that can be used to characterize the situation of an entity. An entity is a person, place, or object that is considered relevant to the interaction between a user and an application, including the user and the application themselves” (Dey 2001, p. 5).

Modern service systems, especially those focusing on context-awareness, build on top of service-dominant designs (Edvardsson et al. 2011; Alter 2012; Böhmann et al. 2014). Service-dominant designs encompass contextualization, value bound to a given context (value-in-context), and collaboration, which describes the process of value co-creation and co-consumption (value-in-use). Co-creation resp. co-consumption in this regard means that the value of a considered service is created by service providers and users together resp. employed by multiple users together (Vargo and Lusch 2004; Grönroos 2011). This means that some actions from otherwise possibly different processes of users have to be conducted simultaneously together by more than one user. This can be necessary due to the needs or preferences of users aiming to use and employ special customer services with additional value. Processes containing actions that have to be conducted simultaneously together by multiple users are called multi user context-aware processes in the following and are in the focus of this paper.

In mobile environments the amount of available information can easily overwhelm a user and lead to an information overload problem (Zhang et al. 2009; Shen et al. 2012a). Thus, users require decision support to find and use the appropriate service for a given context. This issue is further intensified when considering multiple users and their individual preferences and needs. From this viewpoint, the underlying decision problem can be characterized as a selection problem. Here, we aim to select the most suitable services while dealing with individual context information of users and their coordination (e.g., to conduct actions simultaneously together). Our aim is to provide a selection method that can be used by service systems (Alter 2012) for multiple users with the consideration of context information in mobile environments.

Providing such a method and thus supporting a corresponding service system can be valuable in different application fields. For example, information service providers such as Yelp or TripAdvisor can be used to retrieve informational entities (and thus service offers) about restaurants, museums, sights or other real-world objects. In this regard, a multi user context-aware process in the tourism domain can represent a city day trip by a group of users (tourists). The providers (i.e., Yelp, TripAdvisor, etc.) of the informational entities referring to real-world objects and the users with their mobile devices form the participants of a service system (cf. Maglio et al. 2006; Alter 2012; Lyons and Tracy 2013; Frost and Lyons 2017). Moreover, a city day trip (process) consists of multiple actions (e.g., having lunch, visiting a museum), where some actions may be conducted together by several users, requiring the coordination of the users’ actions. Furthermore, each action can be supported by different informational entities referring to real-world objects that differ only in attributes such as price or selection of food. To find favorable entities, the individual preferences (e.g., for a certain user, price could be more relevant than selection of food) and global end-to-end constraints (e.g., restricted overall budget) of each user need to be taken into account. Additionally, context information such as business hours and location (of both users and informational entities) is also highly relevant. The huge amount of informational entities that can support a certain action (e.g., almost 10,000 restaurants can be visited in the city of Berlin, Germany¹) further contributes to an information overload problem, requiring that users need to be supported in their decision making (a discussion of further application fields of multi user context-aware service systems like healthcare or disaster relief assistance can be found in the Online Appendix 1).

The underlying decision problem can be characterized as a service selection problem: By modeling and representing real-world objects as informational entities or service objects, service selection methods can be utilized as decision support. More precisely, a multi user context-aware service selection problem can be defined as the problem of determining the specific composition of service objects for each user that fits best to the users’ current context as well as to their individual preferences and global constraints regarding non-functional properties (NFP) such as price and duration (cf. Zeng et al. 2004; Yu et al. 2007; Alrifai et al. 2012). Furthermore, if there exist any dependencies between the service compositions of individual users, the coordination of the users’ actions is also required. This includes the mandatory simultaneous use of one or more service objects by several users together (cf. Wang et al. 2010; Wanchun et al. 2011; Benouaret et al. 2012), which will be in the focus of this work.

In mobile environments, often a huge number of different alternative service objects for the realization of each action of a process (cf., e.g., the tourism domain) exists. This leads to large service selection problems. Due to the NP-hardness of the underlying decision problem, finding an optimal solution in appropriate time is not practical, as computation time increases exponentially subject to problem size (cf. Zhang et al. 2012; Moghaddam and Davis 2014; Zhang et al. 2016). These performance issues are amplified by the increased problem complexity that results from considering multiple users and context information (cf. Lewerenz 2015). This is due to existing dependencies within a user’s service composition (resulting from context information) as well as between different service compositions of several users (resulting, e.g., from the mandatory simultaneous use of service objects by several users) need to be taken into account. To address these issues, the use of a heuristic technique instead of an exact service selection approach is envisioned. Existing works presenting exact service selection approaches also state the need to develop heuristic techniques (e.g., Zeng et al. 2004; Klöpper et al. 2010; Xu and Jennings 2010. As to the best of our knowledge no such heuristic technique for solving multi user context-aware service selection problems exists, the research question of our work is as follows:

How to design a heuristic technique for the multi user context-aware service selection that determines a close-to-optimal solution in a short amount of time while scaling efficiently with problem size?

In this regard, we position our work within service systems engineering as a method to enable and enhance the contextualization and collaboration within multi user context-aware service systems and processes (Böhmann et al. 2014). The remainder of this paper is structured as follows: In the next section, we introduce a running example to illustrate our research in more detail. Then, we analyze the existing literature and, based on this analysis, discuss the research gap and our contribution. This is followed by the introduction of our model setup, which is the foundation for the presentation of our heuristic technique in the succeeding section. In the evaluation section, we analyze the performance and scalability as well as the solution quality of our approach. Finally, we conclude our paper with a short summary and an outline of limitations and further research.

2 Running Example

We introduce a running illustrative example as a basis for discussing our approach. This example is based on a scenario of five users being on a day trip in the city of Munich, Germany (see Fig. 1). All users share a process consisting of several actions (i.e., service classes) such as visiting a museum or zoo, having lunch at a restaurant, visiting a sight, fun attraction or nature (e.g., park), city tour and café. Furthermore, all users want to have lunch together at a restaurant (e.g., “Sababa”, “Ni House”) and want to have a city tour together in the afternoon, which can be understood as the mandatory simultaneous use of the same service object in both cases. An action resp. service class in the focus for a mandatory simultaneous use is denoted by Focus Class (FC) in the following. Thus, in a FC all users have to use the same service object at the same time. Moreover, in the example, all service objects are described by the attributes price and duration. All five users have their individual preferences and global end-to-end constraints regarding these NFP (e.g., restricted budget for the whole city trip). Additionally, the service objects representing real-world objects are further described by the context information GPS position (in terms of latitude and longitude) and business hours (cf. Fig. 1). While the GPS position can be used to determine the distance between service objects, business hours indicate whether a service object is available with respect to the time of day. For example, the restaurant “Ni House” is closed until 11:00 am. Consequently, having lunch at “Ni House” is only possible after 11:00 am whereas “Sababa” opens already at 10:00 am. Therefore, depending on the time of day each of the users starts the day trip (i.e., the users’ initial contexts) and on the time each of them spends in the same or different museums or zoos, they will be able to have lunch together at a specific restaurant or not. This means that a temporal coordination of the users is necessary. In order to determine a (close-to-)optimal solution of this service selection problem, all users’ preferences and constraints regarding price, duration and distance, all users’ initial context as well as the dependencies resulting from context information (i.e., GPS position, business hours) and multiple users (in terms of the FCs restaurant and city tour) need to be taken into account. The heuristic technique presented in this paper aims to address such decision problems in a multi user context-aware service system.

Fig. 1

Illustrative example of a city trip

3 Literature Background and Research Gap

In the following, we will discuss existing service selection literature that deals with the consideration of dependencies resulting from both multiple users and context information. This discussion is based on a search of related work conducted in aisnet.org, Web of Science, ACM, IEEE Xplore, INFORMS and ScienceDirect. Here we used the search terms (1) “multi* user” AND “service selection” (character “*” as wildcard for any character(s)) as well as (2) “context” AND “service selection”, which resulted in 82 papers for (1) and 330 papers for (2). We then analyzed whether these works present service selection approaches relevant for our research. Moreover, in order to identify further relevant works, we also conducted a backward and forward search based on these papers. After screening titles, keywords and abstracts and removing duplicates 16 works regarding (1) and 101 works regarding (2) remained. Based on reading both introduction and summary of these papers, we extracted only the papers that take dependencies resulting from multiple users and context information into account. This resulted in 9 works for search term (1) and 7 works for search term (2). The results indicate that much service selection literature considering multiple users or context information exists, but only 16 works propose (mathematically defined) service selection approaches that deal with dependencies resulting from multiple users or context information. In the next paragraph we discuss this literature and present the identified research gap and our contribution.

3.1 Literature Background

Besides traditional single user service selection approaches (cf., e.g., Zeng et al. 2004; Ardagna and Pernici 2007; Yu et al. 2007; Alrifai et al. 2012), a variety of approaches that consider multiple users (e.g., Wang et al. 2010, 2014; Kang et al. 2011; Wanchun et al. 2011; Benouaret et al. 2012; He et al. 2012; Jin et al. 2012a, b; Liang et al. 2013; Heinrich et al. 2015a; Zhu et al. 2017) or context information (e.g., Zhou et al. 2008; Yu and Reiff-Marganiec 2009a; Xu and Jennings 2010; Yuan et al. 2013; Zhang et al. 2013a; Heinrich and Lewerenz 2015; Lewerenz 2015; Deng et al. 2016; Zhang et al. 2016) exists.

To begin with approaches that consider multiple users, Benouaret et al. (2012), Wanchun et al. (2011) and Wang et al. (2010) focus on the mandatory use of the same service (object) by several users – as we do. However, they consider only one single action (i.e., one service class) and thus not a complete process. He et al. (2012), Jin et al. (2012a) and Zhu et al. (2017) address capacity limits of services in their works, and Heinrich et al. (2015a) propose a multi user service selection approach for processes where users have preferences with respect to other users. However, all of these works do not deal with any context information (see also Table 1).

Table 1 Summary of literature discussion

In contrast, context information and resulting dependencies are considered, for instance, by Heinrich and Lewerenz (2015) in terms of business hours and the distance between different service objects. Shen et al. (2012a) address the distance between different devices of a user in their approach. Yu and Reiff-Marganiec (2009a) consider price discounts for certain sets of services when determining suitable services for scenarios such as organizing a meeting or planning a trip. The service selection approach of Deng et al. (2016) considers the variation of the mobile network’s signal strength in case a user is moving around. All of the approaches taking into account context dependencies resulting from context information but do not cope with multiple users.

Existing literature considering multiple users or context information can be distinguished in works proposing exact approaches and works presenting heuristic techniques for solving the service selection problem. While exact approaches can assure the optimal solution, they usually are faced with performance issues due to the high problem complexity, in particular caused by the consideration of multiple users or context information. Therefore, other researchers have proposed heuristic techniques that aim to overcome these issues while still achieving a close-to-optimal solution. For instance, Ai and Tang (2008) and Zhang et al. (2013b) provide genetic algorithm approaches, where the dependencies resulting from context information are regarded in the crossover and mutation phase of the algorithm. Moreover, Zhu et al. (2017) utilize artificial bee colony optimization to solve the multi user service selection problem taking capacity limits of services into account. Other authors such as Yu and Reiff-Marganiec (2009a) and Zhang et al. (2013a) restrict the consideration of context information to certain areas of the whole process and solve the service selection problem based on that. A similar idea is followed by Jin et al. (2012a) and Lewerenz (2015) who transform the user’s global end-to-end constraints regarding the NFP into local constraints to adapt local service selection. Table 1 summarizes the literature discussion.

3.2 Research Gap and Contribution

As discussed in the literature background, several service selection approaches that either address context information or multiple users exist. An approach that allows to consider both is – to the best of our knowledge – missing so far. Moreover, due to the high complexity of the multi user context-aware service selection problem, a heuristic technique that determines a close-to-optimal solution in a short amount of time while scaling efficiently with problem size is needed. Therefore, we aim at developing such an approach in this work.

To do so, we will utilize the concepts of decomposition and local service selection which refer to the selection of locally optimal service object(s) regarding a sub process of a multi user context-aware service system. As stated in literature (cf. Alrifai et al. 2012; Jin et al. 2012a; Surianarayanan et al. 2015), these concepts provide a promising foundation for developing heuristic techniques for service selection as the overall problem complexity can be distributed to several smaller service selection problems. Additionally, local selection is efficient in terms of computation time compared to global optimization (Sun and Zhao 2012). However, local selection without considering the users’ global end-to-end constraints regarding the NFP (e.g., restricted overall budget) may result in possibly infeasible service compositions. To address this issue, we propose an optimized decomposition of global end-to-end constraints into local constraints, which can then be used in local selection. Furthermore, in order to enable the consideration of context information and multiple users in decomposition and local service selection, our heuristic technique is based on a stateful representation (cf., e.g., Heinrich and Lewerenz 2015). This representation allows to coordinate the users’ actions based on dependencies resulting from context information and between service compositions of individual users.

In conclusion, our aim is to present a heuristic technique that is able to consider both context information and multiple users while providing close-to-optimal solutions and a good scalability with problem size.

4 Model Setup

To enable a better differentiation between existing knowledge and our contribution, we introduce existing definitions and concepts in this section that can serve as a foundation for our service selection approach.

4.1 NFP Model and Utility Function

In a first step, we consider a sequential process consisting of several service classes $S_{i}$ (i.e., actions), with $i = 1$ to $I$ (cf. Ardagna and Pernici 2007; Yu et al. 2007) and multiple participating users $a \in A$. Each service class encompasses a set of functionally equivalent service objects $s_{ij}$ (with $j = 1$ to $J_{i}$). Consequently, all service objects of a certain service class differ only in their values of the considered NFP. A service composition is a concrete realization of a process (i.e., a set of service objects with exactly one service object for each service class of the process). The used formal notation throughout this work is summarized in Online Appendix 2.

To deal with context information, context-aware (CA) and non-context-aware (NCA) attributes need to be distinguished (cf. also Yu and Reiff-Marganiec 2009b; Xu and Jennings 2010; Lin et al. 2012; Heinrich and Lewerenz 2015). NCA and CA attributes together form the set of NFP $N$ considered in a multi user context-aware service selection problem. Furthermore, we denote the quantified value of an attribute $\propto \in N$ for service object $s_{ij}$ by $q_{ij}^{ \propto }$. The quantified values (e.g., distance) of a CA attribute are dependent on context information and thus on preceding and succeeding service objects. For NCA attributes, this is not the case. We begin with the simpler case of NCA attributes. Initially, we assume that all NCA attributes are independent from each other. Therefore, depending on the quantified values $q_{ij}^{ \propto }$ of the NCA attributes and the user’s individual preferences, a certain service object is more or less favorable for the user compared to another functionally equivalent service object. When more than one attribute is considered in a service selection problem, a common approach to enable the assessment of different service objects is to apply a utility function that aggregates the quantified values $q_{ij}^{ \propto }$ of a service object to a single utility value $U$ (cf., e.g., Zeng et al. 2004; Ardagna and Pernici 2007; García et al. 2008; Alrifai et al. 2012; He et al. 2012; Lin et al. 2012). Here, we adapt the widely used utility function (cf., e.g., Ardagna and Pernici 2007; Alrifai et al. 2012; Jin et al. 2012a; Lin et al. 2012; Guidara et al. 2014) described in detail by Alrifai and Risse (2009), which applies the simple additive weighting (SAW) method: The quantified values of a service object are first normalized to support comparability between different dimensions of the attributes, and afterwards weighted with the user’s individual preferences regarding these attributes (see Alrifai et al. 2012). In this way, the utility value $U_{{a_{ij} }}$ for each service object $s_{ij}$ and each user $a$ can be calculated. The utility value of a certain service object is usually different for each user as each user has his individual preferences.

The overall utility value of all users’ service compositions can then be determined by summing up the utility values $U_{{a_{ij} }}$ of the selected service objects of all users $a \in A$. The binary decision variable $x_{{a_{ij} }}$ indicates whether a certain service object $s_{ij}$ is selected by user $a$ ($x_{{a_{ij} }} = 1$) or not ($x_{{a_{ij} }} = 0$):

$$ \mathop \sum \limits_{a \in A} \mathop \sum \limits_{i = 1}^{I} \mathop \sum \limits_{{s_{ij} \in S_{i} }} U_{{a_{ij} }} x_{{a_{ij} }} $$

(1)

Moreover, a certain service composition for a user is only feasible if it does not violate any constraint. In our case such constraints are, on the one hand, the user’s global constraints $Q_{a}^{ \propto }$ regarding each NCA attribute $\propto$ and, on the other hand, constraints regarding two or more users such as the mandatory simultaneous use of the same service object by the users.

The kind of utility calculation presented in term (1) requires that the utility value $U_{{a_{ij} }}$ can be determined for each service object $s_{ij}$ independently. This means in particular that dependencies between different service objects are not considered here. However, in the case of CA attributes, the quantified value of a service object may depend on other (preceding and succeeding) service objects, which means, it may rely on context information and context dependencies. Examples for CA attributes are distance, price discounts on a certain set of service objects, discomfort with growing travel time and business hours. Similar to NCA attributes, each user also has his own preferences and global end-to-end constraints $Q_{a}^{ \propto }$ for these CA attributes. As the utility value of a service object is determined based on its quantified values, in case of CA attributes, context dependencies between service objects influence their utility values. To enable the determination of the quantified values of CA attributes, we utilize the existing concept of a stateful representation of context dependencies which is introduced in the following paragraph.

4.2 Decomposition Based on Stateful Representation of Context Information

As stated above, our approach for multi user context-aware service selection utilizes the concepts of decomposition and local service selection. Because local selection itself is not able to deal with global NFP constraints, the decomposition of the users’ global NFP constraints into local constraints is needed in order to determine a feasible service composition. Thus, in the following, we discuss how existing approaches cope with single user decomposition and context information in order to form a foundation for our approach.

To decompose global NFP constraints with respect to NCA attributes, existing approaches (e.g., Alrifai et al. 2012; Jin et al. 2012a; Surianarayanan et al. 2015) determine a specific number of quantified NFP values for each service class $i$ and attribute $\propto$ serving as candidates for local constraints. Then a dedicated value (which is further referred to as benefit value²) for each local constraint candidate is calculated based on its potential capability to enable close-to-optimal solutions during local selection. The local NFP constraints are then determined by maximizing the overall benefit value while satisfying the global NFP constraints.

As described above, the determination of the quantified NFP values of CA attributes for a certain service object does not only depend on the service object itself but also requires to take preceding or succeeding service objects of the service composition into account. Thus, considering context information results in context dependencies within one user’s service composition. To cope with CA attributes we use the concept of world states (cf. Ghallab et al. 2004; Heinrich and Schön 2015) which maps the context dependencies onto a state space (i.e., a stateful representation of the dependencies). The basic idea is to model the feasible values of context information for each CA attribute (e.g., time of day, GPS position, etc.), based on the user’s initial context (e.g., time and GPS position at start) and all service objects (e.g., duration and GPS position of corresponding real-world object) in the preceding service classes of the process. Each combination of such feasible values of context information is described by a world state $ws_{ik}$ with $i$ referring to the corresponding service class $S_{i}$ and $k$ as index for the world states in that service class. A world state therefore consists of exactly one state variable for each CA attribute, containing its corresponding value. In this way, the utility of a service object can be determined using the utility function proposed above and with respect to a considered world state (based on its quantified values for all NCA and CA attributes). We denote combinations of world state and service object as world-state-service-object combinations (WSC; for an illustration of the state representation, cf. Online Appendix 3).

Adopting this stateful representation allows to decompose a context-aware service selection problem: For each service class $S_{i}$ a number $\Upsilon$ of suitable local constraint candidates $lcc_{i \propto }^{\varphi }$ (with $\varphi = 1$ to $\Upsilon$) regarding a CA or NCA attribute $\propto$ can be determined based on its quantified values. Subsequently, the benefit value $B\left( {lcc_{i \propto }^{\varphi } } \right)$ for each local constraint candidate can be calculated considering the created state space (for a detailed discussion cf. Alrifai et al. 2012; Lewerenz 2015). By solving the corresponding optimization model, the local NFP constraints $LQ_{{a_{i} }}^{ \propto }$ for each service class $S_{i}$ regarding the attribute $\propto$ are determined. These determined local constraint candidates then form the user’s vector of local NFP constraints $LQ_{{a_{i} }} = \left[ {LQ_{a}^{1} , \ldots ,LQ_{a}^{N} } \right]^{T}$ for each service class $S_{i}$ that can be used in a local selection approach.

Moreover, the consideration of context information makes a temporal coordination of users necessary. This occurs, for instance, when taking a time-dependent availability of service objects (e.g., business hours) into account. Such a temporal coordination is also required when considering the mandatory simultaneous use of one or more service objects by multiple users. While a temporal coordination can be achieved by means of a state variable representing time in each world state, there is also the need to consider possible waiting times: It may be beneficial for a user to wait a certain amount of time, for example, to be able to use a service object which currently is not available but will be a few moments later instead of directly choosing a less favorable service object. In order to consider potential waiting times as well as the loss of utility caused by waiting, Heinrich et al. (2015a) introduce waiting time as additional NFP and special waiting service classes right in front of each regular service class. They further model attributes representing time (i.e., duration, waiting time) as discrete values (i.e., in discrete steps, such that every waiting service class encompasses a defined number of waiting services, each being described by a different specific amount of waiting time). In this way, the utility value of a waiting service can be determined similar to a regular service object.

To illustrate the existing concepts presented above, Fig. 2 contains an excerpt of the running example described in Sect. 2 (focusing on only two users, the actions “Museum”, “Restaurant (FC)” and “Sight”, and the NFP duration, price and business hours). First, waiting actions (actions 0, 2 and 4) are added right before each of the three actions (1) visiting a museum, (3) having lunch at a restaurant and (5) visiting a sight to enable a temporal coordination of the users’ actions. Second, the state space for this service selection problem is created by using the existing concept of a stateful representation of context dependencies. Figure 2 illustrates the state spaces for both users with respect to the Action 3 “Restaurant (FC)”: All world states encompass the context information required for the consideration of the CA attribute business hours (depending on the time of day) where the values are based on the duration of the previous service objects and the initial start time of each user (as part of the user’s initial context). By combining each service object and world state all feasible WSCs of a user for an action are determined.³

Fig. 2

Excerpt of city trip example modeled as stateful representation

5 Heuristic for Multi User Context-Aware Service Selection

In this section, we present our heuristic technique to support a multi user context-aware service system. This technique consists of the two stages Multi User-oriented Decomposition and Local Service Selection.

5.1 Multi User-Oriented Decomposition

In the last section, we described existing concepts, which do not consider any dependencies among different users’ service compositions like resulting from the mandatory simultaneous use of the same service object by multiple users in the Focus Classes (FCs) which also needs to be addressed. Regarding multiple users, we have to consider that each user may have its own set of local NFP constraints, because usually each user has different global constraints and context information (e.g., location or time of day). To address this issue, the decomposition is initially conducted for each user $a$ separately, leading to local NFP constraints $LQ_{{a_{i} }}$ (with $i = 1$ to $I$ representing the different service classes) for each individual user. Second, we need to ensure that the determined local NFP constraints of each user do not violate the mandatory simultaneous use of the same service object in a FC. This happens if the local NFP constraint for an attribute is determined such that at least one user would be excluded from using a service object in the FC in regard to his own context information and local NFP constraints. To avoid this, the local NFP constraints regarding the FC determined for all users must enable the selection of at least one WSC referring to the same service object and context information. To consider these dependencies between different users’ service compositions we define additional restrictions in our decomposition optimization model. For this purpose, we introduce the general concept of common WSCs (ComWSCs) which encompass WSCs from different users referring to the same service object and context information. For each FC the sets of ComWSCs are built based upon the following three criteria:

• (a) All WSCs of a set of ComWSCs refer to the same service object of the FC.

• (b) All WSCs of a set of ComWSCs refer to world states with the same values for each state variable (i.e., each world state encompasses the same context information).

• (c) From each user participating in the mandatory simultaneous use of the FC, exactly one WSC must exist in every set of ComWSCs.

In our example of Fig. 2, $wsc_{31}$ (User 1) and $wsc_{30}$ (User 2) form a set of ComWSCs because they (a) refer to the same service object $s_{30}$ “Sababa”, (b) the context information time of day equals to 11:00 am and (c) the set encompasses one WSC from each user. Precisely, there are two different sets of ComWSCs regarding the FC “Restaurant” due to the two different manifestations of time (10:45, 11:00) and the two restaurants considered in the example: $ComWSC_{0}$ = {($wsc_{31}$, $wsc_{30}$)}⁴ and $ComWSC_{1}$ = {($wsc_{32}$, $wsc_{31}$)}.

Therefore, our decomposition optimization model that allows to determine the local NFP constraints for each user from the set of local constraint candidates $lcc_{i \propto }^{\varphi }$ is formulated as follows:

$$ \mathop {\hbox{max} }\limits_{{x_{i \propto }^{\varphi } }} \mathop \sum \limits_{i = 1}^{I} \mathop \sum \limits_{\varphi = 1}^{\varUpsilon } B\left( {lcc_{i \propto }^{\varphi } } \right)*x_{i \propto }^{\varphi } $$

(2)

$$ {\text{s}} . {\text{t}} .\; \mathop \sum \limits_{i = 1}^{I} \mathop \sum \limits_{\varphi = 1}^{\varUpsilon } lcc_{i \propto }^{\varphi } *x_{i \propto }^{\varphi } \le Q_{a}^{ \propto } $$

(3)

$$ \mathop \sum \limits_{\varphi = 1}^{\varUpsilon } x_{i \propto }^{\varphi } *Z\left( {lcc_{i \propto }^{\varphi } } \right) = 1\quad \forall i \in I_{FC} $$

(4)

$$ \mathop \sum \limits_{\varphi = 1}^{\varUpsilon } x_{i \propto }^{\varphi } = 1\quad \forall i = 1, \ldots ,I\quad {\text{with}}\; x_{i \propto }^{\varphi } \in \left\{ {0,1} \right\} $$

(5)

With each local constraint candidate $lcc_{i \propto }^{\varphi }$ having its individual benefit value $B\left( {lcc_{i \propto }^{\varphi } } \right)$, the aim of the objective function (2) is to maximize the accumulated benefit value over all selected local constraint candidates for a user. Here, $x_{i \propto }^{\varphi }$ are decision variables that indicate whether the corresponding candidate $lcc_{i \propto }^{\varphi }$ is selected as local NFP constraint ($x_{i \propto }^{\varphi } = 1$) or not ($x_{i \propto }^{\varphi } = 0$). Restriction (3) ensures that the sum of the values of all selected candidates $lcc_{i \propto }^{\varphi }$ for the attribute $\propto$ is less than or equal to the user’s global NFP constraint $Q_{a}^{ \propto }$ and thus the global constraints are satisfied.⁵

Restrictions (4) integrate the concept of ComWSC which, as described above, is necessary to guarantee the mandatory simultaneous use of a service object by multiple users: We introduce $I_{FC}$ as the set of the indices of all FCs of the process. Furthermore, we also introduce $Z\left( {lcc_{i \propto }^{\varphi } } \right)$ which equals to 1 if there is at least one set of available ComWSCs when the local constraint candidate $lcc_{i \propto }^{\varphi }$ is chosen as local NFP constraint for FC $i \in I_{FC}$, and equals to 0 otherwise. Multiplied with the binary decision variable $x_{i \propto }^{\varphi }$, these restrictions ensure that only local constraint candidates that allow the selection of at least one ComWSC in the local selection for FC $i \in I_{FC}$ can be chosen. Referring to our illustrative example, the local constraint candidate $lcc_{3 Price }^{1}=$ 10€ has one possible ComWSC ($ComWSC_{0}$). Thus, this local constraint candidate would allow the selection of at least one ComWSC and therefore $Z\left( {lcc_{3 Price }^{1} } \right) = 1$. The last restrictions (5) are used to assure that exactly one local constraint candidate $lcc_{i \propto }^{\varphi }$ is selected for each service class $S_{i}$.

By solving the proposed decomposition optimization model for every user and every global NFP constraint we receive local constraints $LQ_{{a_{i} }}$ for all service classes of the process. These local constraints $LQ_{{a_{i} }}$ are used in our local service selection approach to fulfill the global NFP constraints of each user during selection.

5.2 Local Service Selection

Based on the local NFP constraints from our Multi User-oriented Decomposition, the approach for local service selection can be proposed. The purpose of local service selection is to find both a feasible and close-to-optimal service composition under the consideration of the mandatory simultaneous use of the same service object in the FCs. To achieve this goal, we present our local service selection approach for multiple users and a single FC.

A solution of local service selection encompasses a WSC for each service class and every user. Due to the mandatory simultaneous use of the same service object in the FC, a solution is feasible if – and only if – a WSC which is part of the same set of ComWSCs for the FC is selected for all users. Selecting services for each service class and user independently similar to existing approaches (cf. Jin et al. 2012a; Lewerenz 2015; Surianarayanan et al. 2015) is not promising here. This is due to the fact that the different initial contexts, preferences and local NFP constraints of every user would most likely lead to different optimal world states (as part of the optimal WSC) for the FC and therefore the users would not be temporally and spatially coordinated. Thus, local service selection has to assure that the same context information in conjunction with the same service object for every user is selected with respect to the FC. To achieve this, we introduce our local service selection algorithm consisting of three selection steps: (1) ComWSC selection, (2) backward selection and (3) forward selection. Each step addresses one different part of the process (cf. Fig. 3) and is presented in the following.

Fig. 3

Local service selection for the city trip example

We propose to start with (1) ComWSC selection at the FC as the definition of ComWSCs (cf. Multi User-oriented Decomposition) guarantees the mandatory simultaneous use of the same service object in the FC. This step allows for a successful service selection since the state space of each user ensures that service objects for the remaining preceding resp. succeeding actions can be selected. This is due to the fact that the state space is created based on the initial context of each individual user and therefore only WSCs in the ComWSCs and the succeeding actions exist that can be accessed from the initial context. To determine which ComWSC should be selected, the local selection of our heuristic technique is based on two fundamental criteria:

• (a) Feasibility: Only ComWSCs that fulfill the local NFP constraints of every user can be selected

• (b) Optimality: Selection of the ComWSC that leads to the highest aggregated utility among all users

Regarding our city trip example, the aggregated utility is 0.5 for $ComWSC_{0}$ and 0.425 for $ComWSC_{1}$ (cf. Fig. 2). Since both ComWSCs are feasible, the algorithm selects $ComWSC_{0}$, and thus $wsc_{31}$ for User 1 and $wsc_{30}$ for User 2. To sum up (1), ComWSC selection considers the dependencies between the users at the FC and the local service selection approach can further proceed with a (2) backward selection and (3) forward selection addressing the remaining actions of a process.

(2) Backward selection starts for each user at the WSC selected for the FC. Going backwards and step by step, it determines a WSC for every action until the beginning of the process is reached. To do so, again local selection under the consideration of the feasibility and optimality criteria takes place. Additionally, a path between the WSC to be selected and the previously selected WSC (i.e., a path between the corresponding world states in the user’s state space) needs to exist. In our example, this means that for Action 2 the WSC providing the highest utility which has a path to WSC $wsc_{31}$ (and therefore to world state $ws_{31}$) is selected subject to User 1’s local NFP constraints for this service class. This selection is repeated for all service classes until the beginning of the process is reached and conducted for each user.

Afterwards, (3) forward selection is used to select the remaining WSCs from the FC to the end of the process. The WSCs are selected in the same manner as in (2) backward selection, with the difference that the succeeding WSCs must contain a world state connected to the previously selected WSC. In case of our city trip example, this means that with respect to User 1’s local NFP constraints the WSC with the highest utility in Action 4 and a path to $wsc_{31}$ is selected. Similar to (2) backward selection, this selection is repeated until the end of the process is reached and is conducted for each user.

To sum up, by applying the three selection steps we aim to select a feasible, close-to-optimal WSC for each action of the process and user, and thus a service composition for each user in which all users use the same service object in the FC simultaneously.

Above, we discuss the local service selection for multiple users and a single FC. From a methodical perspective, it is necessary to present two extensions of this approach (cf. Online Appendix 4). First, we have to consider multiple FCs, which is explicated in Online Appendix 4.1. Second, as a core aspect of the heuristic technique, we have to deal with potential local selection failures (i.e., in case local selection cannot find a feasible WSC for a certain action in the first run, for instance, due to context dependencies). To overcome this issue, we include the concept of backtracking in our local service selection approach by identifying the world state responsible for the selection failure and to assure that this world state cannot be selected again. To do so, the world state is put onto a so-called blacklist and an additional feasibility criterion is added to the selection steps, which inhibits the selection of WSCs associated with blacklisted world states. A discussion of the concept of backtracking is shown in Online Appendix 4.2.

6 Evaluation

In this section, we evaluate our heuristic technique regarding solution quality (i.e., providing close-to-optimal solutions) as well as performance and scalability. For this purpose, we compare our method with two exact service selection approaches as well as two heuristic techniques by means of a simulation experiment using real-world data in the tourism domain. Thus, our evaluation design follows the compositional style of simulation- and metric-based benchmarking (cf. Prat et al. 2015). We implemented our heuristic technique in Java and use the mathematical programming solver GUROBI⁶ for solving the optimization models of the decomposition stage. To ensure a correct implementation of our algorithm, we conducted intensive testing of the source code, namely manual code reviews by persons other than the programmers, unit tests, runs with extreme values and plausibility checks. Moreover, we feel confident that our approach provides correct feasible solutions since for 10,000 randomly generated service selection problems (with a maximum problem size of 429,981,696 possible combinations of service objects) each determined heuristic solution was a feasible solution out of the set of all feasible solutions provided by an exhaustive enumeration.

First, we evaluate our heuristic technique (abbreviated with HA) by comparing its results to the results of two exact approaches that were extended to allow the determination of the optimal solution of a multi user context-aware service selection problem. The first exact approach, which we denote by StatefulGO (GO = Global Optimization), is based on an approach proposed by Heinrich and Lewerenz (2015) and uses a stateful representation of context information similar to our approach. It then applies integer programming to solve the corresponding optimization model for single user context-aware service selection problems. The second one, StatelessGO, is derived from Heinrich et al. (2015a) who propose an approach for multi user service selection without considering any context information. In this approach, the existing dependencies among different users are modeled directly within a knapsack optimization model. In order to apply these two exact approaches in our evaluation, we extended them to cope with multi user context-aware processes. With regard to these extensions, we implemented both extensions as fair as possible, taking into account all possible optimizations to reduce their computation time.

Furthermore, we evaluate our technique HA by comparing its results to the results of other potential heuristics for multi user context-aware service selection. Because of the lack of such heuristics in existing literature (cf. Sect. 3), we examine “competing” approaches in two ways: First, we use the criterion TimeLimit⁷ in GUROBI, which can be applied to both exact approaches StatefulGO and StatelessGO by setting their maximum computation time equal to the computation time of HA. However, these approaches were not able to find a feasible solution in the given time, thus this criterion is not applicable to evaluate the proposed heuristic technique (a more detailed discussion can be found in Online Appendix 5). Second, we use the criterion SolutionLimit⁸ in GUROBI in combination with both exact approaches. Here, we set the criterion SolutionLimit to 1, which means that GUROBI is forced to return the first feasible solution found. Regarding the second criterion SolutionLimit, we were able to define two new heuristics StatefulSL and StatelessSL and to analyze and compare the results to the results of HA.

Our evaluation is based on a real-world scenario of the tourism domain. More precisely, several users conduct a day city trip sharing the same process (cf. running example). Here, we consider the NCA attributes duration, waiting time, price and favorite score (an attribute used for modeling user favorites) as well as the CA attributes distance and business hours. Furthermore, we use TripAdvisor⁹ to determine suitable real-world service objects with their NFP values. To take the necessary transport between two succeeding actions into account, we integrate an additional service class representing “transport” before each regular action of the process. In detail, the different services of such a transport service class represent different transport options (walk, bike, car) for the users, each with its corresponding NFP values for duration, price and favorite score. In this way, the process in our evaluation consists of alternating transport and focus service classes with a waiting service class right before each transport or focus service class. Furthermore, each user has his individual initial context and end point. The initial problem size encompasses three users, two FCs with 40 functionally equivalent service objects each, 5 waiting services per waiting service class and 144 transport services per transport service class. For each simulation run, we randomly generate the users’ preferences and constraints as well as their initial context (i.e., time of day, GPS position; the basic evaluation configuration is summarized in Online Appendix 6).

To evaluate our approach, we derive three extended configurations from the basic evaluation configuration where in each configuration only one parameter is changed while all other parameters remain as defined in the basic evaluation configuration (i.e., ceteris paribus). To do so, we stepwise increase the value of each analyzed parameter until the computation time of each of the approaches StatelessGO, StatefulGO, StatelessSL and StatefulSL reaches a limit of 250 s on average (i.e., the upper limit for a parameter such as no. of FCs can be different for each of these approaches). Table 2 illustrates the resulting parameter intervals for the three extended evaluation configurations. Although we cannot compare HA with the four other approaches above their particular upper limit per parameter (cf. Table 2), we continue the stepwise increase of each parameter regarding HA to further analyze its scalability (e.g., we increase no. of users stepwise up to the value 20).

Table 2 Evaluation setup parameters per approach

Our evaluation is two-fold: We analyze solution quality by means of a utility comparison and performance and scalability by means of a comparison of the computation time of HA with StatelessGO, StatefulGO, StatelessSL and StatefulSL. Thereby, each of the settings of the three evaluation configurations is simulated 50 times. We then determine the average utility (U) and computation time (CT) over all simulation runs for each of the five approaches. Computation time is measured in seconds [sec] and, for each run, encompasses state space creation, decomposition and local service selection for HA, state space creation and building/solving the optimization model for StatefulGO and StatefulSL, and building/solving the optimization model for StatelessGO and StatelessSL. All simulation runs are conducted on an Intel Xeon E5-2470 v2 processor with 2.40 GHz, 32 GB RAM, Win7 64bit, Java 1.8, and GUROBI Optimizer 6.5. In order to analyze and compare solution quality as well as performance and scalability, the indicators Quality and Computation Time Percentage (CTP) are used, which are defined as follows:

$$ Quality = \frac{{U_{A} - U_{EXACT}^{min} }}{{U_{EXACT}^{max} - U_{EXACT}^{min} }}\quad CTP = \frac{{CT_{HA} }}{{CT_{A} }} $$

(6)

The indicator Quality is determined by setting the utility $U_{A}$ achieved by HA, StatefulSL and StatelessSL in relation to the maximum utility $U_{EXACT}^{max}$ and the minimum utility $U_{EXACT}^{min}$ determined by an exact approach. Furthermore, to assess performance and scalability we use the indicator CTP which is determined by dividing the computation time $CT_{HA}$ required by HA by the computation time $CT_{A}$ required by any another approach. In the following, we discuss the evaluation results in terms of solution quality, performance and scalability.

Solution quality: As illustrated in the diagrams (a), (c) and (e) of Fig. 4, the proposed heuristic HA reaches an average value of 89.02% of the Quality indicator over all evaluation configurations. This solution quality can be compared to the two other heuristic approaches, which reach an average value of only 81.53% (StatefulSL) and 63.15% (StatelessSL) of the Quality indicator. Moreover, the results show that HA outperforms StatefulSL and StatelessSL not only on average, but also in each single evaluation configuration (1)–(3). Especially for the highly relevant evaluation configuration (2) focusing on a stepwise increase of the number of FCs, HA provides significantly better results compared to both other heuristics. Further, the solution quality offered by our approach is quite constant for all evaluation configurations [cf. Table 3 for the minimum, maximum and average values of the Quality indicator in each evaluation configuration (1)–(3)]. Here, the range between the minimum and maximum value of the Quality indicator is between 3.2 and 6.3% for HA, 10.3 and 18.1% for StatefulSL and 6.9 and 9.5% for StatelessSL (see Table 3). Thus, our heuristic technique seems to be able to provide a high and robust solution quality regarding different problem sizes.

Fig. 4

Evaluation results

Table 3 Values of the quality indicators per evaluation configuration (1)–(3)

In addition, comparable to both heuristics StatefulSL and StatelessSL, HA was nearly always (precisely, in 99.6% of the cases) able to determine a feasible solution (i.e., a feasible service composition). All considered heuristic techniques (HA, StatefulSL and StatelessSL) provide the optimal solution (i.e., a solution with utility equal to the maximum utility $U_{EXACT}^{max}$) only in about 1% of all simulation runs. In case of HA, the obvious reason for this is the local perspective of decomposition and local selection. Consequently, only taking a global perspective (as done by exact approaches) would allow to overcome this issue.

Performance and Scalability: To begin with, the exact approaches StatelessGO and StatefulGO show the expected increase in computation time [cf. diagrams (b), (d) and (f) in Fig. 4] since the service selection problem is known to be NP-hard (Alrifai et al. 2012). For our technique HA, we expect the increase in computation time to be much lower with growing problem size. Indeed, this is supported by our results for all three evaluation configurations: The CTP of HA compared to both StatelessGO and StatefulGO is steadily decreasing (cf. Online Appendix 7) when increasing the number of considered service objects per FC, the number of FCs, and the number of users. For instance, regarding evaluation configuration (1) the CTP is 54.0% (StatelessGO) resp. 7.7% (StatefulGO) for 10 service objects compared to 4.3% (StatelessGO) and 1.8% (StatefulGO) for 70 service objects. This also holds with respect to the heuristic techniques StatelessSL and StatefulSL as HA outperforms both techniques in each simulation run. In addition, although HA, StatefulSL and StatefulGO have in common the computation time required for state creation, HA clearly outperforms StatefulSL and StatefulGO. This indicates that our Multi User-oriented Decomposition in combination with Local Service Selection is performing much better than building and solving an optimization model based on the same state space. Furthermore, based on the evaluation results even for larger problem sizes, HA seems to provide very good scalability (cf. Fig. 4).

7 Conclusion, Limitations and Future Research

In this work, we presented a heuristic service selection technique to support multi user context-aware service systems. More precisely, our approach is able to determine a close-to-optimal service composition for multi user processes under the consideration of the users’ individual preferences and constraints, context information (especially in mobile environments) and the mandatory simultaneous conduction of one or many actions in the processes.

To the best of our knowledge, existing approaches either neglect the support of context information or multiple users. To address this research gap, we developed a technique consisting of two stages: first, Multi User-oriented Decomposition decomposes the users’ global NFP constraints into local NFP constraints to address the mandatory simultaneous use of a service object by several users. In the second stage Local Service Selection (consisting of three steps) a feasible and close-to-optimal service composition for each user is determined. We further extended this procedure by backtracking to take care of possible local selection failures, which, for instance, can be caused by context dependencies.

Besides its scientific contribution, our heuristic approach also provides some important benefits for practice: Due to the NP-hardness of the service selection problem and the high complexity caused by considering multiple users and context information, existing exact approaches may be unable to determine a solution for larger real-world problems in appropriate computation time. Based on findings from our evaluation, we feel confident that our heuristic technique provides good performance and scalability as well as a high solution quality. Thus real-world multi user context-aware processes can be supported by the provided approach which can be used to enable and enhance the contextualization and collaboration within multi user context-aware service systems and processes (cf. Böhmann et al. 2014). This may be of particular relevance to service systems in dynamic domains such as tourism, healthcare or disaster relief assistance, because the respective participants may require quick and helpful support for decision making. In this regard, the rising availability of mobile devices accompanying the omnipresence of context information and services may awaken the request for coordinated, spontaneous and immediate decision support, for instance, in the tourism domain (e.g., day city trips, visiting a restaurant or meetups). Similar developments may hold for service systems of other domains, for instance, in healthcare, roadside assistance or disaster relief management. In these application contexts, the fast coordination of, for example, diverse disaster relief forces (police, emergency doctors or firefighters) is highly valuable as it is more beneficial for certain actions to be conducted together by forces with complementary professional skills. Here, our proposed approach could help to address this demand.

However, our heuristic technique is also subject to some limitations regarding the feasibility and utility of the determined solutions. These limitations are the starting points for further research. The evaluation has shown that our approach is not always capable of finding an existing feasible solution. One reason for this is that the decomposition of global NFP constraints into local NFP constraints cannot fully take into account context dependencies. This can lead to local NFP constraints of a user that are too restrictive or to local NFP constraints resulting in blacklisted WSCs in all available sets of ComWSCs, making the selection of a common service object not possible. To overcome this limitation, further research may focus on enhancing the decomposition stage by learning from the information of previous local service selections. For instance, the information about a local selection failure at a specific action could be used to repeat the stage Multi User-oriented Decomposition with different parameters leading to different local NFP constraints, thus allowing for a new and possibly feasible local service selection. Furthermore, our evaluation has shown that while the proposed heuristic technique is able to achieve a high solution quality, the optimal solution was determined only in about 1% of the evaluated settings. The reason for this is the local perspective of the selection procedure as for each action the service object with the highest utility is selected. Thus, the heuristic technique is vulnerable to finding only local optima. A possible solution to overcome this limitation and to even further increase the solution quality is to integrate probability distributions in local selection and to conduct the stage Local Service Selection multiple times moderated by these distributions. Obviously, this requires a trade-off between computational effort and solution quality.

Moreover, considering multi user context-aware service systems and processes, we also have to discuss that the proposed approach does not cope with uncertain context information (cf., e.g., Heinrich and Schön, 2015) that can occur during the execution of a predetermined service composition. Such uncertain information can result from different causes such as data quality problems (e.g., incorrect or outdated NFP values of a service object), altered preferences or restrictions of one or more users, user failures or even variable external influences (e.g., turning weather or unexpectedly long traffic jams during travel). Some works in the research field of service selection deal with uncertain information by proposing proactive strategies that build on more robust models or rule-based supervision already before the execution of the service composition (cf., e.g., Yu and Lin 2005; Ardagna et al. 2011; Shen et al. 2012b; Heinrich et al. 2015b). Moreover, further research could also consider stochastic approaches, which could overcome local optima and also take into account alternative service compositions to deal with uncertain information. Additionally, exceptional events that occur disruptively during the execution of a service composition still have to be considered. Since starting to reselect the whole service composition in case of a disruptive event usually leads to a waste of resources (time, budget, etc.), many researchers in the field of service systems (e.g., Kuster 2008; Mu et al. 2011) and in particular in service selection (e.g., Ardagna and Pernici 2007; Sandionigi et al. 2013; Liang and Du 2017) suggest to only reselect the remaining part of the service composition in order to promptly enable continuing the execution of the composition. This could also be a promising start for a multi user context-aware service re-selection approach able to consider uncertainties at execution time.

In conclusion, our heuristic technique constitutes a first step to provide support for service systems utilizing multi user context-aware service selection.