# Does Parking Matter? The Impact of Search Time for Parking on Last-Mile
Delivery Optimization

A Preprint

###### Abstract

Parking is a necessary component of traditional last-mile delivery practices,
but finding parking can be difficult. Yet, the routing literature largely does
not account for the need to find parking. In this paper, we address this
challenge of finding parking through the Capacitated Delivery Problem with
Parking (CDPP). Unlike other models in the literature, the CDPP accounts for
the search time for parking in the objective and minimizes the completion time
of the delivery tour. When we restrict the customer geography to a complete
grid, we identify conditions for when a Traveling Salesman Problem (TSP)
solution that parks at each customer is an optimal solution to the CDPP. We
then determine when the search time for parking is large enough for the CDPP
optimal solution to differ from this TSP solution. We also identify model
improvements that allow reasonably-sized instances of the CDPP to be solved
exactly. We introduce a heuristic for the CDPP that quickly finds high quality
solutions to large instances. Computational experiments show that parking
matters in last-mile delivery optimization. The CDPP outperforms industry
practice and models in the literature showing the greatest advantage when the
search time for parking is high. This analysis provides immediate ways to
improve routing in last-mile delivery.

Sara Reed1 | Ann Melissa Campbell2 | Barrett W. Thomas2
---|---|---
<EMAIL_ADDRESS>|<EMAIL_ADDRESS>|<EMAIL_ADDRESS>

1 School of Business, University of Kansas, Lawrence, Kansas

2 Department of Business Analytics, University of Iowa, Iowa City, Iowa

##  1 Introduction

Recent studies find that delivery drivers spend on average 5.8 minutes and 24
minutes searching for each parking spot in Seattle and New York City,
respectively (Dalla Chiara and Goodchild 2020, Holguin-Veras et al. 2016). In
urban environments across the United States, a driver spends on average nine
minutes searching for on-street parking (Cookson and Pishue 2017). Increasing
levels of e-commerce leading to greater demands on delivery drivers further
exacerbates the problem of parking. In New York City, more than 1.5 million
packages need to be delivered every day (Haag and Hu 2019). These volumes are
expected to increase 68% by 2045 (Danigelis 2018). Attempts to improve
productivity in last-mile delivery often explore the use of new technology,
such as drones or autonomous vehicles (Poikonen and Golden 2020, Reed et al.
2021b). However, it may be many years before the deployment of such
technologies, and we need to look for immediate ways to improve last-mile
delivery to handle the exploding demand for such deliveries.

Despite the significant amount of time currently spent looking for parking and
the growing delivery volumes that will increase search times further, the
last-mile routing literature largely ignores the search time for parking in
route planning. However, choosing when and where to park the vehicle is a
choice made by the driver, often without the aid of decision support (Boysen
et al. 2020). Where decision support is available, it is often in the form of
a solution to the Traveling Salesman Problem (TSP) which does not consider
parking. For example, a routing algorithm used by UPS includes a TSP
algorithm, but gives drivers autonomy in making final routing decisions about
where to drive, where to park, and where to walk (Rosenbush and Stevens 2015).
Only recently have modeling choices in the literature started to consider the
need to park the vehicle and the trade-offs between driving and walking in the
last-mile, but these studies are restricted to a set of tight assumptions
(Nguyen et al. 2019, Martinez-Sykora et al. 2020).

In this paper, we examine how including the search time for parking impacts
optimal routing decisions. We model last-mile delivery practices using the
Capacitated Delivery Problem with Parking (CDPP). The CDPP is the problem of
serving a set of customers with a vehicle and delivery person. The delivery
person must park the vehicle to service customers on foot. The carrying
capacity of the delivery person may be restricted based on the number, weight,
or volume of packages. The delivery person must return to the parked vehicle
after making deliveries on foot. Once returned to the vehicle, the delivery
person can load more packages or drive to the next parking spot. Unlike other
vehicle routing problems in the literature, the CDPP accounts for the search
time for parking in the objective when minimizing the completion time of the
delivery tour. In addition, the delivery person in the CDPP can serve multiple
customer sets from the same parking spot.

These generalizations relative to the current literature in last-mile delivery
make the mixed integer programming (MIP) formulation for the CDPP difficult to
solve. To analyze the impact of the search time for parking, we develop new
technology to solve the CDPP to optimality. We exploit structure in optimal
solutions to identify valid inequalities that raise the lower bound of the MIP
and variable reduction techniques that reduce the large number of variables
present in the model. These techniques allow us to solve larger instances than
those present in the literature. For instances that face computational
limitations, we provide a heuristic for the CDPP that finds high quality
solutions quickly.

To understand the impact of considering the search time for parking in routing
decisions, we benchmark the CDPP with multiple other vehicle routing problems.
The simplest comparison is to use the solution to the TSP with respect to
driving times and assume the delivery person parks at every customer. When we
restrict the customer geography to a complete grid, we identify conditions for
when this TSP solution is an optimal solution to the CDPP. Then, we determine
when the search time for parking is large enough for the CDPP optimal solution
to differ from this TSP solution. For experimental comparisons, we benchmark
the CDPP with models that represent current industry practice as well as
recent models in the literature.

The CDPP was introduced as a benchmark in Reed et al. (2021b). This paper is
the first to fully analyze and explore the problem. The contributions of this
paper can be summarized as follows:

  * •

We analyze the first model to include the search time for parking in the
objective function to evaluate the impact of the search time for parking on
last-mile delivery optimization.

  * •

By restricting the customer geography to a complete grid, we identify
conditions under which following a TSP tour of the customers and parking at
each one is an optimal solution to the CDPP as well as the value of the search
time for parking that defines change in the structure of an optimal solution
to the CDPP.

  * •

We contribute to solving the CDPP exactly through valid inequalities and
variable reduction.

  * •

For instances that face computational limitations, we provide a heuristic
solution to the CDPP that finds high quality solutions quickly.

  * •

We provide valuable insights from computational experiments showing when the
consideration of parking in the model makes the greatest impact.

Section 2 reviews the literature specifically addressing the limited work in
vehicle routing that considers the need to park the vehicle. Section 3
discusses the service times, assumptions, and the MIP formulation for the
CDPP. In Section 4, we directly compare the structure of the CDPP solution
with a TSP solution that parks at every customer on a complete grid of
customers, providing conditions for when the solutions are equivalent and the
value of the search time for parking that defines change in the structure of
an optimal solution to the CDPP. Section 5 discusses necessary improvements to
the model to be able to solve reasonably-sized instances. Section 6 provides
the experimental design. In Section 7, we show the effect of the model
improvements on computational performance. Section 8 presents the experimental
results and discusses the impact of considering the search time for parking on
the structure of the solution and the completion time of the delivery tour.
Section 9 provides a heuristic for the CDPP that finds high quality solutions
quickly. Conclusions and future work are discussed in Section 10.

##  2 Literature Review

In this section, we focus on the vehicle routing literature that consider the
need to park the vehicle. We begin by summarizing work that introduced the
CDPP to the literature. The remaining studies in routing of last-mile delivery
do not explicitly consider the search time for parking in the objective
function. Instead, they focus on the trade-offs of walking and driving for the
delivery person and ignore trade-offs between the difficulty to find parking
and other routing decisions.

Reed et al. (2021b) introduce the CDPP as a benchmark to the Capacitated
Autonomous Vehicle Assisted Delivery Problem (CAVADP). To evaluate the impact
of autonomous-assisted delivery in urban environments, Reed et al. (2021b)
solve the CDPP on a complete grid. However, some instances could not be solved
to optimality so the potential sets of customers were restricted to reduce the
number of variables. An optimal solution to the CDPP on a complete grid is
shown to follow a linear trend in the number of customers. Reed et al. (2021a)
use the CDPP as a benchmark when exploring the CAVADP on a general graph to
represent urban to rural settings. These papers use the CDPP as a benchmark
and do not explore the CDPP beyond stating and modeling the problem. In this
paper, we present model improvements to the CDPP and focus on the impact of
including the search time for parking in the objective function. The
conclusions of this paper support the use of the CDPP as a benchmark problem
to represent delivery practices where the delivery person must park the
vehicle prior to servicing customers on foot. Further, while the CAVADP shows
great promise for autonomous-assisted delivery, it may be many years before
the deployment of such technologies. The analysis of this paper provides
immediate ways to improve routing in last-mile delivery.

The closest problem to the CDPP is the two-echelon last-mile delivery system
introduced by Martinez-Sykora et al. (2020). In this system, the decisions are
the locations where the vehicle will park, the locations visited by the
delivery person on foot, and the order of delivery locations in both the
driving and walking routes. The carrying capacity of the delivery person
restricts the volume and weight of packages in a customer set. Martinez-Sykora
et al. (2020) also require that one node within each customer set be
designated as the parking location. A generalization for the CDPP relative to
Martinez-Sykora et al. (2020) is the ability to serve multiple customer
service sets from the same parking spot. In addition, this paper provides a
model formulation for the CDPP that allows the parking locations to differ
from customer locations. Martinez-Sykora et al. (2020) include the clustering
of customers as a decision in the optimization problem, but do not include the
search time for parking in the objective function. Instead, the objective is a
weighted sum of the driving time and walking time for the delivery person.
This paper uses the objective function of Martinez-Sykora et al. (2020) to
benchmark the objective function in the CDPP. Comparing the solutions with the
objective value in Martinez-Sykora et al. (2020) to the solutions using an
objective value that includes the search time for parking highlights the
impact of the search time for parking on optimal routing decisions. Martinez-
Sykora et al. (2020) use a branch-and-cut algorithm to solve instances up to
30 customers. This paper introduces model improvements for the CDPP to solve
larger instances than the instances in Martinez-Sykora et al. (2020).

Nguyen et al. (2019) define a two-level clustered routing problem to
distinguish between the driving route and walking routes of the delivery
person. Service time to customers is restricted by time windows. The grouping
of customers is an input to the model. Two different partitions of customers
are considered: one based on observations of drivers from a case study in
London and one based on geographical proximity. Each cluster is required to
have a parking location within the cluster. The CDPP generalizes this approach
by making the partition of customers and the parking locations optimization
decisions. In addition, the CDPP allows multiple service sets from the same
parking spot. The optimization decisions in Nguyen et al. (2019) are to select
the parking location in each cluster, route the vehicle between the parking
locations and depot, and route the walking of the delivery person in each
cluster. These decisions capture the delivery person’s walk back to the
parking location but fail to capture the advantages of serving more than one
customer set per parking location if the search time for parking is high.
Nguyen et al. (2019) solve the mixed integer programming formulation for the
case study in London and observe that optimizing with respect to time windows
can reduce total operation time. However, the search time for parking is not
considered in the operation time. We leave the consideration of time windows
in the CDPP for future work and focus this paper on the impact that the search
time for parking has on the total time of the delivery tour and the structure
of the solution.

More generally, the CDPP can be related to the two-echelon routing problem. In
the application of last-mile delivery, one echelon refers to the driving route
and the second echelon refers to the walking routes of the delivery person.
Cuda et al. (2015) provide a survey on two-echelon routing problems. The
single truck-and-trailer routing problem with satellite depots (STTRPSD) is
similar to the CDPP with the trailer representing the vehicle and the truck
representing the delivery person. The truck and trailer are routed on a subset
of the satellites (i.e. parking locations for the CDPP) and then the customers
are visited from the truck (i.e. delivery person) with routes at each
satellite. Belenguer et al. (2016) present a branch-and-cut algorithm to solve
the STTRPSD. Belenguer et al. (2016) solve all instances up to 50 customers to
optimality and solve 100 to 200 customers to an average optimality gap of
3.02%. The test instances consider at most 10 satellites with 25 to 50
customers and at most 20 satellites with 100 to 200 customers. In our case, we
consider all customer locations to be available parking spots (i.e. satellite
locations) significantly increasing the size of the model. Therefore, we
introduce necessary model improvements to be able to solve the CDPP to
optimality. These model improvements may have application in the truck-and-
trailer routing problem.

Unlike the STTRPSD and other two-echelon models for last-mile delivery, the
CDPP considers a search time in finding a parking location. This feature
aligns the CDPP with the two-echelon capacitated location-routing problem
(2E-CLRP) where an opening cost is associated with the satellites (i.e.
parking locations). Boccia et al. (2011) present three mixed integer
programming formulations for the 2E-CLRP. The 2E-CLRP considers two different
fleets of vehicles for first-level and second-level trips, connected by the
satellites for transshipment operations. Therefore, the 2E-CLRP can decompose
into two different capacitated location routing problems (Contardo et al.
2012). However, in the CDPP, there exists a dependence between the two levels.
The vehicle must remain at the parking spot on the first-level route while the
delivery person serves potentially multiple second-level routes on foot. In
addition, the travel times in the two levels differ and we capture these
differences by using real-world data for the driving times and walking times
between customers. For the application of last-mile delivery, the CDPP
balances the trade-offs of the delivery person walking and driving to find a
new parking location, so differing travel times influence the solution
structure. Nguyen et al. (2012a) and Nguyen et al. (2012b) propose
metaheuristic approaches to solve the 2E-CLRP. The heuristic solution proposed
in this paper may be applicable to other problems that align with the 2E-CLRP
where there is a dependence between the two echelons.

Another line of research uses simulation to model parking availability and the
impacts on commercial vehicle parking behavior (Lopez et al. 2019, Nourinejad
et al. 2014). Figliozzi and Tipagornwong (2017) combine queuing and logistical
models to model parking availability but use continuous approximation models
to estimate routing constraints. These papers show that parking has an impact
on operations, but still do not consider parking in the routing optimization.
In this paper, we argue the search time for parking makes a significant impact
on the routing optimization.

