key: cord-0136952-u6zbq1yw
authors: Herthel, Ana Beatriz; Hartl, Richard; Vidal, Thibaut; Subramanian, Anand
title: Share-a-ride problems: Models and Solution Algorithms
date: 2021-10-28
journal: nan
DOI: nan
sha: 830f0ad1826c30fdddd924705cf29d364bb8e0b8
doc_id: 136952
cord_uid: u6zbq1yw

Some of today's greatest challenges in urban environments concern individual mobility and rapid parcel delivery. Given the surge of e-commerce and the ever-increasing volume of goods to be delivered, we explore possible logistic solutions by proposing algorithms to add parcel-transport services to ride-hailing systems. Toward this end, we present and solve mixed-integer linear programming (MILP) formulations of the share-a-ride problem and quantitatively analyze the service revenues and use of vehicle resources. We create five scenarios that represent joint transportation situations for parcels and people, and that consider different densities in request types and different requirements for vehicle resources. For one scenario, we propose an alternative MILP formulation that significantly reduces computation times. The proposed model also improves scalability by solving instances with 260% more requests than those solved with general MILP. The results show that the greatest profit margins occur when several parcels share trips with customers. In contrast, with all metrics considered, the worst results occur when parcels and people are transported in separate dedicated vehicles. The integration of parcel services in ride-hailing systems also reduces vehicle waiting times when the number of parcel requests exceeds the number of ride-hailing customers.

Growing urbanization and the desire to decrease dependence on fossil energy and thereby reduce greenhouse gas emissions are two important factors that motivate the search for new solutions in urban mobility.

In this context, crowd-based transport has emerged as a meaningful alternative to share resources and reduce our carbon footprint. Crowd-based transport relies on members of a crowd offering underused space in their vehicles to perform associated activities. Companies such as Uber, Lyft, and Didi have benefited from this trend by providing peer-to-peer ride-sharing services, where people who need rides are paired with drivers offering rides. This business model facilitates access to city centers from suburban areas and can reach regions underserved by public transport. In turn, this contributes to the growth of productivity in bustling economic centers without increasing the population in those areas (Graham and Gibbons 2019) .

The rapid growth of e-commerce is also shifting the way last mile is covered for deliveries in large cities. Online stores are gaining ground over brick-and-mortar shops given the former's inherent comfort, ease of ordering, and rapid purchasing process. This causes a surge in the number of smaller parcels to be delivered. According to the International Post Corporation (2021), lightweight parcels accounted for the largest part of revenues for postal services in 2020. Although this trend may have been fueled by changes in consumer behavior due to the lockdown policies put in place during the COVID-19 pandemic, revenues for the same type of service for the previous year were similar (International Post Corporation 2020) . Note also that lightweight parcels must weigh less than one or two kilograms, depending on the postal service provider. Reports from the commerce-solutions company Pitney Bowes Inc. (2020) show that, in 2019, the 13 largest markets in the world transported 103 billion parcels collectively, which corresponds to 3000 units being shipped every second.

The growth in volume shipped of smaller parcels has also occurred in large e-commerce companies such as Amazon. The majority of packages transported by Amazon (around 86%) weigh less than 2.3 kg (Columbia Broadcasting System 2013), with 1.9 billion units delivered in the US alone in 2019 (Pitney Bowes Inc. 2020). High-capacity vehicles, such as vans and trucks, become oversized for deliveries of parcels of such size, which, in most cases, are expected to be delivered quickly and at minimal costs (Convey 2019) .

The concept of sharing instead of buying, which is the backbone of the shared economy, is expected to reduce CO 2 emissions. Nevertheless, recent studies of ride-hailing systems indicate the opposite. According to Anair et al. (2020) and Environment (2019) , private-hire vehicles in Europe and the US have led to a surge in greenhouse gas emissions. A major reason for this phenomenon is that about 42% of their trips are for relocation and waiting for passenger requests.

Usually, in urban areas, people and parcels are transported in separate systems dedicated to each activity, even though these systems generally use the same network. By having additional parcel-transport services make use of these relocation trips, vehicles can be employed more efficiently, which would allow reductions in fleets dedicated to these services in city centers.

The integration of parcel-transport services with ride-hailing systems can be attractive to both peer-to-peer ride-sharing companies and small-scale retailers. For the former, parcel transport represents a new source of revenue, and, for the latter, it represents the possibility of moving goods quickly and safely without having to invest heavily in dedicated shipping solutions. Moreover, the growth of ride-hailing systems at the expense of taxis makes these systems promising candidates for incorporation into frameworks in which parcels and passengers share trips. This logic is reinforced by the fact that ride-hailing systems already have a structure that supplies information about parcel transport to customers with no reduction in service level for passengers. Li et al. (2014) first proposed algorithms for solving the problem of joint mobility of parcels and passengers. This problem is called the "share-a-ride problem" (SARP) and arises when parcels and passengers share taxi trips. This problem is an extension of the well-known dial-aride problem (DARP) (Cordeau and Laporte 2003) , which is NP-hard (Baugh Jr. et al. 1998) . We use the SARP as a framework in which to model the integration of parcel and passenger transport in ride-hailing systems, which has not been sufficiently explored from the viewpoint of operations research. Furthermore, few studies discuss the shared transport of people and parcels or assess its impact on vehicle-use efficiency.

