We introduce the Stochastic Delivery Problem (SDP). The SDP is the problem faced by parcel delivery companies more concerned about maximizing customer satisfaction than minimizing routing costs alone. In this context, customer satisfaction is highest when the delivery attempt is successful - i.e., the customer is available for receiving the goods at the time the parcel company visits him.
To fully define the SDP we need to introduce the notion of customer availability profiles. These are general functions representing the likelihood of customers being available for deliveries at any instant during the regular delivery period.
The main objective in the SDP is to minimize the expected number of unsuccessful deliveries. To achieve this it might be optimal to visit the same customer more than once in a route. This is a key difference between the SDP and other related routing problems such as the Team Orienteering Problem.
We formulate the SDP as a set-partitioning problem and we apply the successful branch-and-price methodology for routing problems. In our case, however, the definition of strong dominance rules is not possible due to the generality of the availability profiles. For this reason, to solve the pricing problem we employ a labeling algorithm that, at each extension, bounds the minimum reduced costs that such extension can generate. We discuss different approaches to efficiently calculate these bounds, and present some acceleration strategies for solving the pricing problem.
Finally, we present some promising results for a few SDP instances.
| Subject : | : | Abstracts |
| Topics | : | Column generation/branch-and-price |
| Topics | : | Exact methods |
| Topics | : | Stochastic vehicle routing |
| PDF version | : |  PDF version |
