Recommending Eco-Friendly Route Plans Efthimios Bothos Dimitris Apostolou Gregoris Mentzas National Technical University University of Piraeus National Technical University of Athens Piraeus, Greece of Athens Athens, Greece dapost@unipi.gr Athens, Greece mpthim@mail.ntua.gr gmentzas@mail.ntua.gr ABSTRACT issue of high importance pertains the development of meth- As personal transportation is one of the greatest contrib- ods and tools able to support and guide citizens towards utors of CO2 emissions, means able to assist travelers in pro-environmental behaviors with respect to their traveling reducing their ecological impact are urgently needed. In habits and decisions. this work we focus on travel recommenders that encourage Previous research has demonstrated that information re- green transportation habits among travelers who have a pre- garding transport-related attributes such as travel time, travel existing interest in taking action to lessen their impact on costs and carbon emissions can lead to changes in citizens’ the environment. We aim to provide urban travelers with travel behavior [3]. Nevertheless, although individuals base a personalized travel recommender that will nudge them to their choices on the attributes of the choice set (content), plan routes while considering the environmentally friendli- the presentation of information (context) has also a strong est travel modes. We present a novel, ecologically-aware effect on travelers’ behavior [4]. The presentation of choices, approach for travel recommender systems and propose a sys- also known as “choice architecture” [17], refers to the design tem architecture that incorporates dimensions of recommen- and incorporation of small features or nudges in the choice dation information elements and profile matching methods. making process, which can assist individuals to overcome cognitive biases by highlighting the better choices for them, without restricting their freedom of choice. Tools available Categories and Subject Descriptors to choice architects can be divided into two categories: those H.3.3 [Information Search and Retrieval]: Information used in structuring the choice task and those used in describ- filtering, Selection process; H.3.4 [Systems and Software]: ing the choice options [9]. Recommender systems can act as User profiles and alert services tools for structuring the choice task and address the prob- lem of what to present to travelers. Furthermore the use of information technologies incorporating feedback and per- General Terms sonalization can be central to make lifestyle or behavioral Design, Human Factors, Algorithms changes [5] and, in our case, can nudge environmentally- responsible behavior. Keywords In this work in progress we focus on recommender sys- tems that encourage lifestyle changes towards green trans- Travel Recommenders, Choice Architecture, Nudging, Per- portation habits among travelers who have a pre-existing suasive Technologies, Lifestyle Change interest in taking action to lessen their impact on the en- vironment. We aim to provide urban travelers with a per- 1. INTRODUCTION sonalized travel recommender that will nudge them to plan Environmental issues are becoming increasingly pressing multi-modal routes while considering the environmentally in our times and means to reduce the ecological impact of friendliest travel modes. We present a novel, ecologically- citizens’ activities are needed urgently. A major source of aware approach for travel recommender systems and pro- environmental pollution from citizens’ activities is carbon pose a system architecture that incorporates dimensions of emissions due to traffic and mobility. It is estimated that recommendation information elements and profile matching urban transport in the European Union accounts for 15% of methods. all greenhouse gas emissions [12]. As work and leisure life Our approach is detailed in Section 2. We synthesize con- become progressively geographically distributed, a research cepts from multi-criteria decision making (MCDM) recom- mender systems and recommendations diversification to in- fuse the ecological dimension on travel recommenders. Namely, we focus on MCDM to infer user preferences and we balance the utility of routes with their carbon footprint in order to generate travel recommendations with ecological character- Paper presented at the Workshop on Recommendation Technologies for istics. In Section 3 we analyze the conceptual architecture Lifestyle Change 2012, in conjunction with the 6th ACM conference on of a system that implements the proposed approach. An il- Recommender Systems. Copyright c 2012 for the individual papers by the papers’ authors. This volume is published and copyrighted by its editors. lustrative scenario depicts the various user interactions with the proposed system in Section 4. We conclude with related Lifestyle @RecSys’12, September 13, 2012, Dublin, Ireland work and future directions. 2. APPROACH Contrary to the vast majority of previous research on rec- ommender systems that has focused on improving the accu- racy of recommendations, i.e. better modeling user pref- erences to present individually preferred items, we focus on recommender systems as a tool for nudging users to- wards eco-friendly traveling decisions. Specifically, the rec- ommender generates a list of suggested routes which reside within the limits of users’ preferences and presents choices with low carbon emissions. With our approach we address the problem of a “filter bubble” [15] in its ecological dimen- sion: users of existing navigation services may be trapped in a self-reinforcing cycle of emission-intensive travel modes Figure 1: Travel profiles as combinations of alter- while never being pushed to discover alternatives. native travel modes and corresponding qualitative The problem an ecologically aware travel recommender CO2 emissions. system is asked to solve can be formulated as follows: Given a user u, find a subset S ⊆ AvailableRoutes(u) such that |S| = P resentedRoutes and the choice of S provides a good balance between the user perceived route utility and CO2 The alternative routes emerge from ‘travel profiles’ [18] emissions. The research agenda of the above problem in- which in our case are defined as the combination of one or cludes two main issues: First what is meant by user per- more of the major transportation modes (personal vehicle, ceived route utility and how this is calculated and second public transportation, walking or bicycle). In total there what is the meaning of the term ‘balance’. Both issues can 3 3 P  be answered in a number of ways. Our approach is based on are k = 7 travel profiles to choose from. Based on the k=1 utility-based recommenders and involves a three-step pro- travel mode characteristics and associated emission models cess: users provide their preferences which are then trans- of each travel profile we can infer that the use of more walk- formed to a user perceived route utility value. In the final ing or bicycle leads to less CO2 emissions (see Figure 1), step, the utility and the CO2 emissions of a route are pro- thus our aim is to nudge users into using travel profiles that vided as input to a recommendation algorithm that selects include walking or bicycle. |S| results to be presented to the user. The alternative routes are annotated with a utility value based on the submitted user preferences. To this direction 2.1 User Preferences Multi-Criteria Decision Making (MCDM), a set of widely Following [18] we adopt a utility based approach to elicit studied methods in the Operations Research domain for de- user preferences. In more details users provide their pref- cision making, can be employed. With MCDM a decision erences over a set of criteria when planing a route. The problem can be seen as the selection of the best alternative revealed preferences are used to infer a user perceived util- from a decision matrix M × N with N alternatives and M ity per route. criteria. More specifically we select Multi-Attribute Utility First users are asked to assign themselves in one of six Theory (MAUT) methods [7] which determine the utility of groups of drivers as identified by [2] - Hard driver, Compla- alternatives from user preferences on selected criteria. These cent car addict, Malcontented motorist, Aspiring environ- methods are based on the concept that bad performing al- mentalist, Car-less crusader, Reluctant rider (for a thorough ternatives on one criterion can be compensated by good per- description of these categories please see [2]). This informa- forming criteria. In our case an alternative is a route with tion is asked only once and affects the level of nudging the criteria Cj . Each criterion has a weight Wj and the ele- user may be inclined to accept (i.e. an Aspiring environmen- ments ai,j in the decision matrix denote the utility U (ci,j ) talist will be presented with more routes that involve public of criterion ci,j . Indicative MCDM models that can be used transportation and walking than a Hard driver). include Weighted Sum and Weighted Product models. Although most navigation applications provide the quick- In Weighted Sum Models a weighted mean over all criteria est routes as suggestions, in real life situations users are dimension for all alternatives is calculated. The result is n concerned with other aspects when deciding on a specific P a utility score per alternative: Ui = aij wj . Weighted trip in a city. For example, the price of the ticket or the fare j=1 (e.g. for a taxi) of the transport mean might influence the Product Models multiply instead of summing up the criteria, user’s decisions [18]. Moreover travelers interested in reduc- and power instead of multiplying the weights in order to ing their carbon footprint may be willing to walk a bit more n w aijj . Q calculate the utility scores: Ui = or accept a longer trip. Based on the above arguments, in j=1 a second step users are asked to provide their preferences on a set of criteria which are then used to calculate a per route utility value. Indicative criteria are: preferred delay 2.3 Recommendation Strategies for arrival, preferred walking or bicycling time and preferred Given a set of candidate routes AvailableRoutes(u) and a travel cost. given threshold K of final desired number of recommenda- tions, the optimal scenario of recommendation is finding a 2.2 Routes and Utility Calculation set of routes, that has the highest perceived utility and the preferences as well as information related to the current con- text. In more details we identify the following information elements: • User preferences provided by the user through a multi- criteria input interface together with the routing query before the trip planning. • User profile configured by the user through an input interface on the first use of the system. • Current context of the user, e.g. trip purpose (busi- ness, leisure, tourism), weather and traffic information. 3.2 Routing engine The routing engine takes as input a set of routing options and generates a set of itineraries. It is controlled by the Rec- Figure 2: Proposed Architecture. ommendation service that manages the options on behalf of the user and adjusts the values based on the user’s profile. Routing options to be supported include route characteris- lowest CO2 emissions. However such an optimal top−K an- tics such as travel modes. The results should include infor- swer set in general does not exist: lowering CO2 emissions mation regarding emission levels, calculated with emission typically does not correlate with the highest utility routes models and the estimated arrival time at the destination. being selected. As a result, we have to achieve a balance be- tween CO2 emissions and route utility. In order to generate 3.3 Recommendation Service lists of suggested eco-friendly routes, recommendation diver- This component comprises of four distinct functions re- sification algorithms can be employed following [23]. The sponsible for personalizing and contextualizing the alter- two problems share similarities: diversification solutions at- native routes to be presented to the user. The first two, tempt to identify relevant yet diversified items whereas we query personalization and contextualization, transform the want to suggest relevant yet eco-friendly routes. user routing query and context signals into the appropriate Two optimal algorithms are the MaxUtil which maximizes routing engine API parameters. Query personalization is de- the utility of the K routes presented and the MinCO2 that pendent on the available transportation means the user has minimizes the CO2 emissions of the K routes. Additional at her disposal i.e. car/motorcycle and bicycle and considers heuristic algorithms are the Swap and Greedy similarly to any disabilities the user may have. Two rules are defined for [20] and [22]. With algorithm Swap we begin with the K these cases: highest utility routes, and swap the route with the high- est emissions with the next highest utility route among the • If the user owns a vehicle then routing results involving remaining routes. A route is swapped only if the overall car/ motorcycle should be considered, similarly if the CO2 emissions of the displayed set is decreased. To prevent user owns a bicycle, routing results involving a bicycle a sudden drop of the overall utility of the resulting set, a should be considered. pre-defined upper-bound U B denoting how much drop in utility is tolerated has to be used. With the use of U B, • If the user has disabilities then bicycle and public means swapping stops when the utility of the resulting routes be- of transportation that do not provide amenities for per- comes lower than U B. Furthermore the value of U B de- sons with disabilities should be avoided. pends on the drivers group the user has assigned herself (see Section 2.1). With algorithm Greedy recommendation lists Query contextualization considers a number of static rules are formed by combining routes from different travel profiles. to further filter the initial set of results: The list with the lowest emissions and acceptable utility is • Weather data: if the day is rainy, then bike and walk- selected. Lists with acceptable utility are those whose differ- ing time should be kept to a minimum. ence with the highest utility list resides within certain limits: HU − Ui ≤ AD where HU is the Highest Utility, Ui is the • Traffic data: if there is indication of high traffic den- utility of list i and AD is the Acceptable Difference which sity, car time should be kept to a minimum. depends on the drivers group the user has assigned herself. • Trip purpose affects the possible delays with respect 3. ARCHITECTURE to the time of arrival. Expected delays should be min- imized for business trips, can be moderately tolerable In this section we describe a system architecture that for leisure trips, and tolerable for tourism trips. shows how our approach can be instantiated and extended to incorporate personal and contextual information. The pro- Based on the aforementioned rules, the user query is aug- posed architecture comprises of the following components: mented and a request is sent to the routing engine for alter- Recommendation information elements, Recommendation ser- native itineraries. vice and Routing engine (see Figure 2). Following query personalization and contextualization, the routing engine is triggered to generate a set of n results per 3.1 Recommendation information elements travel profile given the set of personalization and contex- These elements incorporate the individual user profile and tualization parameters. Once the results are available, two Figure 3: User input: Preferences on the criteria, Figure 4: Recommendation lists as combinations of and relative importance of criteria. travel profiles. Each travel profile is a combination of one or more travel modes (CAR, PT - Public Transport, W/B - Walking or Bicycle). more functions are triggered. The utility calculation func- tion maps the recommendation information elements and the characteristics of the route to a perceived utility value In this scenario we use the Ordered Weighted Averag- per user and route following MCDM methods as described ing (OWA) MCDM method [19]. With OWA the normal- in Section 2.2. This step allows the projection of the user’s ized criteria values aij (numerical values of the poor, fair, decision strategy on the results. The final step refers to the good selections) are multiplied with the corresponding im- generation of recommendations following Section 2.3. portance weights wj (importance percentages). Next, rather than being aggregated, weighted criteria values bij = aij wj for each alternative i are re-ordered by descending value so 4. ILLUSTRATIVE SCENARIO that bi1 > ... > bin . An OWA operator is applied to the In the following we describe an illustrative use case sce- ordered criteria values that can potentially emphasize the nario of our approach. John is about to go out and meet his better or the poorer values. At this preliminary phase of friends at a movie theater and uses his eco-friendly travel this work we opt for the neutral operator [19] which assigns recommender to plan the route. equal weights to each criterion and the final utility scores are calculated as the weighted sum of the criterion values. 4.1 Query Personalization and Contextualiza- tion 4.4 Recommendations The recommendation service interacts with the routing Using algorithm Greedy, as explained in Section 2.3, we engine and retrieves a number of routes to present to John. generate lists of recommended routes by combining results According to the user profile, John owns a car, has no dis- from travel profiles (see Figure 4). The total utility and CO2 abilities and has described himself as a ‘complacent car ad- emissions of each list are calculated as the sum of the utilities dict’. According to the contextual information elements, the and emissions of each element in the list. The ‘Recommen- weather conditions are good, traffic is low and the trip is for dation List 1’ has the highest utility for John. The accept- leisure. A number of results are retrieved from the routing able difference indicates that the recommendation lists one engine per travel profile. to three should be considered and from those, list 2 has the lowest emissions and is presented to John: 4.2 User Preference Elicitation 1. Using only his car, John can reach his destination John is asked to define the poor, fair and good levels of within 30 minutes. each option per criterion (Figure 3.a). Normalized scales are selected for the criteria in order to make the alternatives 2. Using his car to a parking spot near his destination and comparable. Similarly to [16] we employ qualitative scales then walk for 15 minutes, John can reach his destina- which are then transformed to numerical values according tion within 40 minutes but save 20% of CO2 emissions. to the rank order rule for further processing. The numerical mapping is 1 for poor, 2 for fair and 3 for good. 3. Using his car to reach a bus stop close to his home Furthermore John specifies the relative importance of cri- John can reach his destination within 30 minutes and teria on a percent range, with weights summing up to a total save 30% of CO2 emissions. of 100% as shown in Figure 3.b. Changes in one of the slid- ers in Figure 3.b adapt the values of the rest of the criteria John decides to follow option 2 to reach his destination and so as to preserve the total of 100. In order to ease user in- save 20% of CO2 emissions. put we can determine a set of predefined profiles (e.g. in the Figures we see that the ‘Leisure’ preferences profile has the 5. RELATED WORK Delay criterion set to 10-30 minutes and the ‘Importance on Commonly, recommender systems generate prioritized lists Delay’ option assigns higher weight to the ‘Delay’ criterion). of unseen items, e.g., music, books, by trying to predict a user’s preferences based upon their profile. Travel rec- 4.3 Utility Calculation ommender systems are designed to support travel planning decisions before travel or while on-the-move [6]. These sys- menders. Users are presented with route alternatives that tems capture user preferences, either explicitly or implicitly reside within the limits of their preferences and yield re- and suggest destinations to visit, points of interest (POIs), duced carbon emissions. Furthermore we described a system events or activities and/ or alternative routes. The main architecture which combines multi-criteria recommendation objective of a travel recommender system is to ease the in- techniques with profile matching methods. formation search process of the traveler and to convince her There are various aspects that need further research. First, of the appropriateness of the proposed services [10]. the field of MCDM encompasses a number of methods which With respect to route suggestion, certain systems consider could potentially fit into our problem, such as the Analytical multi-modal itineraries (i.e. routes that involve the use of Hierarchy Process and the Linguistic Ordered Weighted Av- more than one transportation means, for example reaching eraging (LOWA). Our plan is to examine the applicability of the destination with a combination of car, bus and walk- these methods as well as compare them. Second, implement- ing). Tumas and Riccie [18] present a personalized mobile ing and comparing the suggested algorithms for striking a city transport advisory system that allows users to receive good balance between routes utility and eco-friendliness will recommendations for personalized paths between two arbi- reveal which are best suited for this problem. Third we trary points in the city of Bolzano on their mobile phone. will investigate combinations of the proposed recommender They specify travel and user profiles which are then utilized with persuasive interfaces for eco-feedback. We expect that to rank different multi-modal routes in the city and present such interfaces, by informing users of their carbon footprint, the top ranked to users. They focus on computing sugges- can persuade them to choose the recommendations with low tions according to users’ travel-related preferences captured environmental impact. Last, we are going to evaluate our through questionnaires and based on four criteria: walking, proposed approach in real life situations. To this direction, a bus changes, time of arrival at the destination and sightsee- prototype system that materializes the approach and related ing. Zenker and Bernd [21] combine event recommendations architecture is under development within the Peacox FP7 and pedestrian navigation with (live) public transport sup- project. In addition two field trials in Vienna and Dublin port in order to assist passengers in finding interesting events have already been planned. In these trials a set of 65 users and navigating to them. will use and evaluate the proposed recommendation service Decision making is a central component in route planing in their everyday life for a total duration of two weeks. applications [8]. In this respect, MCDM techniques have been employed to model combinations of user desires and to 7. ACKNOWLEDGMENTS allow users to specify their personal decision strategies while Research reported in this paper has been partially funded receiving personalized alternatives adjusted to their needs. by the European Commission in the Information Society This view is similar to recent definitions of recommenda- Technologies (IST) project “Ecological aware navigation: us- tion problems as MCDM problems. Multi-criteria based able persuasive trip advisor for reducing CO2 consumption” recommenders provide suggestions by modeling a user’s util- (Contract no.: 63761). ity for an item as a vector of ratings along several criteria. A comprehensive study of recommender systems based on MCDM methods was done in [11]. Other related work in- 8. REFERENCES cludes Nadi and Delavar [14] who study the use of OWA in [1] G. Adomavicius and Y. Kwon. Improving Aggregate a route planning application in order to generate personal- Recommendation Diversity Using Ranking-Based ized routes while considering user specific decision strategies Techniques. in a manner that can provide multiple options regarding the [2] J. Anable. Complacent car addicts or aspiring user’s preferred decision strategies. Additionally Rinner and environmentalists? identifying travel behaviour Raubal [16] proposed a personalized location-based service segments using attitude theory. Transport Policy, using OWA, for finding the most preferable hotel. 12(1):65 – 78, 2005. Diversity in recommender systems is a research stream [3] E. Avineri and O. Waygood. Applying goal framing to that tries to provide solutions beyond improving the rel- enhance the effect of information on transport-related evance of recommendations [13]. Most approaches focus co2 emissions. 9th Biennial Conference on on attribute-based diversification, e.g. in [23], an order- Environmental Psychology, 2011. independent intra-list similarity metric to assess the topi- [4] M. Ben-Akiva and S. Lerman. Discrete Choice cal diversity of recommendation lists and a topic diversifica- Analysis: Theory and Application to Travel Demand. tion approach for decreasing the intra-list similarity is intro- MIT Press, 1985. duced. Recently, explanation based approaches have been [5] P. Eslambolchilar, M. L. Wilson, and A. Komninos. suggested [20]. They rest on the premise that for two differ- Nudge: influence through mobile devices. In ent recommended items i and j, the closer their explanations Proceedings of the 12th international conference on (i.e., the sets of items that are similar to the recommended Human computer interaction with mobile devices and items and that are liked by the user), the more homogeneous services, MobileHCI ’10, pages 527–530, New York, i and j. Last but not least, in [1] a number of recommenda- NY, USA, 2010. ACM. tion ranking techniques for diversity are proposed. [6] D. R. Fesenmaier, H. Werthner, and K. W. Wober. Travel Destination Recommendation Systems: 6. CONCLUSIONS AND FUTURE WORK Behavioural Foundations and Applications (Cabi The environmental problems of our times demand new Publishing). CAB International, 2006. methods and applications able to provide nudges to citi- [7] J. Fülöp. Introduction to Decision Making Methods. zens towards pro-environmental traveling choices. We sug- Technical report, Hungarian Academy of Sciences, gested an approach that infuses nudges in travel recom- 2005. [8] M. J. Geiger and W. Wenger. On the interactive ACM Trans. Intell. Syst. Technol., 2(1):2:1–2:29, Jan. resolution of multi-objective vehicle routing problems. 2011. In Proceedings of the 4th international conference on [23] C.-N. Ziegler, S. M. McNee, J. A. Konstan, and Evolutionary multi-criterion optimization, EMO’07, G. Lausen. Improving recommendation lists through pages 687–699, Berlin, Heidelberg, 2007. topic diversification. In Proceedings of the 14th Springer-Verlag. international conference on World Wide Web, WWW [9] E. J. Johnson, S. B. Shu, B. G. C. Dellaert, C. Fox, ’05, pages 22–32, New York, NY, USA, 2005. ACM. D. G. Goldstein, G. Haubl, R. P. Larrick, J. W. Payne, E. Peters, and D. Schkade. Beyond nudges: Tools of a choice architecture. MARKETING LETTERS, 23(2):487 – 504, 2012. [10] T. Mahmood, F. Ricci, A. Venturini, and W. Hopken. Adaptive recommender systems for travel planning. Strategies, pages 1–11, 2008. [11] N. Manouselis and C. Costopoulou. Analysis and classification of multi-criteria recommender systems. World Wide Web, 10(4):415–441, Dec. 2007. [12] A. D. May, M. Page, and A. Hull. Developing a set of decision-support tools for sustainable urban transport in the uk. Transport Policy, 15(6):328 – 340, 2008. [13] S. M. McNee, J. Riedl, and J. A. Konstan. Being accurate is not enough: how accuracy metrics have hurt recommender systems. In CHI ’06 extended abstracts on Human factors in computing systems, CHI EA ’06, pages 1097–1101, New York, NY, USA, 2006. ACM. [14] S. Nadi and M. R. Delavar. Multi-criteria, personalized route planning using quantifier-guided ordered weighted averaging operators. International Journal of Applied Earth Observation and Geoinformation, 13(3):322–335, 2011. [15] E. Pariser. The Filter Bubble: What the Internet Is Hiding from You. Penguin Press HC, The, May 2011. [16] C. Rinner and M. Raubal. Personalized multi-criteria decision strategies in location-based decision support. Journal of Geographic Information Sciences, 10:149–156, 2004. [17] R. H. Thaler and C. R. Sunstein. Nudge: Improving decisions about health, wealth and happiness. Penguin, London, Mar. 2008. [18] G. Tumas and F. Ricci. Personalized Mobile City Transport Advisory System. In W. Höpken, U. Gretzel, and R. Law, editors, Information and Communication Technologies in Tourism 2009, chapter 15, pages 173–183. Springer Vienna, Vienna, 2009. [19] R. R. Yager. On ordered weighted averaging aggregation operators in multicriteria decisionmaking. IEEE Trans. Syst. Man Cybern., 18(1):183–190, Jan. 1988. [20] C. Yu, L. Lakshmanan, and S. Amer-Yahia. It takes variety to make a world: diversification in recommender systems. In Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, EDBT ’09, pages 368–378, New York, NY, USA, 2009. ACM. [21] B. Zenker and B. Ludwig. Rose - an intelligent mobile assistant - discovering preferred events and finding comfortable transportation links. In ICAART (1), pages 365–370, 2010. [22] Y. Zheng and X. Xie. Learning travel recommendations from user-generated gps traces.