##  3 CDPP

In this section, we detail the service times, assumptions, and MIP for the
CDPP. Section 3.1 defines the problem and provides notation for the parameters
and service times. Then, Section 3.2 provides the MIP formulation.

###  3.1 Problem Description and Notation

The CDPP serves a set of $n$ customers in a set $C$ by a delivery person with
a vehicle. The delivery person and vehicle start and end the tour at the
depot, denoted as $0$. The delivery person must park the vehicle to service
customers on foot. Let $\Pi$ be the set of parking locations and depot. The
search time for parking at parking location $i\in\Pi\setminus\\{0\\}$ is
$p_{i}$ minutes. Once parked, the delivery person services a set of customers
on foot. After servicing a customer set on foot, the delivery person returns
to the parked vehicle. The delivery person can serve another set of customers
from this parking spot or move to a different parking spot (e.g. $k\in\Pi$)
incurring a search time for parking of $p_{k}$ minutes.

Each customer $i$ requires a single package delivery with weight $\psi_{i}$
and volume $v_{i}$. Multiple customer nodes at the same customer location may
represent a single customer ordering multiple packages. Let $S$ be the set of
potential customer service sets. The capacity of the delivery person may
restrict the number of packages, weight, or volume of the service sets in $S$.
For example, if the delivery person can service at most $q$ packages at a
time, then $|\sigma_{j}|\leq q$ for all sets $\sigma_{j}\in S$. Similarly, if
the delivery can service at most $\Psi$ in weight or $V$ in volume, then
$\sum_{i\in\sigma_{j}}\psi_{i}\leq\Psi$ or $\sum_{i\in\sigma_{j}}v_{i}\leq V$,
respectively, for all sets $\sigma_{j}\in S$. For each $i\in C$, let
$J_{i}=\\{\sigma_{j}\in S|i\in\sigma_{j}\\}$ be the set of customer service
sets that includes customer $i$. Define $I_{ij}=1$ if $\sigma_{j}\in J_{i}$
for all $i\in C$ and $\sigma_{j}\in S$, and 0 otherwise. Table 1 summarizes
the parameters for the CDPP.

Notation | Description
---|---
$n$ | Number of customers
$C$ | Set of customer locations
$S$ | Set of customer service sets
$\Pi$ | Set of parking locations and depot
$p_{i}$ | Expected search time for parking at parking location $i\in\Pi$ (minutes)
$q$ | Capacity of delivery person (number of packages)
$\Psi$ | Weight capacity of delivery person
$\psi_{i}$ | Weight of package for customer $i\in C$
$V$ | Volume capacity of delivery person
$v_{i}$ | Weight of package for customer $i\in C$
$J_{i}$ | Set of customer sets that include customer $i$ for $i\in C$
$I_{ij}$ | Indicator variable that customer $i$ is in service set $\sigma_{j}$ for $i\in C,\sigma_{j}\in S$
Table 1: Set of parameters.

The service times require more detail in their definition. Table 2 summarizes
the service times for the CDPP. Let $D(i,k)$ be the time to drive between
locations $i$ and $k$ for $i,k\in\Pi$. We assume driving times satisfy the
triangle inequality. Let $d_{ik}$ be the time to drive from location $i$ to
location $k$ and park at $k$. Then, $d_{ik}=D(i,k)+p_{k}$ for $i,k\in\Pi$ such
that $i\neq k$. In the case where $k=0$ (i.e. the return to the depot), the
vehicle does not need to search for parking and $d_{i0}=D(i,0)$ for all
$i\in\Pi\setminus\\{0\\}$.

Let $W(i,k)$ be the time to walk between locations $i$ and $k$ for $i,k\in
C\cup\Pi\setminus\\{0\\}$. We assume walking times satisfy the triangle
inequality. Let $w_{ij}$ be the shortest walking time to service set
$\sigma_{j}$ when parked at parking location $i$ for
$i\in\Pi\setminus\\{0\\},\sigma_{j}\in S$. This walking time is the shortest
walk from parking location $i$ to the first customer to be served in set
$\sigma_{j}$, the walk between customers in $\sigma_{j}$, and the walk back to
customer $i$ where the vehicle is parked. For the pair
$(i,\sigma_{j})\in\Pi\setminus\\{0\\}\times S$, let
$(c_{1},c_{2},...,c_{|\sigma_{j}|})$ be an optimal order to serve $\sigma_{j}$
when parked at $i$. Then,
$w_{ij}=W(i,c_{1})+W(c_{1},c_{2})+\cdots+W(c_{|\sigma_{j}|-1},c_{|\sigma_{j}|})+W(c_{|\sigma_{j}|},i)$.

Let $f_{j}$ be the time to load package(s) to service set $\sigma_{j}$. We
consider a loading time linearly dependent on the number of packages in the
service set, i.e. $f_{j}=f\cdot|\sigma_{j}|$ for some $f\geq 0$. Therefore,
the total loading time in the delivery tour is a constant $nf$, and the
solution to the CDPP is equivalent to the solution when $f_{j}\equiv 0$ or
$f=0$.

Notation | Description
---|---
$D(i,k)$ | Time to drive from $i$ to $k$ for $i,k\in\Pi$ (min)
$d_{ik}$ | Time to drive from $i$ to $k$ and park at $k$ for $i\in\Pi,k\in\Pi\setminus\\{0\\}$ such that $i\neq k$ (min)
$d_{i0}$ | Time to drive from parking location $i$ to depot for $i\in\Pi\setminus\\{0\\}$ (min)
$W(i,k)$ | Time to walk from $i$ to $k$ for $i,k\in C\cup\Pi\setminus\\{0\\}$ (min)
$w_{ij}$ | Time to walk and serve set $\sigma_{j}$ while parked at location $i$ for $i\in\Pi\setminus\\{0\\}$, $\sigma_{j}\in S$ (min)
$f$ | Time to load one package (min)
$f_{j}$ | Time to load packages for customer set $\sigma_{j}$ for $\sigma_{j}\in S$ (min)
Table 2: Definition of service times in CDPP.

###  3.2 MIP Formulation

Reed et al. (2021b) introduce a variant of the CDPP presented here and provide
a MIP formulation. Reed et al. (2021b) take $f_{j}\equiv g$ for some constant
$g\geq 0$. For the purposes of clarity and updated notation, we provide the
general formulation here. We also adapt single commodity subtour elimination
constraints, as opposed to the adapted MTZ subtour elimination constraints
presented in Reed et al. (2021b). Table 3 summarizes the decision variables
for the model.

Notation | Description
---|---
$x_{ik}$ |  $x_{ik}=1$ if the vehicle drives from $i$ to $k$ and parks at parking location $k$ (if $k\neq 0$) for
|  $i,k\in\Pi$ such that $i\neq k$
$y_{ij}$ |  $y_{ij}=1$ if the delivery person is parked at parking location $i$ and serves set $\sigma_{j}$
| for $i\in\Pi$ and $\sigma_{j}\in S$
$v_{ik}$ | Flow of packages from location $i$ to location $k$ for $i\in\Pi$ and $k\in\Pi\setminus\\{0\\}$ such that $i\neq k$
Table 3: Set of decision variables in CDPP.

$\displaystyle\min$
$\displaystyle\sum_{i\in\Pi}\sum_{k\in\Pi\setminus\\{i\\}}x_{ik}d_{ik}+\sum_{i\in\Pi\setminus\\{0\\}}\sum_{\sigma_{j}\in
S}y_{ij}(w_{ij}+f_{j})$ (1) s.t. $\displaystyle\sum_{i\in\Pi}x_{0i}=1$ (2)
$\displaystyle\sum_{i\in\Pi}x_{i0}=1$ (3)
$\displaystyle\sum_{k\in\Pi\setminus\\{0\\}}\sum_{\sigma_{j}\in
J_{i}}y_{kj}=1$ $\displaystyle\forall i\in C$ (4)
$\displaystyle\sum_{k\in\Pi}\setminus\\{i\\}x_{ki}=\sum_{k\in\Pi\setminus\\{i\\}}x_{ik}$
$\displaystyle\forall i\in\Pi\setminus\\{0\\}$ (5) $\displaystyle
y_{ij}\leq\sum_{k\in\Pi\setminus\\{i\\}}x_{ki}$ $\displaystyle\forall
i\in\Pi\setminus\\{0\\},\sigma_{j}\in S$ (6)
$\displaystyle\sum_{i\in\Pi\setminus\\{0\\}}v_{0i}=n$ (7) $\displaystyle
v_{ik}\leq n\cdot x_{ik}$ $\displaystyle\forall
i\in\Pi,k\in\Pi\setminus\\{0\\}\textrm{ s.t. }i\neq k$ (8)
$\displaystyle\sum_{k\in\Pi\setminus\\{i\\}}v_{ki}-\sum_{k\in\Pi\setminus\\{0,i\\}}v_{ik}=\sum_{\sigma_{j}\in
S}|\sigma_{j}|y_{ij}$ $\displaystyle\forall i\in\Pi$ (9) $\displaystyle
v_{ik}\in\mathbb{Z}_{+}$ $\displaystyle\forall
i\in\Pi,k\in\Pi\setminus\\{0\\}\textrm{ s.t. }i\neq k$ (10) $\displaystyle
x_{ik}\in\\{0,1\\}$ $\displaystyle\forall i,k\in\Pi\textrm{ s.t. }i\neq k$
(11) $\displaystyle y_{ij}\in\\{0,1\\}$ $\displaystyle\forall
i\in\Pi\setminus\\{0\\},\sigma_{j}\in S$ (12)

The objective function in Equation (1) minimizes the completion time of the
delivery tour. The first term includes the driving time and search time for
parking. The second term is the walking and service time for the delivery
person. Constraints (2) and (3) require the vehicle to leave from the depot
and return to the depot, respectively. Constraints (4) require that each
customer is served in a service set. When the delivery person parks at a
parking location, Constraints (5) ensure that the vehicle leaves that parking
location. Given that the delivery person services set $\sigma_{j}$ when parked
at parking location $i$ (i.e. $y_{ij}=1$), Constraints (6) require the vehicle
to drive to and park at location $i$. Constraints (7)-(10) provide the adapted
single commodity subtour elimination constraints. Constraints (7) and (8)
ensure $n$ packages flow through the network. While at parking location $i$,
the flow should change by the number of customers in all service sets served
from parking spot $i$. Constraints (9) capture the change in flow. The integer
constraints on the $v_{ik}$ variables are given in Constraints (10). Finally,
the binary constraints on variables $x_{ik}$ and $y_{ij}$ are given in
Constraints (11) and (12), respectively.

##  4 When is the TSP optimal?

A TSP solution parking at every customer location is a feasible solution to
the CDPP. Because driving is often faster than walking, this TSP solution may
be optimal if the search time for parking is low, particularly when customers
are further apart. However, when customers are close together, a small search
time for parking may make it advantageous for the delivery person to
consolidate packages into larger customer service sets to reduce the number of
times the delivery person searches for parking. Therefore, we expect the
density of customer locations in combination with the search time for parking
to impact the structure of the CDPP solution.

In this section, we identify when a TSP solution parking at every customer
location is optimal for the CDPP. We analyze the trade-offs between the
density of customers and the search time for parking by considering a complete
grid of customers and determining when the search time for parking is large
enough that an optimal solution to the CDPP is no longer this TSP solution.
For the purpose of this analysis, we restrict the setting to a
$\sqrt{n}\times\sqrt{n}$ complete grid of $n$ customers where $\sqrt{n}$ is
even. We assume $\Pi=C\cup 0$ and take $p_{k}=p$ for all
$k\in\Pi\setminus\\{0\\}$. Let $\hat{d}$ be the time to drive a unit and
$\hat{w}$ be the time to walk a unit where $\hat{d}\leq\hat{w}$. The length of
a block is $\hat{l}$ units. The capacity of the delivery person is based on
the number of packages $q$ assuming that each customer has a single package.
Let $(0,0)$ represent the location of the depot with the bottom left corner of
the grid at $(1,1)$, bottom right corner at $(\sqrt{n},1)$, top left corner at
$(1,\sqrt{n})$, and top right corner at $(\sqrt{n},\sqrt{n})$.

We first contemplate the case of a TSP tour through the set of customer
locations parking at every customer. Figure 1 shows an example of this TSP
solution on a $6\times 6$ grid of customers. The black square indicates the
location of the depot and circles represent the customer locations. The solid
blue lines represent the path of the vehicle. A red square designates the
customer location as a parking spot. Lemma 1 characterizes the completion time
of a TSP tour through the grid parking at every customer. The result follows
from the analysis in Reed et al. (2021b).

######  Lemma 1.

Consider a TSP solution where the delivery person parks at every customer
location. The objective value for this solution on a $\sqrt{n}\times\sqrt{n}$
complete grid of customers when $\sqrt{n}$ is even is

$\displaystyle(2\cdot MinDistance+n)\hat{d}\hat{l}+nf+np$ (13)

where $MinDistance=\min_{c\in C}D(0,c)$ is the minimum distance between the
depot and grid.

Figure 1: An example of the TSP solution parking at every customer on a
$6\times 6$ grid of customers.

Next, we identify nonzero search times for parking where an optimal solution
to the CDPP is this TSP solution parking at every customer location. We also
determine when $p$ becomes large enough that this TSP solution is not optimal.
Claim 1 summarizes these results when $q\leq 2$. This and all other proofs can
be found in Appendix A.

######  Claim 1.

Assume $q\leq 2$. Then,

  1. (a)

if $p\leq\hat{l}(2\hat{w}-\hat{d})$, then an optimal solution to the CDPP is a
TSP solution parking at every customer;

  2. (b)

