Transportation Network Companies employ dynamic pricing methods at periods of peak travel to incentivise driver participation and balance supply and demand for rides. Surge pricing multipliers are commonly used and are applied following demand and estimates of customer and driver trip valuations. Combinatorial double auctions have been identified as a suitable alternative, as they can achieve maximum social welfare in the allocation by relying on customers and drivers stating their valuations. A shortcoming of current models, however, is that they fail to account for the effects of trip detours that take place in shared trips and their impact on the accuracy of pricing estimates. To resolve this, we formulate a new shared-ride assignment and pricing algorithm using combinatorial double auctions. We demonstrate that this model is reduced to a maximum weighted independent set model, which is known to be APX-hard. A fast local search heuristic is also presented, which is capable of producing results that lie within 10% of the exact approach for practical implementations. Our proposed algorithm could be used as a fast and reliable assignment and pricing mechanism of ride-sharing requests to vehicles during peak travel times.

The occurrence of congestion has an extremely deleterious impact on the performance of Wireless Sensor Networks (WSNs). This article presents a novel protocol, named COALA (COngestion ALleviation and Avoidance), which aims to act both proactively, in order to avoid the creation of congestion in WSNs, and reactively, so as to mitigate the diffusion of upcoming congestion through alternative path routing. Its operation is based on the utilization of an accumulative cost function, which considers both static and dynamic metrics in order to send data through the paths that are less probable to be congested. COALA is validated through simulation tests, which exhibit its ability to achieve remarkable reduction of loss ratios, transmission delays and energy dissipation. Moreover, the appropriate adjustment of the weighting of the accumulative cost function enables the algorithm to adapt to the performance criteria of individual case scenarios.

The uptake of Electric Vehicles (EVs) is rapidly changing the landscape of urban mobility services. Transportation Network Companies (TNCs) have been following this trend by increasing the number of EVs in their fleets. Recently, major TNCs have explored the prospect of establishing privately owned charging facilities that will enable faster and more economic charging. Given the scale and complexity of TNC operations, such decisions need to consider both the requirements of TNCs and local planning regulations. Therefore, an optimisation approach is presented to model the placement of CSs with the objective of minimising the empty time travelled to the nearest CS for recharging as well as the installation cost. An agent based simulation model has been set in the area of Chicago to derive the recharging spots of the TNC vehicles, and in turn derive the charging demand. A mathematical formulation for the resulting optimisation problem is provided alongside a genetic algorithm that can produce solutions for large problem instances. Our results refer to a representative set of the total data for Chicago and indicate that nearly 180 CSs need to be installed to handle the demand of a TNC fleet of 3000 vehicles.

The problem of pollution control has been mainly studied in the environmental economics literature where the methodology of game theory is applied for the pollution control. To the best of our knowledge this is the first time this problem is studied from the computational point of view. We introduce a new network model for pollution control and present two applications of this model. On a high level, our model comprises a graph whose nodes represent the agents, which can be thought of as the sources of pollution in the network. The edges between agents represent the effect of spread of pollution. The government who is the regulator, is responsible for the maximization of the social welfare and sets bounds on the levels of emitted pollution in both local areas as well as globally in the whole network. We first prove that the above optimization problem is NP-hard even on some special cases of graphs such as trees. We then turn our attention on the classes of trees and planar graphs which model realistic scenarios of the emitted pollution in water and air, respectively. We derive approximation algorithms for these two kinds of networks and provide deterministic truthful and truthful in expectation mechanisms. In some settings of the problem that we study, we achieve the best possible approximation results under standard complexity theoretic assumptions. Our approximation algorithm on planar graphs is obtained by a novel decomposition technique to deal with constraints on vertices. We note that no known planar decomposition techniques can be used here and our technique can be of independent interest. For trees we design a two level dynamic programming approach to obtain an FPTAS. This approach is crucial to deal with the global pollution quota constraint. It uses a special multiple choice, multi-dimensional knapsack problem where coefficients of all constraints except one are bounded by a polynomial of the input size. We furthermore derive truthful in expectation mechanisms on general networks with bounded degree.