Keywords

1 Introduction

The courier, express and parcel services (CEP) industry experienced a great boom in recent years. Commercial carriers have delivered about 4.05 billion consignments in Germany in 2020 [3]. Acceleration factors are the e-commerce boom, the digitalisation, and the COVID-19 pandemic [22]. Due to these trends, CEP providers are facing many challenges in satisfying their customers’ needs [9, 12]. They especially struggle with the last mile, which is often considered one of the biggest challenges in business to consumer (B2C) e-commerce [7]. One method to face these challenges is parcel lockers, as they support the last-mile delivery [14]. For instance, parcel lockers can help to reduce traffic in residential areas and vehicle mileage of CEP providers [1, 8, 14]. Nonetheless, parcel lockers also mean a higher investment for CEP providers [1, 30, 32]. A pilot project in the German city of Magdeburg is currently facing these challenges with a novel concept since 2019. It uses parcel distribution with an innovative hub-and-spoke approach with several distribution levels. This approach has multiple system components, like an urban hub, micro depots, stationary and mobile parcel lockers, and electric cargo bikes. The mobile parcel lockers are small-scale self-service parcel lockers stored in the urban hub. Cargo bikes distribute them in the residential using load bike trailers. They can be moved flexibly from one neighbourhood to another. Therefore, they help to overcome the disadvantages of stationary lockers, such as high investments. The pilot project realises this concept for the first time in Germany.

In this paper, the authors provide insights on overcoming the challenges and drawbacks of the increasingly popular stationary parcel lockers with the concept of mobile parcel lockers with changing locations depending on the regional parcel volume. Our research contributes basically in two ways. On the one hand, it is the first initial quantitative assessment of the concept of mobile parcel lockers and, on the other hand, an evaluation of the system component in a practical case study. Therefore, this research aims to evaluate the utility of the mobile parcel locker with cargo bikes in terms of delivery time, driven distance and emissions. Furthermore, we provide a comparison to conventional distribution channels and present an algorithm to plan the locations of mobile parcel lockers and the routing for the distribution of parcels in urban areas.

The remainder of this paper is structured as follows. Section 2 explores the state of the art in last-mile delivery, mobile parcel lockers, cargo bikes and greenhouse gases (GHG). Section 3 presents the methodology regarding the location planning and routing algorithms and the handling of datasets. In Sect. 4, we provide computational results for four scenarios and compare them. Finally, Sect. 5 discusses the results and determines future research directions.

2 Literature Review

2.1 Last-Mile Delivery

Last-mile delivery is a major topic for CEP providers. It is the most critical part and bottleneck in the distribution of parcels. With the increase of e-commerce and urbanisation and negative environmental impacts occurring, it is necessary to find new, sustainable, and ecological approaches for solving the last-mile delivery issues [12, 28]. Algorithms can help to solve last-mile delivery problems. Many authors presented algorithm-based approaches to evaluate and optimise the last-mile delivery. To the best of our knowledge, there are no publications concerning the capacitated vehicle routing problem (CVRP) in combination with the maximum coverage problem (MCP). Considering the use case of our research, equally not. Nevertheless, many publications address the CVRP and the MCP separately.

Ranathunga et al. [23] state that a variety of variants of the CVRP have been formulated in the context of last-mile delivery in recent years. Whereas the MCP does not have many uses in last-mile delivery. Cao et al. [6] build a model to reduce the investment for delivery fleet or trucks. They use a strategy that combines ride-sharing platforms with traditional in-house van delivery systems. As a result, they optimise the last-mile delivery of n packages from a distribution centre to their final recipients. Grabenschweiger et al. [11] present a model with multi-size locker box stations and parcels. They introduce the vehicle routing problem with heterogeneous locker boxes (VRPHLB) and propose a metaheuristic solution approach. The customer can receive the parcel directly or through a parcel locker in this approach. Furthermore, customers are shifted to parcel lockers as long as it benefits the overall solution quality. Also, the minimisation of the total cost, which consists of total travelled distance and compensation costs for serving customers at parcel lockers, is integrated into their model. In addition, they consider the bin packing problem when assigning parcels to parcel lockers.

2.2 Mobile Parcel Lockers and Cargo Bikes

The general concept of mobile parcel lockers is currently a vision in some research projects and enterprises. It is still a concept which has not been implemented as a prototype and put into practical use. Mobile parcel lockers are a topic of interest for CEP providers and big players from the technology sector. Google has received a US patent for mobile delivery platforms [18]. Moreover, different trend reports regarding the future of last-mile logistics mention the potential of mobile parcel lockers. Here, the examples of DHL [13], and McKinsey [16] can be mentioned. Furthermore, Renault introduced a concept for an autonomous driving platform named EZ-GO in 2018. The platform has a variety of use cases, for instance, passenger cabins or also as mobile parcel lockers [17].

