We present a study to assess the feasibility and implications of replacing internal combustion engine vehicles with battery-powered electric vehicles (EVs) in a car-sharing fleet. For the analysis, we used operational data from a local car-sharing company, which encompasses various aspects such as trip distance, start and duration, vehicle type, and pickup and return locations. To evaluate the impact of transitioning the entire fleet to EVs, we used EV and charger models to simulate the battery-powered trips and also the necessary post-trip recharging. Both could affect the service quality of car sharing services, as the requested trip distance might not be covered by an electric vehicle due to range or charging time limitations. Specifically, in our simulation-based analysis, we identified chains of consecutive bookings as a critical factor for car-sharing electrification. Furthermore, to assess the potential impact of electrification on the energy grid, we used data about the local grid load and its composition to relate it to the predicted vehicle charging times.

COMPUTATIONAL sustainability is concerned with the development and application of computational methods for balancing environmental, economic, and societal needs for a sustainable future [1]. Specifically, it considers the major problem domains that impact global sustainability, those technologies and processes that offer the greatest opportunity to increase sustainability in these domains, and the fundamental computational methods that support these technologies and processes. The literature demonstrates that key sustainability issues translate into decision and optimization problems that fall within the realm of computing and information science, but generally they have not been studied by computer scientists. Computational sustainability encompasses problems in disciplines as diverse as ecology, natural resources, atmospheric science, materials science, renewable energy, and biological and environmental engineering. According to the Brundtland Commission [2], sustainable development is development that meets the needs of the present generation without compromising the ability of future generations to meet their own needs. Computational sustainability is a new interdisciplinary field [1] that aims to apply techniques from computer science and related fields, namely information science, operations research, applied mathematics, and statistics, to applications related to sustainable development. The range of problems that fall under computational sustainability is rather wide, encompassing computational challenges in disciplines as diverse as ecology, natural resources, atmospheric science, biological and environmental engineering, and land use, conservation, or transportation planning. Research in computational sustainability is necessarily interdisciplinary. The objective of this special section is to promote awareness and deepen understanding of the critical role computer science and computational methods can play in studying and providing solutions to sustainability-related problems. The special section also aims to provide a resource to the research community that we hope will assist in developing the expertise that society will need to address sustainability challenges by inspiring scientists to pursue sustainability-related research. Finally, this special section showcases a variety of cutting-edge techniques and methods that address the scale and complexity of the challenges facing societal efforts to move towards sustainability. Collaboration between computer scientists and fields more traditionally associated with sustainability-related research provides an opportunity to introduce enhanced or new computational methods and techniques to advance work in numerous disciplines. We hope that this special section will also appeal to those working outside computer science, demonstrating what that discipline has to offer to the broader sustainability agenda. We have selected seven papers to be included in this special section, covering a variety of computational sustainability topics. In “Nationwide Prediction of Drough Conditions in Iran Based on Remote Sensing Data,” Mahdi Jalili, Joobin Gharibshah, Seyed Morsal Ghavami, Mohammadreza Beheshtifar, and Reza Farshi, propose the use of artificial neural networks to model and predict the drough conditions based on satellite imagery collecting indexes on vegetation and land cover as well as the temperature. The paper applies multi-layer neural networks, radial-base function networks and support vector machines to the drough forecasting. The three models have been trained with time series and predict the drough conditions in terms of Standardized Precipitation Index. The accuracy of the model achieves up to the 90 percent and the multi-layer perception model is the best performing predictor. Marco Chiarandini, Niels H. Kjeldsen, and Napoleao Nepomuceno, in their paper entitled “Integrated Planning of Biomass Inventory and Energy Production,” essentially merge two problems that have been traditionally kept separate, namely biomass provisioning and its use for heating or energy production of each power plant. The paper proposes a stochastic 0-1 MILP to model the problem. Due to the large instance size, a relaxation of the problem and a Benders decomposition approach are compared in terms of solution quality, ease of implementation, and scalability, showing good accuracy of the relaxed model, but a simpler implementation and higher scalability for the Benders decomposition approach. Sensing and monitoring of environmental phenomena is an important part of computational sustainability; a promising approach is community sensing, where measurements are gathered by individual agents, and aggregated into publicly available maps by a public authority. In their paper entitled “Incentive Mechanisms for Community Sensing,” Boi Faltings, Jason Jingshi Li, and Radu Jurca, present a novel, game theoretic incentive mechanism that rewards accurate and truthful measurements in a community sensing scenario, providing the necessary quality control, and ensuring that the results are valid despite the absence of a centralized control. The scheme is analyzed and evaluated in a testbed of 88 IEEE TRANSACTIONS ON COMPUTERS, VOL. 63, NO. 1, JANUARY 2014

