# Minimising Total Costs of a Two-Echelon Multi-Depot Capacitated Vehicle Routing Problem (2E-MD-CVRP) that Describes the Utilisation of the Amsterdam City Canal Network for Last Mile Parcel Delivery

Bartje Alewijnse, Alexander Hübl

► To cite this version:

Bartje Alewijnse, Alexander Hübl. Minimising Total Costs of a Two-Echelon Multi-Depot Capacitated Vehicle Routing Problem (2E-MD-CVRP) that Describes the Utilisation of the Amsterdam City Canal Network for Last Mile Parcel Delivery. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.603-612, 10.1007/978-3-030-85910-7_64. hal-03806534

HAL Id: hal-03806534

https://inria.hal.science/hal-03806534

Submitted on 7 Oct 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Minimising total costs of a Two-Echelon Multi-Depot Capacitated Vehicle Routing Problem (2E-MD-CVRP) that describes the utilisation of the Amsterdam city canal network for last mile parcel delivery

Bartje Alewijnse and Alexander Hübl

University of Groningen, Industrial Engineering and Management, The Netherlands

**Abstract.** An increase in e-shopping and (last mile) parcel deliveries has contributed to a rapid growth of urban freight transportation. This generates major impacts on city sustainability and liveability. Current solutions for urban logistics concern road traffic, but multiple Dutch cities have an extensive range of city canals that could be used for freight transportation over water. It was investigated how the city canal network of Amsterdam can be utilised for last mile parcel delivery, and what the related effects are. A MILP formulation of a Two-Echelon, Multi-Depot, Capacitated Vehicle Routing Problem (2E-MD-CVRP) was developed. The model describes a network in which ships transport parcels to predetermined satellite locations in the city centre, where the parcels are transferred to cargo e-bikes for the last mile of the delivery to the customer. The model was optimised by minimising the total costs, using the Genetic Algorithm (GA). The algorithm was able to find solutions but could not always stay within the constrained search space. Different possible network scenarios were evaluated, describing the consequences with respect to emissions, costs, and traffic flows. The results show promising economic, social, and environmental outcomes for a network with ships and cargo e-bikes instead of delivery vans. A daily and investment cost reduction of 16% and 36% respectively and a CO₂ emission reduction of 78.26% can be realised.

**Keywords:** Vehicle Routing Problem · Genetic Algorithm · Urban logistics · Last mile parcel delivery · City canal network · Cargo bikes

## 1 Introduction

During the last few years, urban logistics and last mile parcel delivery have become issues of great importance. The amount of city inhabitants is increasing, and people tend to order more goods online every day. In the Netherlands, one out of six vehicles in city centres is driving around for the transportation of goods. As a result, many cities are currently facing social, environmental, and economic problems caused by transport and traffic [3]. When travelling
through a city centre, one will almost always experience traffic congestion. In addition, cities become more polluted, and the number of accidents is increasing [7,5]. Consequently, new solutions are needed to enhance urban transport while decreasing the negative impacts described above.

Many of the current regulations and solutions for urban logistics concern land traffic, mainly on roads. However, multiple Dutch cities have an extensive range of city canals that could possibly be used for freight traffic over water. It has already been proven that (electric) waterway transport can contribute to sustainable logistics, so why not use this in urban areas as well [14]? In fact, the initial purpose of city canals was to serve as a waterway network for the transportation of goods and people [16,10].

Amsterdam, the capital of the Netherlands, has one of the most extensive city canal networks in the world. The aim of this paper is to evaluate a Vehicle Routing Problem (VRP) that describes a network which utilises ships in the city canals of Amsterdam, in combination with cargo e-bikes, for last mile parcel delivery. The goal is to investigate to what extent this solution would result in economic, environmental, and social benefits. A VRP is a combinatorial optimisation problem that calls for the optimal set of routes for a fleet of vehicles to deliver the demand of a given set of customers. In this case, the problem is divided into two levels or echelons. The first level consists of electric ships that leave the distribution centre at the Port of Amsterdam and drive through the city canals as a depot. These ships supply the cargo(e-)bikes that deliver the parcels to the customers in the second level. All locations where transfer of the packages between the vehicles of the two different levels is possible are called satellites. These satellites are located at docks in the city centre.

Section 2 elaborates on the case study that was conducted and the different scenarios that were evaluated. There exist many different variants of the Two-Echelon (2E) VRP [2]. In Section 3.1, the mathematical formulation of the applied 2E-VRP is given. Next, Section 3.2 focuses on the Genetic Algorithm that was used to optimise the model. Lastly, the results are presented in Section 4 and the final conclusion is given in Section 5.

