Sage Journals: Discover world-class research

Abstract

The continuous growth of e-commerce puts pressure on logistic service providers to fulfill more parcel deliveries. Concurrently, there are increasing calls from governments and society to carry this out sustainably. Crowdshipping is one possible innovative logistic service that addresses these challenges. Crowdshipping enlists members of the public to fulfill parcel deliveries, ideally en route along their pre-committed journeys. In this paper, we consider a setting where public transport passengers can serve as crowdshippers and propose a comprehensive framework to organize the scheme. Firstly, outlier parcels are identified as being suitable for crowdshipping. Then, these outlying parcels are matched with crowdshippers, who pick up parcels from a set of selected parcel lockers. We also investigate the viability of crowdshipping with real-world data. By comparing a carrier’s performance to a base case without crowdshipping, the results show that delivery vehicle kilometers traveled and associated carbon dioxide emissions can reduce by up to 20%. A total of 11% of parcels can be redirected to be delivered via crowdshipping. Crowdshipping using public transport has the potential to be a sustainable way to fulfill urban logistics in a dense city.

Keywords

freight systems freight distribution freight model/modeling freight truck planning and analysis freight distribution networks

Rapid e-commerce growth has reshaped the structure of logistics, requiring the fulfilment of online orders through parcel shipment. Globally, shipping parcel volume has grown from 51 billion in 2015 to 131 billion in 2020, more than doubling in 5 years, and this volume is expected to reach 266 billion in 2026 ( 1 ). Compared with traditional bricks-and-mortar commerce activities, e-commerce is expected to result in an increase in urban freight movements ( 2 , 3 ). City logistics require solutions to efficiently and effectively deliver goods in urban areas while also mitigating the negative consequences on traffic, safety, and the environment.

The concept of crowdshipping is one possible solution. Crowdshipping enlists members of the public to fulfill parcel deliveries, ideally en route along their pre-committed journeys. In cities with high transit use, crowdshipping can take advantage of excess capacity in the transit system to fulfill deliveries, engaging public transport passengers to complete deliveries ( 4 ). A visualization of the parcel delivery procedure via crowdshipping using public transport is shown in Figure 1.

Figure 1.

Visualization of conventional and crowdshipped parcel delivery procedures.

Conventionally, a carrier will deliver parcels to receivers directly. In this paper, we consider a setting where a carrier has a set of parcel delivery requests that can be fulfilled by a combination of delivery vehicles and a pool of crowdshippers. With the option of crowdshipping, the carrier operates a fleet of vehicles to direct some parcels to automated parcel lockers (henceforth referred to as “lockers”) and public transport passengers can serve as crowdshippers. Enlisted crowdshippers can pick up parcels from lockers near or at their origin stops and hand-carry the parcel, delivering the parcels to their final destinations, also located close to the passengers’ destination stops.

While crowdshipping is a novel urban logistics solution, it is expected to complement and not entirely replace conventional deliveries using a commercial vehicle fleet. As such, which parcels should be prioritized for crowdshipping? Our hypothesis is that outlier parcels are more suited for crowdshipping, and this also depends on the availability of crowdshippers along the parcel routes. “Outlier” parcels, in this study, are defined as spatial outliers in accordance with their delivery destinations. Therefore, the main objective of this research is to consider the impact of prioritizing outlier parcels in a crowdshipping initiative.

In our study, we focus on the evaluation of crowdshipping using public transport in the case of Singapore. With a population of nearly 5.5 million living on an island of about 700 km², Singapore is ranked as one of the most densely populated countries with 8,383 people per km². In this densely populated city, public transport is the dominant transport mode with high average daily public transport ridership of 5.26 million in 2021 ( 5 ). Nearly 60% of employed people go to work by public transport ( 6 ). The island’s extensive transit network encompasses over 140 metro stations and approximately 5,000 bus stops ( 7 ). Given the high ridership and extent of the transit network, the likelihood of engaging potential crowdshippers is high. Singapore scored highly on public transport convenience in McKinsey’s urban transportation system report ( 8 ). Moreover, Singapore’s public transport system is also recognized by its seamless integration of metro and bus systems, providing a convenient and user-friendly multi-modal transit system ( 9 ). Key aspects of such integration include unified ticketing and fare systems such as EZ-Link, shared information systems, and intermodal hubs ( 10 – 12 ).

Related Work

Crowdshipping Operations Research

Concerning operations research into the concept of crowdshipping, existing studies have evaluated the use of private vehicles or public transport modes. Two types of problem formulation are often encountered: the vehicle routing problem and the network problem.

Some researchers formulate the crowdshipping problem as a variant of the capacitated vehicle routing problem (CVRP), called the vehicle routing problem with occasional drivers ( 13 – 15 ). This problem considers a setting that would allow a professional delivery vehicle fleet and occasional drivers to make deliveries together. The occasional drivers will receive a small compensation and the objective is to minimize the total cost. To solve this problem, Archetti et al. used an integer programming formulation and developed a multi-start heuristic integrating variable neighborhood search and tabu search ( 13 ). Macrina et al. added a penalty function for unsuccessful deliveries to the total cost ( 14 ). Scenarios with time window constraints and multiple deliveries were also generated. Gdowska et al. introduced a probability to represent crowdshippers’ willingness to perform the delivery ( 15 ). The computational results from these studies revealed the potential cost-saving benefits of crowdshipping.

Several researchers extended the crowdshipping problem to a large-scale network problem ( 16 , 17 ). Wang et al. assigned delivery jobs to potential workers in real time with the objective of minimizing additional travel distance and proposed solutions to solve the model for a large network ( 16 ). Soto Setzke et al. further constructed the crowdshipping problem as a minimum-cost, maximum-flow problem to match transportation requests with drivers who have already planned a trip while minimizing additional driving time ( 17 ). A dynamic algorithm was designed to solve the network problem effectively.

