  Inference and prediction of routes have become of interest over the past
decade owing to a dramatic increase in package delivery and ride-sharing
services. Given the underlying combinatorial structure and the incorporation of
probabilities, route prediction involves techniques from both formal methods
and machine learning. One promising approach for predicting routes uses
decision diagrams that are augmented with probability values. However, the
effectiveness of this approach depends on the size of the compiled decision
diagrams. The scalability of the approach is limited owing to its empirical
runtime and space complexity. In this work, our contributions are two-fold:
first, we introduce a relaxed encoding that uses a linear number of variables
with respect to the number of vertices in a road network graph to significantly
reduce the size of resultant decision diagrams. Secondly, instead of a stepwise
sampling procedure, we propose a single pass sampling-based route prediction.
In our evaluations arising from a real-world road network, we demonstrate that
the resulting system achieves around twice the quality of suggested routes
while being an order of magnitude faster compared to state-of-the-art.