## 2 Case study

A numerical analysis was executed in Python 3.7. The data set that was used represents the average daily parcel demand in Amsterdam for one transportation party. The effects were evaluated with respect to three different KPIs: costs (euros), CO₂ emissions, and traffic flows (given by the amount of vehicles per day).

Two different scenarios were analysed. In Scenario 1, it is assumed that all city canals and appointed (un)loading docks are available during the day. However, it is currently not allowed to transport goods through the canals in the inner part of the Amsterdam city centre between 10am and 8pm. Even though it is possible to receive a permit if one has a concrete plan which the municipality supports, this might not always be the case. Therefore, Scenario 2 only includes availability
of the canal network outside the city centre. In Scenario, 31 satellites (docks indicated by the municipality) are available for the (un)loading of the parcels. In Scenario 2, this was decreased to 11.

Furthermore, increasing portions or percentages of the total daily demand were used. This was called the delivery performance, which ranges from 25% to 130%. I.e. it was investigated what the effects are if x% of the current daily demand was delivered via the proposed network. The remaining parcels would then be delivered as usual, with electric vans. In order to compare the outcomes to this current situation, the effects when using electric delivery vans were evaluated too, using the same model (Section 3.1).

# 3 Model

## 3.1 MILP formulation

This problem can be defined as a Two-Echelon, Multi-Depot, Capacitated Vehicle Routing Problem (2E-MD-CVRP) [13]. Both levels of the problem are represented separately by the model that is formulated below. In other words, there are two MD-CVRPs. First, the routes of the second level fleet of cargo bikes should be determined, where the demand is given by the customer demand, and the (pre-determined) satellites in the city centre serve as depots. The outcome will then include the amount of parcels that should be distributed from every satellite, i.e. the demand for the ships. After that, the routes of the ships in the first level can be determined, where hubs at the Port of Amsterdam are the depots, and the satellites from where the cargo bikes should depart are the customers.

The mathematical formulation of these MD-CVRPs is defined on a graph $G = (V, A)$, where $V = \{1, \dots, n + w\}$ is the set of nodes and $A = \{(i, j) : i, j \in V, i \neq j\}$ the set of edges. $V$ consists of two subsets: the set of $n$ customers $V_c = \{1, \dots, n\}$ and the set of $w$ depots $V_d = \{n + 1, \dots, n + w\}$. At every depot, a fleet of vehicles, $K$ with each a maximum capacity $Q_k$ and fixed cost $h_k$ is available. All vehicles are restricted to a maximum work time $T$. For every customer $i$, a non-negative demand $p_i$ and service time $r_i$ is given. The travel cost and time between node $i$ and $j$ is given by $c_{i,j}$ and $t_{i,j}$ respectively.

The decision variable for this problem is given by the binary variable $x_{i,j}^k \in \{0,1\}$, which is equal to 1 if vehicle $k$ travels from node $i$ to node $j$, and 0 if otherwise. The MILP formulation of the model is given below.

$$ \min \sum_{i \in V} \sum_{j \in V} \sum_{k \in K} x_{i,j}^k c_{i,j} + \sum_{i \in V_d} \sum_{j \in V} \sum_{k \in K} x_{i,j}^k h_k \quad (1) $$

s.t.

$$ \sum_{i \in V} \sum_{k \in K} x_{i,j}^k = 1 \quad \forall j \in V_c \quad (2) $$
$$ \sum_{j \in V} \sum_{k \in K} x_{i,j}^{k} = 1 \quad \forall i \in V_c \quad (3) $$

$$ \sum_{i \in V} x_{i,h}^{k} - \sum_{j \in V} x_{h,j}^{k} = 0 \quad \forall k \in K, \forall h \in V \quad (4) $$

$$ \sum_{i \in V_c} \sum_{j \in V} p_i x_{i,j}^{k} \leq Q_k \quad \forall k \in K \quad (5) $$

$$ \sum_{i \in V} \sum_{j \in V} t_{i,j} x_{i,j}^{k} + \sum_{i \in V} \sum_{j \in V} r_j x_{i,j}^{k} \leq T \quad \forall k \in K \quad (6) $$

$$ \sum_{j \in V_c} x_{i,j}^{k} \leq 1 \quad \forall k \in K_i, \forall i \in V_d \quad (7) $$

$$ \sum_{i \in V_c} x_{i,j}^{k} \leq 1 \quad \forall k \in K_j, \forall j \in V_d \quad (8) $$