The use of private vehicles is noted to contribute to traffic congestion and air emissions. Several studies have considered the use of more environmentally friendly public transport modes for crowdshipping ( 18 , 19 ). Gatta et al. used the willingness to engage the crowdshipping service to estimate the potential demand ( 18 ). They transformed individual orders into vehicle equivalent units and used historical data, such as light commercial vehicle kilometers traveled (VKT) and emissions for each year to assess the impacts. Karakikes and Nathanail established an evaluation framework and a city-scale freight traffic microsimulation model in Volos, Greece, to assess the impacts of crowdshipping using public transport ( 19 ). The findings suggest that crowdshipping using public transport has the potential to contribute to more sustainable freight transport.

Few studies were found to provide a comprehensive evaluation methodology that involves matching demand (for parcel deliveries) with supply (available and willing crowdshippers), while considering the optimal use of automated parcel lockers that can store crowdshipped parcels to be picked up. The choice of lockers can certainly influence the availability of crowdshippers.

In addition, there exists a gap in research on parcel selection or prioritization for crowdshipping. Intuitively, one would expect the cost savings arising from removing a parcel from an area with lower parcel delivery demand (i.e., a more remote area) to be larger than removing a parcel from a more dense area. A certain level of demand density is required for parcel deliveries to be cost-effective. This means that greater cost savings can be achieved by designating outlier parcels to be delivered by crowdshipping.

Contributions of this Paper

The main contribution of this study is to offer an integrated modeling approach to: (i) prioritize outlier parcels for crowdshipping that can minimize VKT for the delivery of all parcels, (ii) match parcels with available crowdshippers, (iii) determine the location and number of parcel locker stations to store parcels to be crowdshipped, and (iv) assess and report the impacts from a carrier’s perspective.

Problem Formulation

We consider a same-day home delivery network, consisting of a parcel consolidation center (a warehouse), a set of parcels to be delivered from this origin, and a fleet of delivery vans. The delivery vans cooperate with crowdshippers to deliver all parcels from the warehouse to their delivery destinations. The delivery destinations of the parcels may not be evenly distributed. The outlier parcels that may be difficult or costly to include in the delivery van routes can be delivered by crowdshippers. The vans will be used to transport crowdshipped parcels to their assigned automated parcel lockers (lockers), to be picked up by crowdshippers. They will also be routed to deliver remaining parcels to their destinations.

To formulate the above-mentioned problem, some notations are introduced. Let $P$ be the set of all parcels to be delivered from the warehouse, each associated with a delivery destination. The subset $P_{c}$ represents the set of crowdshipped parcels. The subset of remaining parcels is denoted by $P_{u}$ where $P_{c} \cup P_{u} = P$ . Let $L$ denote the set of lockers that may be visited by the delivery vans. In general, the goal is to identify outlying parcel destinations and plan the routes for the delivery vans such that all the parcels are delivered while minimizing the total VKT.

We assume that each outlying parcel $p \in P_{f}$ may either be matched with a crowdshipper or is assigned to a delivery van for direct delivery. In the following, let $n_{p}$ be the nearest bus stop to the destination of the outlying parcel $p$ where $p \in P_{f}$ . Let $OD$ denote the set of origin–destination (O-D) bus stops of the crowdshippers, and let $O$ and $D$ represent the set of origin and destination bus stops, respectively. Let $T_{ij}$ represent the trip volume from the origin bus stop $i$ to the destination bus stop $j$ , where $(i, j) \in OD$ .

For each locker $l \in L$ , its nearby bus stop set is indicated by $N_{l}$ . Then, the set of all available crowdshipper O-D pairs originating from parcel locker $l$ is indicated by $O D_{l} = {(i, j) | i \in N_{l}, (i, j) \in OD}$ , a subset of $OD$ , and the corresponding set of destination bus stops is indicated by $D_{l}$ where $D_{l} = {j | (i, j) \in O D_{l}}$ . The set of outlying parcels that may be assigned to locker $l \in L$ is denoted by $P_{f}^{l}$ where $P_{f}^{l} = {p | p \in P_{f}, n_{p} \in D_{l}}$ . As such, the outlying parcels from $P_{f}^{l}$ and the crowdshippers from $O D_{l}$ share the same origin. By comparing the volumes of outlying parcels and available crowdshippers from the locker $l$ to each destination bus stop $j$ , we can obtain the total set of crowdshipped parcels assigned to $l$ , indicated by $P_{c}^{l}$ where $P_{c}^{l} \subset P_{c}$ and $P_{c} = \cup_{l \in L} P_{c}^{l}$ . Each outlying parcel and crowdshipper can be matched at most once. So, if the number of the outlying parcels from locker $l$ to bus stop $j$ is smaller than the number of available crowdshippers with same movement, then these outlying parcels $P_{f}^{l}$ can be totally delivered with the help of crowdshippers. On the contrary, if there are not enough available crowdshippers, then only a proportion of the outlying parcels can be delivered by this mode. In this case, the same number of outlying parcels as the number of available crowdshippers will be randomly designated to be crowdshipped. In this study, we assume that the parcels associated with the same nearest bus stop will have equal chances to be crowdshipped, as they are close to one other. The notations are summarized in Table 1.

Table 1.

Outlying Parcel-Crowdshipping Matching Model Notations

Notation	Definition and description
$P$	Initial set of all parcels to be delivered
$P_{f}$	Set of outlying parcels
$P_{c}$	Set of parcels that will be delivered by crowdshippers
$P_{u}$	Set of parcels that will be delivered by conventional delivery vans where $P_{u} \cup P_{c} = P$
$OD$	Set of origin–destination (O-D) bus stops of the crowdshippers
	( $O$ and $D$ represent the set of origin bus stops and destination bus stops, respectively.)