Traditionally routing has focused on finding shortest paths in networks with positive, static edge costs representing the distance between two nodes. Energy-optimal routing for electric vehicles creates novel algorithmic challenges, as simply understanding edge costs as energy values and applying standard algorithms does not work. First, edge costs can be negative due to recuperation, excluding Dijkstra-like algorithms. Second, edge costs may depend on parameters such as vehicle weight only known at query time, ruling out existing preprocessing techniques. Third, considering battery capacity limitations implies that the cost of a path is no longer just the sum of its edge costs. This paper shows how these challenges can be met within the framework of A* search. We show how the specific domain gives rise to a consistent heuristic function yielding an O(n2) routing algorithm. Moreover, we show how battery constraints can be treated by dynamically adapting edge costs and hence can be handled in the same way as parameters given at query time, without increasing run-time complexity. Experimental results with real road networks and vehicle data demonstrate the advantages of our solution.

The goal of testing is to discriminate between multiple hypotheses about a system - for example, different fault diagnoses - by applying input patterns and verifying or falsifying the hypotheses from the observed outputs. Definitely discriminating tests (DDTs) are those input patterns that are guaranteed to discriminate between different hypotheses of non-deterministic systems. Finding DDTs is important in practice, but can be very expensive. Even more challenging is the problem of finding a DDT that minimizes the cost of the testing process, i.e., an input pattern that can be most cheaply enforced and that is a DDT. This paper addresses both problems. We show how we can transform a given problem into a Boolean structure in decomposable negation normal form (DNNF), and extract from it a Boolean formula whose models correspond to DDTs. This allows us to harness recent advances in both knowledge compilation and satisfiability for efficient and scalable DDT computation in practice. Furthermore, we show how we can generate a DNNF structure compactly encoding all DDTs of the problem and use it to obtain a cost-optimal DDT in time linear in the size of the structure. Experimental results from a real-world application show that our method can compute DDTs in less than 1 second for instances that were previously intractable, and cost-optimal DDTs in less than 20 seconds where previous approaches could not even compute an arbitrary DDT.

Many complex systems today, such as robotic networks, automobiles and automated factories, consist of hardware components whose functionality is extended or controlled by embedded software and which exhibit continuous dynamics. We address the problem of monitoring and control in such systems with a twofold contribution. First, we extend probabilistic hierarchical constraint automata (PHCA), introduced in previous work as a means to compactly describe uncertain hardware and complex software behavior, to hybrid PHCA (HyPHCA). These allow to model continuous behavior in the form of differential equations. Continuous behavior can be conservatively approximated with discrete Markov chains, and in previous work we showed how to transform PHCA monitoring into a constraint optimization problem that can be solved using off-the-shelf reasoners. Our second contribution is to show how to combine these and additional known methods to use a HyPHCA to monitor the internal state and plan for contingencies in a rich class of mixed hardware/software, discrete/continuous systems. Preliminary results of our approach for an industrial filling station scenario demonstrate its feasibility.

Today's complex production systems allow to simultaneously build different products following individual production plans. Such plans may fail due to component faults or unforeseen behavior, resulting in flawed products. In this paper, we propose a method to integrate diagnosis with plan assessment to prevent plan failure, and to gain diagnostic information when needed. In our setting, plans are generated from a planner before being executed on the system. If the underlying system drifts due to component faults or unforeseen behavior, plans that are ready for execution or already being executed are uncertain to succeed or fail. Therefore, our approach tracks plan execution using probabilistic hierarchical constraint automata (PHCA) models of the system. This allows to explain past system behavior, such as observed discrepancies, while at the same time it can be used to predict a plan's remaining chance of success or failure. We propose a formulation of this combined diagnosis/assessment problem as a constraint optimization problem, and present a fast solution algorithm that estimates success or failure probabilities by considering only a limited number k of system trajectories.