However, in the case of this pilot project, the mobile parcel locker is a small-scale self-service parcel locker which is rollable and should be transported to the neighbourhood by cargo bikes with the help of cargo bike trailers. The mobile parcel locker is rolled off the trailer and moved to a rail system in the neighbourhood. It is installed on-site and locked in place to prevent it from rolling away or being stolen. The receivers would then have time to pick up their parcels, and this would be near their residence, i. e., in their neighbourhood with less than 300 m to walk.

Schwerdfeger and Boysen [26] quantify the advantage of mobile over stationary lockers. The authors formulate a so-called mobile locker location problem (MLLP). It is an optimisation problem that determines the changing locations of mobile parcel lockers during a planning horizon, considering that customers have a changing whereabout and that customers can pick up their parcels near the locker assigned to them. They aim to minimise the locker fleet size required to satisfy all customers.

In the model, the changing whereabouts of the customers are defined as specific intervals and positions. The customer can pick up the parcel at a specific locker and has an individual maximum range for the pick-up. Moreover, it is possible to utilise customer position changes to reduce the total number of necessary parcel lockers. The placement decision of the mobile parcel locker is thus determined by successive stops during the planning horizon and customers’ whereabouts.

Wang et al. [31] focus on the use case in which the mobile parcel locker moves to the following distribution point only when the demands at the current point have been successfully fulfilled within the service time window. There is a restriction that each mobile parcel locker must drive to the various distribution points individually after leaving the depot and return to the depot after visiting all the assigned distribution points. Hence, their use case also involves route planning. The authors want to solve the following problems simultaneously: Which demand points should be selected as the distribution points to accommodate mobile parcel lockers, how many mobile parcel lockers should be assigned and what route each mobile parcel locker takes.

2.3 Emissions in Last-Mile Delivery

The energy sector is responsible for a significant share of worldwide GHG emissions. It also includes the transportation sector with 16.2% and, more precisely, road transport with 11.9%. Therefore, 60% of road transport emissions come from passenger travel, and the remaining 40% originate from road freight transport [24]. Last-mile delivery is not only critical in terms of time and cost but especially because of the GHG emissions since these occur directly in the cities. Hence, reducing GHG emissions in the last mile has been a topic of interest for some years. For example, Figliozzi [10] investigates the CO\(_{{2}}\) emissions of alternative transport vehicles on the last mile and compares them to a conventional internal combustion engine van. Jiang et al. [15] include carbon emissions as an additional objective in a travelling salesman problem and also consider customer self-collection.

When talking about the causes of climate change, carbon dioxide (CO\(_{{2}}\)) is the most prominent GHG emitted by e. g. burning of fossil fuels. However, CO\(_{{2}}\) is not the only gas driving global warming [24]. There are seven more GHG that directly affect climate change, such as methane or nitrous oxide. Other gases such as nitrogen oxides (NO\(_{\text {x}}\)) and particulate matter (PM\(_{10}\)) can also harm the health of human beings when emitted in densely populated urban areas. PM\(_{10}\) is a non-exhaust particulate emission from road transport. However, there is little policy action against them [20].

3 Methodology

3.1 Location Preselection for Mobile Parcel Lockers

Big cities must deal with similar problems because the city districts are usually densely populated. The amount of parking spaces is low, and there is a great conflict between the delivery traffic, the inhabitants, and other stakeholders. In this case study, we consider the district of Stadtfeld Ost in the German city of Magdeburg. It has the following characteristics:

  • Most densely populated district in Magdeburg

  • Residential areas have the biggest share

  • Narrow roads due to the conflict between delivery traffic and parking spaces

These characteristics underline the necessity of improving traffic and logistics by using mobile parcel lockers to reduce the amount of delivery traffic needed. The objective of the preselection was to a set of possible locations for mobile parcel lockers. This set is necessary for the location planning to evaluate the quality of the determined locations and compare the different scenarios. In preparation for the utility analysis, we used the land use map to understand the points of interest within the city district. We marked already existing parcel lockers, stations for public transport and public facilities within the map. Afterwards, we explored the whole city district and marked every location that could be suitable for mobile parcel lockers. This methodology led to a set of possible locations for the utility analysis. We use two categories of factors. The first set of factors concerns mandatory criteria that need to be fulfilled by the location to be considered in the following location planning. The mandatory factors were the following:

  • Sufficient availability of space

  • Reasonable location costs

  • Accessibility with a cargo bike

  • Accessibility with a small delivery truck

  • Public space

