Exact route evaluation for node edge and arc routing problems with stochastic customers

Arc routing problems arise in applications such as postal delivery services or waste collection where the density of service points is high, and the direction of edge traversal is relevant (Assad and Golden, 1995). We consider a general arc routing setting where the presence of nodes, edges and arcs of the network is stochastic according to a known probability. This feature is known as stochastic customers in the vehicle routing literature (Lagos et al., 2019). While considerable research has been devoted to the arc routing problem with stochastic demands, research about stochastic customers is rather scarce (De Maio et al., 2021).
Evaluating the expected travel time of a given route in the presence of stochastic customers is a complex task because is requires computing a shortest path for each distinct realization of the random variables, i.e., the presence or absence of the stochastic customers. Even when a fixed sequence is used for customer visits, decisions about edge traversal orientation must still be made. In the literature, a fixed traversal orientation of customers has been considered for all realizations of a given route (Mohan et al., 2010). However, this type of approach may be highly sub-optimal when the customer presence probability is low, as this will likely lead to an overestimated travel time.
In this research, we propose a method to accurately estimate the expected travel time of routes containing stochastic customers, assuming a fixed sequence of customer visits. Each time a customer is missing, the path is adapted by skipping that customer and following the shortest path to the next stop. Unlike existing approaches, the proposed procedure optimally re-evaluates the best edge traversal orientation for each possible realization of the random variables. The time complexity of the proposed method is O(n2) for n customers, which is lower than the complexity of one known approach using fixed sequences and fixed edge traversal orientations (O(n3)).
We perform extensive numerical analysis to evaluate the practical performance of the presented method on different instance sizes. We also measure the travel time improvement against a fixed edge traversal strategy. Finally, we present managerial insights related to the impact of the customer presence probability.