A multi-modal and variable-echelon last-mile delivery system
C. Baylissa∗ , T. Bektaşa , V. Tjon-Soei-Lenb and R. Rohnerba University of Liverpool, Management School, Liverpool, UK

Christopher.Bayliss@liverpool.ac.uk, T.Bektas@liverpool.ac.uk
b Darwin Evolution Technologies, UKvernon@bezos.ai, remo@bezos.ai∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

March 28, 2022
Keywords: Open vehicle routing; multi-modal variable-echelon; mobile satellites; cargo bikes

1

INTRODUCTION

Online retail is accounting for an ever increasing of portion of all retail sales. In the UK alone, thevolume of the parcel market reached 2.6 billion items in the 2018-19 financial year (Ofcom, 2019).
Online sales channels have lead to increased competition with retailers trying to increase theirmarket share by offering lower prices and cheap fast delivery to the customer’s doorstep Whenhome delivery demand density is sufficiently high, hiring storage spaces in areas close to points ofdemand can become cost effective, since it reduces warehouse-to-delivery-zone stem costs. Also,
when demand density is sufficiently high and package sizes are small, it can become cost effective
to make use of alternative modes of delivery, such as cargo bikes and porters (walkers), whichhave relatively limited capacity but are environmentally friendly. When the vehicle fleet is highly
diversified and some vehicles have limited carrying capacity or range, mobile satellites (kerb side
spaces) can be used for transferring parcels between delivery modes en-route.
In this work we address a routing problem that arises within a logistics network composed ofmultiple localised storage warehouses and a diverse fleet of delivery vehicles. Delivery of an item
may be made using a sequence of different transport modes (multi-modal delivery). Parcels canbe transferred to and from any pair of vehicle types, hence we consider a pick up and delivery
problem with a variable echelon structure.

2

LITERATURE REVIEWOne recent focus in last-mile delivery research is the use of environmentally friendly vehicles suchas electric vehicles or porters (walkers). Allen et al. (2018) analyse data from delivery routesof two different parcel carriers operating in London, with the aim of evaluating the potential
benefits of utilising porters in conjunction with truck deliveries. It was found that, on average,
trucks spend 60% of the time stationary, while drivers make deliveries on foot, and that handing
over parcels to porters, at relatively few drop off points has the potential to reduce vehicle time by
55% while increasing vehicle utilisation. Martinez-Sykora et al. (2020) develop an optimisation
model for last-mile delivery in London using a combination of walking and driving. Performing
sequences of deliveries on foot, within a vehicle route, can be helpful in densely populated areas
where kerbside parking space is hard to find.
TRISTAN XI Symposium

Original abstract submittal

C. Bayliss, T. Bektaş, V. Tjon-Soei-Len and R. Rohner

2

When deliveries are outsourced to third party logistics providers or couriers, vehicles need notstart from and end at a specific vehicle depot, in such cases the vehicle’s routes are referred toas open routes. Yu et al. (2020) consider a two-echelon open location routing problem for urbandelivery. The first echelon consists of (closed) trunk routes from the main depot to kerbside
inventory exchange points, where inventory is transferred to third party logistics providers who
use motorcycles for (open route) delivery.
Multi-modal delivery concepts which make use of kerbside inventory exchange points require
the tours of the vehicles involved to be synchronised. Drexl (2012) provides a classification andreview of VRPs with multiple synchronisation constraints. As an archetypal example, the VRP
with trailers and transshipments (VRPTT) is used. The main synchronisation issues include
determining when must some vehicles be simultaneously present and when some events need toprecede others. To the best of our knowledge no other work considers a multi-modal and variableechelon delivery system described in this work.

3

PROBLEM DESCRIPTION

