Public transport crowdshipping: moving shipments among parcel lockers located at public transport stations

Wyrowski, Alexander; Boysen, Nils; Briskorn, Dirk; Schwerdfeger, Stefan Article — Published Version Public transport crowdshipping: moving shipments among parcel lockers located at public transport stations OR Spectrum Provided in Cooperation with: Springer Nature Suggested Citation: Wyrowski, Alexander; Boysen, Nils; Briskorn, Dirk; Schwerdfeger, Stefan (2024) : Public transport crowdshipping: moving shipments among parcel lockers located at public transport stations, OR Spectrum, ISSN 1436-6304, Springer, Berlin, Heidelberg, Vol. 46, Iss. 3, pp. 873-907, https://doi.org/10.1007/s00291-024-00748-0 This Version is available at: https://hdl.handle.net/10419/313827 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Vol.:(0123456789) OR Spectrum (2024) 46:873–907 https://doi.org/10.1007/s00291-024-00748-0 1 3 ORIGINAL ARTICLE Public transport crowdshipping: moving shipments amongparcel lockers located atpublic transport stations AlexanderWyrowski1· NilsBoysen1 · DirkBriskorn2· StefanSchwerdfeger3 Received: 2 January 2023 / Accepted: 12 January 2024 / Published online: 25 February 2024 © The Author(s) 2024 Abstract In view of success stories of unicorn startups from the sharing and gig economy such as Airbnb, DiDi, or Uber, it is not surprising that postal service providers try to transfer the sharing idea toward their last-mile delivery services: owners of underused assets (here private crowdshippers traveling anyway) are connected with users willing to pay for the use of these assets (here postal service providers having to deliver parcels). In this paper, we consider a special form of crowdshipping where public transport users, steered by a smartphone app, pick up parcels from parcel lockers, take these shipments with them on their subway rides, and deposit these parcels into other lockers. Finally, the actual recipients can pick up their shipments from their most convenient parcel lockers, e.g., on their own way back home from work. We formulate the optimization problem that matches crowdshipping demand and supply and determines the routes along lockers and crowdshippers each parcel takes. Specifically, we allow that each parcel is moved by multiple cooperating crowdshippers and solve this problem with different objective functions capturing the individual aims of the main stakeholders: shippers, crowdshippers, recipients, and the platform provider. We evaluate the relationship of these objectives and quantify the efficiency loss of a more restricted matching policy, where only a single crowdshipper can be assigned to each parcel’s complete path between origin and destination. Finally, we also explore the impact of delays and investigate whether specific objectives protect against unforeseen events. Keywords Transportation· Urban logistics· Crowdshipping· Public transport 1 Introduction Crowdshipping, defined as the application of individuals for delivery of other peoples’ shipments on trips they would make anyway (Behrend and Meisel 2018), has received much attention in the recent years. This is mainly triggered by the following general trends: Extended author information available on the last page of the article 874 A.Wyrowski et al. 1 3 (i) Increasing parcel volumes: In Germany, for instance, a study predicts that by 2024 5.1 bn shipments will need to be processed per year compared to 2.47 bn in 2011 (Statista 2022). Managing this sharp increase with the traditional courier service infrastructure seems barely possible, especially in the aging societies of many developed countries. Therefore, many postal service providers are on the lookout for novel forms of last-mile delivery. (ii) Gig economy: Large sharing platforms like Uber, Lyft, and AirBnB enjoy increasing popularity. In Europe, the sharing economy is estimated to have generated a total sales volume of €28 bn in 2015 (Vaughan and Daverio 2016). A sharing platform connects owners of under-used assets, such as cars, spare room, or parking spaces, with users willing to pay for the use of these assets. Naturally, unused transport capacity is also a potential asset to be shared. (iii) Ecological awareness: Road transport is among the most serious emission sources. It is estimated to contribute a 20% share of all CO 2 -emissions (Schroten etal. 2012). Obviously, utilizing unused transport capacity on trips made anyway is a simple means to reduce traffic volume and thus emissions. Given these trends, crowdshipping is the attempt of retailers (e.g., Amazon Flex or Walmart), logistics companies (e.g., DHL), and specialized online platforms offering a matching of supply and demand as a service (e.g., Uber Freight or postmates. com) to transfer the basic idea of the sharing economy to transport services, especially on the last mile. In this context, this paper treats a specific form of crowdshipping, which we call public transport crowdshipping. On the demand side of public transport crowdshipping, we have shipments, e.g., parcels with goods ordered online, which have to be transported toward suitable parcel lockers. We assume that these lockers are located directly in the access paths of public transport, so that recipients can conveniently receive their shipments, e.g., on their way back home after work. Initially, the shipments to be transported are placed in other parcel lockers close to their origins. For instance, a small brick-and-mor- tar store also running an online sales channel can place an online order in a parcel locker close to the store and can announce their transport demand on the crowdshipping platform. Alternatively, the platform organizer could also offer the service to pick up larger shipment volumes, e.g., at a distribution center of a retail chain, and place the parcels into well-frequented lockers where many potential crowdshippers pass by. On the supply side, public transport users can register on the central crowdshipping platform and announce their travel behavior, e.g., their daily commute to and from work via the metro system, in a smartphone app. Once a sufficient number of potential crowdshippers is collected, the platform matches supply and demand, e.g., with the help of the solution procedures provided in this paper, and announces transport requests onto the smartphones of selected crowdshippers. Such a request advises a crowdshipper via the smartphone to pick up a shipment at a specific parcel locker and also contains the access code to open the respective locker compartment. The crowdshipper can accredit the pickup by scanning a bar code on the parcel via the smartphone app, which is also the signal that the respective locker compartment is available again. Then, the crowdshippers take the parcels with them on their public transport rides. Once arrived, they place the 875 1 3 Public transport crowdshipping: moving shipments amongparcel… parcels into other parcel lockers advised by the app and accredit the deposit by scanning the bar codes of parcels and locker compartments. These lockers can either be the parcels’ final destinations where they are picked up by the parcels’ actual recipients, or they are just intermediate lockers where the parcels wait for other crowdshippers to be moved onward. The big advantage of public transport crowdshipping is its sustainability. Compared to road transportation, trains are eco-friendly means of transportation (Schroten etal. 2012) and, since public transport users make their trips anyway, this form of parcel delivery does not produce any additional traffic. Thus, especially environmentally aware travelers get intrinsically motivated and may request no high monetary compensation for their crowdshipping services, so that public transport crowdshipping can also become a low-cost parcel delivery mode. Long-term invest is only required for the development of the smartphone app, the setup of the IT infrastructure, and the parcel lockers to be positioned in stations of public transport. On the negative side, many crowdshipping platforms struggle with providing secure, scalable, and reliable transport services (Le etal. 2019). They depend on the volatile participation of crowdshippers, which varies from day to day and is hard to forecast. Ways to take on this challenge are, for instance, discussed by Savelsbergh and Ulmer (2022). The basic idea of public transport crowdshipping is formulated in different publications, e.g., (Gatta etal. 2019a, b; Zhang etal. 2017), and companies such as Amazon (ParcelHero 2016) and HistSystem Co. (2019) have announced their intentions to establish a network of parcel lockers in public transport stations. However, the (to the best of the authors’ knowledge) only company that established parts of the public transport crowdshipping concept is the French platform Chronobee. Public transport users can register on the Chronobee platform (https:// app. chron obee. com/) with their daily commute and are matched to transport requests also announced on the platform. However, parcel pickup and delivery are not organized via parcel lockers (but via direct interaction) and there is no option for multiple crowdshippers sharing the transport of a single parcel. In this paper, we investigate the basic optimization problem of public transport crowdshipping and provide suitable solution methods to match crowdshipping supply and demand. The matching task also includes the planning of each parcel’s route through the public transportation network and its utilization of different parcel lockers as well as crowdshippers until finally reaching the destination locker in time. Specifically, we formulate six alternative objective functions that consider the aims of different stakeholders. While the crowdshipping platform aims to maximize their profit consisting of postal charges for each delivered parcel minus crowdshipping fees, crowdshippers rather focus on their own crowdshipping fees. The customers of parcel delivery services, instead, prefer reliable services and want to avoid that parcel handovers between crowdshippers are missed in case of train delays. We formulate our public transport crowdshipping problem and provide computational complexity results for all problem versions. Furthermore, we provide a heuristic decomposition approach that is easily adaptable to solve all problem versions. This allows us to investigate the relationship of the stakeholders’ objectives. Furthermore, we compare our cooperative crowdshipping policy that allows multiple subsequent 876 A.Wyrowski et al. 1 3 crowdshippers to jointly transport a parcel from origin to destination with a more restrictive policy that excludes crowdshipper cooperation. Finally, we also investigate the impact of train delays and explore which of our objectives produces robust plans where only a few parcels miss their recipients. Thus, our paper makes the following contributions to the literature: (a) We detail the operational processes and the basic matching task of a novel form of crowdshipping: public transport crowdshipping. (b) We provide suitable solution methods for the basic matching task with six different objectives to cover the aims of all main stakeholders. (c) We apply our solution methods in a comprehensive computational study in order to identify critical success factors. Here, we show that a large crowdshipper base of volunteering public transport users must be recruited, explore the different aims of the main stakeholders, investigate how to protect against stranded parcels due to unforeseen train delays, and evaluate the gains of cooperative transport where parcels take multiple legs with different crowdshippers toward their destination lockers. The remainder of the paper is structured as follows. Section2 reviews the related literature. Section3 defines our public transport crowdshipping problem with its six alternative objectives and explores computational complexity. In Sect.4, we provide the basic model formulation and report on necessary adaptions when dealing with the different objectives. Our heuristic decomposition approach is introduced in Sect.5. Insights into the computational performance and managerial issues are provided in Sect.6 and7, respectively. Finally, Sect.8 concludes the paper. 2 Literature review The sharing and gig economy in general and crowdshipping in particular have attracted a lot of research in the recent years. Thus, we refer the reader to the following in-depth survey papers: Dablanc etal. (2017) (on-demand deliveries), Le etal. (2019) as well as Savelsbergh and Ulmer (2022) (crowdshipping), Boysen et al. (2019) (matching of supply and demand in the sharing industry), and Boysen etal. (2021) (last-mile delivery). For an overview on different crowdshipping applications, our own literature review, first, elaborates on the different user groups that are targeted as potential crowdshippers: (i) Hired drivers: Some crowdshipping platforms hire independent drivers, who are hourly paid, contribute their own vehicle, and sign up in advance for prefixed time-slots. These platforms are either directly operated by large retailers like Amazon (with their Amazon Flex service) or by third-party companies offering a matching of supply and demand as a service (e.g., Uber Freight or postmates.com). Optimization approaches matching crowdshipping supply and demand as well as planning delivery routes are, for instance, provided by Archetti etal. (2016) and Arslan etal. (2018). The main disadvantage of this form of crowdshipping is that parcel delivery is not processed on trips made anyway. Instead, extra traffic is generated and, from an environmental perspective, nothing is gained compared to traditional delivery modes. 877 1 3 Public transport crowdshipping: moving shipments amongparcel… (ii) Occasional drivers: This disadvantage is avoided, if pickup and delivery requests of customers are properly integrated into existing trips, e.g., of private drivers with their own cars having some flexibility regarding the timing of their regular (independently planned) journeys (Zehtabian etal. 2022) or taxis offering additional freight services (Li etal. 2014). (iii) In-store customers: Attracting a sufficiently large external driver base can produce a lot of effort (Le etal. 2019). Hence, it can be advantageous if specific groups of people, e.g., customers of large retail outlets, can directly be offered crowdshipping participation, e.g., for the purchases of their neighbors. Applications are reported for retail chain Walmart (Dayarian and Savelsbergh 2020), and optimization approaches are, for instance, provided by Gdowska etal. (2018). (iv) Employees: Large brick-and-mortar retail outlets or distribution centers of online retailers employ hundreds of workers, who can increase their earnings by crowdshipping online orders to neighbors on their way back home from work. Test runs are reported for Walmart, and decision support matching parcels and employees is provided by Boysen etal. (2022). (v) Air passengers: To exploit price differences between different countries and save on air mail freight tariffs, crowdshipping platforms such as piggybee.com broker crowdshipping air passengers with free luggage space. (vi) Public transport users: In this paper, we consider public transport users as potential crowdshippers. The literature in this specific area of crowdshipping is summarized in more detail in the following. The main factors influencing the willingness to participate in public transport crowdshipping are investigated in (Gatta etal. 2019a, b). They report on a survey from Rome (Italy) and state that about 50% of the questioned metro users are willing to participate. A brief review on further empirical studies on crowdshipping participation is provided by Punel etal. (2019). In the following, we only focus on operations research contributions. A combination of delivery by traditional delivery vans and public transport is considered by (Ghilas etal. 2016b, a, c, 2018). Here, company-owned delivery vans cooperate with public transport operating on fixed timetables. Shipments can be handed over and, after transport, received from public transport, which acts as an additional intermediate transport option. A problem definition and a first MIP is presented by Ghilas etal. (2016b). The same problem is tackled by Ghilas etal. (2016a) and Ghilas etal. (2018) with adaptive large neighborhood search and branch-and- price, respectively. A stochastic problem version is treated by Ghilas etal. (2016c). A similar problem setting for alternative vehicles, i.e., cargo bikes and buses, is investigated by Masson etal. (2017); Azcuy etal. (2021) as well as Schmidt etal. (2022). Kou etal. (2022) investigate the peculiarities of combining delivery vans and public transport in a rural setting. In our problem setting, we have no delivery vans (or cargo bikes), and we decouple the handover process by parcel lockers. Two crowdshippers cooperating in the transport of a specific parcel need to subsequently access the locker, but not at the same time. This leads to a completely different problem structure. Crowdshipping between different parcel lockers is also considered by Chen etal. (2017) and Chen etal. (2016). They, however, consider taxis and not public 878 A.Wyrowski et al. 1 3 transport users as potential crowdshippers. This requires an additional coordination of parcel delivery with people transport and leaves more flexibility, because taxis are not bound to fixed timetables. Furthermore, crowdshipping between parcel lockers without any time constraints is considered by Wang etal. (2016) and Zhang etal. (2017). Finally, Kızıl and Yıldız (2022) consider the problem to decide the location of parcel lockers, that is to choose the stations where parcel lockers are to be installed, and evaluate solutions, including backup services with zero-emission vehicles for parcels that are not crowdshipped, using a scenario-based approach. The problem is formulated as a two-stage stochastic program and solved by a branch- and-price approach. The existing crowdshipping literature also includes transshipment nodes into operational routing and assignment problems (e.g., Macrina et al. 2020; Vincent etal. 2022). These nodes add flexibility where shipments, delivered by company owned vehicles, are finally picked up by the crowdshippers. In our problem setting, the origin position at the first parcel locker is fixed for each shipment. Instead, we allow that multiple crowdshippers can participate in delivering shipments to their destinations by handing the parcel over at intermediate lockers. This transshipment option rather relates our problem setting to multi-hop ridesharing (e.g., Masoud and Jayakrishnan 2017; Wang etal. 2023), where passengers can hitch multiple subsequent rides to finally reach their destinations. In this domain, however, vehicles (crowdshippers) typically do not operate on predefined routes without any time flexibility and have a capacity for more than one passenger (parcel). It can be concluded that the crowdshipping literature provides no suitable optimization procedures where public transport users with known travel behavior are coordinated to crowdship other peoples’ parcels between parcel lockers. Finally, there are other optimization problems from other domains that share some important structural similarities with our optimizations problem for public transport crowdshipping. However, we come back to these similarities after having defined this problem in the following section. 3 Problem definition The critical element of any crowdshipping solution is a central IT platform that matches supply and demand. This also holds true for our specific crowdshipping application, where public transport users pick up and deliver parcels among parcel lockers located in stations s∈S with given locker capacity Ls for storing shipments in locker compartments. (i) On the demand side, we have a set J of parcels. Beginning from release date rj , parcel j∈J is available at the parcel locker at origin station 𝛼j . To deliver a parcel successfully, it needs to arrive at the parcel locker at destination station 𝜔j no later than deadline dj , which is the point of time when the parcel’s actual recipient passes the lockers at station 𝜔j , e.g., on the way back home from work. If parcel j∈J is successfully delivered, the platform receives a postal charge pj . If a parcel cannot be forwarded to its destination on time, it 879 1 3 Public transport crowdshipping: moving shipments amongparcel… cannot be accepted for crowdshipping services and the platform receives no postal charge. (ii) On the supply side, we have a set I of public transport users who have registered at the crowdshipping platform and are willing to participate in parcel delivery; we call them crowdshippers. Each crowdshipper i∈I is associated with a time-stamped path defining i’s movement through the public transportation network. Specifically, the time-stamped path is given as a sequence of tuples each referring to a departure time at a specific station. We presuppose that only those station visits are added to the time-stamped path, where the respective crowdshipper has enough time to pickup and/or deposit a parcel at a parcel locker. Hence, we do not explicitly consider a specific pickup and deposit duration. Furthermore, we only consider those stations where a parcel locker is located and where a parcel is to be picked up or delivered to (or at least one other crowdshipper can access the locker). When traversing a travel leg between two subsequent stations according to a time-stamped path, a crowdshipper has a capacity to carry at most one parcel. We refer to the joint travel of a crowdshipper i and a parcel j starting with i picking j up at station s∈S , moving from s to another station s�∈S , and finally depositing j at station s′ as an entrainment. For each entrainment, an entrainment fee f is paid to the crowdshipper by the platform. For a station s and a point in time t a crowdshipper passes through s, we say that ns,t is the number of parcels stored in the lockers at s immediately after t. This number ns,t is composed of (i) parcels that originate from station s and have not been picked up yet at t, of (ii) parcels that have been intermediately deposited in s until t, but have not been picked yet, and of (iii) parcels with delivery station s that have already reached their destination until t and have not been picked up by the recipient yet since ds>t . A parcel is moved from its origin to its destination station not necessarily by a single entrainment. Instead, a solution to our crowdshipping problem is a sequence 𝜎j of entrainments assigned to each parcel j∈J . An empty sequence 𝜎j reflects that parcel j is not delivered at all. We say a solution is delivery-feasible, if for each parcel j∈J with non-empty sequence (a) the first entrainment starts at station 𝛼j and does not start before release date rj , (b) each other entrainment starts at the station where the previous entrainment ended and does so not before the end time of the previous entrainment, and (c) the last entrainment ends at station 𝜔j and does not end after deadline dj . Furthermore, we say a solution is capacity-feasible, if (i) the crowdshippers’ capacity is not exceeded. This means that for each crowdshipper i and each station s on the path there is at most one entrainment involving i that starts at s or a previous station on the path and ends at a station that is reached after s. Furthermore (ii), the parcel lockers’ capacities are not exceeded. That is for each station s and each point in time t where a crowdshipper passes through s, there are at most Ls parcels in the locker and we have ns,t≤Ls . Finally, we say a solution is feasible, if it is both delivery-feasible and capacity-feasible. Since we have different involved stakeholders, i.e., crowdshippers, 880 A.Wyrowski et al. 1 3 recipients, and the platform provider, there may be different views on what is a good solution among the feasible ones. We consider six problem versions in the following: (1) MAX-PROFIT: The problem is to find a feasible solution maximizing profit. The profit associated with a feasible solution is the total postal charge for successfully delivered parcels (i.e., those with non-empty sequences of entrainments) minus the entrainment fees for the crowdshippers (i.e., the total number of entrainments multiplied by fee f). This objective mirrors the aim of a crowdshipping platform maximizing its own profit. (2) MAX-PARCELS: The problem is to find a feasible solution with a profit of at least a given threshold P that maximizes the number of delivered parcels. This objective aims to maximize the number of satisfied customers while granting the platform a minimum profit. (3) MAX-INVOLVEMENT: The problem is to find a feasible solution with a profit of at least a given threshold P that maximizes the number of crowdshippers with at least one entrainment. This objective aims to engage a maximum number of crowdshippers, while granting the platform a minimum profit P. (4) MIN-TOTAL-ENTRAINMENTS: The problem is to find a feasible solution with a profit of at least a given threshold P that minimizes the total number of entrainments over all parcels. Since each entrainment involves a failure risk, e.g., a parcel missing its subsequent entrainment due to a delayed train, this objective reduces the risk of stranded parcels. This is something both the platform and the recipients prefer to avoid. (5) MIN-MAX-ENTRAINMENTS: The problem is to find a feasible solution with a profit of at least a given threshold P that minimizes the maximum length of entrainment sequences among all parcels. A parcel is only successfully delivered toward its destination, if all its entrainments are successfully completed. Thus, reducing the number of entrainments per parcel should promote the number of successful deliveries by protecting against uncertainty. An obvious disadvantage of this objective is that in the worst case a single shipment with a large number of inevitable entrainments removes the optimization pressure from all other shipments. It will be part of our computational study in Sect.7.3 to explore how severely this deteriorating effect impacts average results. (6) MAX-MIN-SLACK: For each successfully delivered parcel j∈J , we consider the minimum slack time at 𝜔j and at each station j where it is picked up by a crowdshipper (including 𝛼j ). The slack time of parcel j at each such station s is the time it spends there in the locker between delivery and pickup. For the sake of convenience, we say that for each other pair of parcel j and those stations where j is not handled the slack time is infinite, so that they do not influence the minimum slack time. The problem is to find a feasible solution, which maximizes the minimum slack time among all pairs of parcels and stations while granting at least a minimum profit of P to the platform. Slack time protects against delays of trans and crowdshippers, and the larger the slack, the more delay of entrainments is acceptable without leading to stranded parcels. Note that in the field of robust optimization adding slack (buffer) time is one prominent approach to achieve solution-robustness (e.g., see Briskorn etal. 2011; Kouvelis and Yu 1996). Fur- 887 1 3 Public transport crowdshipping: moving shipments amongparcel… Objective function (1) defines the aim of the platform provider, which is the maximization of the total profit consisting of the sum of postal charges for all successfully delivered parcels minus the total entrainment fees to be paid to the crowdshippers. Note that for given x-variables yi,s gets assigned the smallest feasible value in optimum solutions due to (1). Constraints (2) enforce the capacity of (at most) a single parcel per travel leg for each crowdshipper. Only a single crowdshipper can move a parcel j from a specific station s due to (3). Naturally, this can be crowdshipper i∈I , if and only if parcel j is an element of Ji,s , which contains all parcels that can be moved from station s by i. Constraints (4) guarantee that each parcel j moved to a station s will be carried further unless 𝜔j=s , that is if s is its destination. Note that i ∈I + i,s and, hence, (4) covers the case where a parcel travels through s without being put in a locker. Note, furthermore, that (4) implies that a sequence of entrainments can only end at a parcel’s destination. Note, finally, that (4) together with (3) implies that parcels cannot travel in circles and, hence, each parcel that is picked up at all gets assigned a sequence of entrainments ending at the parcel’s destination. Constraints (5), then, ensures that such a parcel is transported from its origin. Violations of lockers’ capacities are prevented by constraints (6). The left side reflects n s,t i,s , that is the number of parcels in the lockers at s immediately after crowdshipper i has left s. The first sum counts the parcels which start at s ( 𝛼j=s ) and have been put into a locker until ti,s ( ti,s≥rj ). The second sum counts the parcels which do neither start nor end at s ( 𝜔j≠s ) and have been transported to s until ti,s ( i�∈I− i,s∩I� s ). The third sum counts the parcels which end at s ( 𝜔j=s ), arrived at s until ti,s ( i�∈I− i,s∩I� s ), and have not been taken out of the locker by the recipients until ti,s ( dj≥ti,s ). Finally, the fourth sum counts the parcels that have been transported from s until immediately after ti,s . Note that a parcel which travels through s without ever being put into a locker at s never contributes to the capacity load. Constraints (7) and (8) enforce that yi,s≥1 if j is picked up by i at s and s is not i’s first station and s is i’s first station, respectively. Note that in this case we obtain yi,s=1 in optimum solutions, since yi,s will get assigned a value as small as feasibly possible due to the objective function. Finally, (9) and (10) define the variables’ domains. If neither (7) nor (8) enforce yi,s≥1 , then we obtain yi,s=0 in optimum solutions, again, due to the objective function. Note that it is not enforced that the sequence of entrainments actually starts at the parcel’s origin. We can, however, cut all entrainments leading to the parcel’s origin without decreasing the objective value or losing feasibility. We suggest to add Constraints (11) and (12) to MAX-PROFIT-MIP to restrict the solution space. (10) y i,s ≥0∀i∈I;s∈S � i (11) ∑ i ∈I� 𝛼j ∶j∈Ji,s− i,𝛼 j xi,s− i,𝛼j,j≤0∀j∈J 888 A.Wyrowski et al. 1 3 Constraints (11) cut solutions where the sequence of entrainments does not start at the parcel’s origin. Constraints (12) do not cut any solutions but make it explicit that a sequence of entrainments must end at a parcel’s destination. Preliminary computational test have shown that these extensions lead to a speed up of standard solver Gurobi, so that all computational tests reported in Sect.6 include these valid inequalities. Given our basic model MAX-PROFIT-MIP, the adaptions in order to cover our five alternative objectives are truly straightforward. While MAX-PROFIT directly aims to maximize the profit, the other problems rather have a minimum platform profit P that must be ensured by additional constraint (12) ∑ i ∈I� 𝜔 j ∶j∈Ji,𝜔j xi,𝜔j,j≤0∀j∈ J Table 2 Additional notation for other objectives Mlarge value (BigM) Pminimum platform profit Fi binary variables: 1, if crowdshipper i∈I moves any parcel j∈J ; 0, otherwise Fe continuous variable: maximum number of entrainments among all crowdshippers Fs continuous variable: minimum slack among all crowdshippers zi,j binary variables: 1, if crowdshipper i∈I moves parcel j∈J ; 0, otherwise Table 3 Extended MIP formulations for the remaining objectives Problem Objective and new constraints in addition to (2)-(13) MAX-PARCELS Maximize ∑ j∈J ∑ i∈I1 j xi,𝛼j, j MAX-INVOLVE- MENT Maximize ∑i∈I F i ∑ s∈S� i∑ j∈J i , s xi,s,j≥F i ∀i∈I Fi∈[0, 1] ∀i∈I MIN-TOTAL- ENTRAINMENTS Minimize ∑ i ∈ I ∑ s ∈ S� i yi, s MIN-MAX- ENTRAINMENTS Minimize Fe ∑s∈S z s,j ≤F e ∀j∈J x i,s,j −x i,s − i,s ,j ≤z s, j ∀ i∈I,s∈S � i zs , j≥0 ∀j∈J;s∈S MAX-MIN-SLACK Maximize Fs (2−x i,s,j −x i�,s+ i,s ,j ) ⋅ M+(t i�,s+ i,s −t i,s+ i,s )≥Fs ∀i≠i�∈I;s∈S� i ; s + i,s ∈S� i� ;j∈J i,s ∩J i�,s+ i , s (1−x i,𝛼 j ,j ) ⋅ M+(t i,𝛼 j−r j )≥Fs ∀i∈I;s∈S� i;j∈Ji , s;s= 𝛼 j (1−x i,s,j ) ⋅ M+(d j −t i,𝜔 j)≥Fs ∀i∈I;s∈S� i;j∈J i,s , s + i,s= 𝜔 j 889 1 3 Public transport crowdshipping: moving shipments amongparcel… Given constraints (2)-(13) and the notation reported in Table2, the modified objective functions and the necessary additional constraints for our five alternative objectives are summarized in Table3. Due to the complexity status of our problem versions, we cannot expect that our MIPs are solvable for an off-the-shelf solver if the numbers of parcels and crowdshippers reach dimensions relevant to real-world crowdshipping platforms. Therefore, the following section provides an additional heuristic solution procedure. 5 A heuristic decomposition framework forall objectives A suitable solution procedure should cover all of our six problem versions with only minor adaptions, and it should deliver close to optimal solutions in acceptable time even for considerable numbers of parcels and crowdshippers. Our suggestion to meet these requirements is a heuristic decomposition framework that consists of two stages. On the first stage, which we describe in more detail in Sect.5.1, we introduce a modification of Dijkstra’s algorithm to generate a pool of single-parcel tours through a given public transportation network. On the second stage (see Sect.5.2), we apply a standard solver to select parcel tours from the pool by solving a MIP similar to the well-known set packing problem. 5.1 Generating apool ofsingle‑parcel tours In the first stage, we generate a pool of single parcel tours for all parcels. If each parcel tour was optimized individually, then most of them would utilize the central resources where most traffic passes. Therefore, we apply a special mechanism where also tours via less central resources are generated to ensure diversity within the pool. Specifically, we consider a sequence 𝜋 of all parcels in J and generate a tour for parcels one by one in the order indicated by 𝜋 . When generating a tour for the k-th parcel in 𝜋 , we account for capacities of crowdshippers occupied by tours for the first k−1 parcels. Virtually, whenever a part of a crowdshipper’s path is occupied by the k-th parcel, we consider each remaining part of this path as a distinct crowdshipper (who is available throughout this path) for the (k+1) -th parcel. For a specific parcel j∈J , we then generate a path from 𝛼j to 𝜔j respecting release date rj , deadline dj , and the crowdshippers’ time-stamped paths as follows. The scheme loosely follows Dijkstra’s algorithm and the A ∗ -algorithm (Ikeda etal. 1994) with stations corresponding to nodes in a graph and paths of crowdshippers corresponding to paths in that graph. Rather than restricting ourselves to a purely time-driven evaluation of paths for j, we consider 𝜙s=w𝜇 ⋅ 𝜇s+wd ⋅ qs+wt ⋅ ts for each station s∈S , where 𝜇s is the number of entrainments on the path of j from 𝛼j to s, qs represents the Manhattan distance between stations s and 𝜔j , ts is time parcel j reaches s on the path, and w𝜇 , wd , and wt are weights. (13) ∑ j∈J ∑ i∈I1 j pj⋅xi,𝛼j,j− ∑ i∈I ∑ s∈S� i f⋅yi,s≥P . 890 A.Wyrowski et al. 1 3 We designed 𝜙s to reflect various aspects relevant for the different objectives. Furthermore, we maintain for each station s∈S the crowdshipper is , which brought j to s. Initially, we set 𝜙 𝛼 j =w 𝜇⋅ 0+w d⋅ q 𝛼 j +w t⋅ rj and 𝜙s=∞ for each s≠𝛼j and initialize is=⋅ for each s∈S with a dummy. In each iteration, the procedure then determines a station s∗ to which the best path is then fixated. Furthermore, we update the best found paths to stations which can be reached be traveling one station with a crowdshipper from s∗ , given that s∗ is reached at time ts∗ . In the course of the procedure, S represents the set of stations with fixated paths toward them. Initially, we have S=� . In each iteration, s∗ is determined as s ∗=arg min { 𝜙s∣s∈S⧵S } . If s∗=𝜔j and ts ∗ ≤dj , we have found the (feasible) path from 𝛼j to 𝜔j . If s∗=𝜔j and ts ∗ >dj , the procedure failed to find a feasible path. Finally, if s∗≠𝜔j , we determine the set Is∗ of crowdshippers starting from s∗ not before ts∗ . For each i∈Is∗ and the corresponding station s+ i,s∗ to which i travels from s∗ , we determine the implied value 𝜙 s+ i,s ∗, i of 𝜙 s+ i,s∗ as In both cases, q s+ i,s∗ reflects the distance between the next station s+ i,s∗ and 𝜔j , and t i,s+ i,s∗ represents the time parcel j would reach the next station s+ i,s∗ if it is carried from s∗ by crowdshipper i. In the upper case, this crowdshipper i is the same as the one that brought j to s∗ (that is, j travels through s∗ with i) and, hence, 𝜇 s + i,s ∗ =𝜇 s ∗ . In the lower case, crowdshipper i picks up j at s∗ and, hence, 𝜇 s+ i,s ∗ =𝜇 s∗ +1 . Note that the same station s might be the next station for multiple crowdshippers in Is∗ and the implied values might differ among them. We update all path information for station s+ i,s∗ for each i∈Is∗ , if that is if the best implied path by any crowdshipper traveling from s∗ to s+ i,s∗ yields a lower value of s+ i,s∗ . To generate a pool with multiple tour candidates for each parcel, we repeatedly draw a random sequence 𝜋 and employ the procedure detailed above for four different weight sets (w𝜇,wd,wt)=(1∕3, 1∕3, 1∕3),(1∕3, 2∕3, 0),(0, 1∕2, 1∕2),(0, 2∕3, 1∕3) . These weight sets haven proven most effective in preliminary tests, which (for a matter of conciseness are not reported in this paper). A tour is admitted to the pool, if it generates a profit, that is if the postal charge exceeds the total entrainment fees. The pool is complete once we gathered 10 tours per parcel on average. The latter choice, too, has proven as a reasonable compromise between runtime and solution quality in preliminary tests not reported in this paper. 𝜙 s+ i,s∗,i= { w𝜇⋅𝜇s∗+wd⋅qs+ i,s∗+wt⋅ti,s+ i,s∗i=is∗ w𝜇⋅(𝜇s∗+1)+wd⋅qs+ i,s∗+wt⋅ti,s+ i,s∗i≠is∗ . 𝜙 s+ i,s ∗>min { 𝜙s+ i � ,s ∗,i�∣i�∈Is∗,s+ i,s∗=s+ i�,s∗ }, 891 1 3 Public transport crowdshipping: moving shipments amongparcel… 5.2 Combining single‑parcel tours After generating a set Tj of single-parcel tours for each parcel j∈J as detailed in Sect.5.1, we use an off-the-shelf solver and a MIP model formulation in order to combine single-parcel tours to a feasible solution. We present the MIP model formulation in the following, while using the additional notation summarized in Table4. Again, we describe our basic MIP for objective MAX-PROFIT first and report on necessary adaptions for our alternative objectives afterward. Our MAX-PROFIT-SELECT model uses binary variable 𝜖𝜓 for each 𝜓∈Tj , j∈J , which takes value 1 if tour 𝜓 is selected and value 0 otherwise. At most one tour can be selected per parcel j∈J , see (15), that is each parcel is delivered at most once. Two tours concerning different parcels cannot be selected simultaneously, if they occupy the same crowdshipper on the same travel leg, see (16). Similarly, at each relevant point of time no more than Ls parcels can be stored in a locker at station s, (14) MAX-PROFIT-SELECT: Maximize F(𝜖)= ∑ j∈J ∑ 𝜓∈T j c𝜓 ⋅𝜖𝜓 (15) s.t. ∑ 𝜓∈T j 𝜖𝜓≤1∀j∈ J (16) ∑ j ∈J ∑ 𝜓∈T j Ξi,s,𝜓 ⋅𝜖𝜓≤1∀i∈I;s∈S � i (17) ∑ j∈J ∑ 𝜓∈T j Δi,s,𝜓 ⋅𝜖𝜓≤Ls∀i∈I;s∈S � i (18) 𝜖 𝜓 ∈{ 0, 1 }∀ 𝜓 ∈ T j ,j ∈T Table 4 Additional notation for stage 2 Tj set of single-parcel tours for each parcel j ∈ J c𝜓 profit of tour 𝜓∈Tj , j∈J Ξi,s,𝜓 binary parameters: 1, if crowdshipper i∈I moves parcel j∈J from station s ∈S � i toward s+ i,s according to tour 𝜓∈Tj ; 0, otherwise Δi,s,𝜓 binary parameters: 1, if parcel j∈J is stored in a locker at s∈S when i∈I leaves s according to tour 𝜓∈Tj ; 0, otherwise Γ𝜓 minimum slack in tour 𝜓∈Tj , j∈J Y𝜓 number of entrainments in tour 𝜓∈Tj , j∈J 𝜖𝜓 binary variables: 1, if tour 𝜓∈Tj , j∈J , is selected; 0, otherwise 892 A.Wyrowski et al. 1 3 see (17). Finally, objective function (14) represents the goal to maximize the total profit achieved. To represent our five alternative objectives, additionally a minimum total profit P is ensured by constraint Given constraints (15) to (19) and the notation listed in Table4, our modified objective functions as well as the additional constraints are specified in Table5. Our MIP formulations extend the famous set packing problem (see Garey and Johnson 1979). Today’s default solvers are generally known to be quite capable in solving this kind of model. The computational performance analysis reported on in the following section explores whether this claim can be confirmed in our case. 6 Performance ofalgorithms In this section, we test the performance of our solution approaches. Since no established testbed is available for our public transport crowdshipping problem, we first elaborate how our instances have been generated in Sect.6.1. Afterward, in Sect.6.2, we benchmark the performance of our heuristic decomposition procedure with a standard solver solving our MIP models. All computations have been executed on a 64-bit PC with an 7-3770 3.40 GHz CPU and 16.0 GB of RAM. All solution methods have been implemented using VisualBasic (Visual Studio 2019), and off-the-shelf solver Gurobi (version 9.1.2) has been applied for solving the MIP models with a general time limit of 300s, if not explicitly stated otherwise. (19) ∑ j∈J ∑ 𝜓∈T j c𝜓 ⋅𝜖𝜓≥P . Table 5 Extended set packing formulations for the different objectives Problem Objective and new constraints in addition to (15)-(19) MAX-PARCELS Maximize ∑ j∈J ∑ 𝜓∈T j 𝜖 𝜓 MAX-INVOLVEMENT Maximize ∑i∈IFi ∑ j∈J ∑ 𝜓∈T j∑ s∈S� i Ξ i,s,𝜓 ⋅𝜖𝜓≥F i ∀i∈I Fi∈[0, 1] ∀i∈I MIN-TOTAL-ENTRAINMENTS Minimize ∑ j∈J ∑ 𝜓∈T j( pj − c𝜓 )∕ f⋅𝜖 𝜓 MIN-MAX-ENTRAINMENTS Minimize Fe (pj−c𝜓)∕f ⋅𝜖 𝜓≤Fe ∀ 𝜓 ∈Tj,j∈J MAX-MIN-SLACK Maximize Fs Γ𝜓 ⋅𝜖 𝜓+(1− 𝜖 𝜓) ⋅ M≥Fs ∀ 𝜓 ∈Tj ,j ∈J 893 1 3 Public transport crowdshipping: moving shipments amongparcel… 6.1 Data generator This section reports on our data generator, which is based on the public transport system of Hamburg (Germany). Our data generator receives the number of parcels |J| and the number of crowdshippers |I| as its own input data. Given this input, each single instance is obtained as follows. • Public transport network: Given the railway system of Hamburg, we utilize subway lines U1, U2, U3, and U4 as well as urban railway lines S1, S21, S3, and S31 (see Fig.2). Each line l∈L is defined by a sequence of stations Sl⊆S , so that our test bed consists of |S|=147 stations in total. These stations of set S are partitioned into two subsets S=SC∪SS . Stations of sets SC and SS represent inner city and suburban stations and they are marked in gray and pink, respectively. For each line l∈L , we use frequency fl given by the original schedule of the HVV during the working hours (i.e., fU1=fU2=fU3=5 ), and fl=10 for the rest of the time. The travel times between any two consecutive stations of a line are drawn from U{1, 2, 3} , which is in line with the vast majority of realworld stations. Finally, our planning horizon is set to 10 hours, i.e., T=600 minutes. • Lockers: For each station s∈S , we draw a locker capacity Ls proportional to the crowdshipper traffic. Parameter Ls is initially determined by normalized ratio vnorm s , defined as the ’number of lines’ divided by the ’sum of corresponding frequencies’. Subsequently, Ls is finally established through L s= 1 8| J | + 1 4| J | ⋅vnorm s. Fig. 2 Public transport system of Hamburg [Source: HVV] 894 A.Wyrowski et al. 1 3 This ensures that the minimum capacity is 1 8| J | , while the maximum capacity is 3 8| J | . • Parcels: For each parcel j∈J , we draw a release date rj∼U{1, …,|T|∕10} and a deadline dj∼U{9 ⋅ |T|∕10, …,|T|} . We assume that with a probability of 50% a parcel has to be transported from a city center to a suburban station, where origin and destination stations are randomly chosen from sets SC and SS , respectively, and with 50% vice versa. For each successfully delivered parcel, the platform receives a constant postal charge of pj=p=5 . • Crowdshippers: We assume that 40% of the crowdshippers move during the morning hours, i.e., we determine their departure time ti by drawing from a uniform distribution: ti∼U{1, …,3 ⋅ |T|∕10} . Another 40% of crowdshippers move during the late hours ( ti∼U{6 ⋅ |T|∕10 +1, …,9 ⋅ |T|∕10} ), and the remaining 20% of crowdshippers move during main working hours ( ti∼U{3 ⋅ |T|∕10 +1, …,6 ⋅ |T|∕10} ). Crowdshippers of the morning hours needs to travel from a suburban area to a city center station (with a probability of 60%), while 30% move in the opposite direction, and 10% travel entirely within the city center. The origin and destination stations are randomly selected from sets SC and SS . During the late hours, the selection of origin and destination station is reversed, so that 60% move from the city center to the suburban area, while 30% move in the opposite direction, and again 10% stay in the city center. For crowdshippers that travel during the main working hours, we assume that they travel with equal probability from a suburban area to the city center, the other way round, or within the city center. Given the origin station, departure time, and destination of crowdshipper i∈I , we determine the shortest path by the standard Dijkstra algorithm through our network in order to determine their time-stamped paths ti,s . The fixed entrainment fee is f=1 . Finally, we set the repetition counter to ten for each data setting defined by the number of parcels |J| and the number of crowdshippers |I|. Hence, ten instances, each derived as defined above, are returned by our data generator. 6.2 Computational results Our performance tests benchmark our heuristic decomposition procedure (see Sect.5) with off-the-shelf solver Gurobi when fed with the MIPs of Sect.4. Our complete tests have shown that there are no significant performance differences of both competitors for the different objectives. To not overload this paper, we therefore decided to only report the performance results of objective MAX-PROFIT. When comparing the performance of these solution approaches in Table6, we report on the average optimality gap in percent determined by Gurobi (column ’gap’), the average gap in percent to the best solution found among both competitors (column ’gap b ’), the number of instances where the approach found the best solution among 895 1 3 Public transport crowdshipping: moving shipments amongparcel… both competitors (column ’best’), the number of solutions proven to be optimal (column ’opt’), the number of instances where at least one feasible solution with an objective value ≥0 was obtained (column ’feas’), and the average CPU-seconds (column ’sec’). Note that time limit of the default solver was set to 15min and the CPU-seconds of the heuristic include the preprocessing time of pool generation. In our study, we vary the number of parcels |J| and the number of crowdshippers |I|. For each combination of these parameters, ten instances as described in Sect.6.1 have been obtained, so that in total 270 instances constitute this testbed. The results summarized in Table6 suggest the following findings: Table 6 Performance test of Gurobi and the heuristic decomposition procedure for objective MAXPROFIT Gurobi Decomposition heuristic |J| |I|gap gap b best opt feas sec gap b best opt feas sec 20 20 0.00 0.00 10 10 10 0.72 2.33 8 8 10 3.56 20 40 0.00 0.00 10 10 10 1.51 14.19 2 2 10 2.42 20 60 0.00 0.00 10 10 10 3.52 7.03 1 1 10 1.85 30 30 0.00 0.00 10 10 10 1.58 7.90 3 3 10 3.85 30 60 0.00 0.00 10 10 10 5.82 5.82 4 3 10 3.31 30 90 0.00 0.00 10 10 10 26.82 3.55 2 1 10 3.49 40 40 0.00 0.00 10 10 10 3.40 2.40 5 5 10 5.50 40 80 0.29 0.00 10 9 10 115.57 7.54 1 0 10 4.92 40 120 1.61 0.10 9 7 10 377.50 5.42 3 1 10 5.61 50 50 0.00 0.00 10 10 10 14.12 6.96 2 2 10 7.80 50 100 2.52 2.55 6 6 10 457.02 4.65 4 0 10 7.68 50 150 7.60 0.85 8 0 10 920.24 4.60 3 0 10 9.00 60 60 0.00 0.00 10 10 10 18.64 5.21 1 1 10 9.25 60 120 4.52 0.00 10 0 10 918.19 8.00 0 0 10 11.12 60 180 17.71 5.13 4 0 10 935.84 1.91 7 0 10 13.98 70 70 0.38 0.00 10 8 10 315.41 7.31 1 1 10 11.69 70 140 8.43 0.00 10 0 10 925.98 6.36 0 0 10 16.25 70 210 31.33 12.20 1 0 10 952.31 0.29 9 0 10 20.48 80 80 0.41 0.00 10 7 10 387.24 6.50 0 0 10 16.20 80 160 21.74 2.65 4 0 10 935.14 1.27 7 0 10 22.00 80 240 91.68 69.93 0 0 10 977.49 0.00 10 0 10 27.83 90 90 1.62 0.00 10 5 10 672.58 6.47 0 0 10 19.79 90 180 49.20 18.87 2 0 10 952.45 0.00 10 0 10 29.19 90 270 55.77 27.59 0 0 9 1015.92 0.00 10 0 10 41.56 100 100 4.40 0.00 10 0 10 921.50 4.55 0 0 10 25.54 100 200 55.38 24.13 0 0 9 968.71 0.00 10 0 10 37.91 100 300 79404.22 3027.54 0 0 8 1743.52 0.00 10 0 10 54.09 896 A.Wyrowski et al. 1 3 • Gurobi: Default solver Gurobi performs very well when handling smaller instance sizes of |J|≤30 parcels. Here, it is able to verify all optimal solutions within short computational times. However, Gurobi struggles with larger instance sizes of |J|≥70 parcels, especially with a large crowdshipper base. Here, gaps as well as runtimes increase and less best solutions are obtained. For larger instances with fewer crowdshippers, however, Gurobi still outperforms our heuristic. Unfortunately, our computational evaluation in Sect.7.1 will show that a large crowdshipper base is required to move a substantial number of parcels. In these cases, our heuristic seems the better option. Note that these results did not improve significantly in further tests, where we allowed the default solver longer running times up to one hour. • Decomposition heuristic: Our heuristic, instead, produces a good compromise between solution quality and time, especially for large instances with many parcels and crowdshippers. It determines feasible solutions for all instances and requires less than one minute even for the largest instance sizes. The (optimality) gaps are reasonably small. We conclude that both solution approaches seem an appropriate choice for our crowdshipping problem. Especially, for large instances with many shipments and potential crowdshippers, our heuristic seems the better choice, especially when fast decisions are required. 7 Managerial issues This section is dedicated to managerial issues. We want to identify critical factors for the successful diffusion of public transport crowdshipping. Specifically, we explore how many volunteering crowdshippers must be recruited in order to successfully deliver a given amount of parcels in Sect.7.1, we provide a relationship analysis between the different objectives in Sect.7.2, and we address robustness issues to avoid stranded parcels in case of unforeseen train delays in Sect.7.3. Finally in Sect.7.4, we compare a splitting of a shipment’s travel from origin to destination among multiple crowdshippers with direct single-crowdshipper transports. The latter promise a better protection against unforeseen train delays but offer less planning flexibility. If not explicitly stated otherwise, we generate our instances as described in Sect.6.1 for a varying number of parcels |J| and available crowdshippers |I|. To not spoil our investigations by heuristic gaps, we decided to apply Gurobi (with a time limit of one hour) on smaller instances with up to |J|≤60 parcels only. 7.1 How many crowdshippers need tobe recruited? Among the outstanding challenges to successfully establish crowdshipping as a reliable every-day delivery option is certainly the volatile participation of volunteering 903 1 3 Public transport crowdshipping: moving shipments amongparcel… However, there may be even better objectives and the best choice among them is certainly only one lever. Future research should thus evaluate the impact of other objectives and further countermeasures, such as a dynamic replanning once delays have occurred with altered entrainment missions for crowdshippers already underway. The right compensation scheme, which properly trades off the impact of stranded parcels on customer satisfaction with losses of platform profit, is certainly an important choice. 7.4 Comparison withthesingle‑crowdshipper‑per‑parcel policy French public transport crowdshipping platform Chronobee (see Sect.1) applies the single-crowdshipper-per-parcel (SCPP) policy. This means that an accepted parcel is brought from origin to destination exclusively by a single crowdshipper. On the positive side, SCPP offers more protection against unforeseen delays. Train delays can still lead to parcels missing the deadlines at their destinations, but at least the handover risk of crowdshippers missing each other is eliminated. Our research provides optimization approaches under the multi-crowdshipper- per-parcel (MCPP) policy, where asynchronous parcel handovers via lockers between multiple crowdshippers are allowed. The asset of the MCPP policy is certainly the larger flexibility to move parcels with multiple crowdshippers. This promises higher delivery rates but increases the risk of stranded parcels. This section benchmarks both policies regarding their profits with and without train delays. Specifically, our experiment is set up as follows. Using our instance generator of Sect.6.1, we generate 10 instances with |J|=30 registered parcels and |I|=2|J| volunteering crowdshippers. To obtain the profits of both policies in a deterministic world where no unforeseen delays occur, these instances are solved with two approaches. For MCPP, we apply the approach that proved best in the previous section. This means, we utilize the MIN-MAX-ENTRAINMENTS objective with a minimum platform profit equal to the maximum profit obtained by MAX-PROFIT to solve the instances and record the resulting profit. Another advantage of the SCPP policy is a much easier matching task, which constitutes a linear assignment problem that can efficiently be solved, e.g., by the famous Hungarian method (Kuhn 1955). Here, we assign crowdshippers to parcels, where the assignment profit is either the parcel charge minus a single entrainment fee if 20 30 40 50 60 70 (a) Pre-delay profit of SCPP in %of MCPP 20 30 40 50 60 70 80 (b)Post-delay profit of SCPP in %of MCPP Fig. 5 Benchmark of MCPP and SCPP before (left) and after (right) delays: Profit of SCPP in % of MCPP’s profit (obtained by the MIN-MAX-ENTRAINMENTS objective with a minimum platform profit equal to the maximum profit obtained by MAX-PROFIT) in % 904 A.Wyrowski et al. 1 3 the crowdshipper timely travels along the parcel’s origin and destination or zero if no feasible transport by a specific crowdshipper is possible. Solving the maxprofit linear assignment problem delivers the optimal profit of the SCPP policy. To also compare both policies if unforeseen train delays occur and stranded parcels may reduce the profit, we apply the high-risk-small-delay setting (i.e., with a delay risk of Pd=15 % and d=3 minute delays) and determine the actual profit of both solutions if the respective delays occur. In Fig.5, we depict the pre-delay (i.e., deterministic world without delays) and the post-delay (i.e., actual profit including compensation for stranded parcels in case of delays) profits. The box plots show the distribution of the profit of SCPP divided by the profit of MCPP in % over the solved instances. Hence, a value below (above) 100% indicates that SCPP realizes a lower (higher) profit than MCPP. The results of Fig.5 indicate that MCPP clearly outperforms SCPP. The loss in flexibility if only a single crowdshipper may transport each parcel reduces the median profit of SCPP to only 40% of MCPP’s profit in a deterministic world. As expected, this disadvantage reduces if unforeseen delay occur, but the median profit of SCPP still merely reaches 47% of MCPP’s profit. However, there are three instances with high risk and long delays where the higher robustness of SCPP leads to even better results than MCPP. On average, however, our experiment shows a clear advantage of MCPP, which leads us to our final managerial take-home message. Actionable insights: The current business practice to only apply the SCPP policy should be reconsidered. Our computational results show that the increase of flexibility enabled by the parcel handover among multiple crowdshippers clearly overcompensates the higher risk of stranded parcels in case of unforeseen delays. 8 Conclusions This paper investigates public transport crowdshipping and provides matching methods to select shipments and their ways through a public transportation network when accompanying crowdshippers on their commute. Based on a computational study applying these methods, we identify the following critical success factors for this innovative last-mile delivery concept: (a) A large crowdshipper base of volunteering public transport users must be recruited that is significantly larger than the number of parcels to be transported. However, even if such a base can successfully be gathered, a platform cannot expect that all parcels can be transported. Thus, a reliable and flexible fall-back option mustbe at hand. (b) Unfortunately, there is no single objective that can satisfy all involved stakeholders equally. When only focusing on the platform profit, this tends to also maximize the number of successfully crowdshipped parcels (and thus the positive environmental impact) but reduces the number of involved crowdshippers. This can get in the way of our previous success factor. 905 1 3 Public transport crowdshipping: moving shipments amongparcel… (c) To account for unforeseen train delays and to protect against stranded parcels, we identify the MIN-MAX-INVOLVEMENT objective, which restricts the maximum number of handovers among crowdshippers per parcel, as best suited. (d) Finally, we show that allowing parcels to take multiple travel legs with more than a single crowdshipper greatly increased planning flexibility and promises much more transported parcels as well as higher platform profits than the singlecrowdshipper-per-parcel policy of current business practice. Future research could take up our research in multiple ways: Other optimization objectives and more complex methods including multiple objectives and explicitly involving stochastic delay information should be developed. In this way, matchings that better serve all involved stakeholders, even if unforeseen delays occur, could be obtained. Furthermore, our solution methods should be challenged, such that they are suitable for large real-world crowdshipping platforms with thousands of shipments and even more crowdshippers. Acknowledgements This research has been supported by the German Science Foundation (DFG) by the grant “Coordination of demand and supply in the Sharing Economy” (BO 3148/8-1 and BR 3873/10-1). Funding Open Access funding enabled and organized by Projekt DEAL. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http:// creativecommons.org/licenses/by/4.0/. References Archetti C, Savelsbergh M, Speranza MG (2016) The vehicle routing problem with occasional drivers. Eur J Oper Res 254:472–480 Arslan AM, Agatz N, Kroon L, Zuidwijk R (2018) Crowdsourced delivery-a dynamic pickup and delivery problem with ad hoc drivers. Transp Sci 53:222–235 Azcuy I, Agatz N, Giesen R (2021) Designing integrated urban delivery systems using public transport. Trans Res Part E: Logist Trans Rev 156:102525 Behrend M, Meisel F (2018) The integration of item-sharing and crowdshipping: Can collaborative consumption be pushed by delivering through the crowd? Trans Res Part B: Methodol 111:227–243 Boysen N, Briskorn D, Schwerdfeger S (2019) Matching supply and demand in a sharing economy: Classification, computational complexity, and application. Eur J Oper Res 278:578–595 Boysen N, Emde S, Schwerdfeger S (2022) Crowdshipping by employees of distribution centers: Optimization approaches for matching supply and demand. Eur J Oper Res 296:539–556 Boysen N, Fedtke S, Schwerdfeger S (2021) Last-mile delivery concepts: a survey from an operational research perspective. OR Spectrum 43:1–58 Briskorn D, Leung J, Pinedo M (2011) Robust scheduling on a single machine using time buffers. IIE Trans 43:383–398 Chen C, Pan S, Wang Z, Zhong RY (2017) Using taxis to collect citywide e-commerce reverse flows: a crowdsourcing solution. Int J Prod Res 55:1833–1844 906 A.Wyrowski et al. 1 3 Chen C, Zhang D, Ma X, Guo B, Wang L, Wang Y, Sha E (2016) Crowddeliver: planning city-wide package delivery paths leveraging the crowd of taxis. IEEE Trans Intell Transp Syst 18:1478–1496 Dablanc L, Morganti E, Arvidsson N, Woxenius J, Browne M, Saidi N (2017) The rise of on-demand ‘instant deliveries’ in European cities. Supply Chain Forum: An Int J 18:203–217 Dayarian I, Savelsbergh M (2020) Crowdshipping and same-day delivery: Employing in-store customers to deliver online orders. Prod Oper Manag 29:2153–2174 Even S, Itai A, Shamir A (1976) On the complexity of timetable and multicommodity flow problems. SIAM J Comput 5:691–703 Garey MR, Johnson DS (1979) Computers and intractability. Freeman, San Francisco Gatta V, Marcucci E, Nigro M, Patella SM, Serafini S (2019) Public transport-based crowdshipping for sustainable city logistics: Assessing economic and environmental impacts. Sustainability 11:145 Gatta V, Marcucci E, Nigro M, Serafini S (2019) Sustainable urban freight transport adopting public transport-based crowdshipping for B2C deliveries. Eur Transp Res Rev 11:13 Gdowska K, Viana A, Pedroso JP (2018) Stochastic last-mile delivery with crowdshipping. Trans Res Procedia 30:90–100 Ghilas V, Cordeau JF, Demir E, Van Woensel T (2018) Branch-and-price for the pickup and delivery problem with time windows and scheduled lines. Transp Sci 52:1191–1210 Ghilas V, Demir E, Van Woensel T (2016) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows and scheduled lines. Comput Ope Res 72:12–30 Ghilas V, Demir E, VanWoensel T (2016b) The pickup and delivery problem with time windows and scheduled lines. INFOR: Information Systems and Operational Research 54, 147–167 Ghilas V, Demir E, Van Woensel T (2016) A scenario-based planning for the pickup and delivery problem with time windows, scheduled lines and stochastic demands. Trans Res Part B: Methodol 91:34–51 HistSystem Co. (2019) On Korean Bizwire website: Seoul metro to begin parcel delivery service. http:// korea bizwi re. com/ seoulmetro- tobegin- parceldeliv eryservi ce/ 148909 (last access: November 2023) Ikeda T, Hsu MY, Imai H, Nishimura S, Shimoura H, Hashimoto T, Tenmoku K, Mitoh K (1994) A fast algorithm for finding better routes by AI search techniques, in: Proceedings of Vehicle Navigation and Information Systems Conference, pp. 291–296 Kızıl KU, Yıldız B (2022) Public transport-based crowd-shipping with backup transfers. Transp Sci 57:174–196 Kou X, Zhang Y, Long D, Liu X, Qie L (2022) An investigation of multimodal transport for last mile delivery in rural areas. Sustainability 14:1291 Kouvelis P, Yu G (1996) Robust Discrete Optimization and Its Applications. Nonconvex Optimization and Its Applications, Springer, US Kuhn HW (1955) The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2:83–97 Le TV, Stathopoulos A, Van Woensel T, Ukkusuri SV (2019) Supply, demand, operations, and management of crowd-shipping services: A review and empirical evidence. Trans Res Part C: Emerg Technol 103:83–103 Li B, Krushinsky D, Reijers HA, Van Woensel T (2014) The share-a-ride problem: People and parcels sharing taxis. Eur J Oper Res 238:31–40 Macrina G, Pugliese LDP, Guerriero F, Laporte G (2020) Crowd-shipping with time windows and transshipment nodes. Comput Ope Res 113:104806 Masoud N, Jayakrishnan R (2017) A decomposition algorithm to solve the multi-hop peer-to-peer ridematching problem. Trans Res Part B: Methodol 99:1–29 Masson R, Trentini A, Lehuédé F, Malhéné N, Péton O, Tlahig H (2017) Optimization of a city logistics transportation system with mixed passengers and goods. EURO J Trans Logist 6:81–109 ParcelHero (2016) Amazon’s Prime Ambition. https:// www. parce lhero. com/ conte nt/ downl oads/ pdfs/ amazon/ amazo nsprime- ambit ionparce lheroindus tryreport. pdf (last access: November 2023) Punel A, Ermagun A, Stathopoulos A (2019) Push and pull factors in adopting a crowdsourced delivery system. Transp Res Rec 2673:529–540 Roth AE, Sönmez T, Ünver MU (2004) Kidney exchange. Q J Econ 119:457–488 Savelsbergh MW, Ulmer MW (2022) Challenges and opportunities in crowdsourced delivery planning and operations. 4OR 20, 1–21 Schmidt J, Tilk C, Irnich S (2022) Using public transport in a 2-echelon last-mile delivery network. European Journal of Operational Research , to appear 907 1 3 Public transport crowdshipping: moving shipments amongparcel… Schroten A, Warringa G, Bles M (2012) Marginal abatement cost curves for heavy duty vehicles. Background Report, CE Delft, Delft Slivkins A (2010) Parameterized tractability of edge-disjoint paths on directed acyclic graphs. SIAM J Discret Math 24:146–157 Statista (2022) Paketsendungen erreichen neuen Rekordwert. https:// de. stati sta. com/ infog rafik/ 9992/ indeuts chlandvon- denpaket- undkurie rdien stenbefoe rdert ensendu ngen/ (Accessed: November 2023) Vaughan R, Daverio R (2016) Assessing the size of the collaborative economy in Europe. https:// publi catio ns. europa. eu/ en/ publi cationdetai l/-/ publi cation/ 2acb7 619- b544- 11e7- 837e- 01aa7 5ed71 a1 (Accessed: November 2023) Vincent FY, Jodiawan P, Redi AP (2022) Crowd-shipping problem with time windows, transshipment nodes, and delivery options. Trans Res Part E: Logist Trans Rev 157:102545 Wang D, Wang Q, Yin Y, Cheng T (2023) Optimization of ride-sharing with passenger transfer via deep reinforcement learning. Trans Res Part E: Logist Trans Rev 172:103080 Wang Y, Zhang D, Liu Q, Shen F, Lee LH (2016) Towards enhancing the last-mile delivery: An effective crowd-tasking model with scalable solutions. Trans Res Part E: Logist Trans Rev 93:279–293 Zehtabian S, Larsen C, Wøhlk S (2022) Estimation of the arrival time of deliveries by occasional drivers in a crowd-shipping setting. Eur J Oper Res 303:616–632 Zhang C, Du Z, Parmar MD, Bai Y (2017) Pocket-switch-network based services optimization in crowdsourced delivery systems. Comput Electr Eng 62:53–63 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Authors and Affiliations AlexanderWyrowski1· NilsBoysen1 · DirkBriskorn2· StefanSchwerdfeger3 * Nils Boysen nils.bo[email protected] https://www.om.uni-jena.de/en/NilsBoysen.html Alexander Wyrowski alexander.wyrow[email protected] https://www.om.uni-jena.de/en/alexanderwyrowski Dirk Briskorn [email protected] http://www.prodlog.uni-wuppertal.de Stefan Schwerdfeger stefan.schwerdf[email protected] https://www.om.uni-jena.de/en/StefanSchwerdfeger 1 Friedrich-Schiller-Universität Jena, Lehrstuhl für Operations Management, Carl-Zeiß-Straße 3, 07743Jena, Germany 2 Bergische Universität Wuppertal, Professur für BWL, insbesondere Produktion und Logistik, Rainer-Gruenter-Str. 21, 42119Wuppertal, Germany 3 Friedrich-Schiller-Universität Jena, Lehrstuhl für Operations Management andLehrstuhl für Management Science, Carl-Zeiß-Straße 3, 07743Jena, Germany