if $p>\hat{l}(2\hat{w}-\hat{d})$, then a TSP solution parking at every
customer is not an optimal solution to the CDPP.

Increasing the capacity of the delivery person to $q=3$ packages allows for
gains from consolidating customers into service sets at lower search times for
parking than identified in Claim 1. Claim 1 finds a threshold of
$p=\hat{l}(2\hat{w}-\hat{d})$ for the solution structure of the CDPP to
change. When $q=3$, Claim 2 reduces this threshold to
$p=\hat{l}(\frac{4}{3}\hat{w}-\hat{d})$.

######  Claim 2.

Assume $q=3$. Then,

  1. (a)

if $p\leq\hat{l}(\frac{4}{3}\hat{w}-\hat{d})$, then an optimal solution to the
CDPP is a TSP solution parking at every customer;

  2. (b)

if $p>\hat{l}(\frac{4}{3}\hat{w}-\hat{d})$, then a TSP solution parking at
every customer is not an optimal solution to the CDPP.

Now, we discuss the implications of Claims 1 and 2 on optimal routing decision
for last-mile delivery. In both claims, the value of $\hat{l}$, and thus the
density of customers, plays a crucial role in determining the structure of the
optimal solution to the CDPP. For this analysis, we consider grids
representing urban-to-rural settings. We estimate the parameters from the
instances presented in Reed et al. (2021a). We take $\hat{l}=0.07$ miles and
$\hat{l}=0.29$ miles for urban and rural environments, respectively. We
estimate $\hat{d}=12.5$ min/mi and $\hat{w}=20$ min/mi based on the driving
time and walking time, respectively, in Reed et al. (2021b).

Figure 2 shows the value of the search time for parking $p$ that defines
change in the structure of an optimal solution to the CDPP when $q\leq 2$ and
$q=3$. In urban environments, when customers are closer together, small values
for the search time for parking impact the structure of the CDPP solution. If
$p>1$ minute, a TSP solution parking at every customer location is not an
optimal solution to the CDPP. In an empirical study, Dalla Chiara and
Goodchild (2020) find that delivery drivers spend on average 5.8 minutes
searching for each parking spot in Seattle. This parking time suggests that
productivity gains can be achieved in urban environments by considering the
search time for parking in routing decisions. In lower density areas, like
rural environments, Figure 2 shows that the search time for parking must be
higher to change the structure of the optimal solution from a TSP solution
parking at every customer. We also expect the driving speed in rural areas to
be greater than in urban areas. A higher driving speed produces higher values
of $p$ in Claims 1 and 2 further supporting that a TSP solution parking at
every customer remains optimal for higher values of $p$ in low density areas.
In Section 8, our experimental results indicate that a TSP solution parking at
every customer best approximates optimal solutions to the CDPP in rural
environments.

Figure 2: The value of the search time for parking $p$ that determines the
optimality of the TSP solution parking at every customer location for the
CDPP.

##  5 Model Improvements

In this section, we develop a series of inequalities and variable reduction
techniques that allow us to much more effectively solve the CDPP. Section 7
evaluates the impact of these model improvements on computational performance.
Appendix B provides model improvements that apply to alternative assumptions
regarding the loading time function $f_{j}$.

The delivery person must park the vehicle in order to service customers on
foot. The parking locations and what customer sets to serve from each parking
spot are decisions in the optimization problem. If the delivery person parks
at customer location $i\in\Pi\cap C$, Claim 3 identifies that one of the
customer sets will include customer $i$. Recall that the solution to the CDPP
when $f_{j}=f\cdot|\sigma_{j}|$ for some $f\geq 0$ is equivalent to when
$f=0$. To simplify the proofs in this section, we show the results for $f=0$.

######  Claim 3.

If the delivery person parks at $i\in\Pi\cap C$ (i.e. $x_{ki}=1$ for some
$k\in\Pi\setminus\\{i\\}$), then there exists $\sigma_{j}\in J_{i}$ such that
$y_{ij}=1$, i.e.

$\displaystyle\sum_{k\in\Pi\setminus\\{i\\}}x_{ki}=\sum_{j\in J_{i}}y_{ij}$
$\displaystyle\forall i\in\Pi\cap C.$ (14)

Claim 3 shows that when the vehicle parks at the location of customer
$i\in\Pi\cap C$, one of the service sets at that parking location includes
customer $i$. In particular, there exists an optimal solution where customer
$i$ is served alone while parked at the location of customer $i$. Claim 4
formalizes this observation.

######  Claim 4.

For $i\in\Pi\cap C$, let $\sigma_{j_{i}}=\\{i\\}$. There exists an optimal
solution where $y_{ij_{i}}=1$ for each parking location $i\in\Pi\cap C$ (i.e.
$x_{ki}=1$ for some $k\in\Pi\setminus\\{i\\}$), i.e.

$\displaystyle\sum_{k\in\Pi\setminus\\{i\\}}x_{ki}=y_{ij_{i}}$
$\displaystyle\forall i\in\Pi\cap C.$ (15)

To strengthen Claim 4, we sum over all customers in set $\Pi\cap C$ in
Equation (15). If $\Pi=C$, then we conclude the number of parking spots is
equal to the number of singleton customers serviced while parked at its
location. Corollary 4.1 provides the strengthened result.

######  Corollary 4.1.

$\displaystyle\sum_{i\in\Pi\cap
C}\sum_{k\in\Pi\setminus\\{i\\}}x_{ki}=\sum_{i\in\Pi\cap C}y_{ij_{i}}.$ (16)

We also use Claim 4 to identify variables that will not be used in an optimal
solution and may be removed from the MIP in Section 3.2. If the vehicle parks
at customer $i$, Claim 4 concludes $\sigma_{j_{i}}=\\{i\\}$ is serviced.
Constraints (6) restrict each customer to be in exactly one service set.
Therefore, any other set that includes $i$ will not be serviced while the
vehicle is parked at customer $i$. Corollary 4.2 formalizes this result.

######  Corollary 4.2.

For all $i\in\Pi\cap C$, $y_{ij}=0$ for all $\sigma_{j}\in\\{\sigma_{j}\in
J_{i}|\textrm{ }|\sigma_{j}|\geq 2\\}$.

##  6 Experimental Design

In this section, we introduce the test instances and experimental design. The
integer programming model for the CDPP is implemented in Python 3.7.0 using
the Gurobi 9.0.0 solver with a 32 thread count on the University of Iowa’s
Argon high performance computing cluster (Johnson 2021).

To explore the impact of the search time for parking in all customer
geographies, we use the test instances for the case study of Illinois that
represent urban to rural settings as described in Reed et al. (2021a). In
particular, we use Cook County, Adams County, and Cumberland County to
represent urban, suburban, and rural environments, respectively, based on the
classification of the United States Department of Agriculture (USDA 2013). We
evaluate ten instances of $n=50$ customers for each county. The test instances
include real-world data for the driving times and walking times between
customers (Reed et al. 2021c). To test the computational performance on larger
instances, we generate five instances in each of Cook, Adams, and Cumberland
counties for $n=100$ following the procedure of Reed et al. (2021a). All test
instances are posted at: https://doi.org/10.25820/data.006124.

We restrict the parking locations of the vehicle to all customer locations
(i.e. $\Pi=C\cup\\{0\\}$.) We vary the search time for parking in each type of
customer geography (i.e. urban, suburban, and rural) as parking poses a
greater challenge in urban environments than rural environments. Within each
geography, we consider a search time for parking $p$ independent of the
parking location (i.e. for all $k\in\Pi\setminus\\{0\\}$, $p_{k}=p$ for some
$p\geq 0$.) Doing so allows us to isolate the impact of the search time for
parking on optimal routing decisions in different geographies. Like Reed et
al. (2021a), we use $p=9$ minutes in Cook County, $p=5$ minutes in Adams
County, and $p=1$ minute in Cumberland County as our base case. These values
reflect location-dependent parking times where a higher search time for
parking is realized in urban environments compared to rural environments. For
each county, we also experiment with smaller values of $p$ to understand how
including the search time for parking changes the structure of the solution in
the CDPP. For Cook County, we experiment with $p=0,3$ and $6$ minutes. For
Adams County, we include experiments with $p=0$ and $3$ minutes. For
Cumberland County, we also consider $p=0$.

We choose the parameter values for the capacity of the delivery person $q$ and
the time to load a package $f$ based on observations in the literature. A
study of last-mile delivery in London finds that a delivery person delivers 3
packages on average per stop (Allen et al. 2018). Therefore, we consider a
carrying capacity based on the number of packages $q$ and use $q=3$ packages
in our base case. We experiment with capacities of 1 to 4 packages. The
average delivery time for a package is estimated to be between 2.5–4.1 minutes
(Allen et al. 2018, Simoni et al. 2019, Zhang et al. 2018). This time often
includes multiple delivery activities. Allen et al. (2018) observe 4.1 minutes
of service time per customer where this estimate includes the time spent
unloading the package, walking to the customer, and gaining proof-of-delivery.
Nguyen et al. (2019) estimate a one minute walking time allowance and one
minute consignee service time. Combining the estimates of Allen et al. (2018)
and Nguyen et al. (2019), we assume the time to unload a package is 2.1
minutes in our base case.

##  7 Computational Performance

In this section, we show the impact of the model improvements in Section 5 on
computational performance. For this analysis, we use the first five instances
of $n=50$ customers for each county. We consider the base case ($q=3$ packages
and location-dependent parking times). Since we assume a loading time linearly
dependent on the number of packages, the total loading time is a constant and
it is sufficient to solve the MIP with $f=0$.

First, we focus on the valid inequalities introduced in Claim 4 and Corollary
4.1. Table 4 provides the average linear program (LP) relaxation bound at the
root node and the average runtime (in minutes). The second column of Table 4,
labeled LP, gives the average LP bound for the MIP in Section 3.2. The third
column in Table 4, labeled Claim 4, gives the average LP bound of the MIP
including the valid inequalities in Claim 4. The results show that Claim 4
raises the LP bound on average 5.3%, 7.8%, and 3.7% for Cook, Adams, and
Cumberland counties, respectively. Corollary 4.1 relies on the results of
Claim 4. On average, the fourth and fifth columns of Table 4, labeled
Corollary 4.1 and Both respectively, show no further increase in the LP bound
by including the valid inequality presented in Corollary 4.1.

| LP Bound | Runtime (min)
---|---|---
County | LP | Claim 4 | Corollary 4.1 | Both | MIP | Claim 4 | Corollary 4.1 | Both
Cook | 128.2 | 135.0 | 135.0 | 135.0 | 88.2 | 20.8 | 35.2 | 19.8
Adams | 114.8 | 123.7 | 123.7 | 123.7 | 68.3 | 18.5 | 22.6 | 18.0
Cumberland | 63.4 | 65.7 | 65.7 | 65.7 | 39.1 | 11.2 | 16.1 | 11.2
Table 4: LP bound and runtime (minutes) using the valid inequalities in
Section 5 in the base case and $f=0$.

The valid inequalities significantly reduce the runtime. The sixth column of
Table 4, labeled MIP (min), gives the average runtime for the MIP in Section
3.2. The seventh and eighth columns in Table 4 give the average runtime of the
MIP including the valid inequalities in Claim 4 and Corollary 4.1,
respectively. The results show that Claim 4 improves the runtime on average
76.4%, 72.9%, and 71.3% for Cook, Adams, and Cumberland counties,
respectively. Corollary 4.1 improves the runtime on average 60.1%, 64.4%, and
58.8% for Cook, Adams, and Cumberland counties, respectively. The eighth
column in Table 4 shows the average runtime of the MIP using both valid
inequalities. On average, used together, Claim 4 and Corollary 4.1 improve the
runtime on average 77.5%, 73.6%, and 71.4% for Cook, Adams, and Cumberland
counties, respectively, relative to the MIP presented in Section 3.2. In
summary, these valid inequalities significantly improve the run time across
all counties, and present a greater impact on urban instances that have a
higher search time for parking.

Next, we discuss the variable reduction technique identified in Corollary 4.2.
Table 5 provides details on the number of $y_{ij}$ variables present in the
model with and without the variable reduction identified in Corollary 4.2 for
various capacities of the delivery person $q$. Let $Y=\\{y_{ij}|i\in
C,\sigma_{j}\in S\\}$ be the set of $y_{ij}$ variables for a given instance of
the model presented in Section 3.2. Recall that we consider all service sets
of size at most $q$ packages. The second column of Table 5 gives
$|Y|=n\sum_{i=1}^{q}\binom{n}{q}$. For each $i\in C$, define
$\bar{J}_{i}=\\{\sigma_{j}\in J_{i}|\textrm{ }|\sigma_{j}|\geq 2\\}$ to be the
service sets identified by Corollary 4.2 that will not be serviced while
parked at customer $i$. Then, let
$\bar{Y}_{i}=\\{y_{ij}|\sigma_{j}\in\bar{J}_{i}\\}$ represent the variables
identified by Corollary 4.2 that can be removed from the model with respect to
parking at customer $i$. In total, Corollary 4.2 removes the variables
$\bar{Y}=\cup_{i\in C}\bar{Y}_{i}$ from the model. Let
$\hat{Y}=Y\setminus\bar{Y}$ be the remaining variables in the model. The third
and fourth columns of Table 5 give the remaining number of variables
$|\hat{Y}|$ and the percent reduction in $y_{ij}$ variables. In the base case
of $q=3$ packages, Corollary 4.2 reduces the number of $y_{ij}$ variables by
5.9%. This reduction in variables also reduces the number of Constraints (6).
As capacity $q$ increases, the percent reduction in $y_{ij}$ variables
increases. However, the number of $y_{ij}$ variables $|\hat{Y}|$ grows at a
much greater rate making it more difficult to solve instances of larger
capacity. We further discuss the computational limitations with respect to
capacity in Section 9.