We also elaborated on optional factors to better distinguish between the different locations. The optional factors were clustered in six different categories:

  • Visibility: Criteria regarding the visibility of the location from the road and the possible orientation of the parcel locker

  • Accessibility: Criteria regarding the slope, nearby curbstones and ground condition

  • Reachability: Criteria regarding nearby public transport stops, bicycle stands and parking spaces

  • Safety: Criteria regarding lighting, camera observation, vegetation, accessibility and frequentation

  • Site properties: Criteria regarding availability, possible roofing, weather protection, disturbance of the townscape, marketing friendliness and surface sealing

  • Planning: Criteria regarding energy supply, internet access, nearby parcel lockers and initial costs

3.2 Location Planning and Routing

The location planning concerns the determination of locations for the mobile parcel lockers. In contrast, the routing deals with creating tours to distribute parcels and mobile parcel lockers in the district. As the routing depends on the determined locations, both tasks must be considered successively to find a delivery schedule for the day. Thereby, the location planning must be completed before starting the routing. The planning algorithm distinguishes two types of locations: Customer locations and locker locations. Each locker location has an index, coordinates and status. Customer locations have a demand for parcels in addition. The status (active or inactive) results from the location planning and describes whether the location is relevant for the routing. In the following, we briefly describe both optimisation problems and the corresponding algorithm used to solve them.

Suppose each mobile parcel locker substitutes the door delivery of parcels in a certain service radius around the location. Then, the mobile parcel lockers must be placed in the district so that they cover a maximum number of customer locations under the restriction that only a limited number of lockers can be opened. Operations research considers this problem as an MCP. However, as the parcel deliveries are different every day, the optimal locations for the mobile parcel lockers also change every day. Therefore, the location planning algorithm must not solve the MCP only once but every day. A prerequisite for solving the MCP is the coverage matrix which states for each location which customers it covers. A locker location covers a customer location if the distance between them is smaller than the coverage radius. In the case of coverage, the element in the matrix takes the demand; else, it is denoted by zero. When considering urban environments, Euclidean distances do not appropriately represent the problem. Therefore, the problem requires routing services that take the existing street networks into account when computing distances.

We use a classic greedy algorithm to solve the MCP. A status change of the locations represents the opening of locker locations and customer locations. All customer locations are active, and all locker locations are inactive in the initial state. First, the algorithm computes the coverage of each locker by accumulating the demands from each column of the coverage matrix. Then, it opens the locker location with the highest coverage at each stage until it reaches the limit of lockers to be opened. At the same time, it closes all the covered stops by setting the customer location status as inactive. Before opening the locker locations, it checks two capacity restrictions. If the coverage exceeds the capacity of the locker, customer locations are opened according to ascending indices until the capacity is reached. The algorithm terminates if the coverage is lower than the lower limit for opening a locker. Otherwise, it terminates after reaching the maximum number of locker locations to be opened.

After terminating, there is an adjusted set of relevant locations for the routing. Due to the limited capacity of the cargo bikes, the carrier must deliver each locker on a separate tour. He can approach the remaining customer locations in any order. As the number of parcels to be delivered possibly exceeds the capacity of a single cargo bike, multiple tours are necessary. Operations research considers this problem as a CVRP. The objective is to deliver the parcels for the least cost. Standard cost metrics are distance or travel time. Like the MCP, the CVRP requires a cost matrix that states the cost from each customer location to each customer location. Determining distance or travel time also requires a routing service. We use a local search algorithm to solve the CVRP that searches for better solutions iteratively based on an initial solution. A simple greedy nearest neighbour algorithm constructs the initial solution by always selecting the next stop based on the lowest cost until it reaches the vehicle’s maximum capacity.

figure a
figure b

The implementation was done using Python. For calculating the distances and travel times between two locations, we used the OSMnx and NetworkX libraries that can download street networks as graphs from OpenStreetMap and determine the shortest paths using the Dijkstra algorithm [4]. The greedy algorithm for solving the MCP was implemented using the Python standard library. The optimisation of the CVRP uses the solver of the Google OR-Tools library, which has a specialised solver for vehicle routing problems based on constraint programming and large neighbourhood search with routing-specific neighbourhoods [21]. In addition, we implemented an interactive web interface for visualising the results that uses the Folium library [29].

3.3 Datasets

