Impact of bot-return policies in truck-and-bot transportation
systems
M. Gajdaa,∗ , N. Boysenb , O.Gallaya
a University of Lausanne, Department of Operations, Quartier UNIL-Chamberonne, CH-1015

Lausanne, Switzerland
mikele.gajda@unil.cholivier.gallay@unil.chb Friedrich-Schiller-Universitaet Jena, Chair of Operations Management, Carl-Zeiss-Strasse 3,D-07743 Jena, Germany
nils.boysen@uni-jena.de∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

January 14, 2022Keywords: Last-mile delivery; Autonomous bots; Return policies; Fleet sizing.

1Introduction

Following the existing trend towards online shopping, home delivery services have been consistently increasing during the COVID-19 pandemic. This has created additional challenges formaintaining a satisfying supply level while meeting the growing expectations of stakeholders andcustomers for last-mile services. In Germany alone, it is forecast that by 2023, 4.4 billion shipments will need to be handled every year compared to 1.69 billion in 2000 (Boysen et al., 2021).
It is also worth noting the reluctant attitude of customers to accept higher prices, while they still
demand for fast and efficient deliveries, as it is highlighted in Joerss et al. (2016). Given theseever-increasing challenges, alternative delivery modes, in substitution for traditional truck delivery systems, are likely to be beneficial from multiple viewpoints. New delivery modes have been
made available in a recent past as a result of technology advances in domains such as digitization
and automation. These new technologies are expected to play an important role in industrializedcountries, where the aging population puts additional stress on the logistics job market, (Otto &Battaïa, 2017). In this work, we focus on small autonomous delivery robots (SADRs), when usedin combination with trucks. SADRs, also named bots, travel at pedestrian speed along sidewalks,
and they are transported to and released from trucks at appropriate drop-off points. We rely ona system characterized by the presence of bot stations, to which the bots return autonomously
after completing a job, and where their batteries are swapped. Then, a truck picks the bots up
again, loads a parcel into them, and transports them to their next drop-off point. Choosing theright return policy for the bots (i.e., to which bot station they should return) is likely to heavily
impact the required bot fleet size to achieve a given set of deliveries at a given service level.
In this work, we evaluate and compare various bot return policies regarding their operational
efficiency.
TRISTAN XI Symposium

Original abstract submittal

M.Gajda, N. Boysen, O. Gallay

22d1dC

C6

1C2

D2

3C42

dC3Start (t)End (t)C1D1710C2D1

710C3D1

1215C4D2

12C5D2

14C6D2

16

SADR route

11Origin

Truck route
C52Destination
Customer

21D1d1

D

Robot depotd

Drop-off point

7C1

1

Figure 1 – Example of a given service plan and its resulting delivery jobs.

2Problem description

As shown by Boysen et al. (2018), when bot stations are available in the delivery network,
the truck waiting time for bot to return after a delivery is drastically reduced compared tothe situation where the bots would be picked up by the trucks themselves at determined pickup points. In the same work and focusing on this situation, the authors provide truck routes
together with bot scheduling solutions for a large set of various instances. We refer at this typeof output solutions as service plans, which is the starting point for the present work. A service
plan defines for a given set of customers to be served:• a truck route visiting bot stations and drop-off points;• a scheduling plan for the bots, which defines where and when they are picked up andreleased;• a timing for the entire delivery process.
In Figure 1, we display the combination of two truck routes and associated bot scheduling plans,computed using the methodology introduced in (Boysen et al., 2018). In order to make the bots
as reusable as possible for other trucks later in their schedule, we focus in this work on evaluating
different return bot policies for the bots, namely the dedicated-station policy, the closest-station
policy, and the most-suitable-station policy.
We consider a set J of delivery jobs, in which each job j ∈ J is defined by an origin oj , adestination dj , an initial time ij , and an ending time ej . Each job is performed by one bot b ∈ B.
Ultimately, we aim at computing a solution that minimizes the bot fleet size and which is definedby two main components: an assignment a that matches each job of j ∈ J to a bot b ∈ B, andthe definition of the bot stations that are visited by a bot which performs two consecutive jobs
j and j 0 . Let Ωa be the set of job pairs (j, j 0 ) that are executed in direct succession by a samebot b ∈ B. An intermediate bot station s has to be determined for each (j, j 0 ) ∈ Ωa . A solution
is considered feasible:• If each job j ∈ J is assigned to exactly one bot b ∈ B in assignment a.
• When two jobs j and j 0 are assigned to the same bot to be executed in direct succession,then there must be enough time for the bot to visit its associated bot station bj,j 0 in
between. In other words, it means that ij 0 ≥ ej + δ(dj , bj,j 0 ) + δ(bj,j 0 , oj 0 ) must hold foreach (j, j 0 ) ∈ Ωa , where δ(o, d) represents the bot travel time from o to d.
The selected bot return policy has an influence on the feasibility of a solution. Specifically,
our three alternative policies add respective specific feasibility constraints to the problem:
TRISTAN XI Symposium

Original abstract submittal

M.Gajda, N. Boysen, O. Gallay

3• Dedicated-station policy: we assign each bot to a unique bot station. This means that foreach bot b ∈ B, all jobs assigned to b must have their origin at the same bot station. Thus,oj = oj 0 for all (j, j)0 ∈ Jba , with j 6= j 0 , and where Jba ⊆ J is the set of jobs assigned tobot b within assignment a.
• Closest-station policy: bots must return to the closest bot station after completing the job.
This means that the distance δ(dj , bj,j 0 ) for all (j, j 0 ) ∈ Ωa must be minimized among all
existing bot stations.
• Most-suitable-station policy: with this policy, no additional constraints are added on thechoice of the returning bot station as all of them are eligible.
Our bot fleet size problem seeks the smallest possible fleet size |B|, in the situation where
the three above bot return policies are implemented.