$$ \sum_{j \in V_c} x_{i,j}^{k} = 0 \quad \forall i \in V_d, \forall k \in K_i \quad (9) $$

$$ \sum_{i \in V_c} x_{i,j}^{k} = 0 \quad \forall j \in V_d, \forall k \in K_j \quad (10) $$

$$ \sum_{i \in S} \sum_{j \in S} x_{i,j}^{k} \leq |S| - 1 \quad S \subseteq V_c, 2 \leq |S| \leq n, \forall k \in K \quad (11) $$

$$ x_{i,j}^{k} \in \{0, 1\} \quad \forall i \in V, \forall j \in V, \forall k \in K \quad (12) $$

The objective function (1) aims to minimise the total costs. Constraints (2) assure that only one vehicle arrives at every customer exactly once, and Constraints (3) ensure that this single vehicle also leaves the customer once. Constraints (4) are flow conservation constraints, such that a vehicle leaves a customer after delivering. Constraints (5) state that every vehicle cannot be loaded beyond its capacity. Constraints (6) make sure that the total duration of the route does not exceed the defined work-day. Constraints (7) and (8) ensure that the vehicles also arrive and leave their home depots at most once. Constraints (9) states that a vehicle can only depart from its assigned home depot. In addition, Constraints (10) ensure that the vehicles may also only return to this assigned home depot, however, these are only applicable to the first level of the 2E-VRP. The ships should return to their home depot to spend the night and be re-loaded for the next day, but cargo bikes are finished as soon as they served the last customer of their route. Constraints (11) are sub-tour elimination constraints. Lastly, Constraints (12) define the binary variable that can either be equal to 1 or 0, depending on whether the vehicle travels along that arc. Solving this model will give a network including a required fleet size per depot, routes for the first and second echelon, and an applicable schedule.

The values assigned to the parameters of the mathematical model are given in Table 1 below.
<table><caption>**Table 1.** Parameter values mathematical model.</caption><thead><tr><td>Parameter</td><td>Ships</td><td>Cargo e-bikes</td><td>Delivery vans</td></tr></thead><tbody><tr><td>Speed [km/h]</td><td>6</td><td>24</td><td>30</td></tr><tr><td>Capacity [parcels]</td><td>1517</td><td>40</td><td>184</td></tr><tr><td>Work-day [hours]</td><td>9</td><td>4</td><td>8</td></tr><tr><td>Service time [hours]</td><td>0.5</td><td>0.05</td><td>0.05</td></tr><tr><td>Wages [euros/hour]</td><td>70</td><td>40</td><td>55</td></tr><tr><td>Operational costs [euros/100km]</td><td>20.92</td><td>0.15</td><td>10</td></tr><tr><td>Fixed costs [euros/vehicle/day]</td><td>19.17</td><td>3.30</td><td>28.50</td></tr><tr><td>Investment costs [euros/vehicle]</td><td>200,000</td><td>4,000</td><td>60,000</td></tr><tr><td>Emissions [kgCO<sub>2</sub>/km]</td><td>0.582</td><td>0.00417</td><td>0.278</td></tr></tbody></table>

## 3.2 Genetic Algorithm

The VRP is an NP-hard optimisation problem. Therefore, meta-heuristics should be used to guide the process of searching for solutions and approximate a sufficient solution. The Genetic Algorithm (GA) was used most often to successfully solve VRPs in general [12,6,4,15,1,8]. Also, it was found that the GA was able to optimise problems similar to the one introduced earlier. In the past, the algorithm accomplished to obtain high quality solutions for the 2E-CVRP [17]. In addition, the GA has proven to be a successful approach to optimise several MD-CVRPs [11]. However, it has not been applied yet to the specific 2E-MD-CVRP defined before. Therefore, the GA was implemented to solve this paper's VRP. Operators were applied that allow crossover, inversion and insertion mutation, and to merge routes. In addition, elite solutions were selected to be passed on to the next generation without alternations. The GA parameter values are given in Table 2. Different test-runs have shown that in general, the solution does not improve significantly anymore after approximately 200 generations.

<table><caption>**Table 2.** Parameter values genetic algorithm.</caption><thead><tr><td>Parameter</td><td>Value</td><td>Parameter</td><td>Value</td></tr></thead><tbody><tr><td>Number of generations</td><td>250</td><td>Insertion mutation rate</td><td>0.1</td></tr><tr><td>Population size</td><td>50</td><td>Merge routes rate</td><td>0.05</td></tr><tr><td>Crossover rate</td><td>0.05</td><td>Elite selection size</td><td>4</td></tr><tr><td>Inversion mutation rate</td><td>0.05</td><td></td><td></td></tr></tbody></table>