$T_{ij}$	Trip volume from origin bus stop $i$ to destination bus stop $j$ where $(i, j) \in OD$
$L$	Set of automated parcel lockers that may be visited by the delivery vans
$N_{l}$	Set of nearest bus stop for each parcel locker $l \in L$
$O D_{l}$	Set of available crowdshippers O-D pairs originating from parcel locker $l$
$n_{p}$	Nearest bus stop for each outlying parcel $p \in P_{f}$
$P_{f}^{l}$	Set of outlying parcels for parcel locker $l \in L$
$P_{c}^{l}$	Set of serviceable parcels that are delivered by crowdshipping for parcel locker $l \in L$

Methodology

Overview of Study Methods

The overall study approach makes use of four models (shown in Figure 2):

A spatial outlier detection model that identifies outlying parcels that are difficult to deliver by conventional delivery vans

A parcel-crowdshipper matching model that matches outlying parcels with public bus passengers who can serve as crowdshippers over a single day

A parcel locker selection model involving a CVRP that: (i) determines which parcel lockers to use, (ii) generates delivery van routes that deliver the parcels to be crowdshipped to the lockers, and (iii) van routes to deliver remaining parcels (that are not crowdshipped) to their final destinations, while minimizing VKT

A vehicle routing model that merges the generated routes from the capacitated vehicle routing model to calculate the minimum number of vehicles required to perform all deliveries

Figure 2.

An overview of the study.

Outlying Parcel Identification

The outlying parcel identification problem can be formulated as a spatial outlier detection problem. Starting from defining outliers, previous studies on outlier definition are mostly from the perspective of global view of the total data set referring to global outliers, which considers outliers as observations in a data set that appear to be inconsistent with the remainder of that set of data ( 20 ). Breunig et al. pointed out that real-world datasets always show a more complex structure, and proposed a new concept to view local neighborhoods relative to the entire data set ( 21 ). A local outlier factor (LOF) measures the degree to which the object is isolated from its neighbors. To compare the density of the object with its surrounding neighbors, the object’s relative density is the LOF for that object, which is calculated as the ratio of its local density and those of its k-nearest neighbors. For most objects in a cluster, the LOF of each object is shown to be approximately equal to unity. A similar definition of a spatial outlier is also proposed by Shekhar and Chawla, which describes these outliers as observations that appear to be inconsistent with their neighbors ( 22 ). In addition, the LOF algorithm leads to a complexity of $O (n)$ for the materialization step for low-dimensional data and $O (n \log n)$ for the medium- to medium-high-dimensional data. It is also practical for very large datasets ( 21 ).

In our study, given a set of geographical coordinates of parcel delivery destinations, the LOF of each parcel can be calculated (see more details in the section on algorithms). The set of the parcels $P_{f}$ that are far away from other dense parcels can be identified where $P_{f} \subset P$ .

Parcel-Crowdshipper Matching Model

After outlying parcels are identified, they need to be matched with crowdshippers. On the demand side, we have a given set of outlying parcels, $P_{f}$ , each associated with a delivery destination. On the supply side, we consider public bus passengers as crowdshippers, as bus is a sustainable and accessible transport mode. For simplicity, we assume that each crowdshipper can deliver, at most, one parcel from their origin bus stop to the destination bus stop and each parcel can be matched with, at most, one crowdshipper. We also assume that the lockers are only installed at metro stations (which all have bus stops located nearby), with no capacity limit.

The matching problem aims to find matches between the O-D pairs of the outlying parcels with crowdshippers’ O-D pairs within the day. To minimize the detour that crowdshippers may experience, we define the matching conditions as follows.

Matching conditions: An outlying parcel is said to be matched with a crowdshipper if and only if the following conditions are satisfied: 1) the assigned lockers of the outlying parcel is near the crowdshipper’s origin bus stop, and 2) the bus stop nearest to the outlying parcel’s destination is the crowdshipper’s destination bus stop.

Furthermore, we assume that all the crowdshipped parcels will be stored at their assigned lockers at the start of the day so that crowdshippers can pick up them at any time.

Parcel Locker Selection Model

From the matching model, the set of crowdshipped parcels $P_{c}$ is defined by making use of all available lockers. With crowdshipping, it is expected that the carrier’s VKT can be reduced because the decentralized destinations of the outlying parcels are now allocated to a few parcel lockers. However, there exists a trade-off between increasing VKT as a result of adding a parcel locker and reducing VKT by consolidating crowdshipped parcels at parcel lockers. Given this, the goal is to select lockers with minimum VKT. This problem is similar to the location-routing problem, which is defined as location planning with tour planning aspects taken into account. This type of problem aims to solve a facility location problem by solving a vehicle routing problem ( 23 ). As these are both NP-hard problems, it is difficult to solve this integrated problem exactly ( 24 ).

We start by finding the minimum number of required lockers to complete all the crowdshipped parcel deliveries. Given a fixed number of parcels to be crowdshipped, a shorter VKT will result in a lower number of lockers used. We then formulate this problem as a minimum cover set problem in the following.

Given a set of crowdshipped parcels $P_{c}$ and a collection S of $P_{c}^{l}$ , where $S = {P_{c}^{l} : l \in L}$ and $\cup_{l \in L} P_{c}^{l} = P_{c}$ . The minimum cover set problem aims to find the smallest sub-collection of S denoted as $I \subseteq L$ such that $\cup_{l \in I} P_{c}^{l} = P_{c}$ .

After minimizing the number of lockers used, we continue to determine which lockers from $I$ are used with minimum VKT. To avoid the combinatorial complexity of evaluating all the possible subsets of lockers from $I$ , the objective can be achieved by removing the locker(s) that are not helpful in reducing VKT. It is assumed that the carrier will visit the union of the original delivery destination of parcels for $p \in P$ and the locations of lockers from $I$ first. Then the VKT reduction for selecting a locker can be calculated by the difference between the increased distance by inserting the locker $l$ and the reduced distance by removing the parcels assigned to this locker $P_{c}^{l}$ . This requires prior knowledge of the visiting sequence of the carrier. Thus, a CVRP is involved, which aims to find an optimal routing that departs from the origin warehouse, visits several locations (parcel delivery destinations for $p \in P_{u}$ and locker locations for $l \in h$ ) exactly once, and returns to the warehouse, while minimizing total kilometers traveled with vehicle capacity constraint. We start by removing the locker with lowest VKT reduction from $I$ iteratively and each result of the remaining locker selection is denoted as $H = {H_{1}, H_{2}, \dots, H_{m}}$ .

