Demand-responsive transport (DRT) systems provide flexible transport services for passengers who request door-to-door rides in shared-ride mode without fixed routes and schedules. DRT systems face interesting coordination challenges. For example, one has to design cost-sharing mechanisms for offering fare quotes to potential passengers so that all passengers are treated fairly. The main issue is how the operating costs of the DRT system should be shared among the passengers (given that different passengers cause different amounts of inconvenience to the other passengers), taking into account that DRT systems should provide fare quotes instantaneously without knowing future ride request submissions. We determine properties of cost-sharing mechanisms that make DRT systems attractive to both the transport providers and passengers, namely online fairness, immediate response, individual rationality, budget balance, and ex-post incentive compatibility. We propose a novel cost-sharing mechanism, which is called Proportional Online Cost Sharing (POCS), which provides passengers with upper bounds on their fares immediately after their ride request submissions despite missing knowledge of future ride request submissions, allowing them to accept their fare quotes or drop out. We examine how POCS satisfies these properties in theory and computational experiments.

Grids with blocked and unblocked cells are often used to represent terrain in robotics and video games. However, paths formed by grid edges can be longer than true shortest paths in the terrain since their headings are artificially constrained. We present two new correct and complete any-angle path-planning algorithms that avoid this shortcoming. Basic Theta* and Angle-Propagation Theta* are both variants of A* that propagate information along grid edges without constraining paths to grid edges. Basic Theta* is simple to understand and implement, fast and finds short paths. However, it is not guaranteed to find true shortest paths. Angle-Propagation Theta* achieves a better worst-case complexity per vertex expansion than Basic Theta* by propagating angle ranges when it expands vertices, but is more complex, not as fast and finds slightly longer paths. We refer to Basic Theta* and Angle-Propagation Theta* collectively as Theta*. Theta* has unique properties, which we analyze in detail. We show experimentally that it finds shorter paths than both A* with post-smoothed paths and Field D* (the only other version of A* we know of that propagates information along grid edges without constraining paths to grid edges) with a runtime comparable to that of A* on grids. Finally, we extend Theta* to grids that contain unblocked cells with non-uniform traversal costs and introduce variants of Theta* which provide different tradeoffs between path length and runtime.

We propose a new class of spatio-temporal cluster detection methods designed for the rapid detection of emerging space-time clusters. We focus on the motivating application of prospective disease surveillance: detecting space-time clusters of disease cases resulting from an emerging disease outbreak. Automatic, real-time detection of outbreaks can enable rapid epidemiological response, potentially reducing rates of morbidity and mortality. Building on the prior work on spatial and space-time scan statistics, our methods combine time series analysis (to determine how many cases we expect to observe for a given spatial region in a given time interval) with new "emerging cluster" space-time scan statistics (to decide whether an observed increase in cases in a region is significant), enabling fast and accurate detection of emerging outbreaks. We evaluate these methods on two types of simulated outbreaks: aerosol release of inhalational anthrax (e.g. from a bioterrorist attack) and FLOO ("Fictional Linear Onset Outbreak"), injected into actual baseline data (Emergency Department records and over-the-counter drug sales data from Allegheny County). We demonstrate that our methods are successful in rapidly detecting both outbreak types while keeping the number of false positives low, and show that our new "emerging cluster" scan statistics consistently outperform the standard "persistent cluster" scan statistics approach.