Modelling and Optimization of the Vehicle Routing Problem with Alternative Delivery Locations and Time Windows

Scope of this talk is the development and evaluation of an optimization method for the vehicle routing problem with alternative delivery locations and time windows. Based on an assessment of B2C logistics operations, the absence of customers at the time of delivery is identified as a major challenge to express and parcel delivery services. Current solution concepts rely on depositing shipments at locations wherefrom they are picked up by customers. I propose an additional service oriented approach based on the mutual agreement between customers and service providers on delivery locations and time windows. Customers may offer alternative locations and time windows from which service providers choose a suitable combination. This approach eventually leads to the vehicle routing problem with alternative delivery locations and time windows. The problem is modeled as a mixed-integer program (MIP) and solved with a branch-and-price approach where the pricing problem is modelled and solved with constraint programming. Computational results based on modified benchmark instances taken from literature are presented. In particular, the influence of particular algorithm elements and problem structure on runtime performance are analyzed. The potential for cost reduction from a service providers perspective is analyzed using a set of artificial but realistically structured set of scenarios. The empirical results show that a considerable reduction in cost and smaller fleet sizes can be achieved. A method for rapid comparison of different instances with respect to the achievable cost reduction is presented and future research directions are suggested.

Contact information

Naima Zerhanenzerhane@rsm.nl

Email