## 4 Modeling Approaches to Assess the Costs for the Last Mile for Direct Deliveries  
This research is focused on systems with one central depot, from where customers (or APLs) are served by a fleet of vehicles. Three different approaches (at different aggregation levels) are discussed in the following sub-sections and compared to direct deliveries. The capacity of each vehicle is restricted by a given number of parcels, which serves as a rough abstraction of actually relevant weight or volume restrictions. Solving the underlying VRP consists of two different problems:  
* Defining clusters of customers (to be served on a single tour),
* Defining the sequence in which the customers are served on the tours. Using mathematical optimization, these two problems are solved simultaneously. However, as the VRP is an np-hard problem, only relatively small problem instances can be solved to optimality within a reasonable amount of time. Therefore, usually heuristic approaches are applied. Here, construction and improvement methods are further distinguished [55]. The nearest neighbor construction method starts with a single node (from the set of all nodes to be visited) as the current node \(i\) (usually the depot). The nearest node (from the set of nodes not visited yet) to the current node \(i\) is chosen to be visited next and set as the current node for the next iteration. Once all of the nodes have been visited, the tour is closed by returning to the first node (depot). Often, two well-known heuristic approaches, the sweep and the savings algorithm, are applied to solve VRP instances and have also been implemented in this paper. Originally introduced in the seminal work [56], the sweep algorithm operates as follows: starting from the depot location as the origin, a sweeping line is extended outward in a predetermined direction. As this line sweeps around the depot, it groups nodes within its vicinity for a single tour until the capacity constraints are reached. Once the members of a tour have been determined, the respective instance of the TSP is solved. The savings algorithm is a construction heuristic that seeks to minimize the total distance traveled by vehicles while serving a set of customers [57]. The algorithm starts with the worst-case solution that each customer is served on a single tour. It calculates possible savings for each pair of tours (customers), representing the potential reduction in distance if the two tours are combined in a single tour. These savings are sorted, and the procedure iteratively merges tours (if within the the capacity constraints), gradually forming the final solution. The savings algorithm shows simplicity as well as effectiveness in generating reasonable solutions [55]. While it might not always produce optimal solutions, its efficiency and adaptability make it a valuable tool in practice. Figure 1: Based on the work in [40], the schematic representation of possible scenarios is as follows: (**a**) All recipients are directly served. The CEP service provider tries to find an optimal tour plan of minimal total length serving all recipients. Here, instances of the VRP problem need to be solved. (**b**) Some of the recipients employ the locker such that the CEP service provider does not need to visit all of the recipients. However, the locker locations need to be served by the CEP service provider. (**c**) Extreme case where all recipients employ APLs. Moreover, such construction algorithms can be enhanced by integrating additional heuristics or local search techniques to refine the initial solution, achieving improved results in practice. A typical example for an improvement procedure is 2-Opt, where in each iteration two edges are eliminated from the existing tour. The two remaining parts of the original tour are reconnected after changing the direction of visiting the nodes of one of the two parts, following a greedy approach resulting in a shorter tour.