Impact of lockerboxes location on routing planning in last miledelivery with uncertainty in demand and capacity availability
S. Mancinia,b,∗ , M. Gansterera , C. Trikic,da University of Klagenfurt, Department of Operations, Energy, and Environmental

Management, Klagenfurt, Austria
margaretha.gansterer@aau.at
simona.mancini@aau.atb University of Eastern Piedmont, Department of Science, Innovation and Technology,
Alessandria, Italysimona.mancini@uniupo.it
c University of Kent, Kent Business School, Canterbury, UK
c.triki@kent.ac.uk
d University of Salento, Department of Engineering for Innovation, Lecce, Italy
chefi.triki@unisalento.it∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

March 29, 2022
Keywords: Last-mile delivery, Location, Uncertainty, Unavailable Capacity, Matheuristic

1

INTRODUCTION

In the last years we have observed an exponential growth of e-commerce. The number of customers choosing to perform purchases online increases constantly. The current pandemic situation, which implied long lockdown periods for physical shops, further accelerated this phenomenon. The huge number of requests that have to be fulfilled every day, makes last-miledelivery a very critical issue for logistic companies. In Barenji et al. (2019), is reported that, in alast-mile delivery context, distribution can cost up to 40% of the price of a product. Furthermore,
due to the high number of delivery requests, the companies cannot ensure customers to be servedin their preferred time window, and since the delivery time is not known in advance, the delivery
attempt can fail due to customer absence. According to Morganti et al. (2014), up to 40% of
deliveries are unsuccessful. This could result in a huge extra cost for the company. To overcome
this issue, an unattended delivery system has been established. This system involves deliveries
to shared locations, particularly to lockers. Such facilities are generally located in widely accessible sites, such as supermarkets, refueling stations, train stations or other places with very long
opening hours. Customers can pick their parcels from the lockers when it is most convenient
for them. Not all orders are suitable for this delivery option, due to the size (or the value) of
the parcel or to customers willingness. In fact, customers are well-disposed to accept this option
only if the delivery is performed to a locker not too far from their home (or office etc.), otherwise they request home delivery (Mancini & Gansterer, 2021). Consequently, the location of thelockers may significantly affect the percentage of customers willing to accept this option. Shareddelivery locations offer another great advantage, which is the possibility to strongly reduce thenumber of delivery points, and, consequently, the routing costs. Indeed, several customers can
TRISTAN XI Symposium

Original abstract submittal

S. Mancini, M. Gansterer, C. Triki2

be simultaneously served at the same location, where lockers are installed. Hence, every homedelivery avoided can yield to a potential large saving in terms of routing costs. While lockers
location planning is a tactical decision, routing plans are operational decisions, since they are
made daily based on the set of requests to fulfill. Location decision do strongly impact therouting plans for several months, therefore they are a crucial issue for logistic companies. Since
the set of requests can vary from day to day, demand is uncertain but scenarios can be designed
based on historical data. Lockers are composed of a certain number of lockerboxes, but some ofthem can be temporarily unavailable because they are out of order, they have been damaged, or
because a customer served the day(s) before, did not pick up her parcel yet. This unavailability
can affect the number of customers that can be assigned to the locker and, consequently, thenumber of home deliveries to perform. Hence, both customer demand and also unavailabilityof lockerboxes must be treated as uncertain parameters. The goal of our work is to study the
impact of locker location planning on routing in last mile delivery. We define the problem as acapacitated facility location problem with uncertain demand and uncertain capacity availability(CFLP-UDC), where the goal is to firstly maximize the number of customers served throughfacilities, and in case of a tie, to maximize a service quality level assuming values between 0 and
1, where a higher value corresponds to a better service for the customers. The quality of service
is proportional to the average distance to be covered by customers to pick up their parcel. To
the best of our knowledge, this is the first study where both of these features are consideredsimultaneously. Many papers in the literature on stochastic facility location consider facility
disruption, where the facility is fully operative with a probability p or is completely unavailable
with probability 1-p. There are several applications in the military field or in emergency facility
location for disaster preparedness. The first paper considering that a facility can be partiallyoperative, is Cheng et al. (2021), where a robust optimization approach is proposed. Differently
from our work, their goal is to minimize the total costs, given by the sum of facilities opened,customers assignment and costs for unsatisfied demands. Furthermore, while Cheng et al. (2021)
consider the number of open facilities to be a decision variable, we use it as a exogenous given
parameter. To solve the CFLP-UDC, we propose an integer programming formulation and aconsensus-based matheuristic. We study how different parameters influence computational performance of both methods. Finally, we provide insights about the expected value of perfect
information (EVPI) and the value of the stochastic solution (VSS), as well as the impact on thenumber of home deliveries avoided. Results on a real life scenario arising in the city of Turin, in
Italy, will be discussed at the conference.