For each locker set selected $h \in H$ , the set of crowdshipped parcels is $P_{c}^{h} = \cup_{l \in h} P_{c}^{l}$ and the set of remaining parcels is $P_{u}^{h} = P \ P_{c}^{h}$ . The visiting locations for the carrier include the delivery destinations for $p \in P_{u}^{h}$ and the locations of lockers for $l \in h$ .

The shortest routes between any two locations and the number of parcels to be delivered for each location are identified. In the CVRP, each vehicle has a capacity limit on the number of parcels and a maximum traveling distance limit. The minimum VKT for each locker combination $h \in H$ and the corresponding visiting sequence and the distance of each route can be obtained. The optimal locker selection is the one with minimum VKT.

Vehicle Routing

Following parcel locker selection, the routes with visiting sequences and distances are generated. To calculate the minimum number of vehicles required to perform all the routes with a constraint on the maximum VKT for each vehicle, a bin-packing problem is introduced. The bin-packing problem aims to find the minimum number of bins used to pack different-sized items into a finite number of bins, each of which has a given fixed capacity. The number of routes is denoted as $n$ . The maximum distance for each vehicle is assumed to be $l_{\max}$ . Given a set of routing distance $R = {R_{1}, R_{2}, \dots, R_{n}}$ for the lockers selected, two decision variables are added: $y_{v} = 1$ if the vehicle $v$ is used and otherwise $y_{v} = 0$ , and $x_{rv} = 1$ if the route $r$ is performed by vehicle $v$ and otherwise $x_{rv} = 0$ .

min \sum_{v = 1}^{n} y_{v}

(1)

s . t . \sum_{r = 1}^{n} R_{r} x_{rv} \leq l_{\max} y_{v} v = 1, 2, \dots, n

(2)

\sum_{v = 1}^{n} x_{rv} = 1, r = 1, 2, \dots, n

(3)

y_{v}, x_{rv} \in {0, 1}, r, v = 1, 2, \dots, n

(4)

Algorithms

Outlying Parcels Identification—Local Outlier Factor (LOF) Algorithm

In the outlying parcel identification model, the objective is to identify outlying parcels from a given set of parcel delivery requests based on the geographical coordinates of parcel delivery destinations. We use an algorithm named LOF to achieve this.

LOF is a density-based algorithm on spatial outlier detection. It measures the degree of isolation of the object and its surroundings ( 21 ). By using real-world datasets, the outliers that appear to be meaningful, but cannot be identified with existing approaches, can be detected. Finally, a careful performance evaluation of our algorithm confirms we show that our approach of finding local outliers can be practical.

This algorithm can be used to identify outliers that appear to be meaningful but cannot be identified using other methods.

As this algorithm does not make any assumption on the data distribution, it can detect outliers regardless the distribution of data and it performs well for non-uniform density datasets ( 25 , 26 ). Considering the complex structure and stochasticity of parcel demand distribution, LOF is applied here to detect outlying parcels. The objects that have a significantly lower density than their surrounding neighbors are regarded as outliers ( 27 ).

To identify outliers, it is common to assume that a specified proportion of points are candidates to be outliers, usually no more than 10%. However, this assumes that most points from the dataset are not outliers, which may not be true within the dataset of parcel delivery locations. For example, some clusters may be far away from other clusters but contain more points than a small cluster, as the demand of parcel delivery is stochastic. It is more accurate to regard the points located at the faraway cluster as outlier points from the perspective of traveling distance to deliver these parcels.

Before applying the LOF algorithm, one main parameter is required: the number of nearest neighbors. The determination of this parameter is based on the following two rules:

1) greater than the minimum number of objects required to be considered as a cluster, and

2) smaller than the maximum number of close by objects that can potentially be local outliers.

To determine this number, parcel density can be referred to as a threshold, which is the number of parcels located per defined region. Following this, the LOF algorithm can calculate the LOF for each object. The higher LOF value an object has, the more isolated it is to its surrounding neighbors, thereby identifying outlying parcels from the set of total parcels.

Parcel Locker Selection Model—Heuristic Algorithm

The result of the outlying parcel-crowdshipper matching is the set of crowdshipped parcels assigned to locker $l$ denoted by $P_{c}^{l}$ and the total set of crowdshipped parcels $P_{c}$ by making use of all available lockers. In accordance with the relationships between the location problem and vehicle routing problem, researchers have classified the algorithms into three categories: clustering-based, iterative, and hierarchical heuristics. The clustering-based method starts by dividing the set of points into different clusters first, and then, for each cluster, solving the vehicle routing problem or traveling salesman problem and depot locating problem (see, for example, Nambiar et al. and Branco and Coelho) ( 28 , 29 ). The iterative heuristic is a decomposition-based method in which the location problem and the routing problem are solved iteratively and the useful information from one phase is fed to the other (see, for example, Hansen et al. and Wu et al.) ( 30 , 31 ). To overcome the running efficiency, and in case the routing information is not well-utilized in the location phase from the iterative method, hierarchical heuristics are proposed to solve the locations problem. The routing problems are referred to a subroutine at each step (see, for example, Srivastava, and Srivastava and Benton) ( 32 , 33 ).

Considering the trade-off between VKT increase as a result of inserting locker locations visited and VKT reduction by consolidating parcels at lockers, we aim to find lockers with minimum VKT required to complete all the parcel delivery tasks, which is a set-covering problem as previously described. A greedy approximation algorithm is applied to select a set of lockers with the smallest cardinality. The rule of the greedy algorithm is to pick the set that covers the greatest number of remaining elements that are uncovered at each stage ( 34 ).

