title: Towards A Personal Shopper's Dilemma: Time vs Cost
authors: Samiul Anwar Francesco Lettich Mario A. Nascimento
text: 
  
  ]
  
  Towards A Personal Shopper’s Dilemma: Time vs Cost
  
  
  
  An abridged version of this paper will appear at The 28th ACM SIGSPATIAL Intl Conf. on Advances in Geographic Information Systems 2020 (ACM SIGSPATIAL 2020), Seattle, Washington, USA, November 3-6, 2020.
  
  
  
    University of Alberta, Canada
  
  samiul@ualberta.ca
  
  
  
    Università Ca' Foscari Venezia, Italy
  
  francesco.lettich@gmail.com
  
  
  
    University of Alberta, Canada
  
  mario.nascimento@ualberta.ca
  
  
  
  
  
  
  Consider a customer who needs to fulfill a shopping list, and also a personal shopper who is willing to buy and resell to customers the goods in their shopping lists.  
  It is in the personal shopper's best interest to find (shopping) routes that (i) minimize the time serving a customer, in order to be able to serve more customers, and (ii) minimize the price paid for the goods, in order to maximize his/her potential profit when reselling them. Those are typically competing criteria leading to what we refer to as the Personal Shopper's Dilemma query, i.e., to determine where to buy each of the required goods while attempting to optimize both criteria at the same time. 
  Given the query's NP-hardness we propose a heuristic approach to determine a subset of the sub-optimal routes under any linear combination of the aforementioned criteria, i.e., the query's approximate linear skyline set.
  In order to measure the effectiveness of our approach we also introduce two new metrics, optimality and coverage gaps w.r.t. an optimal, but computationally expensive, baseline solution.
  Our experiments, using realistic city-scale datasets,
  show that our proposed approach is two orders of magnitude faster than the baseline and yields low values for the optimality and coverage gaps.
  
  
  [
      Mario A. Nascimento
      December 30, 2023
  =======================
  
  
  
  
  
  
  
  § INTRODUCTION
  
  
  
  
  Let us consider a customer who needs to acquire some products available in stores within a geographical area, e.g., his/her city's road network. 
  To accomplish this goal the customer submits his/her request to a personal shopper in the form of a shopping list of products, along with their respective quantities.
  
  The personal shopper's task is to serve customers by fulfilling their shopping list. 
  Serving a customer's request entails two different and competing criteria. The first
  criterion is the (shopping) time needed to serve the customer, i.e., the time needed to visit a sequence of stores in order to acquire all products in the customer's shopping list plus the time needed for delivering them to said customer.  The second one is the (shopping) cost of the shopping list, i.e., the sum of the costs of all the products in the shopping list at the stores where they were acquired. 
  Clearly, the shopper's main goal should be to minimize concurrently both criteria;
  the faster he/she can deliver the goods the more customers he/she can serve, and the smaller the actual cost of the goods the higher the profit margins he/she can enjoy.
  The main question the shopper needs to answer then becomes:
  
  
  “Which sequence of stores to visit and which products to acquire in those stores in order to fulfill the customer's shopping list, while, at the same time, minimizing both the shopping time and the shopping list's cost?”
  
  
  Unfortunately, from a practical perspective, it is seldom possible to find a single set of stores that satisfies both criteria. We call this new and practical problem as the Personal Shopper's Dilemma () query. 
  
  At this point one could be tempted to argue that the two considered criteria could be linearly combined into a single one, thus casting into a cost function minimization problem. For instance, though not always desirable, one could express shopping time in terms of monetary cost and then assign appropriate weights to combine both criteria into a single one.  While we use shopping time and shopping cost as the two main criteria one could use, other criteria that could not be expressed in terms of a common unit (e.g., maximize the number of organic and/not locally produced goods, and minimize the customer's waiting time).
  
  There is another, more subtle, limitation to be considered here. Even if a linear combination of the criteria were to be established, appropriate weights would need to be predetermined by the shopper a priori. Thus, any – potentially more interesting – solution for slightly different combinations of weights would not be returned to the shopper by design.  
  To overcome such limitations we let 
  the shopper decide by him/herself how to (linearly) combine both criteria a posteriori.  That is, we aim at computing the set of all optimal sequence of stores for any linear combination of shopping cost and shopping time, also known as linear skyline set (discussed further shortly).
  Notably, the shopper's decisions can be made after running one single query, instead of running one query for each linear combination of the two criteria.
  
  Thus, in hectic periods of the day the shopper may prefer to prioritize more short trips, each with smaller profit, while calmer parts of the day (or changes in traffic patterns) may push the shopper towards longer trips yielding larger profits, or anything in between.
  
  
  
  
  
  
  In order to illustrate the  query, let us introduce a simple instance. Let us suppose that a customer wishes to buy products A, B, C and D and issues the corresponding shopping list to the shopper[For the sake of simplicity and, in the scope of this example only, let us consider that only one unit of each product is required in the shopping list.]. 
  Now, let us suppose that the stores available are those shown in Figure <ref> and they are embedded in a road network not shown for the sake of simplicity. Here, stores are depicted by orange squares (and denoted by s_x), while the customer's delivery location is denoted by lc and the shopper's current location is denoted by ls. Edges between locations represent the fastest paths in the road network connecting them, with labels denoting the associated travel time. Finally, Table <ref> shows the products available in each store, along with their unit prices.
  
  
  
  
  
  
  
  From the above scenario we see that there are multiple solutions that may be of interest for the shopper (Table <ref>). On the one end of the spectrum route R_1 represents the best solution in terms of shopping time, yet its shopping cost is the largest. On the other hand, R_5 offers the lowest shopping cost, but it requires to traverse an expensive route in terms of shopping time. Between these extremes there are several solutions that may interest the shopper, where the notion of “interestingness” depends on the shopper's particular preferences or needs at query time.
  
  
  
  
  When dealing with multiple cost criteria and the problem of determining a set of results that are optimal under any arbitrary combination thereof, a well-known and extensively used tool in the literature are skyline queries <cit.>.
  In general terms, given a set of cost criteria and a pair of objects o_i and o_j, we say that o_j dominates o_i if (i) for each cost criterion the cost of o_j is smaller or equal than that of o_i and (ii) there is at least one criterion for which the cost of o_j is strictly smaller than that of o_i.
  In turn, the set of objects that are non-dominated by any other object defines the notion of skyline, and represents the desired solution. 
  If we represent a skyline on a Cartesian plane, then the skyline represents a frontier beyond which all objects are dominated, i.e., they are not better than those in the frontier.
  
  
  
  
  Computing skyline queries is a computationally intensive task that typically returns many very similar solutions, thus possibly making the choice of a specific solution rather difficult for users.
  To tackle these issues, Shekelyan et al. <cit.> introduced the notion of linear skylines. In general terms, a linear skyline is the subset of the objects defining the convex hull of the (conventional) skyline. Objects belonging to a linear skyline are required to be optimal under any linear combination of the competing cost criteria.  From that, it follows that any solution that is conventionally dominated is also linearly dominated.
  Thanks to this stricter, though still practical, requirement, linear skylines typically contain much less objects than conventional skylines and are thus easier to interpret.  
  Considering the above example, the linear skyline is represented by the set of routes LS = {R_1, R_2, R_5}, depicted with a solid line in Figure <ref>, whereas the dashed line represents the conventional skyline.
  
  Now we can easily observe the shopper's dilemma.   None of the routes R_1, R_2 or R_5 is strictly better than the others, in that each solution creates a different trade-off between shopping time and shopping cost, and that each can be interesting under different circumstances.
  Therefore we target the problem of computing a set of interesting, meaningful, and  diverse shopping routes.
  
  Unfortunately, as formally shown in Section <ref>, even a simplified version of the query, namely one where each store sells a single product and each product is sold at the same price in every store where it is available, is NP-hard. Therefore we propose as our main contribution (in Section <ref>) a heuristic solution that relies on a provably correct pruning framework in order to efficiently
  retrieve a sub-optimal linear skyline.
  We also develop a framework to compare the solutions obtained w.r.t. (costly) optimal ones which we use in our experiments using city-scale realistic datasets (Section <ref>).  Overall we found that our proposed heuristic is robust and able to offer solutions of good quality much faster than the optimal approach.
  
  
  
  
  § PRELIMINARIES
  
  
  
  
  
  
  We assume as underlying framework for the query a city's road network modeled by an undirected
  graph G(V,E,W), where V is a set of vertices that represent road intersections and end-points, E is the set of edges containing all road segments, and W indicates the weight of edges in E. The weight of an edge connecting two vertices v_i and v_j, denoted by w(v_i, v_j) ∈ W, is given by the time needed to traverse the associated road network segment.
  
  There are four main entities within the 's model: stores, customers, shopping lists, and personal shoppers.  
  
  
  
    * A store τ_j is located at a vertex v_τ_j∈ V, and the set of all stores forms a set T.
  Each store sells a specific selection of products. A product has a positive cost, which may differ between stores, and we denote by 
  c(i,τ_j) the cost of a product i at a store τ_j. For simplicity we assume that all stores have an arbitrarily large inventory of all products it sells.
  
  
    * A single customer σ wants to buy a set of products. To this end it issues a request to a personal shopper in the form of a shopping list (described next). 
  We assume the products need to be delivered at the customer's location, which is a vertex in V denoted by v_σ.
  
  
    * λ denotes the shopping list issued by σ and we represent it as a set of pairs 
  ⟨ i, q ⟩ 
  where each i is a product identifier and q represents the number of required units of such product.
  
  
    * Finally, the personal shopper ω is in charge of satisfying a customer's request, i.e., fulfil and deliver the shopping list, and we denote the shopper's location by a vertex v_ω in V. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  The answer of a query is a set of “shopping routes”, each representing a sequence of stores to be visited and yielding a shopping cost (i.e., the monetary cost of acquiring all required products in the visited stores) as well as shopping time (i.e., the time needed to do all needed shopping and deliver the products to the customer). Next, we define such concepts formally.
  
  
  A shopping route θ_i over G is a sequence of stores ⟨τ_1^i, …, τ_n^i ⟩.  
  Furthermore, given a shopping list λ we say that θ_i is feasible w.r.t. λ if
  all products in λ are sold in at least one store in θ_i.
  
  
  
  
  
  Let θ_i represent a feasible shopping route w.r.t. a customer's shopping list λ.
  We define the shopping time associated with θ_i, denoted as ST(θ_i), as the time needed by the shopper to traverse the path that departs from v_ω, visits the stores according to the order defined by θ_i, and finally ends at v_σ, i.e.:
  
  
  
  
      ST(θ_i) = mTT(v_ω, τ_1) + ∑_i=1^n-1mTT(τ_i,τ_i+1) + mTT(τ_n,v_σ)
  
  
  where mTT(v_i, v_j) is the time required by the fastest path
  
  connecting vertices v_i and v_j (though other notions of travel cost could also be used).
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Let λ be the shopping list issued by a customer σ and 
  let θ_i be a feasible shopping route w.r.t. λ.
  Then, we define the shopping cost of θ_i as follows:
  
  
      SC(θ_i) = ∑_⟨ j,q ⟩∈λ (c(j,ss(θ_i, j))× q)
  
  
  where ss(θ_i,j) is a function that returns the store in θ_i from which the product j in λ is to be bought [As discussed in the following Section, such store-product assignment is determined as the solution is obtained.].
  
  
  Note that due to the assumption of arbitrarily large inventories at each store, it is safe to assume that all units of a given product can be acquired at a single store. The case where stores' inventories are limited, and more than one store may be required to fulfil the need for a given product, is left as future work for the time being.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Clearly, there may be different combinations of stores that could interest the shopper, each with its own trade-off between shopping cost and shopping time.  Thus, we propose an approach where the shopper can do his/her own evaluation to choose the one combination that best fits his/her immediate needs/goals. We model such notion of “interestingness”  by leveraging the concept of linear skyline, discussed next.
  
  A linear skyline always represents the subset of some conventional skyline; to distinguish between the two, we start by providing their definitions. Let θ_i be a feasible shopping route.  The two criteria that are being optimized are SC(θ_i) and ST(θ_i), i.e., the cost vector that is being optimized is CV(θ_i) = ⟨ SC(θ_i), ST(θ_i) ⟩.
  
  
  
  be s^i = (s^i_1, s^i_2), with s^i_1 and s^i_2 representing the two cost criteria to minimize. In the context of this work, let us call such vector the compromise vector of S_i, and denote it by CV(S_i) = s^i. Let us then suppose
  that CV(S_i) = (s^i_1 = SC(S_i), s^i_2 = ST(S_i)) – note it is symmetrically possible to define CV(S_i) = (s^i_1 = ST(S_i), s^i_2 = SC(S_i)).
  
  
  
  
  Let θ_i and θ_j be two shopping routes. Then, we say that θ_i conventionally dominates θ_j, denoting by θ_i ≺θ_j, if:
  
  
      ((SC(θ_i) < SC(θ_j) ) 
      (ST(θ_i) ≤ ST(θ_j))) 
       
      ((SC(θ_i) ≤ SC(θ_j)) 
      (ST(θ_i) < ST(θ_j)))
  
  
  
  From this, it follows the definition of conventional skyline.
  
  
  Let Θ be a set of shopping routes. Then, we define the conventional skyline of Θ to be the set of shopping routes that are not conventionally dominated, i.e., {θ_i ∈Θ |  ∄θ_j ∈Θ : θ_j ≺θ_i}.
  
  
  A linear skyline consists of the subset of a conventional skyline that is optimal under all linear combinations of the competing cost criteria <cit.>. Hence, in the scenario considered in this work a linear skyline is composed of combinations of stores that minimize the linear combination 
  ℱ = δ_1 SC(θ_i) + δ_2 ST(θ_i), 
  with δ = (δ_1, δ_2) being a weight vector in ℝ^2_>0.
  
  Note that we find the optimal solution for all such δ, i.e., we do not require any weight vector to be provided beforehand. In the following, we remind the definition of δ-dominance <cit.>, which determines when a combination of stores linearly dominates another one provided a particular δ.
  
  
  A shopping route θ_i is said to δ-dominate another θ_j if and only if δ^T CV(θ_i) < δ^T CV(θ_j).
  
  
  
  From the definition of linear dominance follows the definition of linear skyline <cit.>.
  
  
  
  
  
  Let Θ be a set of shopping routes. Let also Θ' = {θ_1, …, θ_K}⊆Θ. Then, we say that Θ' linearly dominates a shopping route θ∈Θ if and only if:
  
  
      (∃θ' ∈Θ' : θ' ≺θ) 
      (∀δ∈ℝ^2_>0 ∃θ' ∈Θ' : δ^T CV(θ') < δ^T CV(θ) )
  
  
  
  
  
  
  
  
  
  The maximal set of linearly non-dominated combinations of stores is referred to as linear skyline and it can be seen as an ordered set w.r.t. the first cost criteria.
  
  
  Testing the condition on the right hand side of Definition <ref> would require to try out every possible vector δ∈ R^2_>0, which would be computationally impractical. 
  As such, in <cit.> the authors consider the problem from a different perspective, giving it an intuitive geometrical interpretation. More precisely,  the authors observe that a route θ is linearly dominated only if it lies above the segment connecting any pair of shopping routes {θ_q,θ_j} belonging to the linear skyline – this fact is formally denoted by {θ_q,θ_j}≺_LΘ.
  Then they show that it is possible to quickly test whether a route is linearly dominated or not (and thus determine if it can be added to the linear skyline).
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Table <ref> summarizes the main notation used throughout the rest of the paper.
  
  
  
  
  
  
  
  
   §.§ query's NP-hardness
  
  
  
  The query can be shown to be NP-hard by reduction to Trip Planning Queries (TPQs), which are NP-hard <cit.>.
  
  A TPQ instance takes in input a road network G, two vertices v_s and v_e, a set of points-of-interest (POIs) P_i (also vertices in G) each belonging to a single category-of-interest (COIs) C_i, and a set C of COIs. 
  The TP query requires to find a minimum length route in G, from v_s to v_e, and visiting one POI from each COI in C[For instance, it returns the shortest from route from one's office to home visiting a gas station and a supermarket].
   
  Let us now consider the following instance: a road network G', a shopper and a customer located at the vertices v_s' and v_e', respectively, a set of stores T = {T_1, …, T_k}, each selling their own set of products R^T_i,
  
  each at a given price, and finally, a shopping list λ of products.
  The query requires to find the linear skyline of vectors (ST, SC), each representing a route that connects v_s' to v_e' and visits some subset of stores T' ⊆ T, such that all products in λ can be acquired in the stores visited by the route, with ST being the route's shopping (travel) time and SC being the cost of the products acquired from the stores visited by the route to fulfil λ.
  
  Next, we reduce a query into a TPQ one.
  
  Let G' = G, v_s' = v_s, v_e' = v_e, and assume that:
  (1) each store T_i sells exactly one product – this corresponds to R^T_i being a singleton – and (2) each product
  
  in λ is sold, at the same price, in at least one store T_i ∈ T.  Note that, even though it is restricted in scope, this is still a valid instance of the query. 
  Then we map every product into a COI C_i, and consequently each store that sells that product is mapped onto a POI belonging to a single COI. It is then clear that the shopping list λ in the query becomes equivalent to the set C of COIs in TPQ.  
  Given that the same product is sold at the same price regardless of the store, the component SC of the vector solution is constant and the skyline degenerates to a single point minimizing ST, which is equivalent to minimizing the route travel time in TPQ.
  Therefore answering is equivalent, and as computationally complex, as answering a TPQ, thus answering the query is NP-hard.
  
  
  
  The query can be demonstrated to be NP-hard by showing that any instance of a 
  Trip Planning Query (TPQ), a problem known to be NP-hard <cit.>, can be reduced to a PSD one.
  
  Let us suppose to have a road network G, a set C of categories of interest (COIs), and a set of points of interest (POIs) P (also vertices in G), each belonging to some COI c ∈ C.
  Given a starting location v_s, an ending location v_d, and a subset of COIs C' ⊆ C provided by the user, a TPQ requires to compute the route with minimum cost (e.g., travel time) from v_s to v_d that visits exactly one POI from each COI in C'.
  
  In the following we show how we can reduce any TPQ instance to a PSD one. v_s can be trivially mapped to the shopper's location v_ω, while v_d can be trivially mapped to the customer's location v_σ. 
  Next, we map the notion of subset of COIs to visit C' ⊆ C with that of shopping list λ. 
  Each COI c ∈ C in TPQ can be mapped to the notion of a product in PSD, with the POIs within that category representing the stores selling that product.
  Then, any subset C' ⊆ C of COIs to visit can be expressed as a shopping list λ, where we require to buy exactly one unit of each such fictitious products in λ.
  Finally, recall that TPQ requires to compute the route minimizing the considered cost criterion (e.g., travel time), while the PSD query requires to find the set of linearly non-dominated routes w.r.t. shopping cost and shopping time. 
  
  Considering that in TPQ there are no costs associated to POIs, we are free to 
  
  
  impose that all the products have the same cost across all the stores in which they are sold, hence all the shopping routes satisfying λ will have the same shopping cost. Therefore, the linear skyline will be a singleton containing the route with minimum shopping time, i.e., the optimal solution required by TPQ.
  
  
  
  
  
  
  
   §.§ Linear skylines, total order, and efficient insertions
  
  
  
  
  Let ST be the cost criterion used to order the evaluation of shopping routes, let θ^ST be the route yielding minimum shopping time, let LS be the skyline under construction – initially LS = {θ^ST} –, and let θ be a shopping route considered for insertion. 
  Shekelyan et al. <cit.> demonstrate that it suffices to verify whether θ's left neighbor in the skyline, LS_K, i.e., the shopping route being the closest
  to θ w.r.t. to ST, with ST(LS_K) ≤ ST(θ)[This corresponds to the last shopping route inserted into the skyline, or θ^ST in case no route was previously inserted.], conventionally dominates θ. In other words, it suffices to verify whether ST(LS_K) ≤ ST(θ).
  If ST(LS_K) > ST(θ) then θ qualifies for insertion and it is necessary to verify if any route in the skyline becomes dominated due to the insertion of θ.
  First, it is necessary to verify whether ST(LS_K) = ST(θ): if that's the case, LS_K is removed from the skyline as it is conventionally dominated by θ.
  Subsequently, thanks to the order in which linearly non-dominated shopping routes are discovered, it is sufficient to verify whether θ's left neighbor, LS_K, is linearly dominated by LS_K-1 (LS_K's left neighbor) and θ, i.e., verify if {LS_K-1,θ}≺_L LS_K is true, and remove LS_K if this is the case. 
  The procedure is iterated until θ's current left neighbor cannot be removed from the skyline or it represents the first route in the skyline, i.e., the shopping route with shopping time. Considering that linear skylines typically contain few elements, the overall cost of an insertion check can be assumed to be, on average, constant.
  
  
  
   §.§ The query for the case of multiple customers
  
  
  
  A variation of the query as stated so far, is to have a single shopper that can serve several customers.  It can be trivially realized if one is allowed to establish a warehouse. In this case, such a warehouse would effectively serve as a single artificial customer whose shopping list is the union of all actual customers' shopping lists. Observe then that the actual customers would be reached from the warehouse via paths that do not depend on the shopping route chosen by the shopper to fulfill the single (combined) shopping list.  Figure <ref> reuses the scenario discussed in Section <ref> where there are four customers instead of a single one. Note that the road network connecting the warehouse and the customers is not shown, to reinforce that the “delivery” problem is immaterial and orthogonal to the 's routing problem. 
  Finally, one could possibly think of a more complex variant of the query where a shopper has to serve multiple customers 
  without having the possibility to rely on a warehouse. We leave such variant for future work.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § COMPUTING SOLUTION FOR PERSONAL SHOPPER'S DILEMMA QUERY
  
  
  
  
  In this section, we propose two approaches to solve the query. The first one, BSL-, is a baseline capable of computing optimal linear skylines.
  Given some shopping list, the strategy employed by BSL-evaluates in strict increasing order of shopping time shopping routes that fulfill the list, and orchestrate the construction of the skyline accordingly.
  As shown in Section <ref>, computing queries is NP-hard, and thus computing optimal linear skylines becomes unfeasible when the number of stores in a road network or the shopping list size becomes large.
  
  
  
  We thus propose a second approach, APX-(Section <ref>).
  
  The idea behind APX-is to cluster stores spatially and then generate and combine shopping routes from such clusters, rather than from the entire set of stores, to reduce the number of shopping routes to possibly evaluate.
  To this end APX-first superimposes a quad-tree over the stores within the considered geographical area.
  
  
  Then, given a query APX-performs a depth-first search (DFS) of the quad-tree that is driven by a scoring function. Such function directs the search towards the tree leaves that are deemed the most “promising” in terms of shopping time and shopping cost. The generation and expansion of shopping routes are thus conducted within single partitions, rather than on the entire set of stores, to considerably reduce the candidates' search space.  
  
  
  
  
   §.§ A baseline approach: BSL-
  
  
  
  The first approach we propose to solve the query is BSL-, a baseline capable of computing optimal linear skylines. Before delving into its presentation, two important points of discussion concerning the strategy employed by BSL-to compute the linear skyline are: (i) our choice of imposing a total order over the evaluation of shopping routes – from here on shopping routes under evaluation will be called candidate routes – and, (ii) the cost criterion used to define such order.
  For what concerns (i), <cit.> shows that having a total order over the candidates allows efficient insertions while constructing a linear skyline. Indeed, in order to determine if the candidate qualifies for insertion it suffices to verify whether a candidate is conventionally dominated by the last shopping route inserted into the skyline. 
  
  
  
  
  
  
  
  
  
  
  Let us choose one of the two cost criteria as the primary cost. 
  Let us also suppose that it is possible to compute the shopping route yielding the minimum possible value for the primary cost, which in turn establishes an upper bound for the second cost criterion, i.e., shopping routes having the second cost criterion larger than the upper bound are surely dominated by the associated route. 
  Let us finally assume that linearly non-dominated shopping routes are evaluated in increasing order w.r.t. the primary cost criterion. 
  Then, it is sufficient to perform a single conventional domination check to determine if a route qualifies for insertion into the linear skyline.
  
  
  
  
  
  
  
  
  
  For instance, 
  Let ST be the cost criterion used to order the evaluation of shopping routes, let θ^ST be the route yielding minimum shopping time, let LS be the skyline under construction – initially LS = {θ^ST} – and let θ be a shopping route considered for insertion. 
  Shekelyan et al. <cit.> demonstrate that it suffices to verify whether θ's left neighbor in the skyline, LS_K, i.e., the shopping route being the closest
  to θ w.r.t. to ST, with ST(LS_K) ≤ ST(θ)[This corresponds to the last shopping route inserted into the skyline, or θ^ST in case no route was previously inserted.], conventionally dominates θ. In other words, it suffices to verify whether ST(LS_K) ≤ ST(θ).
  If ST(LS_K) > ST(θ) then θ qualifies for insertion and it is necessary to verify if any route in the skyline becomes dominated due to the insertion of θ.
  First, it is necessary to verify whether ST(LS_K) = ST(θ): if that's the case, LS_K is removed from the skyline as it is conventionally dominated by θ.
  Subsequently, thanks to the order in which linearly non-dominated shopping routes are discovered, it is sufficient to verify whether θ's left neighbor, LS_K, is linearly dominated by LS_K-1 (LS_K's left neighbor) and θ, i.e., verify if {LS_K-1,θ}≺_L LS_K is true, and remove LS_K if this is the case. 
  The procedure is iterated until θ's current left neighbor cannot be removed from the skyline or it represents the first route in the skyline, i.e., the shopping route with shopping time. Considering that linear skylines typically contain few elements, the overall cost of an insertion check can be assumed to be, on average, constant.
  
  
  
  
  
  For the moment we assume said total order to be enforced by means of a min-priority queue Q, combined with some suitable generation scheme that progressively extends shopping routes according to the chosen cost criterion, and focuses on which criterion should be used to define the evaluation order. Consider an evaluation strategy that evaluates candidates according to their increasing shopping cost. As it will be shown later on, computing the cost of a shopping route w.r.t. a shopping list can be done in constant time with the use of appropriate data structures. On the other hand, computing a candidate's shopping time always requires to compute the fastest path visiting its stores, i.e., it is necessary to solve an instance of the trip planning query, which is NP-hard. 
  Thus, using shopping time rather than shopping cost allows for an evaluation strategy with greater pruning potential and thus smaller computational costs.
  Now, note that evaluating in increasing order of shopping cost does not take into account the spatial information provided by a query (i.e., shopper's and customer's delivery locations), hence this strategy may end up evaluating shopping routes where the associated fastest paths are long and thus likely being dominated by faster routes. Overall, evaluating in increasing order of shopping time is less penalizing when incurring in dominated candidates, as the cost of computing their shopping cost is negligible.
  
  
  At this point we can start focusing on the baseline's presentation. First, we briefly describe three pre-computed lookup tables BSL-uses to speed up key computations. Subsequently, we introduce the notion of skyline upper bounds, and specify how they are computed and used within the baseline. We then proceed to introduce the set of pruning criteria and the generation scheme the baseline uses to evaluate candidates. Finally, we conclude by formally introducing  BSL-. 
  
  We pre-compute three lookup tables.
  The first table keeps track of the stores where each product is sold, with the list of stores each product is associated with being ordered in increasing order of cost. This is similar to a typical text-based inverted list and allows us to determine in constant time a subset of stores yielding minimum shopping cost for any shopping list λ. 
  The second table stores pairs (product, store), with each pair being associated with the cost of the product at that store. Thus, for any shopping list λ it is possible to compute in constant time if a combination of stores can fulfill it, as well as its shopping cost.
  The third table stores the travel time of the fastest path connecting any pair of stores.
  
  There are two important shopping routes BSL-uses to delimit the candidates' search space, i.e., the one yielding minimum shopping time, θ^ST, and the other yielding minimum shopping cost, θ^SC. The former provides the shopping cost upper bound, SC^U, 
  while the latter provides the shopping time upper bound, ST^U.
   
  Computing θ^SC. Finding out a shopping route with minimum shopping cost requires to find out a subset of stores in T where each product in λ can be bought at minimum cost – this can be done in constant time by using the first pre-computed lookup table.
  Later on we show that during the candidates' evaluation it suffices to find the first shopping route with shopping cost equal to that of θ^SC to terminate the baseline's execution, as subsequent candidates are ensured to be longer (and thus dominated by such route).
  
  Computing θ^ST. To find out the shopping route with minimum shopping time requires to compute a variant of the trip planning query, i.e., it requires to find out the combination of stores that (i) yields the fastest path connecting the shopper's location, the stores, and the customer's delivery location, and (ii) that satisfies λ.
  BSL-generates (and thus evaluates) a combination of stores in increasing order of shopping time. Consequently, the first candidate that fulfills λ always corresponds to θ^ST. We elaborate more on this shortly.
   
  
  BSL-evaluates candidate shopping routes in increasing order of shopping time and constructs the linear skyline accordingly. To do so, it 
  generates shopping routes according to the chosen order, coupled with a set of pruning criteria used to reduce the search space.
  We start by presenting the first pruning criterion, a lemma that allows to update the shopping cost upper bound SC^U as non-dominated routes are progressively inserted into the linear skyline.
  
  
  
  
  Let Q be the min-priority queue used to order the evaluation of shopping routes in strict increasing order of shopping time. Let λ be a shopping list. Let then θ be the last candidate popped from Q: if θ fulfills λ and qualifies for insertion into the linear skyline, then it is possible to set  SC^U = SC(θ).  
  
  
  
   The mechanism used to generate shopping routes in strict increasing order of shopping time ensures that any route θ' popped from Q after θ yields ST(θ') ≥ ST(θ). Then, by virtue of the notion of linear skyline (Definition <ref>) θ' may qualify for insertion only if SC(θ') < SC(θ) = SC^U.
  
  
  
  
  
  
  The above lemma allows to progressively enforce stricter upper bounds on shopping cost, and thus limit the candidates' space as linearly non-dominated solutions are found out.
  Let us now introduce a lemma that allows to early terminate BSL-.
  
  
  
  
  Let θ be the last linearly non-dominated shopping route added to the linear skyline. If SC(θ) = SC(θ^SC) we are guaranteed to have found out all the linearly non-dominated shopping routes and the evaluation can terminate.
  
  
  
  We know that shopping routes are popped from Q in increasing order of shopping time. We also know that θ yields the minimum possible shopping cost. Consequently, any sequence θ' that fulfills λ popped from Q after θ necessarily has ST(θ') ≥ ST(θ) and SC(θ') ≥ SC(θ) = SC(θ^SC), i.e., Definition <ref> ensures that θ' is dominated. 
  
  
  
  In other words, the above lemma guarantees that once a shopping route with minimum shopping cost SC(θ^SC) and that satisfies λ is found, the baseline can  terminate as it is not possible to find further non-dominated routes.
  
  Let us now introduce a slightly modified notation for shopping routes that serves to relate them to the notion of ranked minimum detours. Such notation will be used later on to illustrate the route generation scheme used by the baseline to evaluate candidates in increasing order of shopping time.
  
  
  
  We define a shopping route Θ = ⟨τ_k_1, τ_k_2, …, τ_k_|θ|⟩ to be the route where τ_k_i∈ ST represents the i-th store visited by Θ and that yields the k_i-th minimum detour when added to the fastest path between the store that precedes it in Θ (or the shopper's location v_ω, if i=1) and the customer's delivery location v_σ.
  
  
  
  
  
  [t]
  
  
  
  InputInput
  OutputOutput
  myalg:end
  csrComputeCSR_new
  
  
      Road network G, set of stores T ⊆ V, shopper's current location v_ω, customer's delivery location v_σ, shopping list λ, shopping route yielding minimum shopping cost θ^SC.
      Linear skyline LS.
      
      
      
      
      T ← PruneStores(T, λ) alg:prune stores 
      T ← DijkstraMultipleTarget(v_ω, T ∪{v_σ})  alg:dijkstra shopper 
      T ← DijkstraMultipleTarget(v_σ, T)  alg:dijkstra delivery 
      LS ←∅ alg:init-start 
      SC^U ← + ∞ 
      Q ←{⟨τ_k_1 = 1 = MinDetour(v_ω, v_σ, ∅, T) ⟩} alg:init-end 
      
      Q ≠∅
      alg:while
          θ = ⟨τ_k_1, ⋯, τ_k_|θ|⟩, Q ←Pop(Q) alg:update queue 
          
          
          
              SatisfyList(λ, θ)
              alg:full route insertion
                  SC(θ) < SC^U
                  alg:conventional domination
                      LS ←UpdateLS(LS,θ)alg:update skyline *[r](Observation <ref>)
                      SC^U ← SC(θ)alg:update scu  
                  
  
                  SC^U = SC(θ^SC)
                  alg: early terminate
                      LS
                  
              
              
              θ^s = ⟨τ_k_1, ⋯, τ_k_|θ|⟩⊕MinDetour(τ_k_|θ| , v_σ, θ, T) alg: begin extend sequence 
              
              θ^p = ⟨τ_k_1, ⋯, τ_k_|θ|-1⟩⊕NextMinDetour(τ_k_|θ|-1, v_σ, θ, T)alg: pred extend sequence 
                  
              Q ←Push({θ^s, θ^p}, Q) alg: end extend sequence
      
  
      LS alg:final return
  
  
   BSL-
  
  
  
  Algorithm <ref> presents BSL-, along with the generation scheme used to evaluate shopping routes in strict increasing order of shopping time.
  First, BSL-prunes from T those stores that do not offer any of the products required in λ (line <ref>, function PruneStores). This immediately reduces the candidates' search space.
  Next, BSL-executes two single-source shortest path searches (lines <ref> and <ref>): the first one originates from the shopper's location v_ω and targets the set of stores T as well as the delivery location v_σ. The second one originates from the delivery location v_σ and targets the set of stores T. These searches return the travel times between v_ω and v_σ, and between any pair (v_ω, τ) and (τ, v_σ), with τ∈ T.
  Such travel times are then appropriately combined with those in the lookup table holding the travel times between any pair of stores to support efficient implementations of the functions MinDetour and NextMinDetour (discussed shortly). More specifically, for every store τ∈ T we sum the travel time with any other store τ' ∈ T with that between τ' and v_σ. This yields a list of travel times which, once sorted, allows finding quickly the store yielding the k-th minimum detour when added to the fastest path connecting τ and v_σ.
  
  BSL-then goes on to set the initial state of several entities, namely, that of the linear skyline LS, the shopping time upper bound ST^U, and the priority queue Q, which initially holds the partial shopping route containing the store minimizing the detour w.r.t. the fastest path connecting v_ω and v_σ. 
  Note that such store is found via the function MinDetour, which uses the information  computed previously.
  Subsequently (while cycle, line <ref>),
  BSL-starts generating and evaluating shopping routes in increasing order of shopping time.
  For each candidate θ popped from Q (line <ref>), BSL-first verifies whether θ fulfills λ (line <ref>).
  
  If such condition holds, the baseline goes on to verify whether SC(θ) < SC^U (line <ref>): if this condition does not hold, then θ is conventionally dominated (lemma <ref>) and can be discarded. Otherwise, θ can be inserted into the skyline
  according to the procedure outlined in observation <ref> (function UpdateLS, line <ref>), and SC^U can be tightened (line <ref>, by virtue of lemma <ref>).
  If SC^U = SC(θ^SC) the algorithm immediately terminates (line <ref>), as it is not possible to find further linearly non-dominated shopping routes (by virtue of lemma <ref>).
  
  Lines <ref>–<ref> represent the generation scheme used by BSL-to evaluate shopping routes in increasing order of shopping time, with ⊕ symbolizing the append operation. For each shopping route θ popped from Q the baseline generates two new shopping routes, namely, θ^s and θ^p. θ^s is the shopping route generated by adding a store at the end of θ that (1) does not already appear in θ and that (2) minimizes the detour distance when added to the fastest path between τ_k_|θ| and the delivery location v_σ – such store is found out via the function MinDetour.
  θ^p is the shopping route generated by replacing the last store visited by θ, i.e., τ_k_|θ|, with the store yielding the (k_|θ| + 1)-th minimum detour when added to the fastest path connecting τ_k_|θ| - 1 and v_σ – such store is found out via the function NextMinDetour. Similarly to θ^s, note that we require the store found by NextMinDetour to not already appear in θ. Observe that both θ^s and θ^p have shopping time greater or equal than θ.
  
  
  Finally, we can state two important features regarding BSL-:
  
  
  
  BSL-evaluates all possible shopping routes.  
  
  
  
  We prove it by induction on the size of shopping routes. First we show that the baseline examines every shopping route with |θ|=1. During the initialization phase BSL-initializes the min-priority queue with the shopping route yielding the minimum detour distance between v_ω and v_σ, i.e., θ = ⟨τ_k_1 = 1⟩ (line <ref>). Then, every time some shopping route θ = ⟨τ_k_1⟩ is popped from Q, BSL-generates a shopping route θ^p (line <ref>) where τ_k_1 is replaced with τ_k_1 + 1, i.e., the shop that yields the k_1-th minimum detour between v_ω and v_σ is replaced with the one that yields the (k_1 + 1)-th minimum detour between v_ω and v_σ.
  
  Let us now assume that BSL-generates all the shopping routes of length n. Then, for any route θ = ⟨τ_k_1, …, τ_k_n⟩ we know that the generation scheme generates a route θ^s = ⟨τ_k_1, …, τ_k_n, τ_k_n+1 = 1⟩ (line <ref>), where the store τ_k_n+1 = 1 yields the minimum detour distance when added to the fastest path connecting τ_k_n and v_σ. Then, during subsequent iterations line <ref> guarantees that θ^s allows to generate a whole set of shopping routes of length n+1 where the shop yielding the k_n+1-th minimum detour between k_n and v_σ is replaced with that yielding the (k_n+1 + 1)-th minimum detour.
  
  
  
  
  
  
  
  BSL-evaluates shopping routes in strict increasing order of shopping time. 
  
  
  
  We prove it by contradiction. First, observe that the min-priority queue Q ranks the shopping routes it holds in increasing order of shopping time. Hence, the only event that may violate the theorem's thesis is if a route popped from Q has shopping time smaller than those popped (and thus evaluated) previously. 
  Note, however, that such event is impossible, as the generation scheme used between lines <ref>–<ref> ensures that the shopping routes θ^s and θ^p have shopping time always greater or equal than that of the popped route θ from which they are generated.
  
  
  
  
  
  
  
  
  
  
  
  
    §.§.§ BSL-'s complexity
  
  
  
  BSL-first filters out from T stores that do not offer any product in λ. Thanks to the use of pre-computed lookup tables, the cost of such operation is O(|λ| · |T|).
  Let us now denote by T' ⊆ T the subset of stores that offer at least one product in λ. Let us also denote by N = O(|T'|!) the overall number of candidate shopping routes to possibly evaluate, by S the number of candidate routes θ^s generated at line <ref>, and by P the number of candidate routes θ^p generated at line <ref>, with 1+S+P=N.
  
  The first major operations conducted by BSL-are the two single-source shortest path searches at lines <ref> and <ref>. Both searches have a common component cost of O((|E|+|V|) · log|V|), i.e., the cost inherent to conducting a Dijkstra search. Recall then that the second search is followed by the creation of a set of sorted lists, one per every store τ∈ |T'|, each holding the travel times that result from adding any other store in |T'| in the fastest path connecting τ and v_ω (an information already available in the appropriate lookup table). Thus, creating and sorting such lists has cost O(|T'| · OC), where OC is the sorting algorithm cost. 
  
  
  
   
  Such operations are then followed by the baseline's time-dominant component, represented by the while loop (lines <ref>–<ref>). The cost of executing such component can be expressed as O(Nlog_2N + N2|T'| + S|λ| + |λ|∑_j=1^P|θ^p_j| + N ).
  The first term represents the cost associated with the use of a min-priority queue to order the evaluation of candidates.
  The second term represents the cost of generating two candidate routes from each candidate popped from the queue (i.e., the cost of executing MinDetour and NextMinDetour). By using the aforementioned sorted lists, finding the k-th minimum detour from any store to the delivery location has cost O(|T'|), which in turn yields O(N2|T'|).
  The third term represents the cost of computing the shopping cost of candidates θ^s generated at line <ref> from some candidate θ. Recall that each product in λ shall be bought at the store selling it for the lowest price among those in θ. Hence, computing the shopping cost of a candidate θ^s can be done in O(|λ|) by (1) using the lookup table providing the selling price of any product in any store and (2) by keeping track of the minimum price each product in λ is bought among θ's stores. The fourth term represents the cost of computing the shopping cost of candidates θ^p generated at line <ref>. Recall that such operation requires to replace the last store in some θ with the one yielding the next minimum detour. Now, observe that some of the products in λ may be bought at the store being replaced, hence in the worst case its replacement requires to find out for each product in λ which store among those in θ^p sells it at minimum price.
  Finally, the fifth term represents the cost needed to check if candidate routes qualify for insertion into the linear skyline.
  
  
  
  
  
  
   §.§ An approximated approach: APX-
  
  
  
  The baseline's major drawback lies in its necessity to possibly evaluate a number of shopping routes that is factorial in the number of stores, thus limiting its scalability and applicability to real-world scenarios.
  In order to overcome that, we propose APX-, an approach that trades the optimality of linear skylines for a greatly reduced number of candidates to evaluate.
  The key idea behind APX-is to consider stores at a coarser granularity, i.e., partitions of stores rather than individual stores to generate – and thus evaluate – shopping routes from those partitions, rather than the whole set of stores, that look the most “promising.” 
  
  
  To partition the stores of a road network APX-superimposes a point-region (PR) quad-tree <cit.> 
  over the minimum bounding rectangle (MBR) enclosing the stores. This corresponds to the root quadrant of the quad-tree.
  The PR quad-tree is then constructed by recursively splitting each quadrant having a number of elements (stores) larger than a given capacity threshold in four sub-quadrants. Quadrants that are split during the construction process are the quad-tree intermediate nodes, while unsplit ones make up the leaves. 
  
  
  Given that it relies only on the spatial location of the stores, APX-can pre-compute a quad-tree over the stores of a road-network, along with information concerning travel time between partitions and statistics on the products each quadrant (at any level of the tree) holds. 
  Such statistics are subsequently used to drive the generation and evaluation of candidate routes, i.e., to decide which quadrants are the most promising w.r.t. shopping time and shopping cost.
  
  
  
  We first define the notions of travel time between quadrants and travel time between a vertex and some quadrant, as they are key to the evaluation strategy employed by APX-.
  
  
  
  
  Let Q be a PR quad-tree superimposed over the stores T ⊆ V. Let P_i and P_j be two quadrants of Q.
  
  Then, the travel time between P_i and P_j, denoted by mTT(P_i,P_j), is defined by mTT(τ^i_k, τ^j_l), with τ^i_k∈ P_i,  τ^j_l∈ P_j, and ∄ (τ^i_m, τ^j_n), with τ^i_m∈ P_i, τ^j_n∈ P_j, such that mTT(τ^i_m, τ^j_n) < mTT(τ^i_k, τ^j_l).
  
  
  
  
  
  
  Let Q be a PR quad-tree superimposed over the stores T ⊆ V. Let v ∈ V be some vertex and P ∈ Q be some quadrant. Then, the travel time between v and P_j, denoted by mTT(v, P), is defined by mTT(v, τ^j), with τ^j∈ P, and ∄ (v, τ^j_n), with τ^j_n∈ P_j, such that mTT(v, τ^j_n) < mTT(v, τ^j_l). 
  
  
  
  Observe that Definition <ref> requires to find out the pair of stores, each belonging to one of the considered quadrants, yielding minimum travel time, while Definition <ref> requires to find out the store within a quadrant that minimizes travel time w.r.t. some given vertex.
  Finally note that travel times between partitions can be pre-computed.
  Both definitions allow APX-to enforce upper bounds on shopping time when generating shopping routes from different partitions – to be discussed further shortly.
  
  
  
  
  On top of quadtree we update the boundaries by pushing it inwards in a manner that a partition can give away some stores to to the neighbouring partition. We do this so that every single partition may have more available items. Note that, a partition can give away its store if and only if it does not harm its availability of items. The reconfiguration of stores are done during construction  of the quadtree. At first we generate the minimum bounding rectangle of all the stores. After that we we partition the rectangle by giving partition equal region. Once the partitioning is done, we have list of items available for each partition. Now we try to ensure every partition can have maximum number of items available. We pick a partition and start pushing it's boundaries that are common to a different partition one by one inwards. As a result some stores gets out of that partition. If dropping the stores from the partition does not decrease the availability of items that we keep pushing the boundary until the availability  of items of that partition gets a hit. At this point we have this list of stores that we can drop. However, stores will be assigned to the neighboring partitions, in other words the neighboring partition will gain some region. Adding the new stores may increase the its item availability. However, we do not assign the new configuration right away. We do the same thing for every partition. Now let's suppose two neighboring partition is A and B. If we push A in wards then we get A_1 and B_1 which increases the item availability of B by b but does not change for A. On the other hand if we push the boundary of B inwards then we get A_2 and B_2 increasing item availability of A by a without changing for B. We keep the configuration that provides the maximum gain. Therefore if b>a we keep A_1 and B_1 else we keep A_2 and B_2. We recursively keep partitioning and re-configuring until a partition has maximum n number of stores.
  How do you actually redistribute stores across nearby partitions? Not clear from the text, too generic, you should provide details.
  added some detail in the previous paragraph
  
  
  With a PR quad-tree in place, APX-can then proceed to process queries. Its evaluation strategy relies on a depth-first search (DFS) of the quad-tree driven by a scoring function we introduce below. 
  Given the set of shopping routes under construction (initially empty), such function estimates how “good” each quad-tree quadrant, be it an intermediate node or a leaf, is in terms of shopping time and shopping cost w.r.t. the characteristics of a query and the shopping routes generated so far, thus driving the generation and evaluation of shopping routes towards quadrants that are deemed the “most promising”.
  
  
  
  
  
  Let us consider a shopping list λ, a PR quad-tree Q superimposed over T ⊆ V, and a quadrant P_i ∈ Q (either intermediate node or leaf) that needs to be scored w.r.t. λ.
  Let us assume that P_i must be reached from either the shopper's location v_ω or some other quadrant P ∈ Q.
  Let us further consider that P_i contains m of the products specified in λ; let us denote by λ^P_i the subset of such products, and by λ^P_i_k the average cost of the k-th product within λ^P_i among P_i's stores.
  
  Let us finally denote the minimum travel time needed to depart from v_ω, visit one or more stores in P_i, and finally reach the customer's delivery location v_σ by ST^v_ω_P_i = mTT(v_ω, P_i) + mTT(v_σ, P_i). Analogously, departing from any P ∈ Q yields ST^P_P_i = mTT(P, P_i) + mTT(v_σ, P_i). 
  
  For the sake of simplicity, in this context we denote either v_ω or P by x. Let us finally denote by maxPrice the price of the most expensive product in any store from λ.
  Then, we define the score of P_i w.r.t. x and λ as follows: 
  
  
      
  
  
  We normalize each of the two terms on the right hand side of the equation to give the same importance to shopping time and shopping cost. Specifically, ST^x_P_i is normalized w.r.t. the shopping time upper bound ST^U, while the average cost of each product is normalized w.r.t. the cost of the most expensive product available. 
  Consequently, assuming that m >0 we have ∀(x,λ,P_i), F(v,λ,P_i) ∈ [0,2].
  
  
  Intuitively, the lower the score, the more “promising” a quadrant is. Observe also that the scoring function attempts to balance the importance given to shopping time and shopping cost. We thus expect APX-to generate shopping routes with shopping time and cost having the tendency to distribute more toward the centers of the intervals in the corresponding optimal skyline. 
  
  
  In fact, the experimental results shown in Section <ref> confirm that a scoring function with such a feature makes APX-robust to variations in store and products' price distributions.
  
  
  [htb]
  
  
  
  InputInput
  OutputOutput
  myalg:end
  csrComputeCSR
  
  
      road network G=(V,E), set of stores T ⊆ V, quad-tree Q superimposed over the MBR enclosing the elements in T, shopper's location v_ω, delivery location v_σ, shopping list λ, shopping time upper bound ST^U.
      approximated linear skyline LS.
      
      Q,T ← PruneStores(T, λ) alg:apx_prune stores 
      T ← DijkstraMultipleTarget(v_ω, T ∪{v_σ})  alg:apx_dijkstra shopper 
      T ← DijkstraMultipleTarget(v_σ, T)  alg:apx_dijkstra delivery 
      P ←GetRoot(Q) alg:init-start-APX 
      LS  ← Explore(P, Q, λ, v_σ, ∅, ∅, ST^U)
      apx:exp 
      
      
      
     
      
   
   
  
      LS PSD:Ret
  
  
  APX-PSD
  
  
  
  
  
  
  [htb]
  
  
  
  InputInput
  OutputOutput
  myalg:end
  exExplore
  current partition P, quad-tree superimposed over G, Q, shopping list λ, customer's delivery location v_σ, linear skyline LS, set of partial shopping routes PR, shopping time upper bound ST^U.
  set of partial shopping routes PR (updated), linear skyline LS (updated), shopping list λ (propagated).
     
  λ' ← GetMissingProducts(λ, PR)line: get missing products 
  λ' = ∅
  
      PR, LS, λ
  
  IsLeaf(P,Q)
   line: isleaf
      PR, LS ← ComputePartitionRoutes(λ', P, PR, LS)
      alg:combo1 
   alg:term
   
  alg:leafsearch1
      src ← GetStart(PR)line: getsrc 
      Z = {P_1,P_2,P_3,P_4}← Score (Q, P, λ, src, v_σ, PR, ST^U) 
      Z ≠∅
      
          z ←GetTopScore(Z) 
          PR, LS, λ← Explore(z, Q, λ, LS, PR, ST^U)line: recursive score 
          Z ← Z ∖{z}, src ← GetStart(PR) 
          Z ← ReScore (Q, Z, λ, src, v_σ, PR, ST^U)line: rescore 
      
  
  
  PR, LS, λ 
  
  Explore
  
  
  
  
  
  At this point we are ready to introduce APX-. 
  Algorithms <ref> and <ref> present the pseudo-code behind our approach.
  Algorithm <ref> starts by performing several  preliminary operations. First, it removes from T stores that do not offer any of the products in λ, and updates T and Q accordingly (line <ref>). Next, it performs two single-source shortest path searches at lines <ref>–<ref> that, analogously to those in BSL-, compute the fastest paths between the shopper's and customer's delivery locations and the stores in T. 
  
  The algorithm then initiates to recursively perform a depth-first visit of the quad-tree, with the goal of constructing shopping routes from the tree's leaves that look the “most promising”
  
  and update the linear skyline accordingly.
  Such operations are implemented by the function Explore, invoked at line <ref>. Algorithm <ref> provide the details.
  
  Explore first determines the set of products that cannot be bought from the routes currently stored in PR and stores such set in λ' (line <ref>, function GetMissingProducts).
  Note that if λ' = ∅ then Explore can terminate, as this implies that the depth first search conducted within Q already found out shopping routes that can satisfy λ and inserted them into LS. 
  Explore then verifies if the currently considered quadrant P (initially the quad-tree root) is a leaf or not (line <ref>). 
  If P is a leaf, then the function ComputePartitionRoutes is executed (line <ref>). Such function first counts the number of products in λ' that can be bought from P's stores – let us suppose m products. 
  Subsequently, the function generates the set of (partial) shopping routes from P's stores, where each such route allows to buy exactly those m products (stores that do not offer any of the products in λ' are ignored). 
  ComputePartitionRoutes then goes on to compute the Cartesian product between the set of routes currently stored in PR and that computed from P. The result then becomes the new PR's content. 
  Each route in PR is subsequently checked to verify if its shopping time is above ST^U – in such case the route is removed from PR. Finally, ComputePartitionRoutes verifies if the surviving routes buy all the products in λ (i.e., when λ' = ∅) and, if so, attempts to insert them into LS.
  
  If P is an intermediate node of Q then Explore first proceeds to determine in which partition the routes currently stored in PR terminate and set src accordingly (line <ref>, function GetStart). Then, Explore scores P's four sub-quadrants (line <ref>, function Score) and finally recursively invokes itself by considering such sub-quadrants in ascending order of score (line <ref>). Note that the function ReScore (line <ref>) takes advantage of any update in PR to update the scores of partitions still within Z, and thus better direct the evaluation of candidate routes.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
    §.§.§ APX-'s complexity
  
  
  
  APX-first requires to pre-compute a quadtree, an operation that has cost O(|T|).
  
  The two single-source shortest searches (lines <ref> and <ref>) operate on G=(V,E) and have cost O((|E|+|V|) · log|V|) each.
  
  Let us now focus on the recursive execution of Explore. 
  The cost of such execution is O ((|V^Q| + |E^Q|) + N' + N + N|T'||λ| + NlogN).
  
  The first term is due to the DFS being conducted over Q: if V^Q and E^Q denote, respectively, the nodes and edges in Q, then performing a DFS has cost O(|V^Q| + |E^Q|).
  The second term, N', represents the cost of generating shopping routes from Q's leaves by ComputePartitionRoutes: if L denotes the set of Q's leaves, then N'= ∑_i=1^|L||L_i|!.
  The third term represents the cost of generating (partial) shopping routes by means of the Cartesian products conducted within ComputePartitionRoutes, with N = ∏_i=1^|L||L_i|!.
  The fourth term represents the cost of finding the store, within each of the N shopping routes, from which a product in λ can be bought at minimum price. Finally, the fifth term represents the cost of generating the final linear skyline, i.e., O(NlogN).
  
  
  
  
  
  
  Overall, APX-has to evaluate much less candidate routes (if L denotes the set of Q's leaves, then O(∏_i=1^|L||L_i|!)) than BSL-(O(|T|!)), thanks to the spatial partitioning imposed over the stores and how such partitioning is used to generate and evaluate candidate shopping routes. On the other hand, this limits the evaluation to a restricted subset of candidate routes, which explains APX-'s expected sub-optimality.
  
  
  
  
  
  § EXPERIMENTAL EVALUATION
  
  
  
  
  In order to evaluate the APX-PSD approach, we used datasets containing the road networks and POI locations for Amsterdam, Oslo and Berlin <cit.>. Since those POIs do not include actual stores we used the locations of gas stations and pharmacies (which are typically scattered throughout a city) as proxies for the locations of stores. 
  
  
  Figure <ref> illustrates the store locations in Berlin, Oslo and Amsterdam as used in our experiments. Recall that pharmacies and gas stations were used as proxy for stores, due to (1) the absence of information about real stores in these cities, and (2) it is realistic to assume that pharmacies and gas stations are scattered over a city just like stores would be.
  The total number of vertices, edges and stores for all of the three maps are shown in Table <ref>.
  
  
  
  
  
  
  
  
  
  The parameters considered for the experimental evaluation are: 
  (1) store cardinality (i.e., number of stores in a network),
  (2) distribution of a products' cost in the stores,
  (3) spatial distribution of differently sized stores
  (4) size of shopping lists, and
  (5) capacity of the quad-tree leaves.
  
  
  
  Given that the networks are fixed, varying the store cardinality models the density of stores in a city.
  We also looked into the case when prices increase or decrease w.r.t. the distance of the store to the city's center.
  We considered three different sizes of stores, i.e.,  small, medium and large, according to the percentage of the total number of products they hold, i.e., 25%, 50% and 75%, respectively, out of a total of 1,000 products.
  Note that we chose to not have any store selling all the products to avoid a possibly trivial solution involving a single store.
  Even though stores are by default distributed randomly throughout the network, regardless of their sizes, we also investigated the effect of increasing or decreasing the size of stores according to their proximity to the city's center.
  The values used for each parameter are shown in Table <ref>.
  
  
  
  
  
  
  We attempted to emulate a realistic scenario in terms of the distribution of the cost of products as well as of placement of differently sized stores. 
  
  We thus divide the maps into three concentric rings w.r.t. the city center. The inner, middle and outer rings will host small, medium and large stores, respectively, when the spatial distribution of stores is set to “Increasing”.  Conversely, when that parameter is set to “Decreasing” the inner, middle and outer rings segment will host large, medium and small stores, respectively. 
  
  Similarly, when the product cost distribution parameter is set to “Rising" (Declining) products in stores farther (closer) from the city's center are more expensive. 
  The store closest (farther) to the city centre will sell it at minimum (maximum) price and the one farthest will sell it at the maximum (minimum) price. 
  All the stores in between will sell the product at a price proportional to the distance between those two stores.
  For “Normal” distribution we first find a mean price for each product following a U(5,15) distribution. Once we have the mean price for a product, we assign prices of that product to different stores following a normal distribution with its mean price and a standard deviation of 2.  As discussed in Section <ref>, APX-PSD's evaluation strategy relies on partitions of stores. Thus we observe the effects of the leaf capacity on the APX-by varying the leaf capacity to 4, 8 and 16.
  
  
  
  
  Finally, we test each value each considered parameter  can assume by conducting 100 individual experiments, and report the average optimality gap, coverage gap and processing time. 
  In each experiment we randomly select the shopper's and customer's delivery locations, as well as randomly generate a shopping list of the required size. 
  Furthermore, we randomly select the required number of stores (25 stores in default setting) from those available in the networks. 
  All the experiments were conducted on a virtual machine with an Intel(R)-Xeon(R) CPUs running at 2.30GHz and with 264GB of RAM. 
  
  
  
   §.§ Evaluation metrics
  
  
  We evaluate our APX-by measuring the quality of the results (effectiveness) as well as the efficiency of it. In this section, we discuss the metrics we use to measure such effectiveness and efficiency.
  
  
  
  
    §.§.§ Effectiveness
  
  Comparing an optimal linear skyline (opt-LS) to an approximated one (apx-LS) requires comparing two aspects of skylines: optimality and coverage. 
  For that we propose the two measures presented next.
  
  
  Consider Figure <ref> where opt-LS = {A, B, C, D} and apx-LS = {A', B', C'}. 
  The area given by the polygon OYABCDXO (shaded in green plus orange) represents the area A_opt not dominated by opt-LS, and similarly the polygon OY'A'B'C'X'O (shaded in blue plus the one shaded in green) denotes the area A_apx not dominated by apx-LS. The smaller the difference between A_apx and A_opt the better, but in order to make the right comparison we need to consider only the portion of A_apx that intersects with A_opt, which in the case of this example is given by the polygon OYABCGX'O, which we denote by A_cover.
  Finally, the ratio (A_apx - A_cover)/A_apx  represents the normalized “room for improvement” of the approximated solution. We call this measure the Optimality Gap. 
  
  
  
  
  The optimality gap does not consider part of A_opt that is not “covered” by A_apx, e..g, the orange shaded polygon X'GDXX' in the example and which we denote as A_miss.  This, which we name Coverage Gap, is a consequence of the skyline approximation, i.e., the more points it is missing, the larger such gap. In what follows we compute this (normalized) coverage gap as (A_miss/A_opt) and, like the optimality gap, the smaller it is, the better.
  
  Finally, note that in all the experiments we conducted the optimality and coverage gaps were below 50% and 15% respectively, quantifying that the approximated linear skylines were of good quality.
  As well, the processing time of APX-PSD was always smaller than 1 second and around two orders of magnitude smaller than BSL-PSD's.
  
  
  
  
    §.§.§ Efficiency
  
  
  We evaluate the efficiency of our PSD-by comparing its processing time to the processing time of BSL. The experiments are designed to test whether APX-can provide a good solution in real-time. Even though we can not compare the BSL-and APX-in terms of effectiveness and efficiency for large store cardinality and shopping list size, we can confirm the scalability of APX-reporting the processing time for these extreme cases. 
  
  
  From Sections <ref> and <ref> recall that we assume some information – namely the shortest path between stores and the stores partitioning – is pre-computed offline. 
  We argue that such assumption is reasonable, since stores are seldom added to or removed from networks. Moreover such pre-computation represents a not overly expensive one-time cost.
  
  
  
  
  
  
  Table <ref> shows the time required to pre-compute the shortest path between every pair of stores and also perform the store partitioning. Note that while we have used a typical implementation of Dijkstra's algorithm for shortest paths computation, more efficient alternatives could be used as this is a step completely independent of the approaches being proposed in our work.
  
  
  
  
  
  
   §.§ Effects of store cardinality
  
  
  Figure <ref> shows that the optimality gap increases when increasing the store cardinality, while the coverage gap decreases.  
  We explain such behaviour by observing how quad-trees as well as the scoring function react to changes in store cardinality. 
  When store cardinality increases, the number of stores in each quad-tree leaf increases accordingly. 
  Since product costs are distributed uniformly in the default case, adding more stores smooths the average cost of each product in different partitions, which in turn reduces the impact of product costs in APX-'s scoring function. 
  Therefore, the linear skyline will include routes with higher costs, which will decrease the coverage gap. Consequently, APX-has to visit more leaves to complete the shopping list. Furthermore, with larger store cardinality BSL-generates shopping routes with lower shopping time that APX-fails to find, thus increasing the optimality gap.
  
  
   
  
  
  
  
  Figure <ref> shows that BSL-'s processing time increases when store cardinality increases, mainly due to an increased number of stores (and thus potential candidates) to consider.
  On the other hand, APX-'s processing time exhibits small changes. Recall that the leaves' capacity in a quad-tree is fixed, thus increasing the store cardinality increases the tree's depth.
  Notice that, we varied the parameter upto 500 stores for Berlin but only up to 200 stores and 100 stores for Oslo and Amsterdam respectively. We could not test Amsterdam or Oslo with larger store cardinality due to the limitation of the datasets respectively, 
  
  Recall that APX-'s time-dominant component deals with shopping routes generation and evaluation, rather than tree traversal, which explains the small impact on performance. 
  
  
  
  
  
  
  
  
   §.§ Effects of product cost distribution
  
  
  
  In Figure <ref> we can see that the “Declining” and “Rising” cases have comparable optimality gaps and higher coverage gaps to the “Normal” one. We argue that these results are due to the characteristics of the scoring function used by APX-which, we recall, attempts to balance the importance given to shopping time and shopping cost. 
  Since the product cost gradually decreases towards one direction for both “Declining" and “Rising", the scoring function manages to minimize cost better than “Normal" distribution. However, the optimality gap created due to creating partial routes from a leaf at a time remains comparable to the “Normal" distribution.
  
  Interestingly, both the optimality gap and coverage gap are the highest for Oslo in all of the cases, which we attribute to the skewed distribution of stores compared to the other cities (Figure <ref>). 
  
  
   
  
  
  
  
  Figure <ref> shows that BSL-'s processing time using Berlin's network is larger for the “Declining” and “Rising” cases than for the “Uniform” one. 
  In those two cases the low-cost products are distributed in certain areas of the map, and thus it is more likely to take longer to find routes with lower shopping costs if the shopper's and customer's delivery locations are far from those regions. Note that such differences are further amplified by Berlin's large network size.
  However, APX-'s processing time is not affected since it takes great advantage of pre-computed aggregated paths as it traverses the quad-tree hosting the store partitions.
  
  
  
  
  
  
   §.§ Effects of store size spatial distribution
  
  
  In Figure <ref> we can see that the “Decreasing” and “Increasing” cases have comparable coverage and optimality gaps to the “Random” one. These results can be explained by taking into account the characteristics of APX-'s scoring function, which makes it insensitive to different distributions of store sizes (apart from the effects that can be observed on the shape of both optimal and approximated skylines).
   
  
  BSL-'s processing time (Figure <ref>) is higher when dealing with the “Decreasing” and“Increasing” cases. Since the locations of larger stores are concentrated in certain areas, BSL-takes longer to generate routes with minimum cost and terminate (depending on the shopper's and customer's delivery locations), an effect that is further compounded by the city's network size. As usual, Berlin exhibits the largest processing time for the same reason observed with varying cost distributions. Finally note that APX-PSD's processing time remains unaffected.
  
  
   
  
  
  
  
  
  
   §.§ Effects of shopping list size
  
  
  The optimality (coverage) gap increases (decreases) with the shopping list size as evidenced in Figure <ref>.  Larger shopping lists require more traversals of the network.  Recall that by construction, shopping routes are appended to existing partial routes.  Such appending means that previous not-so-good choices remain and their effect are further compounded by new potentially not-so-good choices as the algorithm evolves, worsening the approximation.
  As a result both the shopping time and cost increase which increases the optimality gap and decreases the coverage gap.
  
  
  BSL-'s processing time (Figure <ref>) increases when increasing the shopping list size. This can be explained by observing that, on average, large shopping lists require more stores per route to be satisfied, and thus likely require to evaluate more candidate routes. 
  On the other hand APX-is mildly affected by such increase, thanks to the noticeably smaller number of candidates it generates and evaluates by design.
  
   
  
  
  
  
  
  
  
  
  
  
   §.§ Effects of quad-tree leaf capacity
  
  
  From the results shown in Figure <ref> we see that the optimality and coverage gaps decrease (i.e., the overall result quality increases) as the leaf capacity increases. This can be explained by observing that leaves containing more stores allow APX-to generate and evaluate more partial shopping routes, thus allowing to discover shopping routes with increasingly lower costs (and thus closer to the ones computed by the baseline). 
  
  Finally, Figure <ref> shows that APX-'s efficiency decreases as the leaf capacity increases, due to the increased number of partial shopping routes that APX-generates and evaluates from the leaves it visits – indeed, from APX-'s complexity analysis (Sec. <ref>) recall that this represents the time-dominant component of this approach.
  
  
  
   
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § RELATED WORK
  
  
  
  To the extent of our knowledge there is no prior work in the literature that address the problem as presented here.  Nonetheless, in the following we discuss some works which are somehow related.
  
  
  One can think of of an extension of the well-known Optimal Sequence Routing (OSR) <cit.> and Trip Planning Queries (TPQs) <cit.>.
  
  An OSR query <cit.> specifies a sequence of categories-of-interest (COIs) and returns the optimal route that visits exactly one point-of-interest (POI) from each COI in the exact sequence provided in the query. 
  
  Trip Plannng Queries (TPQs) <cit.> are similar to OSR queries where the strict sequence of COIs is relaxed.
  
  
  Unfortunately, solutions to TPQs and OSR queries are not applicable to queries, particularly because queries consider two competing cost criteria, whereas in both TPQs and ORS queries only travel cost (distance) is considered.
  
  
  
  
  
  
  The problem of finding the set of routes that are optimal under a given combination of cost criteria has also been researched the skyline paradigm, e.g., <cit.>), however none of those works have a notion similar to fulfilling a shopping list while building a route, as in the query, but merely aim at finding routes.
  
  
  
  
  
  
  In the context of our work the literature targeting bicriteria networks <cit.> is particularly relevant.  
  
  
  
  
  
  
  
  
  
  Linear skylines were employed in various instances of bicriteria networks <cit.>, each requiring to devise a specific solution addressing the peculiarities of the associated problem setting, which, again, are all different from 's query.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Finally, in <cit.> the authors introduced the problem of computing TASeR queries. Each TASeR query requires to visit a sequence of categories of interest (COI) provided by the user (i.e., an optimal sequenced route query <cit.>) with the additional constraints that (1) each POI in a COI yields a non-null cost and that (2) the user wishes to minimize the travel distance as well as the total cost of POIs he/she needs to stop by. The common trait between TASeR and queries lies in the need to return a result set that provides various choices to the user and, at the same time, is easy to interpret from the user's perception, thus calling for the use of linear skylines. Unlike TASeR queries, however, computing queries requires to evaluate combinations of stores rather than sequences of COIs, and the cost of visiting a POI (i.e., a store in the context of this work) is determined by the requirements imposed by a shopping list.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § CONCLUSION
  
  
  
  
  In this paper we proposed a solution to what we called the “Personal Shopper's Dilemma” query, which is to decide on how to fulfil a customer's shopping list while minimizing travel time as well as shopping cost.  The idea is to leave the shopper to decide, “on the fly” how to prioritize these two criteria.  Given the query's NP-hardness we proposed a heuristic solution that leverages on the concept of linear skyline queries.  In order to measure the effectiveness of the proposed heuristic we also proposed a metric to evaluate its loss w.r.t. an optimal solution.  Using real city-scale datasets we show that our proposal is able to deliver good linear skylines yielding optimality and coverage gaps below 50% and 15% respectively
  two orders of magnitude faster than the optimal solution.  
  
  A direction for future work w.r.t. the query itself would be allowing a shopper to find routes to serve multiple customers, possibly in different locations, and/or have multiple shoppers that could, for instance, bid on shopping lists of different customers after considering their perspective on those two criteria. 
  
  
  
  
  § ACKNOWLEDGMENTS
  
  
  Research partially supported by NSERC Canada.  F. Lettich started this work while  at the Univ. of Alberta.
  
  unsrt
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  