Demand is generated by customers who require home deliveries of products for which inventory
can be stored across any number of storage warehouses. Parcel deliveries to customers must be
made within specific time windows. A fleet of vehicles consisting of vans, cargo bikes and porters(walkers) are available for making deliveries. Each vehicle type has their own maximum volume,
maximum weight, drop times, maximum tour length, maximum tour duration and travel speed.
Tours can begin at any warehouse or mobile satellite. Tours end at either a warehouse, customer
or mobile satellite. Such tours are called open tours, which are appropriate when deliveries areto be carried out using third party logistics providers.
Deliveries can be made either: (i) directly from a warehouse to a customer using a single
vehicle, or (ii) using multi-modal transport, where parcels can be transferred from one vehicle
to another by making use of kerb side handover points. For example, a van can meet with anumber of cargo bikes and porters at a mobile satellite, who receive inventory which they thendeliver. Warehouses can also be used as inventory handover points, which have storage capacity
and therefore do not require the vehicles involved to be simultaneously present.
Routes incur travel costs dependent upon tour length (fuel) and duration (wages), and eachvehicle used invokes a fixed cost. The objective is to determine a fleet configuration, i.e., numbersof van, cargo bike and porters, and plan a set of routes which are feasible and transport all parcels
to the required locations, at a minimum total cost.
As an example to highlight the flexibility of the approach, a feasible solution may include avan, a cargo bike and a porter. The van may start from a warehouse, visit a mobile satellite andtransfer inventory to the cargo bike, before making some customer deliveries. The cargo bikemay then visit another mobile satellite where inventory is transferred to the porter, who thenmakes some customer deliveries. The cargo bike may then meet with the van a second time atanother mobile satellite to restock, before both carry on to perform the remaining deliveries.

4

HEURISTIC ALGORITHM

We propose a two-phase heuristic solution methodology. First a constructive phase, followedby an improvement phase. While time remains, this procedure is repeated and the algorithm
generates more solutions, always keeping track of the lowest cost solution generated overall.
The constructive phase is based on building a solution, one step at a time, where in each step,
we find a way to modify the current solution such that a another customer’s delivery is fulfilled,
and continue until all customer orders are fulfilled. The 6 ways (referred to as operations) inwhich another customer’s order can be included in the current solution are as follows: 1) Add acustomer to an already utilised vehicle’s route; 2) Change the type of an already utilised vehicle
TRISTAN XI Symposium

Original abstract submittal

C. Bayliss, T. Bektaş, V. Tjon-Soei-Len and R. Rohner3and visit another customer; 3) Use an existing vehicle rendezvous to generate extra opportunities
to visit another customer; 4) Change the type of an already utilised vehicle and use an existingvehicle rendezvous to generate extra opportunities to visit another customer; 5) Visit anothercustomer by using a new vehicle directly or in conjunction with an existing or a new vehicle
rendezvous; and 6) Add new vehicle rendezvous in the hope that applying the above operations
again generates a way to add another customer to the current solution. These 6 operations are
considered in this order, and we stop when we find the first operation that provides a feasible
way to include another customer in the current solution. Lower cost operations have a higher
probability of selection. The logic behind the ordering of operations is that the earlier ones are
simpler and cheaper and the latter ones are more expensive and generally redundant if earlier
ones return feasible decisions. For example, there is no need to swap a porter to a van (Operation
3) if the porter can still visit more customers, since the porter is generally cheaper.
While the constructive heuristic provides a diversification mechanism, a local search provides
an intensification mechanism. The local search improvement phase focuses on improving theroute efficiency of sub-routes, which consist of customer sequences without vehicle rendezvous in
between, thereby leaving the logistic backbone of the solution, including any vehicle rendezvous
and warehouse visits, intact. The local search procedure uses two neighbourhood structures:i) two-opt, which removes unnecessary cross-overs in routes; and ii) cut-and-insert, which finds
more efficient alternative positions for each customer.

5

COMPUTATIONAL RESULTS

Experiments were conducted on an instance based on real sales data within London that includes
demand information for 340 customers. A customer order comprises a delivery location and aset of parcels, each of which has a size (scalar volume) and a weight. A depot is located on
the outskirts of London, and five mobile satellite locations are distributed across the city. Vans,
cargo bikes and porters are available for making deliveries, and there relative characteristics aredesigned to reflect reality. In general, larger vehicle types are more expensive but have higher
capacity and range. Smaller vehicle have shorter customer service times. Prior to the main
experiments, the proposed heuristic was first benchmarked against an integer linear programming
formulation developed for the problem and was able to find optimal solutions for all instanceswith up to 20 customers. Further tests were run on existing benchmark instances of the open
vehicle routing problem (Ruiz et al., 2019), on which the heuristic achieved an average gap of
3.73% in comparison to best known solutions reported in the literature.
The experiment compares three scenarios, which differ in the way that vehicles can be used tomake deliveries, namely Scenario S) Only vans are allowed to make deliveries and no rendezvous
are allowed at mobile satellite locations; Scenario M) Vans, cargo bikes and porters are allowed
to make deliveries, but no rendezvous are allowed at mobile satellite locations; and Scenario
MM) Vans, cargo bikes and porters are allowed to make deliveries, and rendezvous are allowed
at mobile satellite locations. Each instance is solved using the proposed heuristic method.