After minimizing the number of parcel lockers used, we continue to determine which parcel lockers decided from the previous step are used with minimum VKT. We are inspired by the savings algorithm proposed by Clarke and Wright ( 35 ). It starts by assuming that all parcel destinations and parcel lockers revealed from the cover set problem need to be visited. Then, it iteratively modifies the solution by removing the locker where the difference between the increased distance by inserting it and the reduced distance by removing the parcels assigned to it is the largest, and updating the set of visiting locations accordingly. The steps taken in the process are as follows:

1) Initialize the set of the parcel lockers to be used $M \leftarrow I$ .

2) Calculate the union set of locations to be visited $U = P \cup M$ .

3) Create a matrix of distances $D = (d_{i, j})$ between each pair point from $U$ where $i, j \in U$ .

4) Solve the CVRP based on $D$ to generate visiting sequences for the points from $U$ .

5) For each locker $l \in M$ , its nearest neighbors from the visiting sequences are $l_{last}$ and $l_{next}$ , respectively, and, similarly, for each parcel $p \in P$ , its nearest neighbors are $p_{last}$ and $p_{next}$ .

6) Calculate the savings for removing parcel $p$ by the following equation:

s (p) = (d_{p_{last}, p}) + (d_{p, p_{next}}) - (d_{(p_{last}, p_{next}})

(5)

7) Calculate the savings for removing locker $l$ by the following equation:

s (l) = (d_{l_{last}, l}) + d_{l, l_{next}}) - d_{l_{last}, l_{next}}) - \sum_{p \in P_{c}^{l}} s (p)

(6)

8) Sort the lockers in $M$ based on the saving value $s (l)$ from the smallest to the largest value.

9) Remove the first locker $l^{*}$ from $M$ where $M \leftarrow M \ l^{*}$ .

10) Calculate the set of remaining parcels $P_{u}^{M} = P \ (\cup_{l \in M} P_{c}^{l})$ .

11) Solve the CVRP for $P_{u}^{M}$ to generate minimum VKT, the visiting sequence, and the distance of each route.

12) If $M$ is empty, then the algorithm stops. If not, return to step 2.

Note that Python linked to Google OR-tools is used to solve the CVRP.

Algorithm 1: An iterative heuristic algorithm
First step: Calculate minimum locker set covering all the crowdshipped parcels to be delivered
GREEDY-SET-COVER ( $P_{c}$ , $S$ )
01: $W = P_{c}$
02: $I = ϕ$
03: while $W \neq ϕ$ do
04: Select an $P_{c}^{l} \in S$ that maximizes $\| P_{c}^{l} \cap W \|$
05: $W = W - P_{c}^{l}$
06: $I = I \cup {l}$
07: end while
08: return $I$
Second step: Find the locker set with minimum VKT
ITERATIVE-SAVING-METHOD ( $I$ , $P$ )
09: Initialization: Initialize $M \leftarrow I$
10: while $M \neq ϕ$ do
11: $U = P \cup M$
12: $D = (d_{i, j})$ where $i, j \in U$
13: Solve CVRP for $U$ by Algorithm 2
14: for $l \in M$ do
15: $s (l) = 0$
16: for $p \in P_{c}^{l}$ do
17: $s (p) = (d_{p_{last}, p}) + (d_{p, p_{next}}) - (d_{p_{last}, p_{next}})$
18: $s (l) = s (l) + s (p)$
19: end for
20: $s (l) = (d_{l_{last}, l}) + (d_{l, l_{next}}) - (d_{l_{last}, l_{next}}) - s (l)$
21: end for
22: Sort $M$ based on $s (l)$ in ascending order
23: Select the first locker $l^{*}$ from $M$
24: $M \leftarrow M \ l^{*}$
25: $P_{u}^{M} = P \ (\cup_{l \in M} P_{c}^{l})$
26: Solve CVRP for $P_{u}^{M}$ by Algorithm 2
27: end while

Algorithm 2: Google OR-tools algorithm for CVRP
GOOGLE-OR-TOOLS ( $P$ , $demand$ , $ve h_{c}$ , $l_{\max}$ )
1: Set following parameter values: $ve h_{c}$ and $l_{\max}$ . ⊳ Input vehicle capacities of the fleet and the maximum travel distance for each route.
2: Create a distance matrix $D (P) = (d_{i, j})$ where $(i, j) \in P$ .
3: Input $P$ and corresponding demand for each point into Google OR-tools programming.
4: return minimum VKT, visiting sequence and distance of each route.

Vehicle Routing—Best Fit Decreasing Algorithm

After routes are generated by CVRP, we calculate the minimum number of vehicles required to perform all the routes. We start estimating the maximum daily distance that the vehicle can travel. According to the statistics from the Land Transport Authority in Singapore, the average annual VKT by heavy goods vehicle in Singapore is 39,500 km in 2018. The number of non-work days in that year is 63 and we used the average working day travel distance to represent the limit on vehicle daily travel distance. We assume that each vehicle can travel at most 130 km per day. To solve the route-merging problem formulated as a bin-packing problem as described in the above section, we use a best fit decreasing algorithm to solve this problem and arrive at the minimum fleet size needed to complete all the tours [ 36 ]. The key steps for this algorithm are shown as follows:

1) Sort the routes in decreasing order of distance.

2) Pack the next route into the feasible vehicle where it fits by leaving the smallest residual capacity. If several vehicles have the smallest residual capacity, the first one is chosen.

3) If there is no feasible vehicle available to conduct this route, add a new vehicle to conduct this route.

Algorithm 3: Best-fit decreasing algorithm for vehicle scheduling problem
BEST-FIT-DECREASING ( $l_{\max}$ , $R$ )
for $i = 1$ to $\| R \|$ do
for $j = 1$ to $2, 3, \dots$ do
if route $R_{i}$ can be conducted by vehicle $j$ satisfying capacity constraint ( $l_{\max}$ ) then
Calculate residual capacity after the route $R_{i}$ has been conducted
end if
end for
Assign route $R_{i}$ into vehicle $j$ where vehicle $j$ has the smallest residual capacity after conducting route $R_{i}$
if no such available vehicle conducts route $R_{i}$ then
add a new vehicle to conduct route $R_{i}$
end if
end for