$q$ | $|Y|$ | $|\hat{Y}|$ | Percent Reduction in $y_{ij}$ Variables
---|---|---|---
1 | 2,500 | 2,500 | 0.0%
2 | 63,750 | 61,300 | 3.8%
3 | 1,043,750 | 982,500 | 5.9%
4 | 12,558,750 | 11,576,300 | 7.8%
Table 5: Variable reduction results of Corollary 4.2 for $n=50$ and various
capacities $q$ (packages).

Table 6 provides the average runtime (in minutes) of the MIP with and without
the variable reduction technique in Corollary 4.2. The second column of Table
6 gives the average runtime for the MIP in Section 3.2 using all variables in
$Y$. The third column of Table 6 gives the average runtime under the reduced
$y_{ij}$ variables in $\hat{Y}$. Reducing the number of $y_{ij}$ variables
improves the runtime on average 47.8%, 69.9%, and 61.7% for Cook, Adams, and
Cumberland counties, respectively. The fourth column of Table 6 gives the
average runtime under the reduced $y_{ij}$ variables in $\hat{Y}$ and the
valid inequalities (i.e. Claim 4 and Corollary 4.1). Including the variable
reduction technique further improves the impact of the valid inequalities on
run time. Reducing the number of $y_{ij}$ variables further improves the
runtime on average 25.4%, 26.3%, and 35.0% for Cook, Adams, and Cumberland
counties, respectively, relative to the MIP with valid inequalities (presented
in the ninth column of Table 4). In summary, Corollary 4.2 significantly
improves the runtime across all customer geographies.

| Runtime (min)
---|---
County |  $Y$& no VIs |  $\hat{Y}$ & no VIs |  $\hat{Y}$ & VIs
Cook | 88.2 | 46.0 | 14.8
Adams | 68.3 | 20.5 | 13.3
Cumberland | 39.1 | 15.0 | 7.3
Table 6: Computational results from the variable reduction of Corollary 4.2 in
the base case and $f=0$.

##  8 Experimental Results

In this section, we explore the impact of including the search time for
parking in optimal routing decisions on the structure of the solution and the
completion time of the delivery tour. Section 8.1 introduces benchmarks to the
CDPP that reflect current industry practice as well as recent models in the
literature. Section 8.2 summarizes the differences between the CDPP and
benchmark solutions in the base case (location-dependent parking times, $q=3$
packages, and $f=2.1$ minutes). Then, Sections 8.3 and 8.4 discuss the impact
of the search time for parking and capacity of the delivery person,
respectively, on the structure of the CDPP solution.

###  8.1 Benchmarks

We introduce three benchmarks to the CDPP and use these benchmarks to
highlight why including the search time for parking matters in routing
optimization for last-mile delivery.

####  8.1.1 No parking time

For this benchmark, we solve the CDPP with $p=0$ to show how including the
search time for parking changes the structure of the solution. When we
restrict the customer geography to a complete grid of customers, Claims 1 and
2 show an optimal solution to the CDPP when $p=0$ is a TSP solution parking at
every customer. On a general customer geography, Reed (2021) shows that this
conclusion holds if driving between customers is always faster than walking.
Let $v$ be the optimal value of the CDPP when $p=0$ and $s$ be the number of
times the vehicle parks in the respective optimal solution. Then, the
completion time with a solution of this benchmark is $v+sp$ minutes.

####  8.1.2 Modified TSP

The routing algorithm for UPS provides the driver a solution based on a TSP
algorithm (Rosenbush and Stevens 2015). The driver has autonomy to make the
final routing decisions including where the delivery person will walk and
where he/she will drive. To model this real-life practice, we use a TSP
solution to fix the order of service. To reflect choices made by the driver
and allow service to customers on foot, we transform this TSP solution to take
into account the trade-offs between the search time for parking, driving time,
and walking time.

This benchmark, hereafter called the Modified TSP, is a route-first cluster-
second method to optimize the trade-offs of walking, driving, and searching
for parking given a fixed customer order. A TSP solution with respect to
driving times fixes the order of customer service. We generate potential
service sets based on this order and restrict the size of the service set
based on the capacity of the delivery person $q$. In addition, we allow the
delivery person to serve multiple customer service sets from the same parking
spot while maintaining the order of customer service. We implement this
benchmark by restricting the sets of driving variables $x_{ik}$ and service
variables $y_{ij}$ in the CDPP. We update the walking service time $w_{ij}$ to
maintain the order of service. We use the objective function in Equation (1)
to minimize the completion time of the delivery tour and capture the impact of
the search time for parking on the driver’s decision making.

####  8.1.3 Relaxed M-S

One of the limitations in the models presented by Nguyen et al. (2019) and
Martinez-Sykora et al. (2020) is that both require a parking location in every
customer set. Unlike Nguyen et al. (2019), Martinez-Sykora et al. (2020)
include the clustering of customers as a decision in the optimization problem.
To benchmark the CDPP with the literature, we consider a relaxed version of
the model by Martinez-Sykora et al. (2020), hereafter called Relaxed M-S, that
allows the delivery person to serve multiple customer service sets from the
same parking spot. For comparison purposes, we define the carrying capacity of
the delivery person in the Relaxed M-S benchmark to be based on the number of
packages $q$.

The key difference between the Relaxed M-S and the CDPP is the objective
function. The objective function for the CDPP, in Equation (1), includes the
search time for parking when evaluating the completion time of the delivery
tour. Martinez-Sykora et al. (2020) consider a weighted sum of the driving and
walking times for the delivery person. Using the notation of Section 3.1,
Equation (17) presents the objective function in Martinez-Sykora et al.
(2020),

$\displaystyle\alpha\sum_{i\in\Pi}\sum_{k\in\Pi\setminus\\{i\\}}x_{ik}D(i,k)+(1-\alpha)\sum_{i\in\Pi}\sum_{\sigma_{j}\in
S}y_{ij}w_{ij}$ (17)

where $\alpha\in[0,1]$.

We implement the Relaxed M-S benchmark by using Equation (17) as the objective
value in the CDPP. Since we assume a loading time linearly dependent on the
number of packages, the total loading time is a constant and added to the
objective value in Equation (17). Similar to Martinez-Sykora et al. (2020), we
consider $\alpha\in\\{0.6,0.8\\}$ in the Relaxed M-S benchmark. Let $v$ be the
optimal value of the Relaxed M-S benchmark (including loading time) and $s$ be
the number of times the vehicle parks in the respective solution. Then, the
completion time with a solution of this benchmark is $v+sp$ minutes. Comparing
the completion times for the CDPP and the Relaxed M-S benchmark highlights the
impact of including the search time for parking in the objective function.

###  8.2 Comparison of CDPP to Benchmarks

In this section, we compare the completion time of the delivery tour in the
CDPP with the values of the solutions for the three benchmarks in the base
case (location-dependent parking times, $q=3$ packages, and $f=2.1$ minutes).

Figure 3 shows the average percent reduction in delivery tours by using the
CDPP relative to each benchmark for Cook, Adams, and Cumberland counties.
Including the search time for parking reduces the completion time of delivery
tours in all counties. The CDPP reduces the completion time up to 53% on
average relative to the no-parking-time benchmark. The CDPP also outperforms
industry practice and models in the literature. Using the Modified TSP to
model real-life practice, the CDPP reduces the completion time up to 11% on
average. The Relaxed M-S benchmark generalizes the current models in the
literature. Figure 3 shows that the Relaxed M-S benchmark with $\alpha=0.6$
performs similarly to the no-parking-time benchmark. Increasing $\alpha$ to
0.8, the CDPP reduces the completion time up to 48% on average. In Cumberland
County, the CDPP realizes greater reductions at higher levels of $\alpha$.
Insight 1 summarizes this result.

######  Insight 1.

Parking matters in last-mile delivery optimization. The CDPP outperforms
industry practice and models in the literature highlighting the value of
determining the order of service and including the search time for parking in
optimal routing decisions.

Figure 3: Average percent reduction in completion time of delivery tours by
using CDPP relative to the no-parking-time benchmark, Modified TSP, Relaxed
M-S with $\alpha=0.6$, and Relaxed M-S with $\alpha=0.8$ in the base case.

The impact of parking differs across customer geographies. The CDPP provides
the greatest savings in Cook County, an urban environment with the highest
customer density and search time for parking. Including the search time for
parking in the CDPP reduces the completion time of these delivery tours by an
average of 53% relative to when no parking time is considered. Further, the
delivery person saves an average of 11% and 48% in delivery time relative to
the Modified TSP and Relaxed M-S with $\alpha=0.8$, respectively. In rural
areas where the customer density and search time for parking is generally low,
including the search time for parking reduces the completion time of the
delivery tour for the CDPP on average 3% in Cumberland County relative to when
no parking time is considered. The CDPP provides a similar completion time in
the delivery tour as the Modified TSP. Therefore, using the TSP solution may
be sufficient in making routing decisions for rural environments. Increasing
the value of $\alpha$ in Equation (17) makes walking advantageous in the
solution to the Relaxed M-S benchmark. However, in rural environments, when
the distance between customers is greater, a solution that incentivizes
walking adversely affects the realized completion time of the delivery tour.
Therefore, we see a higher level of savings for the CDPP when $\alpha=0.8$
than $\alpha=0.6$. We further explore this result later in this section.
Insight 2 summarizes these results.

######  Insight 2.

Including the search time for parking in routing optimization for last-mile
delivery provides the greatest advantage in urban environments where parking
is a challenge. In rural areas, the TSP may be sufficient in making routing
decisions.

Now, we explore how the structure of an optimal solution to the CDPP differs
from the solutions of the benchmark problems. Figure 4 shows the solutions to
the (a) CDPP, (b) no-parking-time benchmark, and (c) Modified TSP for a
portion of an instance in Cook County. We focus on a portion of the solution
to highlight the local differences in the CDPP and benchmark solutions. The
solid black lines indicate the driving path of the vehicle. The dotted lines
indicate the walking paths of the delivery person. Each color represents a
different service set. The flag icons indicate the parking spots. The
numerical label at the customer location indicates the order service within
the tour. For example, a numerical label of $i$ indicates that this customer
is $i$-th on the tour. Figure 4a shows an optimal solution for the CDPP in
this instance of Cook County. The delivery person serves three customer sets
from a single parking spot. Figure 4b shows the solution when no parking time
is considered (i.e. $p=0$). For this instance, the solution to the no-parking-
time benchmark is a TSP solution, parking at every customer, and driving
between customer locations. However, the search time for parking in Cook
County is 9 minutes. If the delivery person follows the solution in Figure 4b,
the delivery person spends about an hour looking for parking to serve these
eight customers. Figure 4a shows that even though walking is slower than
driving, it is more advantageous to park once and serve all customers on foot.
Insight 3 summarizes this observation.

######  Insight 3.

When parking time is ignored, routing decisions that focus on the fastest way
to service all customers may result in unnecessary time spent searching for
parking.

(a) CDPP

(b) No Parking Time

(c) Modified TSP

Figure 4: Solutions to a portion of an instance of Cook County for the (a)
CDPP, (b) no-parking-time benchmark, and (c) Transformed TSP benchmark in the
base case.

Recall that the Modified TSP uses a solution to the TSP to fix the order of
customer service. Figure 4c shows the solution of the Modified TSP benchmark.
The Modified TSP optimizes the trade-offs between walking, driving, and
searching for parking. Similar to the CDPP solution in Figure 4a, Figure 4c
shows that the delivery person parks once to avoid high search times for
parking and walks to service customers on foot. However, fixing the order of
service to the TSP results in additional walking time for the delivery person
relative to the CDPP in Figure 4a. The CDPP takes into account the search time
for parking when determining where to park as well as the walking path for the
delivery person reducing the completion time of the delivery tour relative to
the Modified TSP. Insight 4 summarizes this observation.

######  Insight 4.

The CDPP outperforms the Modified TSP by optimizing the service order which
leads to better trade-offs between driving, walking, and searching for
parking.

Finally, we analyze the solution structure of the Relaxed M-S benchmarks to
understand the impact of using the search time for parking in the objective
function of the CDPP. Figure 5 shows the average time (in minutes) spent in
the Relaxed M-S and CDPP delivery tours searching for parking, driving,
walking, and loading packages for Cook and Cumberland counties. When
$\alpha=0.6$, the solution structure in both counties relies on the delivery
person driving with limited to no walking. A solution that focuses on driving
forces the delivery person to search for many parking locations. In Cook
County, Figure 5a shows the delivery person spends on average 77% of the
delivery tour searching for parking. Increasing $\alpha$ to 0.8 makes walking
advantageous and reduces the completion time of the delivery tour by 11% on
average. However, searching for parking remains a significant portion of the
delivery tour. Including the search time for parking in the objective function
further reduces the completion time of the delivery tour by 48% on average. In
Cook County, where the customer density is high, the delivery person controls
the total search time for parking by parking in fewer locations and walking to
service customers. When customers are further apart, like Cumberland County,
Figure 5b shows that increasing $\alpha$ to 0.8 increases the completion time
of the delivery tour 3% on average. Making walking advantageous in rural
environments forces the delivery person to walk between customers that are
further apart. The similarity in the solution structures between the Relaxed
M-S with $\alpha=0.6$ and the CDPP support the conclusions of Insight 2 that a
solution that relies on driving is sufficient in rural environments. Insight 5
summarizes these results.

######  Insight 5.

Including the search time for parking in the objective for last-mile delivery
routing is critical to achieve optimal trade-offs between driving, walking,
and searching for parking.

