Time window assignment in an uncertain world

Kevin Dalmeijer

It is 12.05h and 37 seconds when the doorbell rings. You already know who it is: it is the delivery man with the package you ordered. His arrival is the exact time he said he would be there.

While this would be perfectly normal in an ideal world, it is simply not possible in our world filled with uncertainties. For example, when assigning your time of delivery, it was still uncertain how many other deliveries there would be. To deal with such uncertainties, companies assign time windows to customers, telling them between which times they may expect service. Often, these time windows are set very wide, for example telling the customer to be available between 9h and 17h. I believe this is unnecessary.  By means of mathematical models we can come up with smarter time windows which increase customer satisfaction and keep costs of operation about equal.

Assigning time windows in an uncertain setting is not just relevant to the case where deliveries are made from a store to clients. A second relevant setting is the one in which deliveries are made from a central depot to retail stores or pickup points. A third setting is one in which a company delivers to multiple postal codes and determines a time window per postal code.

When assigning time windows, the goal is to minimize the expected cost of operation, based on historical information. Though very relevant, this problem has been mainly unexplored and is hence far from solved. Most initial work in this field focuses on finding good solutions as opposed to the best solution.

There are good reasons to develop methods that find the best solution. First, the best solution is obviously better than a good solution. In many cases, it does not even take that much time to determine the best solution, especially when the fleet is small, or when only a small number of locations have to be visited. Second, knowing what the best solution is helps us evaluating how good the good solutions really are. Third, studying how to obtain the best solution helps us to gain more knowledge and understanding of the problem, which in the long term translates into better methods and better solutions for practice.

In my research, I will be working on assigning smarter time windows under various types of uncertainties. Our current focus is on demand uncertainty. Specifically, we incorporate that it is oftentimes unknown how much vehicle capacity is required to serve a client. By mathematical modeling and leveraging structural properties of the problem, we are currently able to find the best time window assignment almost 200 times faster than previous methods. By continuously improving our methods, we allow more and more practitioners to start using them, and to improve the satisfaction of their customers.

 

Key takeaways

  • Assigning time windows in an uncertain setting is a relevant problem that is applicable in different settings.

  • Most initial work in this field focuses on finding good solutions, not on finding the best solution.

  • Focusing on how to find the best solution has multiple benefits. Both directly and indirectly it contributes to more efficient transportation and improved customer satisfaction.

  • For time window assignment under demand uncertainty, substantial computational improvements have recently been made.