The contributions of this paper are threefold:

1. We propose novel scenarios for the SARP by limiting either the number of parcels to be transported, the number of consecutive passengers to be transported while transporting parcels, or both.

2. We use general MILP to model all scenarios in this work. In addition, we show that scenarios in which a single passenger and a single parcel are transported can be reformulated as a multi-depot open generalized-vehicle-routing problem with time windows. This allows us to model the problem more efficiently when addressing this particular setting.

3. Through extensive computational experiments we show that, compared with separately transporting parcels and passengers, transporting them together can yield higher profits and a lower percentage of trips with empty vehicles, all for a marginal increase in driverwaiting times.

The remainder of this work is organized as follows: Section 2 reviews the relevant work related to SARP. Section 3 defines the problem and presents the necessary mathematical notation. Section 4 introduces the MILP models and the different scenarios for the SARP. Section 5 presents the results of our computational experiments, and Section 6 concludes and discusses perspectives for future research.

Many studies have focused on optimizing the transport of people and goods. However, in the vast majority of these studies, the two activities were considered separately. Nevertheless, integrating these systems may be profitable because they often share the same network (i.e., roads). Recently, some works have proposed interesting ideas concerning the movement of packages via public transport systems, see, for example, Fatnassi et al. (2015) , Ghilas et al. (2016) , Masson et al. (2017) , Serafini et al. (2018) . Li et al. (2014) proposed the SARP, which is an extension of the DARP and involves the transport of people by requested vehicles. In the SARP, people and goods share trips in taxis. Each taxi can transport only a single person at a time and, if the driver chooses, a parcel can be picked up while transporting a person. Note that parcels may be picked up only if the detour does not significantly affect the expected travel time of the passenger. Li et al. (2014) also proposed a reduced problem called the freight-insertion problem, whereby a route for servicing passengers already exists and parcel requests must be inserted into the given route.

Both problems were optimally solved by using a commercial MILP solver (GUROBI), but only for small instances in the SARP. The results of the SARP highlight the fact that joint transportation can lead to higher profit than the traditional separate transport of parcels and people. The freight-insertion problem has seen an increase in acceptance of parcel insertions with the increase in number of passengers, but this acceptance drops when a larger number of parcels are inserted. Li et al. (2016a) solved the SARP again by using an adaptive large neighborhood search with simulated annealing as a local search strategy. They achieved small solution gaps within reasonable computational times and improved the solutions for two DARP benchmark instances. Li et al. (2016b) extended this work by solving two stochastic variants of the SARP, considering traveling times and delivery locations as sources of uncertainty. Chen et al. (2017) also studied the joint transport of parcels and people, but for the return of purchased items. As with Li et al. (2014) , their solution involves using the idle space in a fleet of taxis. To not inconvenience passengers, they impose the condition that parcels can only be picked up before servicing a client and delivered afterwards. This guarantees no detours during the passenger's trip. However, when solving the problem, they do not consider taxi or shop storage capacities nor time windows. Beirigo et al. (2018) treated a variant of the SARP with shared autonomous vehicles. The resulting problem is called "share-a-ride with parcel lockers". For transporting people and parcels, the vehicles have distinct compartments of various sizes to accommodate goods of different dimensions. One scenario considered is the transport of more than one passenger at a time. Beirigo et al. (2018) also use a commercial solver with a MILP formulation to solve the problem.

The SARP studied by Do et al. (2018) is similar to that studied by Li et al. (2014) in that only a single passenger request can be serviced at a time. Do et al. (2018) consider three different strategies for transporting goods and passengers simultaneously: (1) A parcel can be picked up and delivered before the passenger request is initiated. (2) A parcel can be picked up and delivered after the passenger is dropped off. (3) A parcel can be picked up before the passenger and delivered after the passenger is dropped off, similar to the case considered by Chen et al. (2017) . None of these strategies permit passenger detours. These scenarios were studied in static and dynamic contexts.

Since the SARP is a variant of the DARP, studies of the DARP are important to the present work. The classical version of the DARP has been reviewed by, for example, Cordeau and Laporte (2007) , who discuss two-and three-index formulations for the DARP. They also review algorithms used to solve single-and multi-vehicle variants of the problem in both the static and dynamic cases. For more recent reviews on the state-of-the art of the DARP, we refer the reader to Molenbruch et al. (2017) and Ho et al. (2018) .

This work is also connected to studies of peer-to-peer ride sharing, crowd-shipping, and crowd logistics (see, e.g., Le et al. (2019) , Mourad et al. (2019) , Sampaio et al. (2019) , and Cleophas et al. (2019) ). Such studies provide insights not only on quantitative aspects but also on qualitative aspects of peer-to-peer shipping and ride sharing.

One qualitative aspects is the willingness to adhere to crowd-shipping systems. Punel et al. (2018) found that users are not motivated as much by reduced shipping costs as they are attracted to a potential lower environmental impact of this form of parcel transportation.

The challenges of implementing peer-to-peer shipping and ride-sharing systems should also be explored. Furuhata et al. (2013) list the following three main challenges for ride-sharing companies: (i) the creation of an attractive system, (ii) the offer of personalized ride arrangements, and (iii) building trust between passengers who are not acquainted with each other. These challenges also appear when designing peer-to-peer shipping systems:

1. Drivers and e-commerce customers must have advantages if they are to participate in the transport of goods and in deliveries, respectively.

