Analysis And Evaluation Of The Slugging Form Of Ridesharing*
Analysis and Evaluation of the Slugging Form ofRidesharing*Shuo MaDepartment of Compute ScienceUniversity of Illinois at ChicagoChicago, U.S.A.Ouri WolfsonDepartment of Compute ScienceUniversity of Illinois at ChicagoChicago, haring is a promising method to address transportationproblems such as traffic jams and parking. Although traditionalcarpooling and taxi ridesharing have been investigated by many,slugging, as a simple yet effective form of ridesharing, has notbeen well-studied. In this paper, we formally define the sluggingproblem and its generalization. We provide proofs of theircomputational time complexity. For the variants of the sluggingproblem that are constrained by the vehicle capacity and traveltime delay, we prove NP-completeness and also propose someeffective heuristics. In addition, we discuss the dynamicslugging problem. We conducted experiments using a GPStrajectory data set containing 60 thousand trips. Theexperimental results show that our proposed heuristics canachieve close-to-optimal performances, which means as much as59% saving in vehicle travel distance.Categories and Subject DescriptorsJ.m [Computer Applications]: MiscellaneousGeneral TermsAlgorithmsKeywordsridesharing, slugging, NP-completeness, heuristics.1INTRODUCTIONTransportation problems, such as traffic jams, finding parkingslots, hailing a taxi during rush hours, are long-existingheadaches in cities, especially those with a large population.These problems negatively affect the environment, the economy,and more importantly average peoples’ daily lives.*This research was supported in part by the U.S. Department ofTransportation National University Rail Center (NURAIL), IllinoisDepartment of Transportation (METSI), National Science Foundationgrants IIS-1213013, CCF-1216096, DGE-0549489.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copiesare not made or distributed for profit or commercial advantage and thatcopies bear this notice and the full citation on the first page. Copyrightsfor components of this work owned by others than ACM must behonored. Abstracting with credit is permitted. To copy otherwise, orrepublish, to post on servers or to redistribute to lists, requires priorspecific permission and/or a fee. Request permissions fromPermissions@acm.org.SIGSPATIAL'13, November 05 - 08 2013, Orlando, FL, USACopyright 2013 ACM 978-1-4503-2521-9/13/11 ferent methods have been mainly proposed to tackle theseproblems separately. For example, extending the road network isone common approach to tackle traffic jams; sensors which candetect the availability of parking spaces [1] are installed to helpdrivers find open parking slots more quickly. However, thosesolutions often require additional construction or new equipmentadded to the existing infrastructures and thus are often expensiveto implement. In addition, their benefits are usually limited tothe specific corresponding problem.One reason for the above transportation problems is that thepassenger seats of vehicles are under-utilized. Thus, we studyridesharing as a promising means to improve the utilization ofvehicle ridership and thus reduce the number of cars on the road.Ridesharing practices have a variety of characteristics. Forexample, ridesharing can be either dynamic or static. Dynamicridesharing arranges trips on a very short notice. By contrast,static ridesharing arranges trips that are known in advance,usually hours or a day or two before the departure time.Ridesharing can arrange either recurring or ad-hoc trips. Also,ridesharing can either change or keep the route of the originaltrips of drivers. (In case routes are kept, riders need to get onand off the driver’s car at the origin and destination locations ofthe driver instead of their own.) Riders may share the cost withthe driver or not. Table 1 summarizes the characteristics of someof the most common ridesharing applications.Table 1 Characteristics of some most common ridesharinghitchhikingcarpoolingslugging yesnoyesno/verylowIn this paper we are interested in one particular ridesharingform, i.e. slugging. In slugging a passenger walks to the driver’sorigin, boards at the driver’s departure time, alights at thedriver’s destination, then walks from there to the passenger’sown destination. Thus slugging involves two modes oftransportation, car and walking. Since slugging does not changeany spatio-temporal aspect of the drivers’ original trips, sluggingis the simplest form of ridesharing in the sense of bringingminimum disruptions to the drivers. Thus it can be offered atminimum or no-cost to the riders. Compared to other forms ofridesharing where route change is allowed, e.g. taxi ridesharing[14], slugging avoids unnecessary complications such ascomplex fare mechanism or ridesharing-incurred travel timedelay for drivers (e.g. due to unexpected congestion encounteredon the way to some pickup). Thanks to its simplicity, slugging
has already become a common transport mode in some of thebusiest traffic areas in the North America, e.g. auxiliaryinterstate highways around urban areas such as WashingtonD.C., Bay area, Houston, and other cities [2, 3].Though currently slugging is mainly used for regular commutetrips, we envision that it can also be applied to ridesharingscenarios that involve mostly one-time casual trips. Forexample, consider a ridesharing website where travelers posttheir trips scheduled in the near future. When posting their trip,travelers may announce their roles in ridesharing: drivers,passengers, or both (i.e. travelers who have a car can leave therole to be determined by the website). The website will computea slugging plan to group these travelers and decide the driverand passengers for each group. The only attached string for apassenger is that she needs to walk to the origin location of thedriver’s trip before the driver departs, and she needs to walkfrom her driver’s destination to her own destination. Drivers arewilling to accept such a ride for a various reasons, such asenvironmental-friendliness, companionship, the privilege ofdriving on HOV lanes, reduced or waived toll on highways,small payment, etc.The increasing popularity of bike sharing programs indicatesthat people are open to alternative modes of transportation,particularly the ones like slugging that involve physical activity(i.e. walking). The motor industry is also actively promotingshared services like slugging, as stated in the “Blueprint forMobility” vision recently released by Ford company.To the best of our knowledge, our work is the first one to studyslugging from a computational perspective. We define and studythe basic slugging problem and its variants that are constrainedby the vehicle capacity and travel time delay. We also discussthe dynamic version of the slugging problem. The experimentalresults show that our proposed heuristics achieve 59% saving invehicle travel distance. Given the size of our real data set is 39thousand trips and the average distance of a trip in the data set is6.3 kilometers, the saving equals to 144,963 kilometers, whichmeans the reduction of over 4.5 thousand gallons of gasolineand 71 tons of carbon dioxide emission.In summary, the contributions of the paper include: We formalize the slugging problem using a graphabstraction. We propose a quadratic algorithm to solve theslugging problem. We define a generalization of the slugging problem andprove its NP-completeness. For the variants of the slugging problem that are constrainedby the vehicle capacity and travel time delay, we prove theirNP-completeness and propose effective heuristics. Viaextensive experiments, we demonstrate that the proposedheuristics have near-optimal performance in terms of thesaving in vehicle travel distance. We also consider the dynamic slugging problem andevaluate it via experiments; in the dynamic problem the tripsare announced incrementally.The remainder of the paper is organized as follows. In Section 2,we review existing literature related to our work. Section 3formally defines and studies the slugging problem, itsgeneralization, its constrained variants, its dynamic version, andheuristics for the intractable variants. We evaluate the proposedheuristics in Section 4.2RELATED WORKSIn this section we review existing works on three problems thatare relevant to slugging, i.e. taxi-ridesharing, carpooling and thedial-a-ride. Similar to slugging, all these problems aretransportation problems that involve pickups and drop-offs.Unlike slugging where passengers change their origin anddestinations in order to join the trip of drivers, in all threeproblems, drivers change their route in order to pick up anddeliver the passengers. Both taxi ridesharing and carpooling arespecific forms of ridesharing. The difference is that each driverin carpooling usually is associated with her own trip, while intaxi ridesharing this is not the case. Also taxi ridesharing usuallyneeds appropriate pricing mechanisms to incite taxi drivers. Thedial-a-ride problem slightly differs from carpooling as allvehicles start a trip and return to the same location called thedepot.2.1Taxi RidesharingThere have been a number of works on the taxi ridesharingapplication [14, 15, 16, 17]. These works modeled the taxiridesharing problem by considering different constraints. Incontrast to slugging, the routes of driver trips, i.e. taxis in thiscase, change to accommodate passengers. Among these works,some (see [17]) only considered vehicle capacity constraints,while the rest also considered time window constraints, i.e.travelers need to depart and arrive in given time intervals. [15] isthe only paper that models monetary constraints, which are usedto guarantee monetary incentives for both taxi drivers and taxiriders. These works on taxi ridesharing mainly concern theefficiency and scalability of ridesharing, i.e. how fast a querycan be answered and how many queries the system can handle.In contrast, we focus on the effectiveness of slugging as awhole, e.g. the saving in vehicle travel distance, while theexisting works on taxi ridesharing often consider theeffectiveness of ridesharing from the perspective of a singlerequest, e.g. reducing the increase in vehicle travel distance forevery new request [14].2.2CarpoolingThere have been many works on modeling and analyzing thetraditional carpooling problem where drivers need to changetheir routes due to ridesharing. In [7], the authors modeled acarpooling problem and proposed an exact method based onLagrangean column generation to solve it optimally. Since thecarpooling problem is NP-hard, the exact approach practicallyonly works for small instances of the carpooling problem,where there are at most a few hundred trips. For large instanceswith hundreds of thousands trips, many heuristics have beenproposed [4, 18]. These heuristics are applied to compute thebest route of a vehicle for a given set of requests, since the routeof drivers is allowed to change. As such route changes do notoccur in slugging, these heuristics are not applicable.Despite being a sibling of the carpooling problem, the sluggingproblem has so far drawn little attention from researchers. Therehave been some reports on the current state of sluggingoperations (see [8]). But our work is the first formal study ofslugging from a computational viewpoint.2.3Dial-A-Ride Problem (DARP)The Dial-A-Ride Problem (DARP) [5], a.k.a. the VehicleRouting Problem with Time Windows in the operation researchliterature, is closely relevant to the carpooling problem. TheDARP can be considered the carpooling problem with additional
restrictions (e.g. all vehicles are required to start any trip from adepot location and return to the depot after the trip). In contrastto slugging, vehicle routes are manipulated to accommodatepassengers’ origin and destination locations. DARP is proved tobe NP-hard. Cordeau et al. summarizes the state-of-the-artheuristics for DARP [9].3SLUGGINGWe introduce the concept of slugging in Sec. 3.1. We formallydefine the basic slugging problem in Sec. 3.2. Next we introduceand discuss the vehicle-capacity constrained slugging problemin Sec. 3.3, and the delay bounded slugging problem in Sec. 3.4.Then we describe the slugging problem with both constraintsand propose heuristics for it in Sec. 3.5. Finally, we discuss thedynamic slugging problem and its parameters in Sec. 3.6.3.1PreliminariesIn slugging, some travelers abandon their original trips and jointhe trip of other travellers, the drivers, without asking the driversto change their route or their departure time. To be more specific,consider two travellers and , and their respective trips and, each of which is described by an origin destination pair anda start time at which the traveller intends to depart. Assume thattraveller abandons her trip and joins ’s trip. In this case wesay thatis merged into. More specifically, travellerexecutes her new trip as follows: at the start time ofshewalks to the origin location of trip , then she waits until thestart time of(if arrives later than the start time ofthenshe cannot join ), she shares the ride with , she alights at thedestination ofand finally she walks from there to her owndestination. Clearly, the only impact that traveller has on tripis the occupation of one seat in B’s vehicle. In other words,there is no disruption to any spatio-temporal aspect of .In the above example, there is only one traveler associated witheach trip. In general, each trip can be associated with a party ofmultiple travelers who cannot be separated during the trip(assuming that the size of the party is always smaller than thenumber of seats in a vehicle).As shown in the above example, one necessary condition for tripto be able to be merged into trip is that the travellers of tripcan walk from the origin of at the start time of and arriveat the origin of trip before the start time of (assuming aconstant walking speed and taking the shortest path). Consider aset of tripswhere the travelers of each tripannounce their willingness to serve as: driver, or passenger,or both. Then for each trip pair and , where the travelers ofhave announced their willingness to be passengers, and thetravelers of have announced their willingness to be drivers,we can compute whether or not can be merged into . To dothat, a preprocessing stage is performed. At this stage, a map isused to compute the shortest path between the respective origins.Specifically, for such a trip pair, the shortest pathbetween the origins of the two trips is computed. Based on thecalculated shortest path, a presumed walking speed, and the starttimes of and , we can readily determine whether or not tripcan be merged into . If so, we say that pairis amergable pair where is a passenger trip and is a driver trip.For a mergeable pair, the shortest path between thedestinations of and is also calculated in order to determinethe travel time delay for the passenger trip . The travel timedelay for passenger trips imposes a natural constraint on theslugging problem, which will be discussed further in Sec. 3.4and 3.5.Now that we have defined a mergeable pair, for a given set oftrips, consider the set of all mergeable pairs represented as agraph S. Assuming that the trip start-times are distinct, weobserve that S possesses the following two properties.First, S is acyclic. Suppose there exists a cycle of mergeablepairs,, ,in . Mergeable pairmeans that the start time ofis smaller than that of. However, the first n-1 pairs of the cycle collectively tell usthat the start time ofshould be smaller than that of.Contradiction. In other words, S is acyclic because the starttimes of the trips on a path in S are increasing.Second, S is transitive (i.e. if ()and),then. If the travelers of can arrive at the origin ofbefore the start time of , and the travelers of can arrive atthe origin of before the start time of , then the travelers ofdefinitely can arrive at the origin of before the start time ofas well by: first arriving at the origin of and then taking thesame path used by the travelers of to the origin of ; thisassumes that all travelers have the same walking speed.3.2Basic Slugging ProblemSlugging is a graph problem. We formulate it as follows.Definition 1 A slugging graph, is a directed acyclicgraph whereis a set of trips and is set ofdirected edges between nodes that is transitive, i.e. if ()and (), then.Note that a node in a slugging graph may not have any incidentedges. A node with no incident edge can exist as it represents atrip that cannot be merged into any other trip, or into which noother trip can be merged. For example, a trip geographicallybounded in the northeastern corner of a city may become such adisconnected node if all other trips are bounded in thesouthwestern corner of the city, and they all start atapproximately the same time.A slugging graph indicates which trips can be merged intoothers. However, although a trip can be merged into multipleother trips, in a concrete slugging plan it is merged into only oneother trip. In other words, a slugging graph gives the possiblepairs of trips that can be combined, whereas a slugging plangives an actual combination that will be executed in practice. So,based on a slugging graph, a slugging plan can be constructed.Intuitively, a slugging plan is a subgraph of the slugging graphthat gives the driver and the passengers of each car.Definition 2 Given a slugging graph, a sluggingplan, is a subgraph of that satisfies thefollowing conditions: (i) ()there is nosuchthat; and (ii) ()there does not existsuch that.Intuitively, condition (i) states that any trip can be mergedinto at most one other trip. Condition (ii) states that a trip canbe merged into another trip only if there is no other tripthat has been merged into . These constraints precisely reflectthe nature of the slugging problem: each trip is either aridesharing provider, i.e. providing a car to be shared with other
riders, or a ridesharing consumer, i.e. taking exactly one rideprovided by a provider.Fig. 1 gives an illustrative example of slugging plans. Subfigure(a) shows a slugging graph of four trips. Subfigures (b) (c) (d)(e) show all slugging plans that are maximal, i.e. cannot includemore edges. For instance, consider the slugging plan shown insubfigure (b). Given thatalready exists, neither edgenor edgecan be added because the additionviolates Condition (i), and neither edgenor edgecan be added because either addition violates Condition(ii).T2T1T2T3T4T3T1T2T4T3(b)(a) a slugging graphT1T2T4T3(c)T1T2T4T3T1T4(e)(d)Fig. 1 An illustrative example of slugging plansA mergable pairin a slugging plan means thatismerged into . That is to say,is simply eliminated whilethere is no change to other than the fact that the number ofpassengers in ‘s vehicle is increased. Therefore the benefit ofmergingintoonly depends on the passenger tripandthus can be measured by some attribute of , e.g. the vehicletravel distance that is saved. In other words, the benefit ofmerging into another trip is independent of the other trip. Theimplication is that if an edge is labeled by the benefit of mergingthe two trips at its endpoints, then all the edges exiting a nodehave the same benefit. Formally, we define the benefit of aslugging graph as follows.Definition 3 A slugging graphis called benefitlabeled if each edge ()is associated with a label(), referred to as the benefit of edge, andthe benefits of all edges outgoing of the same node are identical,i.e.such that ()and,().A straightforward example of a benefit function is the constantfunction ()for any mergeable pair () .Intuitively, this benefit function measures the
Analysis and Evaluation of the Slugging Form of Ridesharing* Shuo Ma Department of Compute Science University of Illinois at Chicago Chicago, U.S.A. sma21@uic.edu Ouri Wolfson Department of Compute Science University of Illinois at Chicago Chicago, U.S.A. wolfson@cs.uic.edu ABSTRACT Ri
May 02, 2018 · D. Program Evaluation ͟The organization has provided a description of the framework for how each program will be evaluated. The framework should include all the elements below: ͟The evaluation methods are cost-effective for the organization ͟Quantitative and qualitative data is being collected (at Basics tier, data collection must have begun)
Silat is a combative art of self-defense and survival rooted from Matay archipelago. It was traced at thé early of Langkasuka Kingdom (2nd century CE) till thé reign of Melaka (Malaysia) Sultanate era (13th century). Silat has now evolved to become part of social culture and tradition with thé appearance of a fine physical and spiritual .
̶The leading indicator of employee engagement is based on the quality of the relationship between employee and supervisor Empower your managers! ̶Help them understand the impact on the organization ̶Share important changes, plan options, tasks, and deadlines ̶Provide key messages and talking points ̶Prepare them to answer employee questions
Dr. Sunita Bharatwal** Dr. Pawan Garga*** Abstract Customer satisfaction is derived from thè functionalities and values, a product or Service can provide. The current study aims to segregate thè dimensions of ordine Service quality and gather insights on its impact on web shopping. The trends of purchases have
On an exceptional basis, Member States may request UNESCO to provide thé candidates with access to thé platform so they can complète thé form by themselves. Thèse requests must be addressed to esd rize unesco. or by 15 A ril 2021 UNESCO will provide thé nomineewith accessto thé platform via their émail address.
Chính Văn.- Còn đức Thế tôn thì tuệ giác cực kỳ trong sạch 8: hiện hành bất nhị 9, đạt đến vô tướng 10, đứng vào chỗ đứng của các đức Thế tôn 11, thể hiện tính bình đẳng của các Ngài, đến chỗ không còn chướng ngại 12, giáo pháp không thể khuynh đảo, tâm thức không bị cản trở, cái được
Food outlets which focused on food quality, Service quality, environment and price factors, are thè valuable factors for food outlets to increase thè satisfaction level of customers and it will create a positive impact through word ofmouth. Keyword : Customer satisfaction, food quality, Service quality, physical environment off ood outlets .
More than words-extreme You send me flying -amy winehouse Weather with you -crowded house Moving on and getting over- john mayer Something got me started . Uptown funk-bruno mars Here comes thé sun-the beatles The long And winding road .
