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.

SAT and propagation solvers often underperform for optimisation models whose objective sums many single-variable terms. MaxSAT solvers avoid this by detecting and exploiting cores: subsets of these terms that cannot collectively take their lower bounds. Previous work has shown manual analysis of cores can help define model reformulations likely to speed up solving for many model instances. This paper presents a method to automate this process. For each selected core the method identifies the instance constraints that caused it; infers the model constraints and parameters that explain how these instance constraints were formed; and learns the conditions that made those model constraint instances generate cores, while others did not. It then uses this information to reformulate the objective. The empirical evaluation shows this method can produce useful reformulations. Importantly, the method can be useful in many other situations that require explaining a set of constraints.

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.

This paper presents a novel algorithm for solving the traffic assignment problem (TAP). Contrary to traditional algorithms, which use the one-to-all shortest path algorithm to solve the problem for all origin destinations (OD) pairs, this algorithm tracks the changes of the edges and (at certain iterations) solves the problem only for critical edges whose flows have changed substantially using a state-of-the-art edge p2p shortest path algorithm. When additionally, only OD pairs with larger flows are considered, this enhancement halves the time needed to optimize the solution with a very small error in a large-scale network.

Decision systems for solving real-world combinatorial problems must be able to report infeasibility in such a way that users can understand the reasons behind it, and understand how to modify the problem to restore feasibility. Current methods mainly focus on reporting one or more subsets of the problem constraints that cause infeasibility. Methods that also show users how to restore feasibility tend to be less flexible and/or problem-dependent. We describe a problem-independent approach to feasibility restoration that combines existing techniques from the literature in novel ways to yield meaningful, useful, practical and flexible user support. We evaluate the resulting framework on two real-world applications.

We consider the design and implementation of a centralised oracle that provides commuters with customised and congestion-aware driving directions. Computing directions for a single journey is straightforward, but doing so at city-scale, in real-time, and under changing conditions is extremely challenging. In this work we describe a new type of centralised oracle which combines fast database-driven path planning with a query management system that distributes work across a small commodity cluster of networked machines. Our system allows large-scale changes to the underlying graph metric, from one query to the next, and it supports a variety of query types including optimal, bounded suboptimal, time-budgeted and k-prefix. Simulated experiments show strong results: we can provide real-time routing for all peak-hour commuter trips in the city of Melbourne, Australia.

This paper presents an advanced transit signal priority (ATSP) control model that considers bus progression at downstream intersections when giving priority at upstream intersections and stochastic bus arrival times. The ATSP control model is applicable to arterials with bus lanes. At the center of the ATSP control model is a stochastic programming model formulated to find the optimum priority strategies at each intersection of interest, which minimize bus delays while having the least negative impact on general traffic. The uncertainty in bus arrivals is taken into account by considering stochastic bus dwell times. The ATSP control is implemented in a traffic micro-simulation environment and compared with conventional transit signal priority (CTSP) control. Extensive simulation experiments are conducted with different traffic congestion levels, bus headway levels, and dwell-time distributions. Results show that the ATSP control generates an additional reduction in bus delay of around 10% when compared to the CTSP control.

Stochastic programming is concerned with decision making under uncertainty, seeking an optimal policy with respect to a set of possible future scenarios. This paper looks at multistage decision problems where the uncertainty is revealed over time. First, decisions are made with respect to all possible future scenarios. Secondly, after observing the random variables, a set of scenario specific decisions is taken. Our goal is to develop algorithms that can be used as a back-end solver for high-level modeling languages. In this paper we propose a scenario decomposition method to solve multistage stochastic combinatorial decision problems recursively. Our approach is applicable to general problem structures, utilizes standard solving technology and is highly parallelizable. We provide experimental results to show how it efficiently solves benchmarks with hundreds of scenarios.

The introduction of smart meters has motivated the electricity industry to manage electrical demand, using dynamic pricing schemes such as real-time pricing. The overall aim of demand management is to minimize electricity generation and distribution costs while meeting the demands and preferences of consumers. However, rapidly scheduling consumption of large groups of households is a challenge. In this paper, we present a highly scalable approach to find the optimal consumption levels for households in an iterative and distributed manner. The complexity of this approach is independent of the number of households, which allows it to be applied to problems with large groups of households. Moreover, the intermediate results of this approach can be used by smart meters to schedule tasks with a simple randomized method.

Constraint programming allows difficult combinatorial problems to be modelled declaratively and solved automatically. Advances in solver technologies over recent years have allowed the successful use of constraint programming in many application areas. However, when a particular solver's search for a solution takes too long, the complexity of the constraint program execution hinders the programmer's ability to profile that search and understand how it relates to their model. Therefore, effective tools to support such profiling and allow users of constraint programming technologies to refine their model or experiment with different search parameters are essential. This paper details the first user-centred design process for visual profiling tools in this domain. We report on: our insights and opportunities identified through an on-line questionnaire and a creativity workshop with domain experts carried out to elicit requirements for analytical and visual profiling techniques; our designs and functional prototypes realising such techniques; and case studies demonstrating how these techniques shed light on the behaviour of the solvers in practice.

Drawings of highly connected (dense) graphs can be very difficult to read. Power Graph Analysis offers an alternate way to draw a graph in which sets of nodes with common neighbours are shown grouped into modules. An edge connected to the module then implies a connection to each member of the module. Thus, the entire graph may be represented with much less clutter and without loss of detail. A recent experimental study has shown that such lossless compression of dense graphs makes it easier to follow paths. However, computing optimal power graphs is difficult. In this paper, we show that computing the optimal power-graph with only one module is NP-hard and therefore likely NP-hard in the general case. We give an ILP model for power graph computation and discuss why ILP and CP techniques are poorly suited to the problem. Instead, we are able to find optimal solutions much more quickly using a custom search method. We also show how to restrict this type of search to allow only limited back-tracking to provide a heuristic that has better speed and better results than previously known heuristics.