2. Preferences for different time windows or different delivery locations for parcels should be respected.

3. Customers and shops must trust that the deliveries will be made without fail.

The SARP concerns the problem in which parcels and passengers share trips in taxis. In this work, we consider that this joint transportation takes place in a ride-hailing system. Passenger service is considered as the main activity, so all passenger requests must be serviced and the associated trips cannot have detours. Parcel deliveries, in contrast, are optional and are ignored if they have no economic benefits.

We define G = (V, A) as a directed graph wherein V represents the set of nodes and A represents the set of arcs. Let V be defined as V := N ∪ P ∪ D ∪ S, such that N = {0, 1, . . . , n − 1} is the set of customer service nodes, and P = {n, n + 1, . . . , n + m − 1} and D = {n + m, n + m + 1, . . . , n + 2m − 1} are the sets of parcel-pickup and -delivery nodes, respectively. With this notation, n and m refer to the number of passenger and parcel requests, respectively. Parcels picked up at i ∈ P must be delivered to i + m ∈ D. Since passenger detours are not permitted, a passenger pickup is always followed by a passenger drop-off, so these two activities are represented as a single node.

Ride-hailing vehicles are often privately owned, and a driver can choose when to start servicing passengers and when to end the service. Thus, we consider a multi-depot scenario to account for vehicles starting journeys at different origins. In addition, the driver does not need to return to his or her original location after the last customer or parcel is served. This is commonly known as an "open route."

A fleet of vehicles is represented by a set K = {0, 1, . . . , κ}. Each vehicle k ∈ K starts its trip at a specific origin s k ∈ S such that S = {n + 2m, n + 2m + 1, . . . , n + 2m + κ}. The vehicles also have a maximum driving time T . Vehicle capacity is taken into account through restrictions imposed by our scenarios on the number of passengers and parcels that can be simultaneously transported.

The set A of arcs is defined by the following trips:

1. from a vehicle origin to a passenger or parcel pickup location;

2. from a passenger pickup location to his/her drop-off location;

3. from a passenger drop-off location to a different passenger pickup location;

4. from a passenger drop-off location to a parcel-pickup or -delivery locations;

5. from a parcel-pickup location to its delivery location;

6. from a parcel-pickup or -delivery location to a different pickup or delivery location;

The arcs (i, j) ∈ A have associated traveling times (t ij ), distances (d ij ), and costs (c ij ). The quantities d ij and t ij are related by d ij = νt ij , where ν is the average speed of the vehicles.

Nodes i ∈ V are associated with a service time r i , time windows [e i , l i ], and demand q i . The service time for a parcel is the time required to load and unload the parcel from the vehicle.

For passengers, these times take into account not only the time to board and leave the vehicle, but also the traveling time between the pickup and drop-off locations. For these types of requests, q i = 0. Their time windows are considered as time points such that e i = l i , and service should start at that time. For the remaining nodes, the time window is set to the complete planning horizon, which means that service can occur at any time. We also define r i > 0 (i ∈ P ∪ D) and q i = −q i+m (i ∈ P ). For i ∈ S, r i = 0, q i = 0. Fare per km charged for passenger transport γ 2 Initial fare charged for parcel transport µ 2

Fare per km charged for parcel transport µ 3

Average driving costs per km φ i Revenues for transporting passenger i ∈ N θ i Revenues for transporting parcel i ∈ P

The objective of this problem is to maximize profit by simultaneously transporting passengers and parcels. To solve the problem, we use the parameters presented in Table 1 .

The travel costs are estimated to be proportional to the distance: c ij = µ 3 d ij . We assume that the fuel, insurance and maintenance costs are included in µ 3 .

This section discusses the scenarios created to portray different restrictions on passenger and parcel services. Moreover, we present two MILP formulations used to solve the SARP.

We compare seven scenarios corresponding to different real-life situations in which passengers and parcels share vehicles. From this point forward, we use the terms "passengers" and "customers" interchangeably. The first two scenarios are named "dedicated vehicles" D v and "separated trips" S t , and they both represent cases in which customers and parcels are serviced separately. In the first scenario, vehicles can service either customers or parcels. In the second scenario, a vehicle can service both customers and parcels, but they are never transported jointly.

The four remaining scenarios model situations in which parcels and customers can possibly travel together. These scenarios are labeled single-customer-single-parcel (S c S p ), multiplecustomer-single-parcel (M c S p ), single-customer-multiple parcels (S c M p ), and multiple-customersmultiple-parcels (M c M p ). We also extend scenario M c M p , which is called alternative multiplecustomers-multiple-parcels (AM c M p ).

In S c S p and M c S p , vehicles are restricted to carrying at most one parcel at a time. These scenarios model real-life situations in which passengers use most of a vehicle's capacity to transport their belongings. The difference between these scenarios is that, in S c S p , the vehicle has to service exactly one passenger before delivering a package, whereas in M c S p , several customers can be serviced consecutively while the parcel remains in the trunk.

In scenarios S c M p and M c M p , a vehicle can carry more than one parcel at a time. These scenarios represent cases in which customers need little or no extra vehicle capacity for moving their belongings. In a similar fashion, S c M p is the scenario in which a vehicle must service exactly one passenger before delivering any transported parcel. Conversely, in the scenario M c M p , the vehicle can service any number of customers after picking up parcels.

