Improving Commercial Vehicle Routing Through theConsideration of Cruising for Parking
Klaas Fiete Kruteina,∗ , Giacomo Dalla Chiarab and Anne Goodchildba Department of Industrial & Systems Engineering, University of Washington, Seattle, USA

kfkru@uw.edu, fietekrutein@gmail.com

b Department of Civil & Environmental Engineering, University of Washington, Seattle, USA

giacomod@uw.edu
annegood@uw.edu∗ Corresponding author

Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius IslandApril 4, 2022
Keywords: vehicle routing, parking efficiency, urban freight, logistics efficiency, parking cruising

1INTRODUCTION

Parking availability is a source of uncertainty for urban commercial vehicle drivers. To fulfill pickup and delivery activities, drivers have to not only navigate the urban road network in compliancewith traffic rules, interacting with other road users, but also select appropriate parking locations.
Over the last decades, carriers invested in technology and tools to provide drivers with optimized
route plans. While traffic patterns and time-dependent traffic density are sometimes part of these
considerations, to date, information on parking availability has not been part of these decisionmaking tools. The availability is still largely assessed by the driver in real-time upon arrival,
which can cause significant delays in the routing process if no parking is available and drivers
have to reroute, wait for availability and/or have to cover longer distances by foot. In addition,
the lack of visibility can cause public and traffic safety concerns and inefficient use of urban space,
if drivers choose to park in unauthorized spots due to a lack of alternative options (Dalla Chiara& Goodchild, 2020).
In recent years, cities and corporations have started investing into parking information systems
to collect data on historic driver behavior and bring digital visibility of parking to drivers andplanners. An important finding identified with these tools is the occurrence of cruising, which
describes the decision of a driver to queue, reroute, or circle the area to find better parking
Dalla Chiara & Goodchild (2020). Using historic data, cruising behavior can be predicted, considering the built environment in the area. While this insight raises different research questions
for drivers and for planners, one research question relevant to planners derived from this development is: If information on historic cruising for parking delays is available to drivers and planners,
how can this information be used to improve the routes of carriers in urban environments andincrease the cost efficiency of delivery routes? To address this question, this research combines
parking cruising estimates from real-world delivery data with vehicle routing through a timedependent traveling salesman problem with time-windows (TD-TSP-TW) to show the effect ofconsidering historic cruising delays in vehicle routing, against not using this information.
TRISTAN XI Symposium

Original abstract submittal

K.F. Krutein, G. Dalla Chiara and A. Goodchild2

METHODOLOGY

2.1

Data Acquisition

2

The used methodology consists of five steps. First, a set of historic route data was obtained. Thisdata was obtained from a beverage company that operates and delivers to a large set of customers
in the Seattle metropolitan area on a regular basis. The data consists of two years worth of datawith about 50 drivers, 2,000 customers and 60,000 deliveries, and has two components:• Ordered manifest data for every planned route (incl. delivery addresses, delivery coordinates, time windows, planned dwell times, driver names, load sizes)• GPS traces for every fulfilled route (incl. delivery addresses, delivery coordinates, experienced travel times from engine on to engine off in between stops, dwell times)
Furthermore, a time dependent travel time matrix for all delivery addresses in the data set wasgenerated from travel time forecasting data from the Google Travel Distance API (Google, 2021).

2.2Cruising Time Prediction

Using the GPS trace data, a cruising for parking time prediction model based on Dalla Chiara &Goodchild (2020) was developed to estimate the “true” travel time that reflects not only the timespent on the road driving to a certain destination but also the time spent searching for available
parking. The time of the day and the curb space parking allocation in a 100m perimeter of thedelivery addresses were included as additional predictors. The selected modeling method is a
log-normal regression. The model structure is described in Equation (1), where c represents thecorrected travel time from address a to address b, u represents the travel time as per travel time
matrix, n represents the total length of available curb space of curb type i within 100m arounddelivery address b, and h represents the arrival hour at time t.
log c = β0 + β1 log u +Xi∈I

βi ni +Xβt ht + ϵ(1)t∈T

The model was used to create an alternative travel time matrix that considers the parking delay
experienced at the curb. The adjusted R2 -value is 0.4005, the MSE is 0.416 min.

2.3

Routing Simulation

2.3.1

Model and Solution Method

To assess the impact of considering parking seeking on vehicle routing, a simulation study wasconducted. To consider both the effect of historic cruising data and account for data variation at
different times of the day, the route generation was modeled through a time-dependent expansionof the Traveling Salesman Problem with Time Windows (TD-TSP-TW) (Albiach et al., 2008).
The reason for choosing a TSP instead of a Vehicle Routing Problem (VRP), is the goal to isolate
the effect of the consideration of parking delays on a route and to make the routes comparable
between base case and improved case, which would be more difficult with a VRP due to the higher
degree of freedom. An important assumption made is that drivers choose one stop per delivery
address. Therefore, if multiple delivery addresses in the inputs were in close proximity (lessthan 50m), they were combined into a single stop, and the expected dwell times were added up.
Furthermore, it was assumed that upon finishing the delivery at an address, drivers immediately
depart to go to the next stop, as real-world drivers would not wait for a better departure time,even if the model would allow this. Hence, this approach represents an alternative to the work
presented by Martinez-Sykora et al. (2020), who consider the walking time in between parking
spot and delivery address separately, and Reed et al. (2021), who further consider the cruising
TRISTAN XI Symposium

Original abstract submittal