## 4 Results

In Figures 1 to 4 the outcomes per KPI (i.e emissions, costs, traffic flows) are visualised in bar charts. In every chart, both Scenario 1 and 2 are indicated, and the earlier introduced delivery performance changes over the x-axis. Red represents the effects caused by the electric ships, and yellow the cargo e-bikes.
In addition, the blue bars show the outcomes if (only) electric vans would be used.

When executing the experiments to find routes for the ships in Scenario 2, no feasible solutions were found. Only when the vehicle capacity was increased to 2000 parcels, the search space of possible solutions was found. Therefore, these results include this relaxation of the capacity constraint.

Also, the algorithm was not able to find feasible solutions for the delivery vans serving a demand of 50% or 100%. Consequently, the corresponding results were extrapolated using the solutions for the cargo e-bikes.

<figure><img src="image_3.png" /><figcaption>Fig. 1. Emissions per scenario.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 2. Daily costs per scenario.</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Fig. 3. Investment costs per scenario.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 4. Road traffic flows per scenario.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 5. Traffic flows on water per scenario.</figcaption></figure>
In addition, the solutions showed that the vehicle capacity was used up to almost 100% in every case. However, a utilisation of less than 50% of the total work-day capacity for the bicycle couriers was given. The route duration stayed under 2 hours, while their work-day was set to 4.

Furthermore, the algorithm was not always able to find feasible solutions. For Scenario 1, a relatively small percentage (between 8% and 21.2%) of the 250 generations offered feasible solutions for ship routes. However, in Scenario 2, after increasing the ship capacity from 1517 to 2000, this was almost equal to 100%. For the cargo bike routes the number of generations with feasible solutions was higher (between 7.2% and 100%). When considering this limited amount of successful generations, it can be stated that the current constraints are quite strict, and make it difficult for the GA to find sufficient solutions. Therefore, additional constraints such as traffic jams, multiple trips, and uniting the two levels, might make it impossible to find feasible solutions. Despite the experienced difficulties, it can be argued that the performance of the algorithm has shown to be sufficient in order to find an optimal set of routes for the vehicles. There are feasible solutions available that were optimised over at least 30 generations. Moreover, all solutions follow similar and constant trends, and show no significant outliers. However, even though previous research has shown much promise, the Genetic Algorithm applied to the mathematical model was not validated using another algorithm or meta-heuristic to compare it with. It could be possible that in this specific case, another algorithm shows different, e.g. more favourable, solutions.

Several conclusions can be drawn from the results. First of all, as the relative amount of customers that were served increases from 25% to 100%, the generated emissions, costs, and traffic flows rise as well (Figures 1 to 5). This applies mostly to the second level of the network, where cargo e-bikes are used, and less to the ships.

The generated emissions stay below 100 kgCO₂ per day for the proposed network (Figure 3). On the other hand, if delivery vans would be utilised this number goes up to more than 250 kgCO₂ per day, which means that employing ships and cargo e-bikes is more environmentally friendly.

When meeting 100% of the daily parcel delivery demand, the proposed network of ships and cargo e-bikes requires at best only 84% and 64% of the daily and investment costs respectively needed for delivery vans (Figures 1 and 2).

Regarding the traffic flows, the outcomes show that (at least) 3 ships are needed to meet 100% of the demand (Figure 5). This amount can be considered to be low, which means that no inconveniences will be caused in the city canals. In addition, around 150 cargo e-bikes are required to execute the last mile of the delivery (Figure 4). However, the bicycle couriers are assigned to routes that last on average less than 2 hours, while their work-day duration is set to 4. Therefore, it seems possible to let the bicycle couriers work two shifts. As a result, only half of the cargo e-bikes have to be acquired, which also significantly lowers the investment costs. In both cases, on a daily basis, 75 cargo e-bikes will drive around for 4 hours each, thereby replacing 8 delivery vans that occupy
the streets for 8 hours each. Since cargo bikes can be passed by easily and park on the pavement, this results in less traffic congestion which has several social, economic, and environmental advantages.

The favourable outcomes for Scenario 2 (limited canals) compared to Scenario 1 (all city canals) at first appear to be unexpected. This difference can be explained by the order of optimising the two levels of the VRP. First, the routes for the cargo e-bikes are determined. The availability of a larger amount of depots divides the pick-up or start locations of the cargo e-bikes over more satellites. As a result, the number of customers or stops for the ships increases as well. Therefore, a higher amount of ships and longer routes are required in Scenario 1. Uniting both levels and optimising them as one would solve this drawback and may lead to more optimal solutions.