In addition to the potential locations of mobile parcel lockers, the assessment requires datasets on customer addresses in the district and parameters for calculating emissions and specifications of vehicles and parcel lockers. The set of customer addresses is based on past parcel deliveries of a local CEP provider and contains all parcels that have been delivered in the district in 2021. To enrich addresses and postal codes of the deliveries with coordinates, we retrieved longitude and latitude from OpenStreetMap using the tidygeocoder package in R [5]. As some customers received multiple parcels during the year, the dataset represents a realistic geographical distribution of deliveries in the district when selecting random samples with an equal probability.

The values for calculating CO\(_{{2}}\), PM\(_{{10}}\) and NO\(_{\text {x}}\) emissions for light-duty diesel vehicles (vans) and cargo bikes are based on previous studies [2, 27]. These studies provide mean values that originate from real-world traffic data. Assmann et al. [2] also provide values for the average stop duration of vans and cargo bikes based on the study of Schäfer et al. [27]. On average, a van takes 7.2 min for a stop, whereas a cargo bike only requires 3.6 min. The vehicle capacities come from a previous study in the pilot project. The local CEP provider states the cargo space of the vehicles as 2 \(\text {m}^{3}\) for the cargo bikes and 3.5 \(\text {m}^{3}\) for the vans. The recording of parcel volumes for one week revealed that typically 20 parcels fit in one cubic meter of cargo space. Hence, the cargo bikes, respectively, the mobile parcel lockers, have a capacity of 40 parcels, whereas the vans can transport 70 parcels on average.

4 Experiments and Results

Using the case study of a district in the German city of Magdeburg, we conducted experiments to assess the potential of mobile parcel lockers and cargo bikes regarding distance, travel time and emissions in comparison to conventional delivery with internal combustion engine vans.

4.1 Experiment Design and Implementation

We defined four scenarios that have been simulated using the implemented model (cf. Table 1). Scenario 1 represents the door delivery with internal combustion engine vans, which is the standard delivery method of CEP providers. Scenario 2 represents the innovative delivery concept with cargo bikes and mobile parcel lockers. Scenario 1 is a pure home delivery concept, whereas scenario 2 is a hybrid concept in which some customers get their parcels directly and some via mobile parcel lockers. The scenario assumes that three mobile parcel lockers can be opened at maximum. Each locker serves a coverage radius of 300 m because other studies for similar facilities such as bus or metro stops showed that this is a distance that customers are still willing to walk in an inner-city area [19, 25]. A locker must cover the demand of 20 parcels in the coverage radius at a minimum to be opened, which is equal to the utilisation of 50% of the locker capacity. The experiment design allows for a direct comparison of scenarios 1 and 2 because they both use the total distance metric. The same applies to scenarios 3 and 4, which compare the total time of all tours.

Table 1. Experiment design
Full size table

The algorithm was run for ten different random states to make the results valid. Each random state contains a sample of 300 parcels from the real-world dataset. Based on the findings of Assmann et al. [2], a district of this size has a demand of approximately 4500 parcels per day. The sample size accounts for a market share of approximately 7% which is a realistic assumption for a local CEP provider. Furthermore, the selected number of parcels minds the tradeoff between sample size and computing time, as the computing time increases by the square of the number of customer locations. Each run takes 45–90 min of computing time.

4.2 Computational Results

Table 2 shows the computational results for scenario 1 and 2 for each random state. Due to the higher capacity of the vans, the delivery schedule comprises five tours, whereas the cargo bikes require 8–9 tours. In each random state for scenario 2, the maximum number of three mobile parcel lockers was opened. Hence, three tours account for the delivery of lockers, whereas the remaining tours are door delivery tours. Despite the higher number of tours, the cargo bikes in scenario 2 travel shorter total distances than the vans. On average, the total distance is 3.64% shorter with a maximum of 8.42%. This is because cargo bikes can use car lanes and bike lanes, which increases the options for routing. However, the cargo bike use effects on the distance are quite small because they have a lower capacity than the delivery vans.

Table 2. Computational results of scenario 1 and scenario 2
Full size table

Based on the total distances of the tours, it is also possible to give an initial assessment of the potential reduction of GHG emissions. As it is impossible to measure the GHG emissions directly, we used standard values from the literature for CO\(_{{2}}\), PM\(_{{10}}\) and NO\(_{\text {x}}\) emissions dependent on the distance. Table 3 shows the estimated GHG emissions for each random state and the potential reductions when using cargo bikes and mobile parcel lockers. The values from the literature indicate that it is possible to reduce PM\(_{10}\) and NO\(_{\text {x}}\) emissions by 100%. Merely CO\(_{{2}}\) is emitted to a small extent because of the cargo bike’s electric driving assistance, which requires regular charging. Assuming the current German electricity mix includes electricity from fossil sources, it is still possible to reduce the CO\(_{{2}}\) emissions by 94.77% on average compared to van delivery. If the share of sustainable energy sources rises in the future, it is possible further to reduce the CO\(_{{2}}\) emissions of the cargo bikes.

