# Evaluating the Deployment of Collaborative Logistics Models for Local Delivery Services

Andrea Bari, Fabio Salassa, Maurizio Arnone, Tiziana Delmastro

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

## To cite this version:

Andrea Bari, Fabio Salassa, Maurizio Arnone, Tiziana Delmastro. Evaluating the Deployment of Collaborative Logistics Models for Local Delivery Services. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.613-621, 10.1007/978-3-030-85910-7_65. hal-03806521

HAL Id: hal-03806521

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

Submitted on 7 Oct 2022

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_3.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.
Evaluating the deployment of collaborative logistics
models for local delivery services

Andrea Bari¹, Fabio Salassa¹[0000-0002-9698-6892], Maurizio Arnone²[0000-0002-0948-9346] and Tiziana Delmastro² [0000-0002-3418-865X]

¹ Politecnico di Torino, DIGEP, Corso Duca degli Abruzzi 24, 10129 Torino, Italy
andrea.bari@outlook.it, fabio.salassa@polito.it

² LINKS Foundation - Leading Innovation & Knowledge for Society, via Pier Carlo Boggio 61,
10138 Torino, Italy
{maurizio.arnone,tiziana.delmastro}@linksfoundation.com

**Abstract.** The current pandemic situation and lockdowns have given rise to various problems not only of public health but also of organization of daily activities, especially in the purchase and delivery of goods. As a response to newly generated needs for customers’ demand, in this work, we try to evaluate several aspects for the deployment of collaborative logistics models aimed at the optimization of local delivery services.

**Keywords:** Collaborative logistics, Pickup and Delivery, Optimization.

# 1 Introduction

The current pandemic situation in Italy has given rise to various problems not only of public health, but also of organization of daily activities. Prolonged lockdowns implemented not only in Italy, but also in many countries have often radically changed the habits of most of the citizens. The purchase of food and non-food consumer goods is certainly an aspect that has changed in daily life due to the difficult access to shops for many people, for example, the elderly and all those who, for reasons of contagion, have been placed in quarantine.

During 2019, business-to-consumer e-commerce in Italy has reached a turnover of 31.6 billion euros, with the biggest increase ever, compared to the previous year (+15%). As in the past, consumers buy online more products than services (products accounted for 18.1 billion euros). Moreover, the first quarter of 2020 has registered a further boom in e-commerce sales due to the COVID19 outbreak: during the third week of March the online consumer goods sales increased by 142.3% compared to the same week in 2019 [8-10]. In this period, many large-scale retailers have organized themselves to enhance their home delivery services of consumer goods. Despite this, in many cases, this was not enough to cover the rising demand and it was not unusual that, during periods of total lockdown, the waiting times for deliveries increased dramatically. In addition, the emergency has pushed many small retailers toward e-commerce
and local shops have undergone changes to carry out delivery services for their customers.

B2C e-commerce entails, however, high complexity of logistic activities in the supply chain. As the most complicated segment of the logistic chain, last-mile delivery seems to account for about 30% of total transport costs (up to 50 in some cases) [7].

The study carried out in this paper was born in this context. The purpose is in fact to respond to the need on the one hand of customers to be able to buy not only through large-scale distribution platforms but also from local neighborhood shops. On the other hand to allow local merchants to save delivery costs and time in a collaborative logistics framework for goods delivery. The main idea of the project is to study if and under what conditions a collaborative delivery system, in which several local retailers share a (private or outsourced) delivery service, is sustainable from an economic and operational perspective. The collaborative system will pursue an optimised organization of deliveries and a reduction in the number of circulating vehicles, empty miles and, consequently, in traffic and air pollution, thus also trying to achieve environmental sustainability. To the best of authors' knowledge, we introduce a new variant of the Vehicle Routing Problem with Pickups and Deliveries, which models this particular delivery service.

The studied problem belongs to the broader class of *Pickup&Delivery* problems (PDP) [2]. We focus here on a variant that allows for multiple visits to locations where we consider that local shops and customers are set. Specifically, the routing problem can have multiple location visits as resulting from divisible pickups and deliveries. Other variants of the classic problem may include single commodity problems with split loads, that is, everything that is to be picked up from (delivered to) a location has the same destination (origin) (e.g. [4]). For divisible pickups and deliveries, each location can serve as a pickup and/or delivery point for multiple commodities (e.g. [6]). That is, every location may require transportation of loads to and/or from multiple other locations. Our problem classifies as a problem with divisible pickups and deliveries. Moreover, we restrict the problem to a maximum length for each route as a result of a working shift for drivers and capacitated vehicles. Very recent papers on similar variants with single and multiple vehicles of PDP are [1], [3] and [5].