Instance
S
M
MM

Solutioncost (£)
985.01
943.20898.51

Solutiontime (s)2678.422760.224207.03

Vehiclesused(7)(5 2 0)(5 2 0)

Total
miles
241.38245.43223.78Van
miles
241.38190.03165.20Cargo bike
miles
0
55.40
58.58

Iterations
4000
4000
4000

Table 1 – Three scenario experiment results
Table 1 provides solution costs, solution times, the numbers of vehicles of each type used ineach solution, total miles, van miles and cargo bike miles and the number of iterations completed.
The results show that scenario 3, where multiple vehicle types and vehicle rendezvous at mobile
TRISTAN XI Symposium

Original abstract submittal

C. Bayliss, T. Bektaş, V. Tjon-Soei-Len and R. Rohner

4

Figure 1 – Vehicle route solutions for instances S, M and MM.
satellites are allowed, leads to the lowest solution costs. Similarly, scenario 2, always provides
lower cost solutions than scenario 1, thus highlighting the potential benefits of utilising smaller
vehicles with lower fixed and variable costs. Table 1 shows how the relative savings, between thethree scenarios, were made. Scenarios 2 and 3 both exploits vehicle types with lower fixed andvariable costs, and as a result reduces van miles, and therefore tailpipe emissions. Scenario 3
can also significantly reduce the total distance that must be travelled, which can be attributed
to reduced warehouse stem costs. Figure 1 depicts the differences between the three scenarios.
Porters are only used when the spatial scale of the instance is reduced and parcel sizes reduced.

6

CONCLUSIONS

The multi-modal and variable-echelon last-mile delivery system described in this work is designed
to take advantage of cost and externality savings brought about through the use of distributed
inventory storage, coordinated use of alternative vehicle types and use of mobile satellites fortransporting inventory between vehicle during delivery routes. Experiments conducted on real
data showed that allowing the use of alternative vehicle types, such as cargo bikes, and making
use of vehicle rendezvous at mobile satellites, both introduce cost reducing degrees of freedom
into the routing optimisation problem.

ACKNOWLEDGEMENTS
We thank InnovateUK (Project No: 45624) for funding this work.

References
Allen, Julian, Bektaş, Tolga, Cherrett, Tom, Bates, Oliver, Friday, Adrian, McLeod, Fraser, Piecyk,
Maja, Piotrowska, Marzena, Nguyen, ThuBa, & Wise, Sarah. 2018. The Scope for Pavement Porters:
Addressing the Challenges of Last-Mile Parcel Delivery in London. Transportation Research Record,2672(9), 184–193.
Drexl, Michael. 2012. Synchronization in vehicle routing—A survey of VRPs with multiple synchronization constraints. Transportation Science, 46, 297–316.
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, 645–693.
Ofcom. 2019.
Annual monitoring update on the postal market. Financial year 2018-19. Technical Report. Available at https://www.ofcom.org.uk/__data/assets/pdf_file/0028/186139/
annual-monitoring-update-postal-market-18-19.pdf.
Ruiz, Efrain, Soto-Mendoza, Valeria, Barbosa, Alvaro Ernesto Ruiz, & Reyes, Ricardo. 2019. Solving theopen vehicle routing problem with capacity and distance constraints with a biased random key genetic
algorithm. Computers & Industrial Engineering, 133, 207–219.
Yu, Vincent F., Winarno, Lin, Shih-Wei, & Gunawan, Aldy. 2020. Design of a two-echelon freight
distribution system in an urban area considering third-party logistics and loading–unloading zones.
Applied Soft Computing Journal, 97, 106707.

TRISTAN XI Symposium

Original abstract submittal