K.F. Krutein, G. Dalla Chiara and A. Goodchild

3time as an explicit cost component in the objective, but do not consider the time-dependencyof the cruising estimates. The cruising delays in their model were mostly compensated by adecision trade-off between walking and driving for deliveries.
Since the TD-TSP-TW requires time expansion and is therefore highly complex, the model was
solved using a meta-heuristic instead of a commercial solver, which has not been attempted
before. The chosen method is the Multi-Parent Biased Random-Key Genetic Algorithm (MPBRKGA) (Andrade et al., 2021), which solves the problem implicitly and requires a custom
decoder function that translates between the [0, 1] space that the genetic algorithm uses to represent the solution and the feasible region of the TD-TSP-TW. The decoder follows a similar
logic as the example case introduced by Bean (1994), where the order of deliveries is determinedby the random key values provided by the genetic algorithm. Figure 1 visualizes how every position in the chromosome, which length equals the number of delivery nodes n plus one additional
position, is allocated to a specific delivery address. Sorting the first n positions in the arrayby the random key value in increasing order, provides a route. The last position of the arrayindicates at what time in the depot departure time window, the route starts. Considering soft
penalties in the objective function for time window violations at the delivery nodes, a solution
can be evaluated quickly by the fitness function that minimizes the total route time.

Figure 1 – Translation from random key chromosome into fitness to TD-TSP-TW
Depending on the number of iterations, the algorithm yields a near-optimal objective value. To
the authors’ knowledge, this solution approach has not been applied to the TD-TSP-TW before.
2.3.2

Simulation Set Up

To establish a base case, where cruising for parking is not considered in routing, a benchmark
was created through optimizing routes with the TD-TSP-TW from step 2.3.1, using the originaltime-dependent travel distance matrix from Google Travel Distance Matrix API Google (2021).
Since drivers still experience these delays in reality even if the data is not considered in theroute generations step, the experienced route time is simulated through retroactively updating
the generated route using the corrected travel time matrix from step 2.2. To evaluate the effectof using the travel time matrix corrected by cruising for parking delays, the experiments wererepeated for the same routes, but this time using the corrected travel time matrix, where travel
times include cruising for parking time delays, already in the route optimization phase.

3PRELIMINARY RESULTS

The performance was evaluated and resulted in mean drive time savings of 1.5% (1.02 min perroute). The distribution of results is visualized in Figure 2. The plot shows that considering
cruising for parking does not always lead to drive time savings. The main reason is that theproblem was solved using a meta-heuristic, which cannot guarantee solution optimality. However,the simulation study shows that in the majority of cases savings could be generated throughconsidering the cruising delays in routing, in some cases with larger impacts.
TRISTAN XI Symposium

Original abstract submittal

K.F. Krutein, G. Dalla Chiara and A. Goodchild4

Figure 2 – Savings From Considering Cruising for Parking in Routing

4DISCUSSION

An analysis of the detailed route plan results has shown that the largest savings occur when theaddresses in the manifest are distributed in geographically uniform, clustered, or random shapes,
which allows for many viable alternative routes, and when the cruising delays vary substantiallybetween different time intervals. Most route manifests tested, however, follow a more linear
geographic distribution and thus, reversing the route is often the only viable alternative that
does not generate significantly longer routes. Therefore, the savings generated by considering
cruising delays are small for the tested data set, as the resulting routes are often similar, or atbest reversed. In addition, urban environments are exposed to many random events that are
difficult to model, hence the high noise levels found in the simulation. Nevertheless, the analysis
has provided evidence that time savings can be generated using historic data on cruising forparking in routing based on real-world data and that the significance of savings is dependent
on a few factors in the input data. Future research will focus on generating synthetic routes toexplore these effects further.

5ACKNOWLEDGEMENTS

This research has been supported by the U.S. Department of Energy’s Office of Energy Efficiency
and Renewable Energy (EERE) under the Award Number DE-EE0008462. The views expressedherein do not necessarily represent the views of the U.S. Department of Energy or the UnitedStates Government. We would like to thank the beverage company for providing the trip data.

References
Albiach, José, Sanchis, José María, & Soler, David. 2008. An asymmetric TSP with time windows
and with time-dependent travel times and costs: An exact solution through a graph transformation.
European Jounral of Operational Research, 189(3), 789–802.
Andrade, Carlos E., Toso, Rodrigo F., Gonçalves, José F., & Resende, Mauricio G.C. 2021. The MultiParent Biased Random-Key Genetic Algorithm with Implicit Path-Relinking and its real-world applications. European Journal of Operational Research, 289(1), 17–30.
Bean, James C. 1994. Genetic Algorithms and Random Keys for Sequencing and Optimization. ORSA
Journal on Computing, 6(2), 154–160.
Dalla Chiara, Giacomo, & Goodchild, Anne. 2020. Do commercial vehicles cruise for parking? Empiricalevidence from Seattle. Transport Policy, 97, 26–36.
Google, Inc. 2021. Google Distance Matrix API.
Martinez-Sykora, Antonio, McLeod, Fraser, Lamas-Fernandez, Carlos, Bektaş, Tolga, Cherrett, Tom, &Allen, Julian. 2020. 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.
Reed, Sara, Campbell, Ann Melissa, & Thomas, Barrett W. 2021. Does Parking Matter? The Impact ofSearch Time for Parking on Last-Mile Delivery Optimization. Unpublished Manuscript.

TRISTAN XI Symposium

Original abstract submittal