With the rising popularity of electric vehicles (EVs), modern service systems, such as ride-hailing delivery services, are increasingly integrating EVs into their operations. Unlike conventional vehicles, EVs often have a shorter driving range, necessitating careful consideration of charging when fulfilling requests. With recent advances in Vehicle-to-Grid (V2G) technology—allowing EVs to also discharge energy back to the grid—new opportunities and complexities emerge. We introduce the Electric Vehicle Orienteering Problem with V2G (EVOP-V2G): a profit-maximisation problem where EV drivers must select a subset of customer requests while managing when and where to charge or discharge. This involves navigating dynamic electricity prices, charging station selection, and route constraints. We formulate the problem as a Mixed Integer Programming (MIP) model and propose two near-optimal metaheuristic algorithms: one evolutionary (EA) and the other based on large neighbourhood search (LNS). We compare these three algorithms with a greedy baseline on real-world data, showing that the proposed methods achieve up to twice the profit. V2G contributes about 20 % of the total profit in the default settings. MIP finds optimal solutions for small cases (30 orders, 3 stations) but does not scale well. EA and LNS give near-optimal results for small cases and handle large ones (900 orders, 70 stations) efficiently. Our work highlights a promising path toward smarter, more profitable EV-based mobility systems that actively support the energy grid.

Electric Vehicles (EVs) are increasingly recognized not only as key assets for sustainable transportation but also as flexible, distributed energy resources. This dual role is enabled by the emergence of Vehicle-to-Everything (V2X) technologies, which allow EVs to bidirectionally charge and discharge energy across various domains, such as the grid, homes, buildings, other vehicles, and mobile devices. As global momentum builds toward decarbonizing both transportation and energy systems, the integration of V2X positions EVs at the intersection of these domains, offering new opportunities to enhance energy efficiency, grid resilience, and environmental sustainability. This tutorial provides a comprehensive introduction to the potential of EVs as both transportation and energy storage solutions, focusing specifically on practical applications and recent advancements in V2X integration. Participants will explore foundational concepts and practical use cases across individual and fleet scenarios, including energy-aware EV routing, smart charging, and coordinated energy management. By bridging transportation and energy domains, the tutorial offers participants insights into leveraging EVs to enhance mobility, resilience, and energy efficiency.

Delays in public transport are common, often impacting users through prolonged travel times and missed transfers. Existing solutions for handling delays remain limited; backup plans based on historical data miss opportunities for earlier arrivals, while snapshot planning accounts for current delays but not future ones. With the growing availability of live delay data, users can adjust their journeys in real-time. However, the literature lacks a framework that fully exploits this advantage for system-scale dynamic replanning. To address this, we formalise the dynamic replanning problem in public transport routing and propose two solutions: a "pull" approach, where users manually request replanning, and a novel "push" approach, where the server proactively monitors and adjusts journeys. Our experiments show that the push approach outperforms the pull approach, achieving significant speedups. The results also reveal substantial arrival time savings enabled by dynamic replanning.

We explore the earliest arrival time problem in public transport journey planning. A journey typically consists of multiple scheduled public transport legs. The actual time required to transfer between these legs can substantially influence route planning. Therefore, we properly model transfers by incorporating their exact costs. We then introduce a novel oracle-based routing algorithm that constructs an efficient transfer database, considering the proposed transfer model. The database is leveraged online to quickly reconstruct the optimal journey in response to an earliest arrival time query. Our experimental results show that neglecting exact transfer costs often lead to either infeasible or suboptimal route plans. Furthermore, the findings highlight the efficiency of our algorithm in handling queries, demonstrated by response times within mere microseconds.

Alternative route planning requires finding$k$alternative paths (including the shortest path) between a given source and target. These paths should be significantly different from each other and meaningful/natural (e.g., must not contain loops or unnecessary detours). While there exists many work on finding high-quality alternative paths, the existing techniques are computationally expensive and are unable to accommodate the high volume of queries required by modern navigation systems. To address this, in this paper, we propose an efficient approach to compute high-quality alternative paths. Our approach employs hub-labeling to efficiently identify candidate alternative paths. The candidate paths are then ranked considering multiple quality metrics and the top-$k$alternative paths are returned. We propose several non-trivial optimizations to significantly improve the computation time. In our experimental study, we conduct experiments on three diverse real-world road networks and compare our proposed algorithm against six state-of-the-art algorithms. The results demonstrate that our algorithm is not only up to 3 orders of magnitude faster compared to most algorithms but also consistently generates alternative paths that are comparable or even superior in terms of quality across various metrics.

Finding shortest paths in a Euclidean plane containing polygonal obstacles is a well-studied problem motivated by a variety of real-world applications. The state-of-the-art algorithms require finding obstacle corners visible to the source and target, and need to consider potentially a large number of candidate paths. This adversely affects their query processing cost. We address these limitations by proposing a novel adaptation of hub labeling which is the state-of-the-art approach for shortest distance computation in road networks. Our experimental study conducted on the widely used benchmark maps shows that our approach is typically 1-2 orders of magnitude faster than two state-of-the-art algorithms.

Video games feature a dynamic environment where locations of objects (e.g., characters, equipment, weapons, vehicles etc.) frequently change within the game world. Although searching for relevant nearby objects in such a dynamic setting is a fundamental operation, this problem has received little research attention. In this paper, we propose a simple lightweight index, called Grid Tree, to store objects and their associated textual data. Our index can be efficiently updated with the underlying updates such as object movements, and supports a variety of object search queries, including k nearest neighbors (returning the k closest objects), keyword k nearest neighbors (returning the k closest objects that satisfy query keywords), and several other variants. Our extensive experimental study, conducted on standard game maps benchmarks and real-world keywords, demonstrates that our approach has up to 2 orders of magnitude faster update times for moving objects compared to state-of-the-art approaches such as navigation mesh and IR-tree. At the same time, query performance of our approach is similar to or better than that of IR-tree and up to two orders of magnitude faster than the other competitor.

In this work, we introduce a set of methodological and visualisation tools to track progress and state-of-the-art performance in the area of Multi-Agent Path Finding (MAPF). Our objectives are to lower the barriers of entry for new researchers and to further promote the study of MAPF.

We consider optimal and anytime algorithms for the Euclidean Shortest Path Problem (ESPP) in two dimensions. Our approach leverages ideas from two recent works: Polyanya, a mesh-based ESPP planner which we use to represent and reason about the environment, and Compressed Path Databases, a speedup technique for pathfinding on grids and spatial networks, which we exploit to compute fast candidate paths. In a range of experiments and empirical comparisons we show that: (i) the auxiliary data structures required by the new method are cheap to build and store; (ii) for optimal search, the new algorithm is faster than a range of recent ESPP planners, with speedups ranging from several factors to over one order of magnitude; (iii) for anytime search, where feasible solutions are needed fast, we report even better runtimes.

Abstract Retrieval of arbitrary-shaped surrounding data objects has many potential applications in spatial databases including nearby arbitrary-shaped object-of-interests retrieval surrounding a user. In this paper, we propose directional zone concept to determine directional similarity among spatial data objects. Then, we propose a novel query, called direction-based spatial skyline (DSS), which retrieves non-dominated arbitrary-shaped surrounding data objects in spatial databases for a user. The proposed DSS query is rotationally invariant as well as fair. We develop efficient algorithms for processing DSS queries in spatial databases by designing novel data pruning techniques using R-Tree data indexing scheme. Finally, we demonstrate the effectiveness and efficiency of our approach by conducting extensive experiments with real datasets.