Mixed pickup and delivery vehicle routing problem with time windows, shifts and meal breaks

Abstract

Last mile delivery remains to be a focal point in the operations of logistics service providers. As more customers are willing to pay a premium price for receiving or sending their parcel within a specific time window, the Vehicle Routing Problem with Time Windows (VRPTW) has been an active research area. However, realistic problem features such as the existence of multiple working shifts and the meal breaks of the delivery personnel assigned to each shift have not received sufficient attention in the literature. The existence of these additional requirements gives rise to the VRPTW including Mixed Pickup, Delivery, Meal Breaks and Shifts (VRMPDTW-BS) which is the main focus of the present study. The fact that the time windows of some customers overlap with several shifts brings additional complexity since the problem cannot be decomposed with respect to shifts. We develop three methods for the solution of the VRPMPDTW-BS. The first method involves the formulation of a mixed-integer linear programming model, which can be solved to optimality for relatively small instances up to 25 customers. The main use of this model is to assess the quality of the solutions obtained by the proposed three-phase heuristic that is based on generating an initial solution and improving it using a large neighborhood search mechanism that monitors the positions of the nodes in the solution to learn their best place. With the help of node mobility concept, the initial solutions are improved in terms of the number of vehicles as well as the total distance by combining the proposed large neighborhood search with simulating annealing procedure. For larger instances with more than 1000 customers, we also devise another heuristic based on partitioning the customers into a number of clusters and then applying our heuristic for each cluster. The results obtained on instances of different sizes show that the proposed heuristic yields solutions of good quality within acceptable computation times for VRPMPDTW-BS. Additionally, the proposed heuristic is comparable to the state of art heuristics in the literature for different variants of Vehicle Routing Problem with Backhauls