The scenario AM c M p has the same characteristics as M c M p , but with the added possibility of directly servicing parcels without needing to service customers first. These scenarios are illustrated in Figure 1 .

This formulation allows us to model all previously presented scenarios as a MILP. Since passengers cannot have detours, we represent a direct trip between a passenger pick-up location to his or her drop-off location as a single node. We further refer to these nodes as "collapsed".

The arcs of set A connecting passenger pickup locations to their respective drop-off ones are thus contained in the "collapsed" nodes. The distances associated with those arcs are represented by d ii (i ∈ N ) and they obey the same relationship regarding travel times and average speed as presented for the "non-collapsed" nodes. Moreover, we use µ 3 to obtain the driving costs generated within the passenger nodes. The calculations for the revenue parameters are thus performed as follows:

To model an open route, we create a set of "dummy" depots to be added to V and we define the route as F = {n + 2m + κ + 1, n + 2m + κ + 2, . . . , n + 2m + 2κ + 1}, such that a vehicle k ∈ K that starts its trip at point s k = n + 2m + k ends the trip at f k = n + 2m + κ + k + 1. Since these dummy depots exist only in the modeling, zero cost and time is associated with arcs arriving at f k , k ∈ K. Furthermore, zero service time and demand are associated with these nodes. With this representation of an open route, we add to set A all arcs that leave either a passenger request or parcel delivery node and arrive at a dummy depot.

The variables in this model are the starting time b i of a service, i ∈ V , the load w i of a vehicle after visiting i ∈ V , and the binary variables y k i and x k ij . Note that y i = 1 if i ∈ V is serviced and zero otherwise. Moreover, x k ij = 1 if arc (i, j) ∈ A is traversed by vehicle k and zero otherwise. The model can be expressed as max i∈N j∈V k∈K

k∈K j∈V

k∈K j∈V

j∈N ∪P

The objective function is presented in (1). Constraints (2) state that all passenger nodes must be serviced. Constraints (3) connect the parcel selection and flow decisions, whereas Constraints (4) guarantee that a parcel that is picked up is delivered by the same vehicle. Constraints (5) ensure flow conservation, and Constraints (6) determine the origin and end points of the routes for each vehicle. Time constraints are specified in (7)-(11) whereas load constraints are specified in (12). Constraints (13) remove all arcs between a parcel delivery location and its pickup. Constraints (14)-(17) specify variables domains.

Given that all passengers must be serviced and no detours are allowed for these requests, the first term of (1) is constant and can be removed and added later to the solution. Thus, the objective function can be rewritten as max i∈P j∈V k∈K

We ensure Constraints (7) and (9) are valid by setting M to the value of the end of the time horizon considered. For Constraints (12), the validity is ensured by defining W = m + 1 for "multiple-parcel" scenarios and W = 2 for "single-parcel" scenarios.

The formulation represented by (1)-(17) must be adapted for the different scenarios. In what follows, we present all additional constraints for the general formulation and show how they are assigned to model each scenario. The additional constraints are

Constraints (19) ensure that a single customer is serviced whenever a vehicle carries parcels. Constraints (20) and (21) remove arcs from either two parcel-pickup locations or two parceldelivery locations. Constraints (22) prevent a parcel from being transported directly from origin to destination, whereas Constraints (23) guarantee that a maximum of one parcel can be carried at any time. Constraints (24) ensure that no passenger can be served while the vehicle is transporting parcels. Constraints (25) and (26) guarantee that no vehicles are shared between parcels and passengers. Finally, Constraints (27) and (28) ensure that parcels and passengers do not share trips.

To model these scenarios, we add the constraints shown in Table 2 to the formulation. To solve this model more efficiently, we develop an alternative MILP formulation. This is possible for S c S p given how customers and parcel requests are organized in the solution for this scenario. After leaving its origin, a vehicle visits either a customer or a parcel-pickup location.

Each time a vehicle visits a node v ∈ P , it is followed by u ∈ N and, later, by v + m ∈ D. After this point, the vehicle can again visit either a customer service node or a parcel-pickup location.

Considering this, we reformulated the problem on a different network based on the concept of "service bundles." These bundles can contain either a single customer request u ∈ N or a sequence of requests (v, u, v + m) such that v ∈ P , u ∈ N , and v + m ∈ D.

Inspired by the generalized vehicle-routing problem (GVRP) defined by Ghiani and Improta (2000) , we further separate the bundles into groups according to the customer request associated with each group. In this way, we guarantee that all customers are serviced by visiting each group exactly once. Figure 2 shows an example of grouping bundles and constructing solutions with the new formulation.

The new formulation is defined on a graphḠ = (B, A B ) such that each node corresponds to one of the possible bundles. The set of bundles is represented by B = {0, 1, . . . , n + nm − 1} and A B = {(i, j) : i ∈ B ∪ S ∪ F, j ∈ B ∪ S ∪ F, i = j} is presented as the set of arcs between bundles, origins, and ending locations for vehicles. Let B u ⊂ B be the set of bundles servicing passenger u ∈ N , and let B v ⊂ B be the set of bundles servicing parcel request v ∈ P .

As in the general model, vehicle k ∈ K has to start and end its trip at its origin and ending locations. These points are not bundled with any other requests in this formulation.