The remainder of the paper is as follows. Section 2 is dedicated to the description of the optimization problem that has to be managed for the depicted collaborative logistics delivery service. In section 3 a solution approach for the presented problem is proposed. Finally, in Section 4 and 5, results and conclusions are given.

## 2 Problem Description

The project that is the subject of this work aims to support, in various ways, collaborative commerce enterprises through the use of optimization technologies to achieve greater competitiveness in the management of specific aspects of business such as logistics, home deliveries, orders management etc.

The problem is defined on a graph, $G = (V, A)$, in which the set of vertices $V = P \cup D \cup \{0\}$. $P = \{1, ..., p\}$ is the set of pickup nodes, and $D = \{p + 1, ..., p + n\}$ is the
set of delivery nodes where $|D| = n$ and $p \le n$. The node 0 in G defines the starting and ending depot. Let $R = \{r_1, ..., r_m\}$ be the set of requests to be routed where $|R| = m$ and $m \ge n$: every customer can make an order to one or multiple stores, thus each customer can make multiple requests and each shop is assigned to multiple requests from multiple customers. Each request $r \in R$ is represented by one pick-up node $p_r \in P$ and one delivery node $d_r \in D$ with a volume quantity, $q_r$. All the pick-up nodes must be visited before the delivery nodes for each request, $r \in R$. K is the set of identical capacitated vehicles that can be used located at the depot 0, with $|K| = p$. The set of arcs is $A = V \times V$, each arc $(i, j) \in A$ has an associated travel time $t_{ij} \ge 0$. It is assumed that the travel times satisfy the triangular inequality: $t_{ij} \le t_{il} + t_{lj} \quad \forall i, j, l \in V$. Each node $n_i \in N$ has a service time $s_i$ for loading or unloading at that node. Each node $p_i \in P$ has a quantity of requests to load onto the vehicle, $Q_i \ge 0$, which is the sum of quantities of all the requests having node i as the pick-up node. The sum of the volumes loaded on the vehicle is constrained by the capacity of the vehicle, $C_k$. All the orders loaded on the vehicles must be delivered in the $T_k$ hours slot time, so every vehicle $k \in K$ can do a tour of at most $T_k$. The objective is to minimise the total distance travelled by the vans and also to minimise the number of used vans.

In the current situation, every retailer carries out the deliveries for his customers with a distinct (privately owned) vehicle, without any coordination among the different shops. This situation is used as a benchmark for the proposed business model of collaborative deliveries.

## 3 Solution Approach

Algorithm 1 depicts main algorithmic ingredients used to solve the proposed problem.

<table><thead><tr><th colspan="2">Algorithm 1 Heuristic Algorithm</th></tr></thead><tbody><tr><td>1:</td><td><strong>procedure</strong> Creation routes</td></tr><tr><td>2:</td><td><strong>for</strong> each shop <strong>do</strong></td></tr><tr><td>3:</td><td>TSP (Input: Nodes, Output: Path)</td></tr><tr><td>4:</td><td>Add Path in Best</td></tr><tr><td>5:</td><td>Add Path in Bench</td></tr><tr><td>6:</td><td>Calculate Centroids (Input: Nodes; Output: Distance Matrix Centroids)</td></tr><tr><td>7:</td><td><strong>for</strong> c in C <strong>do</strong></td></tr><tr><td>8:</td><td>Merge Relaxed Routes (Input: Bench, c, Distance Matrix Centroids; Output: Elite Routes)</td></tr><tr><td>9:</td><td><strong>for</strong> each route in Elite Routes <strong>do</strong></td></tr><tr><td>10:</td><td>Reconstruct Route (Input: route; Output: Route)</td></tr><tr><td>11:</td><td>Improved Route (Input: Route; Output: Improved Route)</td></tr><tr><td>12:</td><td>Add Improved Route in Sol</td></tr><tr><td>13:</td><td><strong>if</strong> All Improved Route are feasible AND Objective value ≤ Best <strong>then</strong></td></tr><tr><td>14:</td><td>Best = Sol</td></tr><tr><td>15:</td><td>Sol = 0</td></tr><tr><td>16:</td><td>Return Best</td></tr></tbody></table>
Hereafter a more detailed description of each step of the algorithm:

