In the small package shipping industry, companies try to differentiate themselves by providing high levels of customer service. In practice, each service provider is encouraged to follow a master route—a predesigned sequence of street addresses—over an extended planning horizon (more than one day). The objective here is to construct efficient master routes. Currently, a Deterministic Arc-Routing Problem (DARP) model is used to solve the problem. However, this approach ignores the uncertainty in the street segment presence probability—the probability that a street segment requires (i.e., there is a demand for) a visit on a particular day. We have considered a new model, namely, the Probabilistic Arc-Routing Problem (PARP) model which deals with the street segment presence probabilities. PARP attempts to minimize the expected length of the master route. It assumes that the street segment presence probabilities are independent. The limitation of this model is it requires excessive amounts of computation time. Our computational results show that PARP may produce more efficient master routes than DARP by taking demand uncertainty into account.