Table 3. Estimated GHG emissions of scenario 1 and scenario 2
Full size table

Table 4 presents the computational results of scenarios 3 and 4, which use the total time metric for the optimisation runs. Again, vans need fewer tours than cargo bikes to deliver the parcels because of the higher capacity. The maximum number of three locker locations is opened in each random state, which accounts for three tours to deliver the lockers. The experiment results indicate that the total time decreases significantly when using cargo bikes and mobile parcel lockers. An important driver for the total time is the stop duration which depends on the number of customer locations with door delivery and the used vehicle. The concept in scenario 4 approaches both: It decreases the number of stops by gathering the demand of adjacent customer locations in the opened locker locations, and it exploits the potentially lower stop duration of cargo bikes for door delivery. Hence, we expect to achieve average total time reductions of 59.38%.

Table 4. Computational results of scenario 3 and scenario 4.
Full size table

The implemented software tool also provides interactive visualisations of the tours, customer locations and locker locations. Figure 1 shows the solution of one random state. Each node represents a location, and each edge represents a route between two locations. The colouring of nodes and edges marks the tours. Each tour starts and ends at the depot. Although the edges are displayed as direct lines between the nodes, the model uses the existing street network for routing. Hence, it is impossible to assess a solution’s quality just by considering the visualisation.

Moreover, the visualisation marks opened locker locations with a grey circle equal to the coverage area. The coloured node in the middle of the circle represents the opened locker location. All the covered customer locations remain on the map but are coloured in grey.

Fig. 1.
figure 1

Visualization of solutions with Folium.

Full size image

5 Discussion and Future Research

In the previous section, we evaluated the potential of mobile parcel lockers and cargo bikes. Using a quantitative simulation approach, we have shown that the presented concept can decrease time, distance and GHG emissions compared to door delivery with internal combustion engine vans. However, qualitative aspects such as the usability of mobile parcel lockers require further discussion. The initial concept of the pilot project names the flexible placement according to changing customer demands in certain areas as the main advantage of mobile parcel lockers. This characteristic should make them applicable even for small-scale areas in which the operation of stationary parcel lockers is not cost-efficient. When using the results of the experiments, it is possible to give a first assessment of whether reality complies with the idea. Considering the opened locker locations in each random state, only 6 out of 16 locker locations have been opened at least once. Three were especially important out of these six locations as they almost always provide the highest coverage. Hence, the distribution of demands seems similar in different random states, and the flexibility of mobile parcel lockers was useful only in specific cases. One reason may be the sampling process, as the samples do not represent real daily delivery volumes but random deliveries from the entire year. Real daily delivery volumes might include seasonal fluctuations or trends that lead to more significant deviations in the days. On the other hand, the results might indicate that certain locations are especially suitable, determining another use for mobile parcel lockers. They could be used as enablers for stationary parcel lockers by testing the placement in a promising area. By this, the CEP provider can quickly and cost-effectively assess customers’ acceptance.

The paper also showed how to deploy a greedy algorithm and local search for two optimisation problems transferred to a last-mile delivery setting. Especially the greedy algorithm was developed specifically for the new mobile parcel locker MCP and can serve as a benchmark for other researchers in the future. The algorithm for the CVRP is a standard local search algorithm from the OR-Tools library that was already used for several different routing problems. At the moment, technical limitations regarding the routing limit the applicability of the software tool, as the computing time increases by the square of the number of customer locations. The drivers of the computing time are solely the calculation of the coverage matrix and the distance matrix because the shortest path is required for each combination of locations. Especially when considering the bike lane network, the shortest path computation is slower because bike lanes have many more nodes and possibilities for routing than car lane networks. In contrast, computing the solution of the MCP and the CVRP takes only a few seconds. A sophisticated, more-efficient routing algorithm and the storage of already computed relations can potentially reduce the computing time in the future. Also, the use of straight distances can significantly reduce the computation time but degrades the solution quality.

Another temporary problem is the high amount of construction sites in the considered district, which significantly disadvantages cars when routing. However, future urban planning might benefit bike traffic in inner-city areas more than now and similarly penalise car traffic. Therefore, the computational results can already give a suitable outlook.

The contents and results of this paper originate from the funding of R &D projects for the development of logistic interfaces and handling techniques for combined transport from the European Regional Development Fund (ERDF).

Paket-KV-MD2 / Reference number: 307.4.10-32323/1915003002