* **TSP**: To solve the route of each shop we used the TSP mathematical model in order to use these results as benchmark for the algorithm's solution;

* **Calculate Centroids**: We found the distance matrix of the centroids in order to consider the location in the map of each shop with the relative customers and to merge the routes;

* **Merge Relaxed Routes**: We merged routes with a Bin packing mathematical model through the relaxation of the constraints using factors (C) from 1 to 2.5, which multiply the capacity and time constraints. It also keeps in count of the Centroids to merge the shops in the same area, with maximum execution time: 12 seconds;

* **Reconstruct Route**: For each vehicle using at most 500 order's permutations. We reconstructed the route for each permutation solving the TSP of the first 2 shops with depot and unique customers of the first shop, then putting as constraints all the nodes until shop 2. After that we redo the TSP with shop 3 and unique customers of shop 2 with the constraints found before. We repeat these steps until we found the route;

* **Improved Route**: We improve some of these permutations through the Relocate 1-0 moving the customers ahead in the path if the time decreases and if the capacity constraint is satisfied.

The instances used to test the algorithm have a maximum route time of 6 hours per vehicle and each request order has a volume between 27 $dm^3$ and 33 $dm^3$. The instances are classified according to different properties:

* Number of nodes, which include depot, customers, and shops: 50, 100, 150, 200;

* Map size: 15min x 15min, 30min x 30min, and 45min x 45min;

* Percentage of shops out of all nodes: 10%, 20%;

* Percentage of repeated orders: 0%, 15%, 30%;

* Vehicle capacities: Small (625 $dm^3$), Medium (1250 $dm^3$), Large (2500 $dm^3$).

By percentage of repeated orders, we mean the probability for all customers to have overlapping orders at the same shops. For each combination of these characteristics, there are 5 different simulations for the position of the nodes and the requests (orders). For the position of the nodes, we assumed that the depot can have $(x, y)$ coordinates in the map between 0.3 and 0.7 the map size, in order to have it in the center of the area, instead, customers and shops are random points in the map. The orders are also generated randomly, associating a customer with a shop and random quantity described above. A total of 1080 tests have been performed.

## 4 Results

The experiments reported have been performed on a 1,4 GHz Quad-Core Intel Core i5 CPU with RAM 8 GB. The algorithm is coded in Python 3 and the mathematical model of the algorithm is solved by GUROBI solver. The maximum execution time for all the tests is, in the worst case, 105 seconds.
In Table 1 all instance classes used to test the algorithm for each node size (50, 100, 150, 200) are presented. The first two columns represent the label of each analyzed instance, the first one with all instances having 10% of shops and the second one with 20% of shops.

<table><caption>**Table 1.** Instances used to test the algorithm.</caption><thead><tr><th>10 % shops</th><th>20 % shops</th><th>Map size (min)</th><th>% order repetition</th><th>Capacity (dm³)</th></tr></thead><tbody><tr><td>1</td><td>28</td><td>15</td><td>0</td><td>625</td></tr><tr><td>2</td><td>29</td><td>15</td><td>0</td><td>1250</td></tr><tr><td>3</td><td>30</td><td>15</td><td>0</td><td>2500</td></tr><tr><td>4</td><td>31</td><td>15</td><td>15</td><td>625</td></tr><tr><td>5</td><td>32</td><td>15</td><td>15</td><td>1250</td></tr><tr><td>6</td><td>33</td><td>15</td><td>15</td><td>2500</td></tr><tr><td>7</td><td>34</td><td>15</td><td>30</td><td>625</td></tr><tr><td>8</td><td>35</td><td>15</td><td>30</td><td>1250</td></tr><tr><td>9</td><td>36</td><td>15</td><td>30</td><td>2500</td></tr><tr><td>10</td><td>37</td><td>30</td><td>0</td><td>625</td></tr><tr><td>11</td><td>38</td><td>30</td><td>0</td><td>1250</td></tr><tr><td>12</td><td>39</td><td>30</td><td>0</td><td>2500</td></tr><tr><td>13</td><td>40</td><td>30</td><td>15</td><td>625</td></tr><tr><td>14</td><td>41</td><td>30</td><td>15</td><td>1250</td></tr><tr><td>15</td><td>42</td><td>30</td><td>15</td><td>2500</td></tr><tr><td>16</td><td>43</td><td>30</td><td>30</td><td>625</td></tr><tr><td>17</td><td>44</td><td>30</td><td>30</td><td>1250</td></tr><tr><td>18</td><td>45</td><td>30</td><td>30</td><td>2500</td></tr><tr><td>19</td><td>46</td><td>45</td><td>0</td><td>625</td></tr><tr><td>20</td><td>47</td><td>45</td><td>0</td><td>1250</td></tr><tr><td>21</td><td>48</td><td>45</td><td>0</td><td>2500</td></tr><tr><td>22</td><td>49</td><td>45</td><td>15</td><td>625</td></tr><tr><td>23</td><td>50</td><td>45</td><td>15</td><td>1250</td></tr><tr><td>24</td><td>51</td><td>45</td><td>15</td><td>2500</td></tr><tr><td>25</td><td>52</td><td>45</td><td>30</td><td>625</td></tr><tr><td>26</td><td>53</td><td>45</td><td>30</td><td>1250</td></tr><tr><td>27</td><td>54</td><td>45</td><td>30</td><td>2500</td></tr></tbody></table>

