Bundle generation for last-mile delivery with occasional drivers

Abstract

In this paper, we present the vehicle routing problem (VRP) with occasional drivers (OD) and order bundles (OB). The problem VRP-OD-OB is an extension of the VRP-OD, where instead of assigning one customer per driver, drivers are assigned bundles of customers. To deal with the bundle-to-driver assignment, a bidding system is exploited, in which a company offers a set of bundles and the drivers raise their bids. These bids depend on features such as the drivers’ destination, flexibility in deviating from the shortest path, and willingness to offer service. To generate valuable bundles of customers, we propose two strategies: (i) an innovative approach based on the creation of corridors, and (ii) a traditional approach based on clustering. Through an experimental study, carried out on randomly generated instances and on a real road network, we show that the innovative corridor-based approach strongly outperforms the clustering-based approach. Given a set of bundles and a corresponding set of bids, we provide a mathematical formulation and valid inequalities to solve the VRP-OD-OB. To address larger instances, we design an efficient large neighborhood search-based matheuristic. The results of an extensive computational study show that this method provides near-optimal solutions within very short run times. An analysis of the impact of drivers’ flexibility and willingness levels on the percentage of customers assigned to ODs is presented. Moreover, the case in which ODs dynamically appear at regular time intervals is investigated. Also in this dynamic setting, considerable total cost reductions are shown. Moreover, we derive several important managerial insights, which include the observation that it is not necessary to provide a high number of bundles to achieve good quality solutions. Companies should rather focus on generating fewer but more attractive bundles.