Experiment with Real-World Data

This section describes the data collection and explains the details of implementing the aforementioned study methodology. A discussion of the results obtained will follow.

Data Collection

Real-world datasets on daily parcel deliveries from the Singapore road network and public transport journeys are used in this study. The parcel delivery dataset contains daily delivery requests to be fulfilled and was obtained from an e-commerce carrier in Singapore in January 2019. Each request includes the origin warehouse and the destination for each parcel, in relation to geographical coordinates (longitude and latitude). From the dataset, an average of 5,841 parcels were delivered from the warehouse in a weekday. To calculate the road network distance between each pair of coordinates (which could be parcel delivery destinations or lockers), Open Routing Source Machine, based on OpenStreetMap, is used ( 37 ).

Given high bus ridership and the extensive bus network in Singapore, this study focuses on the potential to enlist public bus passengers as crowdshippers. The dataset on historical public bus journeys was retrieved from the Singapore Land Transport Authority ( 38 ). This data reveal passenger volumes from origin to destination bus stops in weekdays in the month of October 2019. The average weekday volume was utilized to reflect the daily passenger volumes from origin to destination bus stops during that month, in which the number of work days is 22.

Computational Results

This section reports the performance of carriers in the base case without crowdshipping versus with crowdshipping.

Base Case without Crowdshipping—Results from CVRP

Without crowdshipping, the carrier needs to visit all the parcel delivery locations with its fleet of conventional delivery vans. The total VKT is 2,265 km and the required fleet size (number of vehicles) by merging the routes based on the constraint on the daily travel distance is 19 vehicles.

Outlying Parcel Identification and Parcel-Crowdshipping Matching

Given a set of delivery locations and distance between each pair of locations, the LOF algorithm is used to identify the outliers among the 5,841 parcels based on their spatial distribution. To determine the number of neighbors, a parcel density analysis is conducted first before applying the LOF algorithm. According to the range of latitude and longitude of Singapore, the whole city is divided into the grids with number $28 \times 12$ . The number of parcels located per region is calculated as the density and Figure 3 visualizes the density results based on the map.

Figure 3.

Visualization of parcel density.

According to the density calculation results, the densest grid has 878 parcels and we round the number of nearest neighbors to 900, which is smaller than the number of points located in this region and its close-by ones. Under this setting in the LOF algorithm, the number of outlier parcels is 663, 11% of the total parcel set. By feeding this into the outlier parcel-crowdshipping matching model with daily passenger transit O-D information, the maximum number of crowdshipped parcels is 641 with the use of 31 parcel lockers.

Carrier Performance

Three evaluation indicators are chosen from the aspects of sustainability and economics.

VKT: total distance traveled delivering the crowdshipped parcels to the lockers and remaining parcels to the receivers’ addresses

Fleet size: the number of vehicles required to complete all the delivery tasks

Delivery cost:

Fixed cost: Cost of vehicle ownership including purchase cost, ownership taxes, registration fee, road tax, maintenance, and insurance

Variable cost: Fuel cost and human resources

Figure 4 reports the main results on VKT. The left axis represents the value of vehicle kilometers (in vertical bars) with respect to the number of lockers used. The right axis represents the VKT reduction (in a line) compared with the base case without crowdshipping. As VKT depends on the locker location and availability of the crowdshippers, the results show that VKT could be reduced by as much as 19%, from 2,265 km in the base case to 1,832 km, by engaging crowdshippers, using 23 lockers.

Figure 4.

Results of vehicle kilometers traveled (VKT), showing VKT reduction percentage compared with the base case.

Carbon dioxide will be emitted directly through diesel fuel combustion as vehicles are driven. Vehicle emission factors are obtained from the Toyota website ( 39 ). The calculation results are shown in Figure 5. Consistent with the reduction in VKT, we observe that crowdshipping can reduce carbon dioxide emissions by up to 20% by using 23 lockers, suggesting that it is a more environmentally friendly mode.

Figure 5.

Results of carbon dioxide emissions, showing carbon dioxide emissions reduction percentage compared with the base case.

At the same time, the required fleet size would be reduced by 21%, from 19 to 15 vehicles.

Items that contribute to the carriers’ delivery costs are listed in Table 2. Based on available cost information, the carriers’ delivery costs in the base case without crowdshipping is S$4,262 in Singapore dollars. Figure 6 shows the impact of crowdshipping on the carriers’ costs with respect to the number of lockers removed from the minimum parcel locker set. The delivery cost in crowdshipping scenarios can reduce by up to nearly 20%. This is intuitive given reductions on both VKT and fleet size.

Table 2.

Carriers’ Costs—Items and Sources

Cost type	Source
Purchasing cost for vehicles	Toyota website*
Vehicle ownership tax	Singapore Land Transport Authority
Registration fee and road tax	One Motoring, Land Transport Authority**
Maintenance and insurance fee	Singsaver website***
Petrol/diesel price	Motorist website****
Regular working days	Ministry of Manpower, Singapore
Average salary for delivery van drivers	Glassdoor*****

https://www.toyota.com.sg/finance/pricelist-commercial

https://onemotoring.lta.gov.sg/content/onemotoring/home.html

***

https://www.singsaver.com.sg/blog/car-maintenance-cost-in-singapore

****

https://www.motorist.sg/petrol-prices

*****

https://www.glassdoor.sg/

Figure 6.

Results of delivery cost, showing delivery cost reduction percentage compared with the base case.

The reduction in delivery costs provides insights into the limit of compensation that can be paid to the crowdshippers for the initiative to remain cost-neutral. For instance, in the scenario with minimum delivery cost, the delivery cost reduction divided by the number of crowdshipped parcels is S$1.45 per parcel. As a benchmark, the public bus trip fare for such a journey for an adult passenger is S$1.34, based on the average traveling distance of 6.24 km for a commuter trip in Singapore, which is less than the expected delivery cost savings per parcel ( 40 ). This suggests that crowdshipping has the potential to help carriers realize cost savings, while offering an attractive compensation to public transport passengers serving as crowdshippers.