These labels, i.e. instance's names, help to read the next graphs: label 1 is the instance with 10% of shops, 15 minutes map size, 0% of repeated orders and vehicle capacity 625 dm³. For each instance there are 5 random simulations in order to get the average values of the algorithm's results.

In Fig. 1 there is an example of two maps showing the initial routes (a) in comparison with the final routes (b) of the instance 10 (map size 30x30 minutes).

Fig. 2 shows a graph of the average percentage decrease of vehicles used for all instances described in Table 1 with 4 distinct lines for 50, 100, 150 and 200 nodes. The x axis represents the instances from 1 to 54. The percentage decrease of used vehicles
has a similar trend for all the 4 lines, proving that the algorithm gives an output regardless the number of nodes.

<figure><img src="image_4.png" /><figcaption>Fig. 1. Maps of instance 10 with 50 nodes.</figcaption></figure>

In the left part of the plot there are the instances with 10% of shops, here results show that there is a much larger gap between the minimum and maximum decrease of used vehicles compared to the second half of the graph (20%). Another important element in the first half of the graph, is that increasing the map size, from 15 to 45 minutes, the decrease percentage drops, which is also present in the second half with a lower gradient. This relationship is important to understand that this problem is strictly affected by the dimension of the map in case the shops and customers are randomly distributed in the map when the ratio between customers and shops is about 10%. Again, in the left half of the graph it is possible to observe that the line with 50 nodes has some lower values with respect to the other lines for small vehicle instances (7, 10, 13, 16), this is because with more shops it is not straightforward to have vehicles saved. In the second part of the graph instead there is no evidence that vehicles capacity strongly affects results since there are less customers assigned to a shop thus having more chance to decrease the load of the vehicle during the route passing to the customers.

Fig. 3 shows a graph of the average percentage decrease of route time represented in the same way as in Fig. 2.

As in the previous graph, it is notable the fact that in the first part of the graph (10%) the percentage decrease of the global route time has an higher interval of oscillation with respect to the right part (20%). Apparently, there is also the same trend with the map size and the percentage decrease of the routes time, in particular with 45 minutes map size the results do not clearly improve compared to the initial solution. Instead, on the second part of the graph there is an higher linearity for all the instances, which may imply that for instances with low daily orders per shop the algorithm finds a considerable improved solution.
<figure><img src="image_5.png" /><figcaption>Fig. 2. Percentage decrease of vehicles used</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 3. Percentage decrease of route time</figcaption></figure>
We point out that tests performed in this work were mainly dedicated to the assessment of the economic and operational feasibility of the proposed collaborative delivery business model rather than on stressing the algorithmic performances of the approach.

To sum up, instances with 20% of shops (roughly 5 daily orders per shop) have the best improvements in all map sizes, when the shared delivery service can be implemented. Instead, when there are roughly 9 daily orders per shops (10% of shops) it is preferable to have 15 minutes map size or at most 30 minutes map size in order to achieve relevant improvements. Another relevant aspect is that the small vehicles have comparable results with the other vehicle sizes in 80% of the cases, except for 4 instances with 10% of shop out of 18 instances (54 divided by the number of vehicle sizes). This somehow confirms that a local collaborative delivery service can be set up also with small vehicles.