3Methodology

We define an alternative view of the problem making use of a minimum cost bipartite matching
methodology, with adaptations depending on the bot return policy to evaluate.
Dedicated-station policy: as each bot returning to its original station is a strong constraint, theproblem decomposes into multiple station-specific sub-problems (one for each bot station wherejobs originate). We introduce a bipartite graph G = (V, E, c) for each of these sub-problems,
where V is composed by bot nodes and job nodes; edges E are the possible connection between
nodes: Bot2Bot, Bot2Job, Job2Job, and Job2Bot, each characterized by a cost c. The graph G
has bipartition (P, Q), where P represents the successors nodes and Q represents the predecessors nodes, with |P | = |Q| = 2 · |J 0 |, and where J 0 ⊆ J is the subset of jobs corresponding to thesingle bot station under consideration in this sub-problem. There exist |J 0 | potentially usablebots (i.e., upper bound), these are called bot nodes. In both the bipartitions P and Q, there
is a given number of job nodes and the edges between these two bipartitions have the following
meaning:• Bot2Bot: indicates that this bot is not required in the solution; edge weight ce = 0;
• Bot2Job: from P to Q, indicates that the job is the first one performed by that bot; edge
weight ce = 1;
• Job2Job: j ∈ P is connected with a different j 0 ∈ Q, which indicates that j 0 is performedby the same bot after finishing j; edge weight ce = 0.
• Job2Bot: job j ∈ P is connected to bot in Q, which indicates that j is the last job performedby that bot; edge weight ce = 0.
For the resulting bipartite graph, a minimum cost bipartite matching, where each node of P ismatched with exactly one node of Q and the sum of selected edge weights is minimal, can beobtained in polynomial time using an adaptation of the well-known Hungarian method (Kuhn,1955), which runs in O(n3 ), where n = 2 · |J 0 | in this case.
Closest-station policy: with bots (potentially) returning to different bot stations, the bot fleet
sizing problem no longer decomposes into single-station sub-problems. We thus consider a uniquegraph G, where bipartition (P, Q) receives |P | = |Q| = 2 · |J| nodes as defined above (i.e., |J|bot nodes and |J| job nodes). The only other alteration arises for the Job2Job edges, which areinserted between a job j ∈ P and its successor job j 0 ∈ Q only if sj = oj 0 , where sj refers to the
bot station being the closest to job j, and ij 0 ≥ ej + δ(dj , sj ) holds. The weights of these edges
are set to ce = 0.
TRISTAN XI Symposium

Original abstract submittal

M.Gajda, N. Boysen, O. Gallay4

Most-suitable-station policy: The most-suitable-station policy offers bots even more flexibility
to switch between bot stations based on which one is the most convenient. Since multiple trucks
are active in the same area, bot stations are chosen based on the truck routes and the demand forbots at the various stations, as long as these stations are reachable by the bots after completing
their job.

4Insights on results

We consider a large set of instances resulting from those generated and solved (regarding thescheduling dimension) in (Boysen et al., 2018). By merging together several of the instancesconsidered in Boysen et al. (2018), we are facing complex delivery networks, similar to those
appearing in real situations, in which several trucks are serving customers with the use of SADRs.
Our work quantitatively studies the critical impact played by the three considered bot-return
policies on the minimum bot fleet required to fulfil a number of given set of jobs. We observe
significant discrepancies when implementing these distinct return policies. These differences
depend on the one hand on the pre-computed truck routes, and on the other hand on theheterogeneous network layouts that are considered, namely the distribution of the bot stations,the customers and the drop-off points. This aspect suggests that before setting up a two-echelon
system based on truck and SADRs, it is of utmost importance to carefully analyze the geographic
space and the demand distribution in order to establish a distribution of prospective bot stations
and drop-off points. Observing that both the network layout and the bot-return policy influence
the bot fleet size, our findings help in answering several questions that must be raised before
implementing such novel truck-and-bot transportation systems for last-mile deliveries, which
include:• How many bot stations should be implemented to serve a given set of customers using nbots and m trucks?
• When only a limited number of bot stations can be opened, how should their location bedetermined?
• In which way the bots should be distributed between the available bot stations?
• Which impact has the chosen bot return policy on the required bot fleet size to satisfy agiven set of jobs?
While studying formally the best feasible return bot strategies to be implemented for truckand-bots delivery systems, focusing on the above aspects helps us provide useful information for
decision-makers in this context.

References
Boysen, Nils, Schwerdfeger, Stefan, & Weidinger, Felix. 2018. Scheduling last-mile deliveries with truckbased autonomous robots. European Journal of Operational Research, 271(3), 1085–1099.
Boysen, Nils, Fedtke, Stefan, & Schwerdfeger, Stefan. 2021. Last-mile delivery concepts: a survey froman operational research perspective. OR Spectrum, 43(1), 1–58.
Joerss, M, Schroder, J, Neuhaus, F, Klink, C, & Mann, F. 2016. Parcel Delivery: the Future of Last
Mile. Mckinsey & Company Report.
Kuhn, Harold W. 1955. The Hungarian method for the assignment problem. Naval Research Logistics
Quarterly, 2(1-2), 83–97.
Otto, Alena, & Battaïa, Olga. 2017. Reducing physical ergonomic risks at assembly lines by line balancing
and job rotation: A survey. Computers & Industrial Engineering, 111, 467–480.

TRISTAN XI SymposiumOriginal abstract submittal