2

PROBLEM DESCRIPTION

The problem aims at determining the best location for a fixed number of facilities, P , chosen
among a set of candidate locations J. Facilities have identical capacity C. A set of demand
scenarios S is considered. In each scenario s, a set of potential customers I s out of the set of all
customers I has to be served. A customer may be accepted or rejected. If rejected, it has to beserved by home delivery. If accepted, it must be assigned to a compatible open facility, j. Only
facilities within a radius ρ from the customer location are considered compatible. The term ϕij
represents compatibility between customer i and facility j, where ϕij =1 indicates that they arecompatible and ϕij =0 that they are not compatible. The number of customers assigned to afacility, within the same demand scenario, cannot exceed facility’s capacity. A set of capacity
reduction scenarios Ω is defined. In each scenario, the capacity of each open facility is reduced
by a quantity δjω in interval [0, ∆]. This reduction, represents a temporal unavailability of a
portion of the capacity of the facility. The goal of the problem is to determine the location offacilities which maximize the average number of customers assigned to these facilities over all
the demand and capacity availability scenarios. A secondary objective, which intervenes only incase of a tie, aims at minimizing the average covered distance from a customer’s location to the
TRISTAN XI Symposium

Original abstract submittal

S. Mancini, M. Gansterer, C. Triki3

facility to which it has been assigned.
For the mathematical formulation, the following decision variables are needed.
Yijω : binary variable indicating whether customer i is assigned to facility j or not
Zj : binary variable indicating whether facility j is open or not
The stochastic programming (SP) model is formulated as follows.
max

XXX

Yijω +

ω∈Ω i∈I j∈JX

X X X dminω∈Ω i∈I j∈JYijω ≤ C − δjω

dij

Yijω

1
|I||Ω|(1)∀ω ∈ Ω ∀s ∈ S ∀j ∈ J(2)∀i ∈ I ∀ω ∈ Ω

(3)

i∈Is

X

Yijω ≤ 1

j∈J

Yijω = 0∀ω ∈ Ω ∀i ∈ I ∀j ∈ J|ϕij = 0

XXYijω ≤ |I||Ω|Zj∀j ∈ J(4)(5)ω∈Ω i∈I

X

Zj = P(6)j∈J

The hierarchical objective function is reported in (1). It aims firstly at maximizing the number of customers
assigned to a facility, and secondly, to maximize the customers’ level of satisfaction. The latter is measured interms of average distance between customer’s location and the locker station, where the parcel has to be picked up.
The secondary objective is formulated such that it takes values between 0 and 1 by integrating the overall minimum
distance dmin and the distance dij between customer i and locker station j. Since the primary objective can assume
only integer values, the secondary one intervenes only in case of a tie on the primary objective. Constraints (2)ensure that facilities’ capacities is respected in all scenarios. A customer can be assigned to at most one facility, as
expressed in constraints (3). Furthermore, customers can be assigned only to compatible facilities as ensured byconstraints (4). Constraints (5) imply that customers can be assigned only to open facilities. Finally, the numberof facilities to open is expressed in (6). All the variables included in the model are binary.

3

METHODOLOGY

To efficiently solve large and challenging instances, we propose a matheuristic based on the search of consensus
among scenarios. The algorithm is described in the sequel. Firstly, we solve separately each capacity scenario
ω, obtaining an ideal solution for the scenario (Fω ). Combining all the ideal solutions may yield to an infeasible
global solution since more facilities than the maximum number allowed have to be opened. If it is not the case,
we already achieved a global consensus and the solution is optimal. Otherwise we search for consensus among
scenarios. We compute a score for each facility j, as the sum of the number of scenarios in which it is open plus theisolation degree, which is a parameter taking value between 0 and 1. The higher the minimum distance between j
and another facility, the greater the value of isolation. Solutions with a high degree of isolation are most difficult
to replace, therefore they are more likely to stay in the optimal solution. We create an initial core of facilities toopen, picking the P facilities with the highest score. We also calculate a score for the interchangeability of eachclosed facility for each scenario ω. This interchangeability parameter is denoted as γ. It can take a value between
0 and 1, which measures the proximity of j to the nearest open facility in Fω . To generate a first feasible solution,
We solve the original problem by opening only the facilities in the initial core. Then the improvement phase starts
and at each iteration we compute the level of "satisfaction" for each scenario, as the sum of customers served inthat scenario minus the average percentage increment of distance between a customer location and the facility
to which it has been assigned, respect to the nearest facility. The scenario with the lowest satisfaction, denotedas ωworst is further investigated. The fist facility in the γ-based preference list, which has not been marked as
tested yet, is marked as tested and is added to the core. The problem is solved again with the updated core.
Since at most P facilities can be used but the core contains P + 1 facilities, one of them will be discarded by themodel. This facility is removed from the core. Every time an improvement is found, all the tested facilities aremarked again as untested. The algorithm terminates after a maximum number of iterations is reached or in case
all the facilities, not belonging to the current core, are already marked as tested (i.e., if no more improvements
are possible).

