The vehicle routing problems with flexible delivery options were initially investigated by de Jong et al. (1996) [12], who introduced a new variant known as the Multiple Time Windows Vehicle Routing Problem (VRPMTW). Subsequent studies by Doerner et al. (2008) [13], Favaretto et al. (2007) [14], Belhaiza et al. (2014) [15], and Beheshti et al. (2015) [16] also tackled the VRPMTW. Nevertheless, none of these studies incorporated the provision of alternative delivery locations as an option for customers. Another relevant approach to flexible delivery is the Generalized Vehicle Routing Problem (GenVRP), proposed by Ghiani and Improta (2000) [17]. In this problem, customers are grouped into clusters, and it suffices for a delivery vehicle to visit one of the nodes within each cluster.

In 2017, G. Ghiani and G. Improta introduced an extension to the VRPMTW [4], known as the Vehicle Routing Problem with Roaming Delivery Locations (VRPRDL). This advanced variant facilitates the delivery of goods to customers’ vehicle trunks at different times throughout the day. Ozbaygin et al. [18] developed a branch and price algorithm to solve the VRPRDL effectively. Subsequently, in 2019 [19], Ozbaygin et al. extended their research to the dynamic variant of the VRPRDL, where customers can modify their plans within a pre-planned schedule. Consequently, the initially planned schedule is no longer optimal or even feasible. To address this challenge, the authors proposed a branch-and-price algorithm to reoptimize the vehicle routes and delivery locations.

The Vehicle Routing Problem with Transshipment Facilities (VRPTF), as described by Baldacci et al. (2017) [20], allows consumers to be supplied either directly from a central depot or by paying to use a transshipment facility. They outline numerous legitimate inequalities for the VRPTF in their work and offer a mathematical solution. Additionally, they obtain lower bounds by using a formulation of the VRPTF based on set partitioning (SP). Alcaraz et al. (2019) [21] examined the transportation of customer requests, which can be delivered directly to the customer or via a transshipment facility. In the latter case, a third-party subcontractor is responsible for the last-mile deliveries, charging a fee for their services. The researchers focused on a complex vehicle routing problem characterized by long-distance travel and additional factors such as driving hour restrictions, item incompatibility, heterogeneous vehicles, and time windows. To tackle this challenge, they proposed a construction heuristic approach incorporating these characteristics and adapting several established improvement heuristics from the existing literature.

Sitek and Wikarek (2019) [22] conducted a study on the Capable Vehicle Routing Problem with Pickup and Alternative Delivery (CVRPPAD). Their research considered factors such as time windows and fleets with different characteristics. They also considered the possibility of delivering customer requests to alternative destinations such as parcel lockers or postal outlets. To tackle this problem, the researchers proposed a precise method based on mathematical programming and a heuristic solution suitable for larger problem instances. In their heuristic approach, they employed a set of rules to assign customer requests to routes and resolved a travelling salesman problem for each route.

The earliest reference to the Vehicle Routing Problem with Delivery Options (VRPDO) can be traced back to 2005 [23], when Furmans et al. introduced it as a mixed integer programming model. Their proposed solution adopted a branch and price approach with a decomposition scheme. Optimal route selection was achieved through linear programming, while constraint programming was employed for modelling and calculating the optimal vehicle routes. In a subsequent extension, the pickup and delivery problem with shared delivery locations and diverse preferences was considered [24]. To solve this problem, an ALNS was employed, and the resulting solutions were compared to those generated by a commercial solver.

Dumez et al. (2021) [10] conducted research on the Vehicle Routing Problem with Delivery Options (VRPDO), which focuses on various delivery locations available to customers. In this problem, customers can express their preferences for multiple delivery options, with weights assigned to each option. Unlike the VRPTF, the shared delivery options do not incur additional costs, and the objective is to meet customer preference levels while respecting the capacity limits of shared delivery locations. The authors propose a solution to the VRPDO by using a Large Neighborhood Search (LNS) approach. They conducted computational experiments that solved instances with 50, 100, 200, and 400 customers within specified runtime limits of 30, 90, 300, and 2000 s, respectively. The authors assessed the efficacy of the heuristic approach by comparing it with alternative solution approaches documented in various variants of Vehicle Routing Problems. However, when presenting the results of the LNS approach applied to VRPDO, they solely reported the average and best outcomes obtained from five independent runs without comparing them with other methods or the MIP model.

Mancini and Gansterer (2021) [2] have presented two matheuristic approaches, namely the LNS matheuristic (MH) and Iterated Local Search (ILS), as efficient solution procedures for solving large instances of the Vehicle Routing Problem with Delivery Options (VRPDO) containing up to 75 customers. In their model, they incorporated an additional cost that compensates customers who opt to collect their parcels from shared delivery locations. The researchers formulated the problem mathematically and employed a Mixed Integer Programming (MIP) model, with a maximum runtime of 1 h, to obtain the optimal solution. They compared the MIP solution with the results generated by the two heuristics for instances of sizes of 25, 50, and 75 customers. The MH heuristic demonstrated average runtimes of 5.32, 63.75, and 283.47 s for the respective instance sizes, while the ILS heuristic exhibited average runtimes of 18.53, 276.7, and 772.38 s, respectively.