(a) Cook County

(b) Cumberland County

Figure 5: Average time (minutes) spent in the Modified M-S and CDPP delivery
tours searching for parking, driving, walking, and loading packages for (a)
Cook County and (b) Cumberland County in the base case.

###  8.3 Impact of search time for parking

In this section, we focus on how the search time for parking $p$ changes the
structure to the CDPP solution. Figure 6 shows the average time (in minutes)
spent in optimal CDPP delivery tours searching for parking, driving, walking,
and loading packages for Cook County in the base case with various parking
times. In urban settings, the search time for parking is expected to be high.
We test $p=0,3,6,$ and $9$ minutes. Figure 6 shows that the total time spent
searching for parking remains relatively stable — between 40-47 minutes on
average — when $p>0$, indicating that the delivery person parks fewer times as
the search time for parking increases. Relatedly, we observe the walking time
significantly increases (57 to 111 minutes on average) as the delivery person
must walk further to service more customers. Insight 6 summarizes this
observation.

######  Insight 6.

In urban areas, as search time to find parking increases, the total time spent
looking for parking remains stable. At higher search times for parking, the
delivery person parks fewer times at the expense of significantly increasing
walking time.

Figure 6: Average time (minutes) spent in optimal CDPP delivery tours
searching for parking, driving, walking, and loading packages for Cook County
in the base case with various parking times.

Outside of urban environments, we observe that differences in customer
geography reduce the impact of the search time for parking on the structure of
the CDPP solution. Figure 7 shows the average time (in minutes) spent in
optimal CDPP delivery tours searching for parking, driving, walking, and
loading packages for Adams and Cumberland counties. Recall that Adams and
Cumberland counties are classified as suburban and rural areas, respectively.
Therefore, we expect customers to be further apart in these counties than in
an urban area, like Cook County. When $p$ increases from 0 to 3 minutes, the
completion time of the delivery tour increases by approximately the same
amount on average in Cook and Adams counties (95 minutes in Cook County and 98
minutes in Adams County). However, the impact on the structure of the solution
differs. When $p$ increases from 0 to 3 minutes in Cook County, Figure 6 shows
the average search time for parking increases 47 minutes accounting for 49% of
the increase in the completion time of the delivery tour. The remaining 51% of
the increase reflects changes in the solution structure, i.e. less driving
time and more walking time for the delivery person. In Adams County, when $p$
increases from 0 to 3 minutes, Figure 7a shows that the average search time
for parking increases 65 minutes. In this case, the total search time for
parking accounts for 66% of the increase in the completion time of the
delivery tour. Similar to Cook County, when $p$ increases from 0 to 3 minutes,
Figure 7a shows driving time decreases and walking time increases, but these
changes in the solution structure only account for 33% of the increase in the
completion time of the delivery tour. Therefore, the increase in the search
time for parking has less impact on the solution structure in Adams County
than Cook County. The differences in how the solution changes between Cook and
Adams counties reflect that the CDPP solution cannot trade off more walking at
a higher search time for parking in a county, such as Adams, where the
customers are relatively further apart. Insight 7 summarizes these results.

######  Insight 7.

Differences in customer geography influence the significance of including the
search time for parking in routing decisions. Increasing the search time for
parking outside of urban environments has less impact on the solution
structure than in urban environments.

(a) Adams County

(b) Cumberland County

Figure 7: Average time (minutes) spent in optimal CDPP delivery tours
searching for parking, driving, walking, and loading packages for (a) Adams
County and (b) Cumberland County in the base case with various parking times.

In rural environments, like Cumberland County, we test $p=0$ and 1 minute as
we expect search time for parking to be low. Since customers are likely
further apart than urban and suburban environments, we expect the delivery
person to spend more time driving between customers than walking. Figure 7b
shows that there exists customer locations close enough together such that it
is advantageous to walk to them even when $p=1$ minute. However, the driving
time remains the same on average indicating that the increase in the search
time for parking does not have a significant effect on routing decisions.
These observations support the conclusion of Insight 2 that the TSP driving to
all customers may be sufficient in making routing decisions for rural
environments.

###  8.4 Impact of the Capacity of Delivery Person

In this section, we discuss the impact of the capacity of the delivery person
$q$ on reducing the completion time of the delivery tour in different customer
geographies. Figure 8 shows the average objective value of the CDPP for Cook,
Adams, and Cumberland counties in the base case with varying capacities. In
urban areas, like Cook County, increasing the capacity from $q=1$ to 4
packages reduces the completion time of the delivery tour by 20% on average.
We observe a smaller impact in Adams County with an average reduction of 6%
when increasing from $q=1$ to 4 packages. In rural areas, like Cumberland
County, we observe little difference between the solution for $q=1$ and $4$
packages. This observation supports Insight 2 showing that serving customers
individually may be sufficient for routing decisions in rural areas. For all
counties, we observe marginally decreasing reductions in the delivery tour
when increasing capacity. Insight 8 summarizes these results.

######  Insight 8.

Increasing the capacity of the delivery person is more advantageous outside of
rural areas. In all customer geographies, marginal reductions in the
completion time of the delivery tour decrease at higher capacities.

Figure 8: Average optimal value of the CDPP for Cook, Adams, and Cumberland
Counties in the base case with varying capacities.

##  9 Heuristic Solution to CDPP

As we have shown in Section 7, our model improvements allow us to efficiently
solve problems with $n=50$ customers and $q=3$ packages. Most problems in the
related literature focus on at most $n=50$ customers and support the use of
$q=3$ packages as a base case. If we want to solve instances with more
customers or larger capacities for the delivery person, we face computational
limitations due to the growth in the size of the model. For example, when
$n=50$ customers, the average runtime for $q=4$ packages is 5.9, 4.4, and 3.1
hours for Cook, Adams, and Cumberland counties, respectively. Increasing to
$q=5$ packages, the number of $y_{ij}$ variables increases to 118,496,750
making the problem intractably large. Increasing from $n=50$ to $100$ also
significantly increases the runtime. For example, when $n=100$ customers, the
average runtime for $q=2$ packages is 0.4, 3.1, and 8.5 hours for Cook, Adams,
and Cumberland counties, respectively. For $n=100$, with the base case of
$q=3$ packages, the problem again becomes computationally infeasible.

Section 8 shows that by including the search time for parking in routing
optimization for last-mile delivery, the solution to the CDPP may signifcantly
reduce the completion time of the delivery tour. To realize these benefits for
larger instances, we provide a heuristic solution to the CDPP that finds high
quality solutions quickly. The proposed two-echelon location-routing heuristic
decomposes the decisions of the CDPP into two echelons. Section 9.1 describes
the first echelon, defined as the parking assignment and routing problem
(PA-R), where the customers are assigned to parking locations and the route of
the vehicle between these parking locations is defined. For each parking spot,
Section 9.2 describes the second echelon, defined as the service set
assignment problem (SSA), which determines how to optimally partition the
customers in service sets given the parking spots, therefore, defining the
walking paths of the delivery person. Then, Section 9.3 discusses the quality
of the heuristic solutions.

###  9.1 Parking Assignment and Routing Problem

The PA-R determines where to park the vehicle, the assignment of customers to
parking locations, and the route of the vehicle between these parking
locations. We further decompose the PA-R into two IPs.

First, we determine where to park the vehicle and assign customers to parking
locations. Let $\hat{p}_{i}=1$ if the delivery person parks at customer $i$
for $i\in C$, $0$ otherwise. Let $\hat{a}_{ik}=1$ if customer $k$ is assigned
to parking spot $i$ for $i,k\in C$, $0$ otherwise. All service times used in
the IPs of this section are defined in Section 3.1. The cost of opening a
parking spot is the search time for parking $p$. Therefore, the PA-R captures
parking at fewer locations when the search time for parking is high. Solve the
following MIP and denote an optimal solution $Z$.

$\displaystyle\min$ $\displaystyle\sum_{i\in C}p\cdot\hat{p}_{i}+\sum_{i\in
C}\sum_{k\in C}W(i,k)\cdot\hat{a}_{ik}$ (18) s.t. $\displaystyle\sum_{k\in
C}\hat{a}_{ki}=1$ $\displaystyle\forall i\in C$ (19)
$\displaystyle\hat{a}_{ik}\leq\hat{p}_{i}$ $\displaystyle\forall i,k\in C$
(20) $\displaystyle\hat{p}_{i}\leq\sum_{k\in C}\hat{a}_{ik}$
$\displaystyle\forall i\in C$ (21) $\displaystyle\hat{p}_{i}\in\\{0,1\\}$
$\displaystyle\forall i\in C$ (22) $\displaystyle\hat{a}_{ik}\in\\{0,1\\}$
$\displaystyle\forall i,k\in C$ (23)

The objective function in Equation (18) minimizes a linear combination of the
search time for parking and the assignment of walking (without return walks)
to the customers from parking locations. Constraints (19) require that each
customer is assigned to a parking spot. Given that a customer is assigned to a
parking spot, Constraints (20) require the vehicle to be parked at that
parking spot. If no customers are assigned to a parking spot, then Constraints
(21) ensure that the parking spot is not opened. Finally, Constraints (22) and
(23) give the binary constraints on variables $\hat{p}_{i}$ and
$\hat{a}_{ik}$, respectively.

Now, let $P=\\{i\in C|\hat{p}_{i}=1\textrm{ in }Z\\}$ be the parking spots in
solution $Z$. We find the TSP solution of $P\cup 0$ with respect to the
driving times, $D(i,k)$, using the standard TSP IP formulation with single
commodity subtour elimination constraints (Gavish and Graves 1978). This
solution provides the route of the vehicle between the parking locations.

###  9.2 Service Set Assignment Problem

For each parking spot, the SSA partitions the customers into customer service
sets defining the walking paths of the delivery person. For each $i\in P$,
define $K_{i}=\\{k\in C|\hat{a}_{ik}=1\textrm{ in }Z\\}$ to be the customers
assigned to parking spot $i$ in solution $Z$. For each $i\in P$, define
$S_{i}\subset S$ to be the potential sets to be served at $i$, i.e.
$S_{i}=\\{\sigma_{j}\in S|\sigma_{j}\subseteq K_{i}\\}$. For each $k\in
K_{i}$, let $\hat{J}_{k}=\\{\sigma_{j}\in J_{k}|\sigma_{j}\in S_{i}\\}$ be the
service sets in $S_{i}$ that include customer $k$. Let $\hat{y}_{j}=1$ if
$\sigma_{j}$ is serviced for $\sigma_{j}\in S_{i}$. Solve the following MIP
for each parking spot $i\in P$ to determine the service sets.

$\displaystyle\min$ $\displaystyle\sum_{\sigma_{j}\in S_{i}}w_{ij}\hat{y}_{j}$
(24) s.t. $\displaystyle\sum_{j\in\hat{J}_{k}}\hat{y}_{j}=1$
$\displaystyle\forall k\in K_{i}$ (25) $\displaystyle\hat{y}_{j}\in\\{0,1\\}$
$\displaystyle\forall j\in S_{i}$ (26)

The objective function in Equation (24) minimizes the walking time for the
delivery person servicing customers $K_{i}$ while parked at customer $i$.
Constraints (25) require each customer in $K_{i}$ to be in a service set.
Constraints (26) give the binary constraints on the variables $\hat{y}_{j}$.

###  9.3 Quality of Heuristic Solutions

In this section, we evaluate the quality of the two-echelon location-routing
heuristic. For this analysis, we consider the base case (location-dependent
parking times and $f=2.1$ minutes) for $n=50$ and $100$ customers with various
capacities of the delivery person $q$. For $n=50$, averages are taken across
ten instances. For $n=100$, averages are taken across five instances. Appendix
C provides detailed results on the objective value of the heuristic solution.

First, we discuss the quality of the solution with respect to the optimal
value of the CDPP. Table 7 provides the average optimality gap between the
heuristic and optimal solutions for the CDPP across counties and capacities
$q$. An asterisk (*) by the county name indicates that the CDPP MIP of one
instance in that county was solved to an optimality gap of 1.2%. When $n=100$
and $q\geq 3$, we face computational limitations when solving the CDPP and,
therefore, the optimality gap in this case cannot be evaluated. Otherwise, the
value of the heuristic solution is on average within 5.5% of the CDPP optimal
value. For each county, the heuristic performs best for $q=2$ packages and
worst for $q=1$ package.

| $q$
---|---
County | 1 | 2 | 3 | 4
Cook |  |  |  |
$n=50$ | 5.5% | 1.3% | 3.4% | 5.5%
$n=100$ | 4.9% | 0.5% | - | -
Adams |  |  |  |
$n=50$ | 4.0% | 2.2% | 3.1% | 3.6%
$n=100$ | 4.9% | 2.6% | - | -
Cumberland |  |  |  |
$n=50$ | 1.6% | 1.5% | 1.5% | 1.5%
$n=100$* | 1.2% | 1.1% | - | -
Table 7: Average optimality gap (%) between the two-echelon location-routing
heuristic and optimal solution for the CDPP across various capacities of the
delivery person $q$ in the base case.

Next, we discuss the runtime for the two-echelon location-routing heuristic.
On average, the PA-R takes at most 0.6 minutes and the SSA takes at most 0.3
minutes. In total, the average runtime of the two-echelon location-routing
heuristic is at most 0.7 minutes. Thus, the two-echelon location-routing
heuristic finds high quality solution quickly.