TRISTAN XI Symposium

Original abstract submittal

S. Mancini, M. Gansterer, C. Triki

SCENARIO
S1
S2
S3

4

MODEL
OF
TIME
493.37170.92
981.988454.01
1960.831 1944.72

MHOF
493.270980.788
1959.333

TIME
20.99
40.89
80.39

Table 1 – Comparison of MODEL and MH performances in solving the SP.
SET
S1
S2
S3

SP
493.371981.988
1960.831

EVPI
0.51%
0.29%
0.34%

U EV P I
2.5
2.8
6.6

VSS
1.63%
2.12%
1.96%

U V SS
7.8
19.6
37.2

Table 2 – Comparison of stochastic indicators for different sets of instances

4

RESULTS AND DISCUSSION

We discuss here some preliminary results, while an extended computational campaign will be presented at theconference. We analyze three set of instances, S1, S2, and S3, containing 10 instances each. Some parameters are
fixed for all instances: 20 customers per demand scenario, 5 capacity scenarios, 5 facilities to open, 30 potential
locations, 5 lockers per facility, and the probability of unavailability for each lockerbox: 10%. The varying
parameter is the number of demand scenarios, which is equal to 5, 10, and 20 in S1, S2, and S3, respectively. In
Table 1 we report the comparison between the mathematical model (MODEL), executed with a time limit of 3600
seconds and the matheuristitc (MH). As clearly shown in the table, MH is able to provide near optimal solutions
for all the three sets of instances. Furthermore, while times required by the exact approach grows exponentiallywith increasing number of scenarios, MH experiences a linear growth.
In Table 2, we report the average solution of the stochastic problem (SP) as well as two classical stochastic
parameters, Expected Value of Perfect Information (EVPI) and the Value of the Stochastic Solution (VSS),
and two problem specific parameters U EV P I and U V SS . The first one, U EV P I , represents the number of homedeliveries that could be avoided having perfect information on the capacity availability. This gives us a measureof the impact of uncertainty. The second one, represents the number of home deliveries that can be avoided if
the stochastic nature of the problem is taken into account. For this, we calculate a benchmark solution, where wefirst solve a deterministic problem assuming full availability of lockerboxes. Then we perform, for each capacity
scenario, the assignment of customers to facilities taking into account the eventual unavailability related to thescenario. This could be seen as the cost of ignoring uncertainty. Despite the rather small values of EVPI and VSS(which represent relative differences), U EV P I and U V SS show considerable impact of uncertainty. This especiallyholds for the larger instances (S3). This means that uncertainty plays a very important role and, therefore, cannot
be ignored. In fact, in S3 considering the uncertainty in capacity availability will help us to save on average 37
home deliveries over a total of 77, which indicates a huge saving in routing costs.

References
Barenji, A.V., Wang, W.M., Li, Z., & Guerra-Zubiaga, D.A. 2019. Intelligent E-commerce logistics platform using hybrid agent based approach. Transportation Research Part E: Logistics and Transportation
Review, 126, 15 – 31.
Cheng, C., Adulyasak, Y., & Rousseau, L.-M. 2021. Robust facility location under demand uncertainty
and facility disruptions. Omega, 103, 102429.
Mancini, S., & Gansterer, M. 2021. Vehicle routing with private and shared delivery locations. Computers
Operations Research, 133, 105361.
Morganti, E., Seidel, S., Blanquart, C., Dablanc, L., & Lenz, B. 2014. The Impact of E-commerce on
Final Deliveries: Alternative Parcel Delivery Services in France and Germany. Transportation Research
Procedia, 4, 178–190.

TRISTAN XI Symposium

Original abstract submittal