# 5 Conclusion

A GA was used to optimise a 2E-MD-CVRP that describes a network of ships and cargo e-bikes for (last mile) parcel delivery in Amsterdam. When meeting a demand of 100%, favourable outcomes for a network with ships and cargo e-bikes compared to one with delivery vans were obtained. On a daily basis, 56.13 instead of 258.22 $kgCO_2$ will be emitted. Also, the daily and investment costs equal 11,627.95 and 1,192,000 euros, which saves 16% and 36% respectively compared to employing delivery vans. Moreover, the daily traffic flows are represented by 3 ships and 150 cargo e-bikes or 8 delivery vans. However, the bicycle couriers only work for a route duration of less than 2 hours, which means they could execute two trips. This could halve the number of cargo bikes to 75 and the related investment costs from 592,000 to 296,000 euros. Due to the current constraints, the algorithm was not always able to stay within the search space of feasible solutions. However, due to its constant behaviour it can be concluded that the solutions that were obtained sufficiently optimise the network. In the future, the solutions of the optimiser could be tested using discrete event simulation including stochastic effects [9].

# References

1. Boussaïd, Ilhem and Lepagnot, Julien and Siarry, Patrick: A survey on optimization metaheuristics. Information sciences **237**, 82–117 (2013)

2. Cuda, Rosario and Guastaroba, Gianfranco and Speranza, Maria Grazia: A survey on two-echelon routing problems. Computers & Operations Research **55**, 185–199 (2015)

3. Demir, Emrah and Huang, Yuan and Scholts, Sebastiaan and Van Woensel, Tom: A selected review on the negative externalities of the freight transportation: Modeling and pricing. Transportation research part E: Logistics and transportation review **77**, 95–114 (2015)

4. Deng, Puyuan and Amirjamshidi, Glareh and Roorda, Matthew: A vehicle routing problem with movement synchronization of drones, sidewalk robots, or foot-walkers. Transportation research procedia **46**, 29–36 (2020)
5. Ducret, Raphaëlle: Parcel deliveries and urban logistics: Changes and challenges in the courier express and parcel sector in Europe—The French case. Research in Transportation Business & Management **11**, 15–22 (2014)

6. Elshaer, Raafat and Awad, Hadeer: A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants. Computers & Industrial Engineering **140**, 106–242 (2020)

7. European Commission: Clean Transport, Urban Transport, https://ec.europa.eu/transport/themes/urban/urbanulsbility_en. Last accessed 22 Oct 2020

8. Ghoseiri, Keivan and Ghannadpour, Seyed Farid: Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm. Applied Soft Computing **10**(4), 1096–1107 (2010)

9. Hübl, Alexander and Altendorfer, Klaus and Jodlbauer, Herbert and Gansterer, Margaretha and Hartl, Richard F: Flexible model for analyzing production systems with discrete event simulation. Proceedings of the 2011 Winter Simulation Conference (WSC) 1554–1565 (2011)

10. Johnsen, Lenna and Duarte, Fabio and Ratti, Carlo and Xiaojie, Tian and Tian, Tina: A fleet of autonomous boats for Amsterdam. Landscape Architecture Frontiers **7**(2), 100–110 (2019)

11. Karakatič, Sašo and Podgorelec, Vili: A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing **27**, 519–532 (2015)

12. Kumar, Suresh Nanda and Panneerselvam, Ramasamy: A survey on the vehicle routing problem and its variants. (2012)

13. Ramos, Tânia Rodrigues Pereira and Gomes, Maria Isabel and Póvoa, Ana Paula Barbosa: Multi-depot vehicle routing problem: a comparative study of alternative formulations. International Journal of Logistics Research and Applications **23**(2), 103–120 (2020)

14. Rohács, József and Simongati, Gyozo: The role of inland waterway navigation in a sustainable transport system. Transport **22**, 148–153 (2007)

15. Stodola, Petr: Using metaheuristics on the multi-depot vehicle routing problem with modified optimization criterion. Algorithms **11**(5), 74 (2018)

16. Tussenbroek, Gabrië: De grachten van Amsterdam. 400 jaar bouwen, wonen, werken en leven. De Zeventiende Eeuw. Cultuur in de Nederlanden in interdisciplinair perspectief **30**(1), (2014)

17. Wang, Kangzhou and Lan, Shulin and Zhao, Yingxue: A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service. Journal of the Operational Research Society **68**(11), 1409–1421 (2017)