Section 8 shows that including the search time for parking in routing
optimization by using the CDPP for last-mile delivery is advantageous in
reducing the completion time of the delivery tour. We show that the two-
echelon location-routing heuristic outperforms the benchmark problems in
Section 8.1 for most cases, highlighting that this heuristic provides an
improvement to industry practice and models in the literature at low
computational time. Table 8 shows the average optimality gap between the
benchmark models in Section 8.1 and the optimal CDPP value for $n=50$ across
various capacities of the delivery person $q$ in the base case. A single
asterisk $(^{*})$ indicates that 9 out of 10 instances for the benchmark model
being considered solved to optimality. A double asterisk $(^{**})$ indicates
that 8 out of 10 instances for the benchmark model being considered solved to
optimality. We also include the optimality gap for the two-echelon location
routing heuristic. For each county and capacity, the model that achieved the
lowest optimality gap is bolded. The two-echelon location-routing heuristic
significantly outperforms all benchmarks in Cook and Adams counties. For
Cumberland County, the two-echelon location-routing heuristic solution
outperforms all benchmarks aside from the Modified TSP supporting the
conclusion that driving the TSP and parking at every customer may be a
sufficient solution in rural environments. This analysis supports the use of
the two-echelon location-routing heuristic to realize the advantages of
including the search time for parking in routing last-mile delivery.

| $q$
---|---
County | 1 | 2 | 3 | 4
Cook |  |  |  |  |  |
No parking time | 77.0% | 98.8% | 113.3% |  | 122.1% |
Modified TSP | 13.9% | 13.7% | 12.9% |  | 12.8% |
Relaxed M-S $\alpha=0.6$ | 75.6% | 97.8% | 111.7% |  | 121.1% |
Relaxed M-S $\alpha=0.8$ | 65.6% | 79.9% | 93.0% |  | 100.0% | ∗
Two-Echelon Location-Routing Heuristic | 5.5% | 1.3% | 3.4% |  | 5.5% |
Adams |  |  |  |  |  |
No parking time | 34.8% | 39.9% | 42.4% |  | 43.4% |
Modified TSP | 7.4% | 7.0% | 6.4% |  | 5.7% |
Relaxed M-S $\alpha=0.6$ | 33.6% | 38.0% | 41.0% |  | 40.8% |
Relaxed M-S $\alpha=0.8$ | 31.0% | 33.7% | 36.3% | ∗ | 33.7% | ∗∗
Two-Echelon Location-Routing Heuristic | 4.0% | 2.2% | 3.1% |  | 3.6% |
Cumberland |  |  |  |  |  |
No parking time | 4.1% | 4.2% | 4.2% |  | 4.2% |
Modified TSP | 0.9% | 0.7% | 0.6% |  | 0.6% |
Relaxed M-S $\alpha=0.6$ | 3.2% | 3.5% | 3.1% |  | 3.2% |
Relaxed M-S $\alpha=0.8$ | 6.1% | 7.0% | 6.9% | ∗ | 8.0% | ∗∗
Two-Echelon Location-Routing Heuristic | 1.6% | 1.5% | 1.5% |  | 1.5% |
Table 8: Average optimality gap (%) between the benchmark models in Section
8.1 and the optimal CDPP value for $n=50$ across various capacities of the
delivery person $q$ in the base case.

##  10 Conclusions and Future Work

Yes, parking matters. Including the search time for parking in the objective
for routing optimization for last-mile delivery may significantly reduce the
completion time of the delivery tour. Using the CDPP for routing decisions
provides the greatest advantage in urban environments where parking is a
challenge and often time consuming. When parking is a challenge, the CDPP
solution recommends that the delivery person park in fewer locations and serve
multiple customer service sets from the same parking spot. This decision
balances the trade-offs of walking to service customers and driving to find a
new parking location. However, in rural environments where parking is more
readily available, a solution that parks at all customers serving each
customer individually may be sufficient.

These insights are reflected in our analytical results that determine when the
search time for parking becomes large enough that the TSP solution parking at
every customer location is not an optimal solution to the CDPP. These results
show that in urban environments, where customers are close together, small
search times for parking impact the structure of the optimal solution in the
CDPP. A TSP solution that parks at every customer best approximates optimal
solutions to the CDPP in rural environments where customers are further apart.

To solve reasonably-sized instances of the CDPP, this paper introduces several
valid inequalities and a variable reduction technique that improves
computational performance of the CDPP. However, further work needs to be done
to control the growth in the number of variables in the model, particularly
the service variables $y_{ij}$ which grows both in the number of customers as
well as the number of potential service sets. A column generation approach may
improve computational performance. For instances where the model becomes
intractably large, we propose a two-echelon location-routing heuristic and
show that this heuristic finds high quality solutions quickly. These heuristic
solutions outperform other traditional last-mile delivery models providing an
immediate improvement to industry practice and models in the literature.

This work provides immediate ways to improve routing a single vehicle for
last-mile delivery. Future work includes considering the impact of parking
under additional delivery constraints, such as customer time windows and
additional service times, as well as the consideration of a fleet of vehicles.
In the experimental design, we assume that the parking locations are
restricted to customer locations. However, it may be the case that the vehicle
cannot park at every customer and/or there exists parking locations outside of
customer locations that should be considered. Future work includes the
analysis of further restricting or increasing parking locations in the CDPP.

We model last-mile delivery in a deterministic framework to build insights on
the impact that the search time for parking has on routing decisions. However,
we know parking is stochastic and can vary by location and time of day. In
Seattle, Dalla Chiara and Goodchild (2020) conclude that the cruise time for
parking decreases when more curb-space is allocated to commercial loading
zones and paid parking and increases when more curb-space is allocated to bus
zones. A survey of 16 drivers in New York City finds that the search time for
parking ranges from 3 minutes in Brooklyn to 60 minutes in Midtown East
(Holguin-Veras et al. 2016). Future work includes the analysis of spatial
changes in the search time for parking. In addition, future work includes
generalizing the CDPP to consider temporal changes in search time for parking
as well as the impact of parking in a stochastic framework.

An understanding of the availability of parking locations and its impact on
delivery practices also benefits urban planning efforts. Currently, many urban
areas are experimenting with loading zone reservations and pricing schemes for
delivery vehicles (Shaver 2019, Balik et al. 2016). For example, a pilot
program in Aspen, Colorado, allows commercial drivers to reserve and pay for
the use of “Smart Zones” with a mobile app (COORD 2021). Insights into how
parking impacts routing in last-mile delivery may allow for better placement
of loading zones and better pricing schemes to incentivize drivers and yield
better curbside management.

## References

  * Allen et al. [2018] Julian Allen, Maja Piecyk, Marzena Piotrowska, Fraser McLeod, Thomas Cherrett, Karen Ghali, Thuba Nguyen, Tolga Bektas, Oliver Bates, Adrian Friday, et al.  Understanding the impact of e-commerce on last-mile light goods vehicle activity in urban areas: The case of London.  _Transportation Research Part D: Transport and Environment_ , 61:325–338, 2018.
  * Balik et al. [2016] Justin Balik, Richard Dimino, Irene Figueroa Ortiz, Ralph DeNisco, Qingnan Liu, and Jason Schrieber.  Future of parking in Boston.  Technical report, 2016.
  * Belenguer et al. [2016] José Manuel Belenguer, Enrique Benavent, Antonio Martínez, Christian Prins, Caroline Prodhon, and Juan G Villegas.  A branch-and-cut algorithm for the single truck and trailer routing problem with satellite depots.  _Transportation Science_ , 50(2):735–749, 2016\.
  * Boccia et al. [2011] Maurizio Boccia, Teodor Gabriel Crainic, Antonio Sforza, and Claudio Sterle.  Location-routing models for designing a two-echelon freight distribution system.  _Rapport technique, CIRRELT, Université de Montréal_ , 91, 2011.
  * Boysen et al. [2020] Nils Boysen, Stefan Fedtke, and Stefan Schwerdfeger.  Last-mile delivery concepts: a survey from an operational research perspective.  _OR Spectrum_ , pages 1–58, 2020.
  * Contardo et al. [2012] Claudio Contardo, Vera Hemmelmayr, and Teodor Gabriel Crainic.  Lower and upper bounds for the two-echelon capacitated location-routing problem.  _Computers & operations research_, 39(12):3185–3199, 2012.
  * Cookson and Pishue [2017] Graham Cookson and Bob Pishue.  The impact of parking pain in the US, UK and Germany.  Technical report, INRIX Research, July 2017.
  * COORD [2021] COORD.  Smart zones deliver: Full Aspen case study.  Technical report, March 2021.
  * Cuda et al. [2015] Rosario Cuda, Gianfranco Guastaroba, and Maria Grazia Speranza.  A survey on two-echelon routing problems.  _Computers & Operations Research_, 55:185–199, 2015.
  * Dalla Chiara and Goodchild [2020] Giacomo Dalla Chiara and Anne Goodchild.  Do commercial vehicles cruise for parking? empirical evidence from Seattle.  _Transport Policy_ , 97:26–36, 2020.
  * Danigelis [2018] Alyssa Danigelis.  New York City invests $100m in freight infrastructure overhaul.  _Environment Energy Leader_ , July 2018.  URL https://www.environmentalleader.com/2018/07/new-york-city-infrastructure-overhaul/.
  * Figliozzi and Tipagornwong [2017] Miguel Figliozzi and Chawalit Tipagornwong.  Impact of last mile parking availability on commercial vehicle costs and operations.  In _Supply Chain Forum: An International Journal_ , volume 18, pages 60–68. Taylor & Francis, 2017.
  * Gavish and Graves [1978] Bezalel Gavish and Stephen C Graves.  The travelling salesman problem and related problems.  _Massachusetts Institute of Technology, Operations Research Center_ , 1978.
  * Haag and Hu [2019] Matthew Haag and Winnie Hu.  1.5 million packages a day: The internet brings chaos to N.Y. streets.  _The New York Times_ , October 2019.
  * Holguin-Veras et al. [2016] Jose Holguin-Veras, Johanna Amaya, Trilce Encarnacion, Sofia Kyle, and Jeffrey Wojtowicz.  Impacts of freight parking policies in urban areas: The case of New York City.  2016\.
  * Johnson [2021] Glenn P. Johnson.  Argon cluster.  Technical report, Univeristy of Iowa, 2021.  URL https://wiki.uiowa.edu/display/hpcdocs/Argon+Cluster.
  * Lopez et al. [2019] Clélia Lopez, Chuan-Lin Zhao, Stéphane Magniol, Nicolas Chiabaut, and Ludovic Leclercq.  Microscopic simulation of cruising for parking of trucks as a measure to manage freight loading zone.  _Sustainability_ , 11(5):1276, 2019.
  * Martinez-Sykora et al. [2020] Antonio Martinez-Sykora, Fraser McLeod, Carlos Lamas-Fernandez, Tolga Bektaş, Tom Cherrett, and Julian Allen.  Optimised solutions to the last-mile delivery problem in London using a combination of walking and driving.  _Annals of Operations Research_ , 295(2):645–693, 2020.
  * Nguyen et al. [2019] Thu Ba T Nguyen, Tolga Bektas, Tom J Cherrett, Fraser N McLeod, Julian Allen, Oliver Bates, Marzena Piotrowska, Maja Piecyk, Adrian Friday, and Sarah Wise.  Optimising parcel deliveries in London using dual-mode routing.  _Journal of the Operational Research Society_ , 70(6):998–1010, 2019.
  * Nguyen et al. [2012a] Viet-Phuong Nguyen, Christian Prins, and Caroline Prodhon.  Solving the two-echelon location routing problem by a grasp reinforced by a learning process and path relinking.  _European Journal of Operational Research_ , 216(1):113–126, 2012a.
  * Nguyen et al. [2012b] Viet-Phuong Nguyen, Christian Prins, and Caroline Prodhon.  A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem.  _Engineering Applications of Artificial Intelligence_ , 25(1):56–71, 2012b.
  * Nourinejad et al. [2014] Mehdi Nourinejad, Adam Wenneman, Khandker Nurul Habib, and Matthew J Roorda.  Truck parking in urban areas: Application of choice modelling within traffic microsimulation.  _Transportation Research Part A: Policy and Practice_ , 64:54–64, 2014.
  * Poikonen and Golden [2020] Stefan Poikonen and Bruce Golden.  Multi-visit drone routing problem.  _Computers & Operations Research_, 113:104802, 2020.
  * Reed [2021] Sara Reed.  _Value of Parking and Autonomous Vehicles for Last-Mile Delivery_.  PhD thesis, University of Iowa, 2021.
  * Reed et al. [2021a] Sara Reed, Ann Melissa Campbell, and Barrett W Thomas.  Impact of autonomous vehicle assisted last-mile delivery in urban to rural settings.  _Submitted for publication_ , 2021a.
  * Reed et al. [2021b] Sara Reed, Ann Melissa Campbell, and Barrett W Thomas.  The value of autonomous vehicles for last-mile deliveries in urban environments.  _Management Science_ , 2021b.
  * Reed et al. [2021c] Sara Reed, Ann Melissa Campbell, and Barrett W Thomas.  Instances for impact of autonomous vehicle assisted last-mile delivery in urban to rural settings.  2021c.  URL https://doi.org/10.25820/data.006124.
  * Rosenbush and Stevens [2015] Steven Rosenbush and Laura Stevens.  At UPS, the algorithm is the driver.  _Wall Street Journal_ , Feb 17 2015.
  * Shaver [2019] Katherine Shaver.  Study: Allowing delivery drivers to reserve curb space reduces double-parking.  _The Washington Post_ , November 2019.
  * Simoni et al. [2019] Michele D Simoni, Edoardo Marcucci, Valerio Gatta, and Christian G Claudel.  Potential last-mile impacts of crowdshipping services: a simulation-based evaluation.  _Transportation_ , pages 1–22, 2019.
  * USDA [2013] USDA 2013.  Rural-urban continuum codes.  Technical report, United States Department of Agriculture (USDA), May 2013\.
  * Zhang et al. [2018] Lei Zhang, Tilman Matteis, Carina Thaller, and Gernot Liedtke.  Simulation-based assessment of cargo bicycle and pick-up point in urban parcel delivery.  _Procedia computer science_ , 130:18–25, 2018.