Conclusion and Future Direction

Urban freight needs new solutions to fulfill demand growth with the spectacular development in e-commerce industry. At the same time, there are calls from governments and society to complete freight deliveries in a sustainable manner. The integration of passenger and freight transport offers good potential for more-efficient city logistics operations. Using real-world data, this research shows the feasibility and potential benefits of crowdshipping.

We examined the crowdshipping mode in a city setting where public transport passengers can serve as crowdshippers. More precisely, they can pick up parcels from lockers near or at their origin stops, hand-carry the parcels during their public transport trip, and deliver the parcels to their final destinations which are also close to their destination stops.

This study sought to provide an integrated assessment, starting from identifying parcels suited for crowdshipping, followed by matching parcels and crowdshippers, and determining locker locations. To determine which parcels are suitable to be delivered via crowdshipping, we formulate this problem as a spatial outlier detection problem and the LOF algorithm is applied to obtain the set of outlying parcels. A model for matching these outlying parcels with public transport passenger trajectories is developed. To determine which of the lockers should be chosen, a location-routing problem was formulated with constraints (i.e., vehicle capacity and route length). To solve this problem, a heuristic iterative algorithm is designed.

Besides the contributions to problem formulation, we also investigated the viability of the crowdshipping in a real-world case study. Our results show that supplementing conventional van deliveries with crowdshipping using public transport in a dense city such as Singapore can achieve key benefits. Up to 11% of parcels can potentially be redirected to crowdshippers. We report reductions in delivery VKT and associated emissions, fleet size, and costs by almost 20%. Crowdshipping can, therefore, realize both economic and environmental benefits.

Several limitations are acknowledged in this study, which can be addressed in future work. Firstly, this study does not consider the case where the crowdshipping tasks are rejected by crowdshippers. While the number of potential crowdshippers exceeds the number of parcels to be delivered by three orders of magnitude, the probability of rejection can be incorporated into the model. Further research on crowdshipper willingness to serve is ongoing, which is helpful to understand factors that may affect the availability of crowdshippers and practical implementation. Secondly, the capacity of each parcel locker was not limited in this study. The maximum number of parcels assigned to a single parcel locker is nearly 300 from the calculation. While e-commerce parcels tend to be small, this capacity constraint can be added in future work. Thirdly, to estimate the fleet size in the vehicle routing model, the maximum traveling distance per vehicle is used but the working time (driver shift) is not considered. While this distance limitation is calculated according to the related statistics in Singapore, it is better to reconsider this limitation in the future. Lastly, this study does not take into account detailed parcel information, such as parcel weight or size. These attributes can be more carefully examined.

Footnotes

Acknowledgements

We thank an anonymous e-commerce carrier in Singapore for sharing their parcel delivery data.

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: M. Zhang, L. Cheah; data collection: M. Zhang, L. Cheah; analysis and interpretation of results: M. Zhang, L. Cheah; draft manuscript preparation: M. Zhang, L. Cheah. All authors reviewed the results and approved the final version of the manuscript.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was partially funded by the Singapore Ministry of Education (T2-1712).

ORCID iD

Lynette Cheah

References

Statista. Global Parcel Shipping Volume Between 2013 and 2026 (in Billion Parcels). 2021. https://www.statista.com/statistics/1139910/parcel-shipping-volume-worldwide/.

Savelsbergh

Van Woensel

50th Anniversary Invited Article—City Logistics: Challenges and Opportunities. Transportation Science, Vol. 50, No. 2, 2016, pp. 579–590.

Rodrigue

J.-P.

The Geography of Transport Systems. Routledge, New York, NY, 2020.

Zhang

Cheah

Courcoubetis

Exploring the Potential Impact of Crowdshipping Using Public Transport in Singapore. Transportation Research Record: Journal of the Transportation Research Board, 2023. 2677: 173–189.

Land Transport Authority. Public Transport Ridership Average Daily Ridership (’000 Passenger-Trips). 2022. https://www.lta.gov.sg/content/dam/ltagov/who_we_are/statistics_and_publications/statistics/pdf/PT_Ridership_2015-2021.pdf.

Department of Statistics Singapore. Singapore Census of Population 2020. 2021. https://www.singstat.gov.sg/publications/reference/cop2020/cop2020-sr1.

Land Transport Authority. Static Datasets. 2021. https://datamall.lta.gov.sg/content/datamall/en/static-data.html.

Detlev

Pokotilo

Woetzel

Elements of Success: Urban Transportation Systems of 25 Global Cities. McKinsey & Company, New York, NY.

Luk

Olszewski

Integrated Public Transport in Singapore and Hong Kong. Road & Transport Research, Vol. 12, No. 4, 2003, p. 41.

10.

Public Transport Council. About PTC. 2023. https://www.ptc.gov.sg/about/overview.

11.

TransitLink. TransitLink. 2023. https://www.transitlink.com.sg/.

12.

Centre for Livable Cities Singapore. Integrating Land Use Mobility: Supporting Sustainable Growth. CLC Publications, Singapore, 2018.

13.

Archetti

Savelsbergh

Speranza

M. G.

The Vehicle Routing Problem with Occasional Drivers. European Journal of Operational Research, Vol. 254, No. 2, 2016, pp. 472–480.

14.

Macrina

Di Puglia Pugliese

Guerriero

Laganà

The Vehicle Routing Problem with Occasional Drivers and Time Windows. Proc., International Conference on Optimization and Decision Science, Sorrento, Italy, Springer, Springer International Publishing, 2017, pp. 577–587.

15.

Gdowska

Viana

Pedroso

J. P.

Stochastic Last-Mile Delivery with Crowdshipping. Transportation Research Procedia, Vol. 30, 2018, pp. 90–100.

