The node edge and arc routing problem with stochastic customers and service times

This presentation addresses a node, edge, and arc vehicle routing problem with stochastic customers and service times. A maximum duration is defined for each route, where the duration of each route is a random variable in this stochastic environment. We thus model the maximum duration constraint of each route as a chance constraint. In the defined methodology, the solutions obtained with the probabilistic knowledge at hand cover all customers with non-zero occurrence probability. After the demands are realized, only a subset of customers will actually be served. As a recourse strategy, a customer that does not require to be served is skipped in its corresponding route, while keeping the rest of the visiting sequence unchanged. This research is motivated by a real application in the context of postal delivery services. Those services are provided by couriers who perform daily rounds in fixed geographic areas, called districts, typically defined for a long period of time based on the expected demand. However, daily demand variations can negatively impact the couriers' workload, creating extra working hours. We address here the problem of designing routes so that the workload of couriers respects the imposed maximum working duration for most demand realizations.