We describe a dynamic pricing strategy applicable to ride-sharing scenarios in public transportation services. The strategy incorporates data about relation popularity and price acceptance rates. Crucially, it captures interdependencies between tickets for different relations served by a single vehicle, and thus is able to balance out locally optimal pricing with the expected future evolution of vehicle occupancy state. Based on historical data about a real-world ride-sharing operator, we demonstrate that the proposed method is robust to imperfections in the input data, and estimate it to be more profitable than both fixed-price strategies (even theoretically optimal), and an actual dynamic pricing strategy prescribed by business experts.

We consider vehicle routing problems that occur in practice in the context of long-distance ride-sharing. On the one hand, the instances of our problems share the helpful property that the passengers travel in roughly the same geographical direction. On the other, the required cost function has ordering-dependent components. For two such problems, we provide heuristic algorithms employing a dynamic programming optimization of a sliding window in appropriate linear orders. In the first, exemplary problem, we route a single vehicle. In the second, we route a fleet of vehicles with a coordinated stopover and exchange of passengers. The size of the sliding window allows for trade-offs between solution qualities and processing times. Both algorithms are effective and efficient on data sets representing actual travel requests from Hoper, a commercial ride-sharing service operated by Teroplan S.A. in Poland.

We present a novel parsing algorithm for all context-free languages. The algorithm features a clean mathematical formulation: parsing is expressed as a series of standard operations on regular languages and relations. Parsing complexity w.r.t. input length matches the state of the art: it is worst-case cubic, quadratic for unambiguous grammars, and linear for LR-regular grammars. What distinguishes our approach is that parsing can be implemented using only immutable, acyclic data structures. We also propose a parsing optimization technique called context-free memoization. It allows handling an overwhelming majority of input symbols using a simple stack and a lookup table, similarly to the operation of a deterministic LR(1) parser. This allows our proof-of-concept implementation to outperform the best current implementations of common generalized parsing algorithms (Earley, GLR, and GLL). Tested on a large Java source corpus, parsing is 3–5 times faster, while recognition—35 times faster.

We investigate different variants of unambiguity in the context of computing multi-valued functions. We propose a modification to the standard computation models of Turing machines and configuration graphs, which allows for unambiguity-preserving composition. We define a notion of reductions (based on function composition), which allows nondeterminism but controls its level of ambiguity. In light of this framework we establish reductions between different variants of path counting problems. We obtain improvements of results related to inductive counting.