The revenues β i generated by a bundle i ∈ B are calculated by adding individual revenues for the requests in the bundle and subtracting the costs of traveling between these requests. We use the fare and cost parameters presented in Table 1 . Each bundle also has a service duration ∆ i and a time window [ē i ,l i ] that needs to be satisfied. Since passengers are bound to be serviced at specific time points, no bundle can be serviced later thanē i , soē i =l i for i ∈ B. The timeē i to start servicing bundle i ∈ B is obtained from the time point of service for the passenger associated with bundle i (e u , u ∈ N ). If no request requires service before the passenger, the bundle must be served at e u . Otherwise,ē i = e u − t vu − r v such that u ∈ N , v ∈ P , and i ∈ B and u and v are requests present in i.

Each arc (i, j) ∈ A B is characterized by costsc ij > 0 and traveling timest ij > 0. For the cases in which an arc leaves a bundle to proceed to a dummy depot, both values are set to zero.

The arcs (i, j) ∈ A B represent trips from i to j (i, j ∈ B) and exist in the following cases:

1. from a vehicle origin to a bundle;

2. between any two bundles that do not contain the same passenger request;

3. from a bundle to a dummy ending depot.

Note that arcs are removed from the network ifē i < 0,ē i + ∆ i > τ , or both (i ∈ B). The parameter τ is the latest point of the time horizon for the problem.

The graph described is used to develop the "bundle formulation." The decision variables z k ij in this formulation are unity if arc (i, j) ∈ A B is traversed by vehicle k ∈ K and zero otherwise.

The resulting model is max i∈B j∈B k∈K

subject to k∈K i∈Bu j∈B

i∈Bv j∈B k∈K

Objective (29) maximizes profit for visiting bundles. Constraints (30) establish that, for each passenger request, a single arc leaves and enters the group of bundles that contains it. Constraints (31) determine the origin and end points of each route. Constraints (32) ensure that no parcel is serviced more than once, and Constraints (33) guarantee flow conservation between bundles. Constraints (34) ensure that the maximum driving time is not exceeded, whereas Constraints (35) determine the domain of the variables.

We implemented the models using C++ and g++ 5.4.0, compiled with the flag -O3. We conducted all computational experiments on a single thread of a server equipped with an Intel Xeon 2.0 GHz processor and 128 GB of RAM, running Ubuntu Linux 16.04. We used IBM CPLEX 12.7 to solve the models and established a limit of two hours for each run. To solving each instance we use the minimum possible number of vehicles to achieve feasible solutions.

With these experiments we analyze the potential gains produced by adding parcel service to a ride-hailing system. We begin by evaluating the profit variation. We compare the profits obtained for all scenarios considered, reinforcing contrasts between the situations in which parcels and passengers share trips and the situations in which they do not. Our assessments also consider how the parcel service affects the use of resources; that is, how much time a vehicle travels empty and how long a driver has to wait for a request. We compare the performance of all scenarios based on these metrics.

Finally, we test the quality and scalability of the bundle formulation. We start by comparing objective values and the time required to solve the problem with both formulations. Next, we propose larger instances by increasing the number of requests, which we solve by using the bundle model, until optimal solutions can no longer be obtained.