##  Appendix A Proofs

###  A.1 Proof of Claim 1

###### Proof.

To conclude part (a), we begin by providing a lower bound on a solution to the
CDPP where the delivery person parks $k$ times for $k<n$. Then, we show this
bound is bounded below by the objective value for the TSP solution where the
delivery person parks at every customer, given in Equation (13). Thus, the TSP
solution parking at every customer location is an optimal solution to the
CDPP.

The CDPP objective value in Equation (1) decomposes into the time the delivery
person spends searching for parking, driving, walking, and loading packages.
Assume the delivery person parks $k$ times. Then, the search time for parking
is $kp$. Reed et al. [2021b] show that the closest customer to the depot is
unique and $D(0,c_{2})=MinDistance+1$ for each customer $c_{2}$ in the set of
second closest customers to the depot. When $k>1$, driving time to and from
the depot is minimized if the delivery person enters the grid at the closest
customer and exits the grid at a second closest customer to the depot. Thus,
driving time to and from the grid is bounded below by $(2\cdot
MinDistance+1)\hat{d}\hat{l}$ minutes. The case where $k=1$ is addressed at
the end of this discussion. Further, the driving time between the $k$ parking
spots is bounded below by $(k-1)\hat{d}\hat{l}$ minutes as the parking
locations are at least one unit apart. In total, the delivery person drives at
least $(2\cdot MinDistance+k)\hat{d}\hat{l}$ minutes. Since the delivery
person parks $k$ times, $n-k$ customers are serviced from a parking spot that
is not the customer location. When $q\leq 2$, the delivery person walks at
least $2\hat{w}\hat{l}$ minutes per customer as the customer is at least one
block away from the parking location and must also return back to the parking
location. In total, the delivery person walks at least $2\hat{w}\hat{l}(n-k)$
minutes. In summary, Equation (27) gives a lower bound on a solution where the
delivery person parks $k$ times,

$\displaystyle kp+(2\cdot
MinDistance+k)\hat{d}\hat{l}+2\hat{w}\hat{l}(n-k)+nf.$ (27)

We show that the lower bound in Equation (27) holds for $k=1$. Note that when
$k=1$, driving time to and from the single parking spot is bounded below by
$(2\cdot MinDistance)\hat{d}\hat{l}$ minutes. However, for at least one
customer, the delivery person must walk at least $4w$ units. Therefore, the
lower bound when $k=1$ is given in the following equation:

$\displaystyle p+(2\cdot
MinDistance)\hat{d}\hat{l}+2\hat{w}\hat{l}(n-2)+4\hat{w}\hat{l}+nf$
$\displaystyle\hskip 100.00015pt\geq p+(2\cdot
MinDistance)\hat{d}\hat{l}+2\hat{w}\hat{l}(n-1)+2\hat{w}\hat{l}+nf$ (28)
$\displaystyle\hskip 100.00015pt\geq p+(2\cdot
MinDistance+1)\hat{d}\hat{l}+2\hat{w}\hat{l}(n-1)+nf.$ (29)

Equation (28) redistributes the $4\hat{w}\hat{l}$ term. Equation (29) follows
from the assumption $\hat{w}>\hat{d}$, or equivalently
$2\hat{w}\hat{l}>2\hat{d}\hat{l}>\hat{d}\hat{l}$. Thus, the lower bound in
Equation (27) holds for $k=1$, as well.

Now, we show the lower bound in Equation (27) is bounded below by the
objective value in Equation (13). By adding
$0=(n-k)\hat{d}\hat{l}-(n-k)\hat{d}\hat{l}$ to Equation (27), it follows

$\displaystyle kp+(2\cdot
MinDistance+k+(n-k)-(n-k))\hat{d}\hat{l}+2\hat{w}\hat{l}(n-k)+nf$
$\displaystyle\hskip 100.00015pt\leq kp+(n-k)p+(2\cdot
MinDistance+n)\hat{d}\hat{l}+nf$ (30) $\displaystyle\hskip
100.00015pt=np+(2\cdot MinDistance+n)\hat{d}\hat{l}+nf.$ (31)

Equation (30) uses the assumption that $p\leq\hat{l}(2\hat{w}-\hat{d})$, or
equivalently $p(n-k)\leq 2\hat{w}\hat{l}(n-k)-\hat{d}\hat{l}(n-k)$. Then,
Equation (31) simplifies Equation (30). Lemma 1 concludes that Equation (31)
is the objective value to the TSP solution where the delivery person parks at
every customer location. Thus, the lower bound to a solution where the
delivery person parks $k$ times is bounded below by this TSP solution and we
conclude an optimal solution to the CDPP is the TSP solution where the
delivery person parks at every customer location.

To conclude part (b), we construct a solution that has a lower objective value
than the TSP solution where the delivery person parks at every customer
location. Thus, this TSP solution is not an optimal solution to the CDPP.

First, we construct a solution to the CDPP. Figure 9(a) shows an example of
this constructed solution on a $6\times 6$ grid of customers. Dashed green
lines represent walking paths for the delivery person. Consider the complete
grid of customers $\sqrt{n}\times\sqrt{n}-1$ with the bottom left corner of
the grid at $(1,1)$, bottom right corner at $(\sqrt{n},1)$, top left corner at
$(1,\sqrt{n}-1)$, and top right corner at $(\sqrt{n},\sqrt{n}-1)$. Since
$\sqrt{n}(\sqrt{n}-1)$ is even, Reed et al. [2021b] show there exists a
Hamiltonian path from $(1,1)$ to $(1,2)$ through the solid rectangular grid.
In Figure 9(a), this path is shown with the solid, blue driving route. The
delivery person parks at each customer traversed on this path. The remaining
$\sqrt{n}$ customers are located on the line from $(1,\sqrt{n})$ to
$(\sqrt{n},\sqrt{n})$. For each $a\in\\{1,2,...,\sqrt{n}\\}$, the customer
located at $(a,\sqrt{n})$ is serviced from the parking spot $(a,\sqrt{n}-1)$.
Equation (32) gives the objective value for this constructed solution

$\displaystyle(2\cdot
MinDistance+1+\sqrt{n}(\sqrt{n}-1)-1)\hat{d}\hat{l}+\sqrt{n}(\sqrt{n}-1)p+2\hat{w}\hat{l}\sqrt{n}+nf$
$\displaystyle\hskip 100.00015pt=(2\cdot
MinDistance+n-\sqrt{n})\hat{d}\hat{l}+(n-\sqrt{n})p+2\hat{w}\hat{l}\sqrt{n}+nf.$
(32)

Then, it follows

$\displaystyle(2\cdot
MinDistance+n-\sqrt{n})\hat{d}\hat{l}+(n-\sqrt{n})p+2\hat{w}\hat{l}\sqrt{n}+nf$
$\displaystyle\hskip 100.00015pt<(2\cdot
MinDistance+n)\hat{d}\hat{l}+(n-\sqrt{n})p+nf+p\sqrt{n}$ (33)
$\displaystyle\hskip 100.00015pt=(2\cdot MinDistance+n)\hat{d}\hat{l}+np+nf.$
(34)

Equation (33) uses the assumption $p>\hat{l}(2\hat{w}-\hat{d})$, or
equivalently $p\sqrt{n}>2\hat{w}\hat{l}\sqrt{n}-\hat{d}\hat{l}\sqrt{n}$. Then,
Equation (34) simplifies Equation (33). Lemma 1 concludes that Equation (34)
is the objective value to the TSP solution where the delivery person parks at
every customer location. Thus, this constructed solution has a lower objective
value than the TSP solution where the delivery person parks at every customer
location concluding that this TSP solution is not an optimal solution to the
CDPP. ∎

(a) $q\leq 2$ and $p>\hat{l}(2\hat{w}-\hat{d})$

(b) $q=3$ and $p>\hat{l}(\frac{4}{3}\hat{w}-\hat{d})$

Figure 9: Constructed solutions that achieve a lower objective value than the
TSP solution parking at every customer when (a) $q\leq 2$ and
$p>\hat{l}(2\hat{w}-\hat{d})$ or (b) $q=3$ and
$p>\hat{l}(\frac{4}{3}\hat{w}-\hat{d})$ on a $6\times 6$ grid of customers.

###  A.2 Proof of Claim 2

###### Proof.

This proof takes the same approach outlined in the proof of Claim 1.

To conclude part(a), we begin by providing a lower bound on a solution to the
CDPP where the delivery person parks $k$ times for $k<n$. The search time for
parking is $kp$. The arguments for the lower bound on the driving time
presented in the proof of Claim 1(a) hold here. The delivery person drives at
least $(2\cdot MinDistance+k)\hat{d}\hat{l}$ minutes. Since the delivery
person parks $k$ times, $n-k$ customers are serviced from a parking spot that
is not the customer location. If the delivery person serves one or two
customers in a service set, then the delivery person walks at least
$2\hat{w}\hat{l}$ minutes per customer as the customer is at least one block
away from the parking location and must also return back to the parking
location. If the delivery person serves three customers in a service set, the
delivery person walks at least $4\hat{w}\hat{l}$ minutes to walk to each
customer and return back to the parking location. To find a lower bound on the
walking time, we maximize the consolidation efforts to minimize the number of
return walks to parking locations. Find $g,h\in\mathbb{Z}$ where $h<3$ and
$n-k=3g+h$. Then, the delivery person walks at least $4g+2h$ units. In
summary, Equation (35) gives a lower bound on a solution where the delivery
person parks $k$ times,

$\displaystyle kp+(2\cdot
MinDistance+k)\hat{d}\hat{l}+(4g+2h)\hat{w}\hat{l}+nf.$ (35)

We show that the lower bound in Equation (35) holds for $k=1$. Note that when
$k=1$, driving time to and from the single parking spot is bounded below by
$(2\cdot MinDistance)\hat{d}\hat{l}$ minutes. However, for at least one set of
three customers, the parking location is at least one unit away so the
delivery person must walk at least $6w$ units. Therefore, the lower bound when
$k=1$ is given in the following equation:

$\displaystyle p+(2\cdot
MinDistance)\hat{d}\hat{l}+6w\hat{w}\hat{l}+4(g-1)\hat{w}\hat{l}+2h\hat{w}\hat{l}+nf$
(36)

Equation (36) is still bounded below by Equation (35). Thus, the lower bound
in Equation (35) holds for $k=1$, as well.

Now, we show the lower bound in Equation (35) is bounded below by the
objective value in Equation (13). By adding
$0=(n-k)\hat{d}\hat{l}-(n-k)\hat{d}\hat{l}$ to Equation (35), it follows

$\displaystyle kp+(2\cdot
MinDistance+k+(n-k)-(n-k))\hat{d}\hat{l}+(4g+2h)\hat{w}\hat{l}+nf$
$\displaystyle\hskip 40.00006pt=kp+(2\cdot
MinDistance+k+(n-k)-(3g+h))\hat{d}\hat{l}+(4g+2h)\hat{w}\hat{l}+nf$ (37)
$\displaystyle\hskip 40.00006pt\geq kp+(2\cdot
MinDistance+k+(n-k)-(3g+h))\hat{d}\hat{l}+(4g+\frac{4}{3}h)\hat{w}\hat{l}+nf$
(38) $\displaystyle\hskip 40.00006pt\geq kp+(2\cdot
MinDistance+k+(n-k)-(3g+h))\hat{d}\hat{l}+nf+(3g+h)p+(3g+h)\hat{d}\hat{l}$
(39) $\displaystyle\hskip 40.00006pt=kp+(2\cdot
MinDistance+n)\hat{d}\hat{l}+nf+(3g+h)p$ (40) $\displaystyle\hskip
40.00006pt=np+(2\cdot MinDistance+n)\hat{d}\hat{l}+nf.$ (41)

Equation (37) uses that $n-k=3g+h$. Then, Inequality (38) uses that
$2h\hat{w}\hat{l}\geq\frac{4}{3}h\hat{w}\hat{l}$. Inequality (39) uses the
assumption that $p\leq\hat{l}(\frac{4}{3}\hat{w}-\hat{d})$, or equivalently
$3gp+3g\hat{d}\hat{l}\leq 4g\hat{w}\hat{l}$ and
$hp+h\hat{d}\hat{l}\leq\frac{4}{3}h\hat{w}\hat{l}$. Then, Equation (40)
simplifies Equation (39). Finally, Equation (41) simplifies Equation (40)
using $n-k=3g+h$. Lemma 1 concludes that Equation (41) is the objective value
to the TSP solution where the delivery person parks at every customer
location. Thus, the lower bound to a solution where the delivery person parks
$k$ times is bounded below by this TSP solution and we conclude an optimal
solution is the TSP solution where the delivery person parks at every customer
location.

To conclude part (b), we construct a solution that has a lower objective value
than the TSP solution where the delivery person parks at every customer
location. Algorithm 1 constructs a particular solution when $q=3$ packages and
Figure 9(b) shows an example of this constructed solution on a $6\times 6$
grid of customers. This solution parks at $n-6$ customers for a total search
time for parking of $p(n-6)$. As discussed in Steps 8 and 9 in Algorithm 1,
the delivery person serves two sets of three customers for a total walking
time of $8\hat{l}\hat{w}$. In total, the delivery person drives $2\cdot
MinDistance+n-6$ units for a total driving time of $(2\cdot
MinDistance+n-6)\hat{l}\hat{d}$. Equation (42) gives the objective value for
this constructed solution