# 5 Conclusions

In this paper, we have defined and analysed a new variant of the VRP for *Pickup&Delivery* class, allowing for multiple visits to local retails and customers, in relation to the deployment of a collaborative logistics model for local delivery services.

The purpose of the study is to understand whether a collaborative delivery system, in which several local retailers share their (private or outsourced) shipping services, allows local merchants to save delivery costs and time by reducing the number of needed vehicles and the driven empty miles, thus enhancing their competitiveness against large-scale distribution as well as improving environmental sustainability. We designed and implemented a heuristic algorithm testing it on a large instance set. The results proved that for a local collaborative delivery service there is a relevant decrease in used vehicles and in travelled kilometers and time under specific conditions, in particular, for instances with low daily orders per shop (roughly 5 daily orders per shop). This may be a great benefit for small local shops, allowing them to reduce distribution costs but also to serve customers that they may not reach in other ways. Moreover, with low numbers of daily orders, there is no evidence that vehicle capacity affects the variation in the percentage decrease of used vehicles. This means that in these scenarios few smaller vehicles can be used saving fixed vehicle costs, fuel consumption and pollutant emissions volumes, thus improving the environmental sustainability and the urban liveability without reducing the retails' competitiveness and delivery performances.

The algorithm has just been tested with simulated data; however, the simulation of a real case study (with data on current volumes of home-deliveries and on shops and customers' locations within an urban neighborhood) would be needed. This would provide a more precise estimate of delivery costs reduction (in relation to the reduced number of needed vehicles and of driven kilometers and trip time) in a collaborative framework with respect to the current scenario (where local shops deliver their goods autonomously with their own vehicles). Moreover, it would support the assessment of future distribution scenarios and potential business models for collaborative delivery services depending on the neighbourhood conditions.
References

1. Aziez I., Coté J-F., Coelho, L. C.: Exact algorithms for the multi-pickup and deliveryprob- lem with time windows. European Journal of Operational Research (284), 906–919 (2020).

2. Berbeglia G., Cordeau J.-F., Gribkovskaia I., Laporte G.: Static pickup and deliveryprob- lems: a classification scheme and survey. TOP (15), 1–31 (2007).

3. Bruck B.P., Iori M., 2017. Non-elementary formulations for single vehicle routing problems with pickups and deliveries. Operations Research (65), 1597–1614 (2017).

4. Haddad M.N., Martinelli R., Vidal T., Martins S., Ochi L.S., Souza M.J.F., Hartl R.: Large neighborhood-based metaheuristic and branch-and-price for the pickup and delivery prob- lem with split loads. European Journal of Operational Research (270), 1014–1027 (2018).

5. Jargalsaikhan B., Romeijnders W., Roodbergen K.J.: A Compact Arc-Based ILPFormula- tion for the Pickup and Delivery Problem with Divisible Pickups and Deliveries. Transpor- tation Science (55), 336–352 (2021).

6. Nagy G. , Wassan N.A., Speranza M.G. , Archetti C.: The vehicle routing problem with divisible deliveries and pickups, Transportation Science (49), 271–294 (2015).

7. Xiao Z., Wang J. J., Liu Q.: The impacts of final delivery solutions on e-shopping usage behaviour: The case of Shenzhen, China. Int. J. Retail Distrib. Manag.(46), 2-20 (2018).

8. Report Osservatorio eCommerce B2c, "L'eCommerce B2c: il motore di crescita e innova- zione del Retail!", 2019, https://blog.osservatori.net/reportecommerce?hsCtaTrac- king=1b8915c1-7a7e-4209-a329-c36db1fd6d87%7C5d9392aa-cadc-4586-a370- 43378da6e5e4 (in Italian), last accessed 2021/03/18

9. Report Casaleggio Associati, "E-COMMERCE IN ITALIA 2019", 2019, https://www.casa- leggio.it/wp-content/uploads/2019/04/Report_E-commerce-in-Italia_2019-1.pdf (in Ita- lian), last accessed 2021/03/18

10. Report Nielsen, "MarketTrack, Iper+Super+Liberi Servizi+Discount+Specialisti Drug. Vendite a valore per categoria nella settimana 12 del 2020 vs. la stessa settimana del 2019.", 2019, https://nielseniq.com/global/it/insights/analysis/2020/coronavirus-la-spesa-in-qua- rantena/ (in Italian), last accessed 2021/03/18