We gathered Uber data regarding trip price estimates (https://www.uber.com/global/en/ price-estimate/) from cities with a large number of daily ride requests and parcel deliveries. This information was then used to calculate the parameters γ 1 and µ 1 , which allowed us to more accurately portray the characteristics of ride-hailing systems. Table 3 lists the values of γ 1 and µ 1 for each chosen city and presents the final values considered in our experiments, which were calculated by using a simple average. All monetary amounts were converted to US dollars and the fare per mile was converted to fare per kilometer. We also collected data on real driving costs estimates from large countries and from the European Union to compute µ 3 . These values are based on costs of fuel, insurance, and maintenance. The values were converted to US dollars and a simple average provided the final value of µ 3 . Table 4 lists the costs and the average. To estimate the parameters γ 2 and µ 2 , we consider that customers hope to pay as little as possible for transporting parcels. Concomitantly, the integration of parcel-delivery services should be profitable to the ride-hailing companies. To this end, we use γ 2 = 2.74 and µ 2 = 0.83, which maintains µ 2 > µ 3 and guarantees that parcel transport per kilometer is profitable.

From data provided by the Uber Movement initiative (Uber 2017) , we also obtained information regarding average speed and average trip duration for Uber requests. However, this data bank does not contain both pieces of information for all cities listed, so we are limited to the cities for which such data are available. We selected October of 2019 as the source of our data because this month offers the most recent complete set for which customer behavior is not affected by the Covid-19 pandemic or holidays. We focus on the larger cities available. Table 5 lists the results and the averages. 

We worked with three sets of instances for this problem. The first set, named GH, was adapted from the Traveling Salesman Problem Pickup and Delivery Test Instance Library (TSPPDLIB) of O'Neil (2017) (https://github.com/grubhub/tsppdlib), which is based on a meal-delivery application from Grubhub. This library includes ten instances for each number of requests, which, in turn, spans from two to fifteen pickup and delivery pairs. We adapted instances from this library with a minimum of eleven requests by defining 30% and 40% of these requests as parcels and the rest as customer trips. We discarded any resulting adapted instances with less than three parcel requests. We generated points in time for passenger requests and considered our time horizon to be 24 hours. These instances were defined for a single depot, so we maintained this characteristic. Further adaptation was necessary to scale the TSPPDLIB distances, which do not accurately reflect the average length of ride-hailing trips. We applied a multiplicative factor to these values to obtain average distances of a magnitude similar to those obtained from the Uber data.

The second set, named SF , is derived from the instances presented in Li et al. (2016a) . The original instances are based on taxi data from San Francisco. We took instances of size 270 and 300 from this set and selected a number of passenger and parcel requests to form smaller instances of our own. We generated five different instances for each number of requests.

The last set of instances is called M D and is proposed herein. We generated points in a grid such that the distances obtained are consistent with the range previously calculated from Uber data. To pair these points as pickup and destination, we applied a method similar to that proposed by Renaud et al. (2000) . We first took a random point as a pickup location for either parcel or customer and ranked the unassigned points by using proximity as a criterion. We next chose the first λ points and selected one of them at random to be the destination for this request. We used the values λ = {2, 5, ∞} and indexed instances accordingly from A to C. Four instances are generated for each size and pairing method used, which results in twelve instances for each combination of passenger number and parcel requests.

The number of requests chosen for sets SF and M D span from seven to nine passenger trips, which are paired with five to seven parcels and do not exceed a total of fifteen requests.

All instances are named according to the dataset to which they belong, the number of customers, and the number of parcel requests (e.g., gh-7-4 is an instance of data set GH with seven customers and four parcel requests).

The chosen instance sets have particular characteristics due to the sources from which they are generated, which gives us a broader view during our analysis because we work with both artificial and real data as well as with single-depot and multiple-depot settings.

We start by analyzing the objective values yielded by the different scenarios. The goal of these comparisons is to identify how profit is obtained in different scenarios, considering customer and parcel transport and how the balance between these two activities influences this metric. Figures 3-5 show the results. Each graph presents values obtained by solving the various scenarios for the different numbers of requests in each data set. The solutions are averaged over all instances for each group of a distinct number of passengers and parcel requests. Each dataset graph is divided into subgraphs based on the number of parcel requests of the instance groups. The number of parcels is presented at the top of each subgraph. The Y axis is common to all subgraphs and gives the average solution obtained. The X axis is the number of passenger requests in each instance group, segmented according to the subgraph division.

In all sets, scenario D v yields the worst solutions. These only surpass the solutions obtained in S c S p and M c S p in three and two out of 24 of the instance groups, respectively. This phenomenon is even more prominent with datasets GH and SF . In contrast, the other separate transportation approach S t yields good results, often very close in value to M c M p and S c M p . However, when the number of customer requests increases, S t performs slightly worse than "multi-parcel" scenarios, which indicates that, in a context where customer trips represent the majority of requests, adopting separate transport models would not be as financially advantageous as adopting joint transport alternatives.

Note that scenarios S c S p and M c S p as well as S c M p and M c M p produce similar results, with a slightly better performance for the "multi-customer" variant in each subset of scenarios (i.e., M c S p and M c M p ). This is a consequence of the structure of instances used in which, most often, passengers outnumber parcels. Considering the previously mentioned subsets, the "singleparcel" scenarios consistently yield solutions that are worse than the "multi-parcel" scenarios, which indicates that the situations in which vehicle space is restricted by passenger belongings reduces the potential profit from parcel service.

Combining the joint transport of passengers and parcels and the possibility of parcels being transported directly from their pickup to their delivery locations significantly improves the solutions, as becomes clear upon noting that, for all instance groups, the best solutions are consistently obtained from scenario AM c M p .

We further analyze the cost effectiveness of the scenarios by looking at the average number of parcels served in each instance group. Table 6 presents these results.

In scenario S c S p , vehicles service the smallest number of parcels on average, and this number surpasses the number of parcels served in scenario D v for 29% of the instance groups. Even though vehicles in scenario D v serve more parcels on average than in "single-parcel" scenarios, these deliveries incur higher costs, which explains the small profit obtained when using dedicated 6 5.20 5.20 5.40 5.40 6.00 6.00 6.00 sf-7-7 7 5.20 5.20 6.80 6.80 6.80 5.40 6.80 sf-8-5 5 4.60 4.40 4.80 4.80 5.00 2.80 5.00 sf-8-6 6 5.00 5.60 5.60 5.60 6.00 4.80 6.00 sf-8-7 7 5.40 5.20 6.60 6.60 7.00 6.60 7.00 sf-9-5 5 4.40 4.40 4.80 4.80 5.00 3.00 5.00 sf-9-6 6 5.60 5.60 5.80 5.80 6.00 3.60 6.00 md-7-5 5 3.83 3.75 4.33 4.33 4.92 3.75 4.92 md-7-6 6 4.33 4.42 5.33 5.42 5.92 5.42 6.00 md-7-7 7 4.00 4.25 5.92 6.33 7.00 6.50 6.92 md-8-5 5 3.33 3.42 3.67 3.92 4.75 3.17 4.75 md-8-6 6 4.20 4.40 5.20 5.80 6.20 6.00 6.20 md-8-7 7 4.67 4.58 6.17 6.25 6.92 6.58 6.92 md-9-5 5 3.75 3.75 4.25 4.25 4.92 3.92 4.92 md-9-6 6 3.83 4.17 5.00 5.25 5.75 5.25 5.92

A similar situation appears upon comparing S t and AM c M p . In both of these scenarios, vehicles service an equivalent number of parcels, on average. However, when parcels and customers share trips (as in scenario AM c M p ), travel costs decrease, leading to better solutions in the end.

Overall, using dedicated vehicles to transport customers or parcels is the least cost-effective strategy for ride-hailing systems, despite this model being commonly encountered in most major cities. This situation, modeled in scenario D v , yields worse solutions than all other scenarios for the vast majority of instance groups. Moreover, upon increasing the number of requests, the difference between the solutions increases when comparing the previously mentioned scenario with the "multi-parcel" scenarios, namely, S c M p , M c M p , and AM c M p . We highlight comparisons between instance groups gh-7-5 and gh-8-5 as well as between sf-7-6 and sf-9-6. The difference between solutions obtained with D v and AM c M p increases from 49.82% to 69.61% for the former and from 11.37% to 57.98% for the latter, with the addition of only one and two customer requests, respectively.

In addition to analyzing solutions, we measured and compared the use of vehicle space and driving-time resources in the different scenarios. This involved tracking the work time spent servicing a request (either parcel, passenger, or both), driving empty (i.e., relocating), and waiting.

We present graphs containing the results obtained for the activities of driving empty and waiting. For each scenario and number of requests, Figs. 6-8 display the average solutions for the percent of trip duration during which a vehicle is empty. As in the previous section, the graphs are separated into subgraphs according to the number of parcel requests, which is displayed at the top of each graph section. The same conventions apply to Figs. 9-11, which show the average percent of trip duration that a vehicle waits for requests as a function of the number of passenger requests.

The results indicate that vehicles spend less time empty in scenarios in which there is no limit on the amount of parcels transported or on the sequence of customers serviced. This is the case of M c M p , which yields the lowest ratios of empty vehicle trip time for almost 80% of the instance groups. In contrast, S t , which performs well in terms of profit, generates the most empty vehicle trips in 62.5% of the instance groups. This suggests that, even though most parcel requests are serviced in this scenario, the lack of shared trips with customers hinders the efficient use of vehicle space during the trip.

Note also that, due to the inherent transport restrictions of S c S p , this scenario does not score well with these metrics; however, in 75% of the instance groups, it still yields better results in terms of empty vehicle trip duration than the solutions obtained from D v .

When comparing waiting times for these instances, no clear increasing or decreasing tendency emerged upon varying the scenarios, which would suggest that the solutions obtained depend on the particularities of each instance. However, D v clearly yields the worst results in terms of this criterion, especially for the M D data set.

We also compare in Table 7 

With the bundle formulation, we obtain optimal solutions for all instances and in all sets for the scenario considered. When using the general formulation, we do not obtain all optimal solutions for instances containing 15 requests. Moreover, the solution time substantially decreases when using the new formulation. For 23 of the 24 instance groups (sets of 10 instances of each combination of number of requests), the optimal solution is obtained in under two seconds. In contrast, the original formulation requires over one minute, on average, to obtain optimal solutions for 75% of the instance groups. In addition, 12.5% of these groups require over half an hour to obtain optimal solutions.

These results lead to the conclusion that the bundle formulation improves scalability, which allows instances with a much larger number of requests to be solved.

The results obtained with the bundle formulation permitted us to extend the experiments to large-scale data sets. Toward this end, we used the methods described in Section 5.2 to generate instances for both the SF and M D sets. The number of requests in these new instances ranges from 5 to 30 for passengers and from 5 to 25 for parcels, in increments of five. The minimum and maximum total requests for these new instances are 15 and 55, respectively.

These tests were done as described in Section 5, with a time limit of one hour. Table 8 The results show that all SF instances can be solved to optimality, and the optimal solutions for data sets of 55 requests were obtained in under 35 minutes. Set M D is more challenging to solve, even with the new formulation. We obtain optimal solutions for all instances with up to 30 requests. Beyond this size, the method does not produce proven optimal solutions but returns feasible solutions with an overall gap that ranges from 4.08% to 22.27%. The instances of this set with more than 45 requests are not solved within the time limit.

The results of Section 5.4 show that a large portion of route time is spent waiting at a passenger-or parcel-pickup location. We thus analyze further how this metric varies when solving instances with a larger number of requests. Toward that end, we use the results obtained for the SF set, which contains optimal solutions for instances with more requests than M D. Figure 12 plots the average waiting times as a function of number of requests (customers and parcels). We calculate the average of waiting times between all five instances of each group. Furthermore, we divide the graph points into three categories: n > m, n < m, and n = m. They represent the instances for which the number of requests consist mostly of customers, mostly of parcels, or are evenly distributed between the two types of requests. In addition, we monitor how the ratios of number of customer requests to number of parcels requests impacts the waiting time in the solutions. For this comparison, we incorporate the results for the original instances of 12 to 15 requests. Finally, we also report the linear regression for each set of points, where s 1 , s 2 , and s 3 are the slopes of each regression line. Generally, waiting time decreases as the number of requests increases. Moreover, this tendency is much more significant in the cases in which the number of parcels to be serviced represents the majority of requests.

A linear regression gives the trend lines for the set of points in each category. The trend lines for cases n > m and n = m produce similar slopes s 1 and s 2 , which indicates a similar rate of decrease in waiting times with respect to the growth in number of requests. The growth in instance size produces the greatest reduction in waiting times for case n < m. The slope s 3 of its trend is 50% greater than s 1 and 39.65% greater than s 2 . Since parcel requests have flexible time windows, these results suggest that servicing parcel requests occupies sections of the routes that would otherwise serve only as relocation between passenger requests and it helps to avoid early arrival at a passenger request, thereby improving the efficiency of vehicle use.

This work analyzes the potential gains of introducing parcel transport into a ride-hailing system. The analysis involves solving the share-a-ride problem (SARP) proposed by Li et al. (2014) . We propose two new MILP models called the "general formulation" and the "bundle formulation" and solve them by using a commercial solver. The general formulation uses a network of arcs connecting vehicle origin points, passenger service nodes, and parcel-pickup and -delivery locations. An entity of the second set of nodes is defined as a "collapsed node" and represents a direct trip from a passenger pick-up location to his or her drop-off location. In the bundle formulation, customers and parcel requests are systematically grouped together to generate arcs between these groups. Moreover, we discuss five distinct scenarios representing different ways to combine passenger and parcel transportation services.

Our numerical experiments involve three sets of instances with up to 15 requests to be solved. The general model optimally solves most of the instances, although it approaches or reaches the maximum allowed running time of two hours. We compare the results obtained from scenarios in which passengers and parcels are serviced either by the same vehicles, without sharing trips, or by different vehicles entirely. When using joint-transport scenarios, the results indicate gains in profit of up to 35.9% compared with the separate transportation of passengers and parcels. This comparison also reveals a decrease in empty-vehicle trip time and waiting times of up to 7.4% and 32%, respectively, when parcels and passengers share vehicles.

The bundle formulation, which was developed for scenario S c S p , improves scalability and produces optimal solutions for instances with up to 30 and 55 requests for sets M D and SF , respectively. The results obtained from solving larger-scale instances indicate that waiting time decreases as the number of requests increases. The analysis also reveals that the ratio of number of parcels to number of passengers available for service also affects the efficiency of vehicle use. Large-scale instances see a significant reduction in waiting times when there are more parcel requests than passenger requests. This result suggests that parcel servicing may be a viable option for avoiding early arrival at passenger request locations, even when allowing the transport of only a single parcel at a time.

These experiments provide sufficient information to conclude that the implementation of parcel-transport services into ride-hailing systems should not only prove profitable but also improve the efficiency of vehicle use by (i) reducing distances traveled with an empty vehicle and (ii) decreasing the time spent waiting for the start of passenger requests.

The problem tackled in this work has proven very difficult to solve to optimality. To further expand this research, we recommend the development of heuristic methods with the present results serving as a basis for evaluating performance. This would allow SARPs to be solved for even larger data sets and in shorter computational times, especially when considering higherperforming scenarios such as AM c M p . Moreover, we suggest pursuing the solution of integrated problems involving combined passenger and parcel mobility in other transport modes such as buses, rail, and multi-modal transport. Finally, the impact of autonomous vehicles, which are expected in the near future and whose maximum driving time is less problematic, could also be explored (Fatnassi et al. 2015 , Mourad et al. 2021 , Peng et al. 2021 .

Ride-hailing's climate risks: Steering a growing industry toward a clean transportation future

Intractability of the diala-ride problem and a multiobjective solution using simulated annealing

Integrating people and freight transportation using shared autonomous vehicles with compartments

Using taxis to collect citywide e-commerce reverse flows: A crowdsourcing solution

Collaborative urban transportation: Recent advances in theory and practice

Amazon's Jeff Bezos looks to the future

Shoppers have a need for speed (not just free shipping) this holiday season

The dial-a-ride problem (DARP): Variants, modeling issues and algorithms

The dial-a-ride problem: Models and algorithms

A timedependent model with speed windows for share-a-ride problems: A case study for tokyo transportation

Europe's giant 'taxi' company: Is uber part of the problem or the solution?

Planning and operating a shared goods and passengers on-demand rapid transit system for sustainable city-logistics

Ridesharing: The state-of-the-art and future directions

An efficient transformation of the generalized vehicle routing problem

The pickup and delivery problem with time windows and scheduled lines

Quantifying wider economic impacts of agglomeration for transport appraisal: Existing evidence and future directions

A survey of dial-a-ride problems: Literature review and recent developments

Supply, demand, operations, and management of crowd-shipping services: A review and empirical evidence

The share-a-ride problem: People and parcels sharing taxis

An adaptive large neighborhood search heuristic for the share-a-ride problem

The share-a-ride problem with stochastic travel times and stochastic delivery locations

Optimization of a city logistics transportation system with mixed passengers and goods

Typology and literature review for dial-a-ride problems

A survey of models and algorithms for optimizing shared mobility

Integrating autonomous delivery service into a passenger transportation system

Online bus-pooling service at the railway station for passengers and parcels sharing buses: A case in dalian

release -pitney bowes parcel shipping index reports

Studying determinants of crowdshipping use

A heuristic for the pickup and delivery traveling salesman problem

Chapter 15 -Crowdbased city logistics

Sustainable crowdshipping using public transport: A case study evaluation in rome

Uber movement

This research was partially supported by the Brazilian research agencies CNPq, grants 307843/2018307843/ and 308528/2018307843/ -2, and FAPERJ, grant E-26/202.790/2019