$\displaystyle(2\cdot
MinDistance+n-6)\hat{l}\hat{d}+(n-6)p+8\hat{l}\hat{w}+nf.$ (42)

Then, it follows

$\displaystyle(2\cdot
MinDistance+n-6)\hat{l}\hat{d}+(n-6)p+8\hat{l}\hat{w}+nf$ $\displaystyle\hskip
100.00015pt<(2\cdot
MinDistance+n-6)\hat{l}\hat{d}+(n-6)p+nf+6p+d\hat{l}\hat{d}$ (43)
$\displaystyle\hskip 100.00015pt=(2\cdot MinDistance+n)\hat{l}\hat{d}+np+nf.$
(44)

Equation (43) uses the assumption $p>\hat{l}(\frac{4}{3}\hat{w}-\hat{d})$, or
equivalently $6p+6d>8\hat{w}\hat{l}$. Then, Equation (44) simplifies Equation
(43). Lemma 1 concludes that Equation (44) is the objective value to the TSP
solution where the delivery person parks at every customer location. Thus,
this constructed solution has a lower objective value than the TSP solution
where the delivery person parks at every customer location concluding that
this TSP solution is not an optimal solution to the CDPP. ∎

Algorithm 1 Constructed Solution on $\sqrt{n}\times\sqrt{n}$ complete grid
when $q=3$

1: Input: Number of customers $n=\sqrt{n}\times\sqrt{n}$ where $\sqrt{n}$ is
even

2: Output: Feasible Solution for CDPP when $q=3$

3: Drive from depot at $(0,0)$ and park at customer location $(1,1)$.

4: Drive and park at each customer location from $(1,1)$ to $(\sqrt{n},1)$.

5: for $i\in\\{1,...,\frac{\sqrt{n}-4}{2}\\}$: Drive and park at customer
location $(\sqrt{n},2i)$. Drive and park at each customer location from
$(\sqrt{n},2i)$ to $(2,2i)$. Drive and park at customer location $(2,2i+1)$.
Drive and park at each customer location from $(2,2i+1)$ to $(\sqrt{n},2i+1)$.

6: Drive and park from customer location $(\sqrt{n},n-3)$ to customer location
$(\sqrt{n},n-2)$.

7: Drive and park at customer location $(\sqrt{n}-1,n-2)$.

8: Drive and park at customer location $(\sqrt{n}-1,\sqrt{n}-1)$. Serve this
customer individually. Then, from this parking location, walk to service the
customer service set
$\\{(\sqrt{n}-1,\sqrt{n}),(\sqrt{n},\sqrt{n}),(\sqrt{n},\sqrt{n}-1)\\}$.

9: Drive and park at customer location $(\sqrt{n}-2,\sqrt{n}-1)$. Serve this
customer individually. Then, from this parking location, walk to service the
customer service set
$\\{(\sqrt{n}-2,\sqrt{n}),(\sqrt{n}-3,\sqrt{n}),(\sqrt{n}-3,\sqrt{n}-1)\\}$.

10: Drive and park at customer location $(\sqrt{n}-2,\sqrt{n}-2)$.

11: Drive and park at customer location $(\sqrt{n}-3,\sqrt{n}-2)$.

12: for $i\in\\{1,...,\frac{\sqrt{n}-4}{2}\\}$: Drive and park at customer
location $(\sqrt{n}-4+2i,\sqrt{n}-2)$. Drive and park at each customer
location from $(\sqrt{n}-4+2i,\sqrt{n}-2)$ to $(\sqrt{n}-4+2i,\sqrt{n})$.
Drive and park at customer location $(\sqrt{n}-5+2i,\sqrt{n})$. Drive and park
at each customer location from $(\sqrt{n}-5+2i,\sqrt{n})$ to
$(\sqrt{n}-5+2i,\sqrt{n}-2)$.

13: Drive and park at each customer location from $(1,\sqrt{n}-2)$ to $(1,1)$.

14: Drive from customer location $(1,1)$ to depot at $(0,0)$.

###  A.3 Proof of Claim 3

###### Proof.

Assume the delivery person parks at $i\in\Pi\cap C$ but serves $i$ while
parked at a different parking location $l\in\Pi\setminus\\{i\\}$. Therefore,
there exists $\sigma_{j}\in J_{i}$ such that $y_{lj}=1$. Take $v=|\sigma_{j}|$
and denote ($c_{1},...,c_{v}$) to be an optimal order to service set
$\sigma_{j}$ when parked at $l$. Note that $c_{I}=i$ for some
$I\in\\{1,...,v\\}$. After serving customer $c_{v}$, the delivery person
returns to parking spot $l$ making a cycle. Now, we consider two cases:
$l\in\sigma_{j}$ and $l\notin\sigma_{j}$. If $l\in\sigma_{j}$, an optimal
order to serve set $\sigma_{j}$ when parked at $i$ is
($c_{I},c_{I+1},...,c_{v},l,c_{1},...,c_{I-1}$). In this case, $w_{ij}=w_{lj}$
giving an equivalent solution. If $l\not\in\sigma_{j}$, it follows

$\displaystyle w_{lj}$
$\displaystyle=W(l,c_{1})+W(c_{1},c_{2})+\cdots+W(c_{I-1},c_{I})+W(c_{I},c_{I+1})+\cdots+W(c_{v-1},c_{v})+W(c_{v},l)$
(45) $\displaystyle\geq
W(c_{1},c_{2})+\cdots+W(c_{I-1},c_{I})+W(c_{I},c_{I+1})+\cdots+W(c_{v-1},c_{v})+W(c_{v},c_{1})$
(46)
$\displaystyle=W(c_{I},c_{I+1})+\cdots+W(c_{v-1},c_{v})+W(c_{v},c_{1})+W(c_{1},c_{2})+\cdots+W(c_{I-1},c_{I})$
(47) $\displaystyle\geq w_{ij}.$ (48)

Equation (45) follows by the definition of the service times in Section (3.1).
Inequality 46 holds by the triangle inequality on the walking time. Equation
(47) rearranges the terms and Inequality (48) follows by the definition of
service times in Section 3.1. Thus, serving set $\sigma_{j}$ from parking spot
$l$ is an upper bound on the solution that serves $\sigma_{j}$ from parking
spot $i$. In conclusion, if the delivery person parks at $i\in\Pi\cap C$, then
there exists $\sigma_{j}\in J_{i}$ such that $y_{ij}=1$. ∎

###  A.4 Proof of Claim 4

###### Proof.

Assume $x_{ki}=1$ for some $k\in\Pi\setminus\\{i\\}$ but $y_{ij_{i}}=0$ in an
optimal solution. We will show there exists an equivalent solution to the CDPP
such that $y_{ij_{i}}=1$. Since $x_{ki}=1$, Claim 3 concludes there exists
$\sigma_{j}\in J_{i}$ such that $y_{ij}=1$. By assumption,
$\sigma_{j}\neq\sigma_{j_{i}}$. Define
$\sigma_{l}=\sigma_{j}\setminus\\{i\\}$. Observe that
$\sigma_{j}=\sigma_{j_{i}}\cup\sigma_{l}$. By the definition of $w_{ij}$ in
Section 3.1, it follows $w_{ij}=w_{ij_{i}}+w_{il}$. Since $f_{j}$ is linearly
dependent on the number of packages, it follows $f_{j}=f_{j_{i}}+f_{l}$. In
addition, $\sigma_{j_{i}}$ and $\sigma_{j_{l}}$ satisfy any capacity
constraints as subsets of $\sigma_{j}$. Therefore, the objective value of the
solution that services $\sigma_{j}$ when parked at $i$ is equivalent to the
solution that services $\sigma_{j_{i}}$ and $\sigma_{l}$ when parked at $i$. ∎

###  A.5 Proof of Corollary 4.2

###### Proof.

Let $\bar{J}=\\{\sigma_{j}\in J_{i}|\textrm{ }|\sigma_{j}|\geq 2\\}$. We
consider two cases: the vehicle parks at $i$ and the vehicle does not park at
$i$. If the vehicle parks at customer $i$, Claim 4 concludes $y_{ij_{i}}=1$.
By Constraints (4), it follows $y_{kj}=0$ for all $(k,j)\in\Pi\times J_{i}$
except $(i,j_{i})$. Since $j_{i}\notin\bar{J}$, $y_{ij}=0$ for all
$\sigma_{j}\in\bar{J}$. If the vehicle does not park at $i$, then
$\sum_{k\in\Pi}x_{ki}=0$. By Constraints (6), $y_{ij}=0$ for all
$\sigma_{j}\in S$. Since $\bar{J}\subset S$, $y_{ij}=0$ for all
$\sigma_{j}\in\bar{J}$. ∎

##  Appendix B General Model Improvements

In this appendix, we present model improvements that apply to the CDPP with
any loading time function $f_{j}$. The results of Section 5 are restricted to
when the loading time $f_{j}$ is linearly dependent on the number of packages
in the service set. First, we note that Claim 3 in Section 5 holds for any
loading time function $f_{j}$. Here, we provide additional general results and
point out that these results are strengthened in Section 5 when considering a
specific loading time function (i.e. $f_{j}=f\cdot|\sigma_{j}|$).

We strengthen the relationship between the $x_{ik}$ variables and $y_{ij}$
variables by identifying the purpose of the parking location. The delivery
person parks the vehicle to service customers on foot. If the delivery person
parks at parking location $i\in\Pi\setminus\\{0\\}$, Claim 5 shows a set of
customers is serviced while parked at customer $i$ in an optimal solution.

######  Claim 5.

If the delivery person parks at customer $i\in\Pi\setminus\\{0\\}$ (i.e.
$x_{ki}=1$ for some $k\in\Pi\setminus\\{i\\}$), then there exists
$\sigma_{j}\in S$ such that $y_{ij}=1$ in an optimal solution, i.e.

$\displaystyle x_{ki}\leq\sum_{\sigma_{j}\in S}y_{ij}$ $\displaystyle\forall
i\in\Pi\setminus\\{0\\},k\in\Pi\setminus\\{i\\}.$ (49)

###### Proof.

Assume $x_{ki}=1$ but $y_{ij}=0$ for all $\sigma_{j}\in S$. By Constraints
(5), there exists $l\in\Pi\setminus\\{k\\}$ such that $x_{il}=1$. Therefore,
the following contributes to the objective function in Equation (1):

$\displaystyle d_{ki}+d_{il}$ $\displaystyle=D(k,i)+p+D(i,l)+p$ (50)
$\displaystyle\geq D(k,i)+D(i,l)+p$ (51) $\displaystyle\geq D(k,l)+p$ (52)
$\displaystyle=d_{kl}.$ (53)

Equation (50) follows from the definition of the service times in Section 3.1.
Since $p\geq 0$, Inequality (51) holds. Since the driving time satisfies the
triangle inequality, we arrive at Inequality (52) which by definition of the
service times in Section 3.1 is Equation (53). We conclude that an optimal
solution is bounded below by a solution that drives directly from $k$ to $l$
without parking at $i$. Since $y_{ij}=0$ for all $\sigma_{j}\in S$, the change
in the solution structure maintains the feasibility of the solution. Thus,
Equations (49) hold for an optimal solution. ∎

Claim 5 concludes the delivery person services at least one customer set from
each parking spot. A key feature of the CDPP is that the delivery person can
serve multiple customer sets from the same parking spot. Therefore, the number
of parking spots is less than or equal to the number of services sets in an
optimal solution. Corollary 5.1 formalizes this observation.

######  Corollary 5.1.

The number of parking spots is less than or equal to the number of service
sets in an optimal solution, i.e.

$\displaystyle\sum_{i\in\Pi}\sum_{k\in\Pi\setminus\\{0,i\\}}x_{ik}\leq\sum_{i\in\Pi\setminus\\{0\\}}\sum_{\sigma_{j}\in
S}y_{ij}.$ (54)

##  Appendix C Detailed Experimental Results

Table 9 shows the average value of the two-echelon location-routing heuristic
across various capacities of the delivery person $q$ in the base case
(location-dependent parking times and $f=2.8$ minutes). For $n=50$, averages
are taken across ten instances. For comparison purposes, Figure 8 shows the
average optimal CDPP value for $n=50$ and $q=1$ to 4 packages. For $n=100$,
averages are taken across five instances. For comparison purposes, Table 10
shows the average optimal CDPP value for $n=100$ and $q=1$ to 2 packages.

| $q$
---|---
County | $1$ | $2$ | $3$ | $4$ | $5$ | $6$
Cook |  |  |  |  |  |
$n=50$ | 346.4 | 296.2 | 281.8 | 276.2 | 273.9 | 272.4
$n=100$ | 651.4 | 550.6 | 526.1 | 513.3 | 507.9 | 505.2
Adams |  |  |  |  |  |
$n=50$ | 308.8 | 293.0 | 290.5 | 290.3 | 290.2 | 290.2
$n=100$ | 564.4 | 528.6 | 523.2 | 521.7 | 521.7 | 521.3
Cumberland |  |  |  |  |  |
$n=50$ | 196.0 | 195.5 | 195.5 | 195.5 | 195.5 | 195.5
$n=100$ | 364.9 | 364.1 | 364.0 | 364.0 | 364.0 | 364.0
Table 9: Average value of the two-echelon location-routing heuristic across various capacities of the delivery person $q$ in the base case. | q
---|---
County | $1$ | $2$
Cook | 620.8 | 547.6
Adams | 537.4 | 514.2
Cumberland* | 360.5 | 359.9
Table 10: Average optimal value of the CDPP for $n=100$ across various
capacities of the delivery person $q$ in the base case.