Robust workload balance for postal services with stochastic customers and service times

Postal delivery services are an essential part of our lives. They are ensured by couriers who perform daily rounds in fixed geographic areas called districts. Districts are typically defined for a long period of time based on the expected demand. However, usual demand variations can negatively impact the couriers’ workload, either by exceeding their shift duration, or by creating a largely unfair workload distribution among couriers on certain days. The objective of this research is to design robust districts so that the workload of couriers remains balanced when considering stochastic customers and service times. The problem is modeled as a two-stage stochastic program. In the first stage, districting decisions are made by creating routes that cover all of the customers. In the second stage, the workload balance is estimated considering that those routes are followed by the couriers while skipping the absent customers. In this problem, vehicles are uncapacitated. However, a maximum route duration related to the couriers shift time is defined using a chance constraint formulation. The routing problem is modeled as a node, edge, and arc vehicle routing problem with stochastic customers and service times. This research is conducted in partnership with the Belgian postal service company, bpost. Numerical analyses are performed on instances with stochastic information based on realistic data. In addition, the robustness of the districts is evaluated by means of simulations.