16.

Wang

Zhang

Liu

Shen

Lee

L. H.

Towards Enhancing the Last-Mile Delivery: An Effective Crowd-Tasking Model with Scalable Solutions. Transportation Research Part E: Logistics and Transportation Review, Vol. 93, 2016, pp. 279–293.

17.

Soto Setzke

Pflügler

Schreieck

Fröhlich

Wiesche

Krcmar

Matching Drivers and Transportation Requests in Crowdsourced Delivery Systems. Proc., 23rd Americas Conference on Information Systems (AMCIS), Boston, MA, 2017.

18.

Gatta

Marcucci

Nigro

Patella

S. M.

Serafini

Public Transport-Based Crowdshipping for Sustainable City Logistics: Assessing Economic and Environmental Impacts. Sustainability, Vol. 11, No. 1, 2018, p. 145.

19.

Karakikes

Nathanail

Assessing the Impacts of Crowdshipping Using Public Transport: A Case Study in a Middle-Sized Greek City. Future Transportation, Vol. 2, No. 1, 2022, pp. 55–83.

20.

Barnett

Lewis

Outliers in Statistical Data. Wiley Series in Probability and Mathematical Statistics. Applied Probability and Statistics. Wiley, New York, 1994.

21.

Breunig

M. M.

Kriegel

H.-P.

R. T.

Sander

LOF: Identifying Density-Based Local Outliers. Proc., 2000 ACM SIGMOD International Conference on Management of Data, Dallas, TX, Association for Computing Machinery, New York, 2000, pp. 93–104.

22.

Shekhar

Chawla

A Tour of Spatial Databases. Prentice Hall, Upper Saddle River, NJ, 2003.

23.

Nagy

Salhi

Location-Routing: Issues, Models and Methods. European Journal of Operational Research, Vol. 177, No. 2, 2007, pp. 649–672.

24.

Srivastava

Algorithms for Solving the Location-Routing Problem. PhD thesis, The Ohio State University, 1986.

25.

Auskalnis

Paulauskas

Baskys

Application of Local Outlier Factor Algorithm to Detect Anomalies in Computer Network. Elektronika ir Elektrotechnika, Vol. 24, No. 3, 2018, pp. 96–99.

26.

Xiao

Ruan

Wang

An Efficient Density-Based Local Outlier Detection Approach for Scattered Data. IEEE Access, Vol. 7, 2018, pp. 1006–1020.

27.

Pedregosa

Varoquaux

Gramfort

Michel

Thirion

Grisel

Blondel

, et al. Scikit-Learn: Machine Learning in Python. Journal of Machine Learning Research, Vol. 12, 2011, pp. 2825–2830.

28.

Nambiar

J. M.

Gelders

L. F.

Van Wassenhove

L. N.

A Large Scale Location-Allocation Problem in the Natural Rubber Industry. European Journal of Operational Research, Vol. 6, No. 2, 1981, pp. 183–189.

29.

Branco

Coelho

The Hamiltonian p-Median Problem. European Journal of Operational Research, Vol. 47, No. 1, 1990, pp. 86–95.

30.

Hansen

P. H.

Hegedahl

Hjortkjaer

Obel

A Heuristic Solution to the Warehouse Location-Routing Problem. European Journal of Operational Research, Vol. 76, No. 1, 1994, pp. 111–127.

31.

T.-H.

Low

Bai

J.-W.

Heuristic Solutions to Multi-Depot Location-Routing Problems. Computers & Operations Research, Vol. 29, No. 10, 2002, pp. 1393–1415.

32.

Srivastava

Alternate Solution Procedures for the Location-Routing Problem. Omega, Vol. 21, No. 4, 1993, pp. 497–506.

33.

Srivastava

Benton

The Location-Routing Problem: Considerations in Physical Distribution System Design. Computers & Operations Research, Vol. 17, No. 5, 1990, pp. 427–435.

34.

Cormen

T. H.

Leiserson

C. E.

Rivest

R. L.

Stein

Introduction to Algorithms. MIT Press, Cambridge, MA, 2022.

35.

Clarke

Wright

J. W.

Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, Vol. 12, No. 4, 1964, pp. 568–581.

36.

Johnson

D. S.

Demers

Ullman

J. D.

Garey

M. R.

Graham

R. L.

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SIAM Journal on Computing, Vol. 3, No. 4, 1974, pp. 299–325.

37.

Luxen

Vetter

Real-Time Routing with OpenStreetMap Data. Proc., 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS ’11, ACM, New York, 2011, pp. 513–516. http://doi.acm.org/10.1145/2093973.2094062.

38.

Land Transport Authority. Passenger Volume by Origin Destination Bus Stops. 2021. https://datamall.lta.gov.sg/content/datamall/en/dynamic-data.html.

39.

Toyota. HIACE. Brochure, 2017. https://www.toyota.com.sg/finance/pricelist-commercial.

40.

TransitLink. Adult Fare Structure. 2022. https://www.transitlink.com.sg/travel-fares/adult-fares/.

Prioritizing Outlier Parcels for Public Transport-Based Crowdshipping in Urban Logistics

Abstract

Keywords

Related Work

Crowdshipping Operations Research

Contributions of this Paper

Problem Formulation

Methodology

Overview of Study Methods

Outlying Parcel Identification

Parcel-Crowdshipper Matching Model

Parcel Locker Selection Model

Vehicle Routing

Algorithms

Outlying Parcels Identification—Local Outlier Factor (LOF) Algorithm

Parcel Locker Selection Model—Heuristic Algorithm

Vehicle Routing—Best Fit Decreasing Algorithm

Experiment with Real-World Data

Data Collection

Computational Results

Base Case without Crowdshipping—Results from CVRP

Outlying Parcel Identification and Parcel-Crowdshipping Matching

Carrier Performance

Conclusion and Future Direction

Footnotes

Acknowledgements

Author Contributions

Declaration of Conflicting Interests

Funding

ORCID iD

References