Transcription
HindawiJournal of Advanced TransportationVolume 2018, Article ID 6430950, 21 pageshttps://doi.org/10.1155/2018/6430950Research ArticleRidesharing Problem with Flexible Pickup and DeliveryLocations for App-Based Transportation Service: MathematicalModeling and Decomposition MethodsMeng Zhao1,1 Jiateng Yin,2 Shi An,1 Jian Wang,1 and Dejian Feng1School of Transportation Science and Engineering, Harbin Institute of Technology, Harbin 150090, ChinaState Key Laboratory of Rail Traffic Control and Safety, Beijing Jiaotong University, Beijing 100044, China2Correspondence should be addressed to Jian Wang; wjhit1974@163.comReceived 14 February 2018; Revised 14 May 2018; Accepted 24 May 2018; Published 5 July 2018Academic Editor: Wai Yuen SzetoCopyright 2018 Meng Zhao et al. This is an open access article distributed under the Creative Commons Attribution License,which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.App-based transportation service system, such as Uber and Didi, has brought a new transportation mode to users, who are ableto make reservations using mobile apps conveniently. However, one of the fundamental challenges in app-based transportationsystem is the inefficiency and unreliability of the vehicle routing plans caused by complex topology of urban road network andunpredictable traffic conditions. A common way to tackle this problem is repositioning pickup or delivery locations via thecoordination between drivers and passengers. This paper studies an on-demand ridesharing problem that determines the optimalride-share matching strategy and vehicle routing plan with respect to flexible pickup and delivery locations. By introducing theconcept of space-time windows, the problem is formulated as the pickup and delivery problem with space-time windows (PDPSW)in space-time network. To solve the model efficiently and accurately, we particularly develop a customized solution approach basedon Lagrangian relaxation. Numerical examples are conducted to demonstrate the performance of the proposed framework anddraw some managerial insights into the optimal system operation. The results indicate that adopting the serving strategy of flexiblepickup and delivery locations will evidently reduce the system cost and improve the service quality in app-based transportationservice systems.1. IntroductionWith the constant growth of urban size and population,private car use has increased rapidly for its convenience,flexibility, and comfort, which yet causes a series of traffic and environment issues, such as congestion, parking shortage, energy overconsumption, and air pollution.The app-based transportation network and taxi companies (TNC), such as Uber, Lyft, and Didi, have rapidlydeveloped to provide the on-demand ridesharing service that achieves the balance of transport mobility andsocial benefit. For example, in 2017 the number of Uberuser reservations has reached 40 million per month andUber’s share of the United States ride hailing market is77% s/).In China, the number of TNC users is more than 150 million,accounting for 22.3% of the netizens.Different from the conventional taxi companies, TNC isable to collect passengers’ reservations through smartphoneapps and quickly extract the detailed travel information, suchas the origin and destination locations and the correspondingdeparture and arrival time windows. The request informationis then converted into some task lists involving the specificservice schedules (i.e., visiting times and locations) androuting path, which is then performed by a fleet of vehicles.This new technology brings great convenience to passengersbut may incur a series of fleet management issues due to thecomplex topology of urban road network and unpredictabletraffic conditions. Specifically, in some cases the pickup ordelivery locations of passengers may be spatially nearby buttopologically inaccessible or even temporally unreachable forvehicles. This will cause extra detours of vehicles or long-timewaiting, which will apparently impact the efficiency of theoperation system and reduce the service quality.
2Journal of Advanced Rout of vehicle before coordinationRout of vehicle after coordinationRout of passenger(a)Rout of vehicle before coordinationRout of vehicle after coordinationRout of passenger(b)Figure 1: Illustration of pickup and delivery locations repositioning.In practice, one intuitive way to tackle this problem isrepositioning pickup or delivery locations. In practice, thespatial accessibility and flexibility of passengers are muchhigher than that of vehicles within some local intersections orroad segments. Such as shown in Figure 1(a), location 1 (thecrossing of 168th St. and 88th Ave.) is the origin of passengeras requested. Since the 168th St. is one-way to north, thevehicle has to take a long detour to pick up the passenger,which is shown as blue dashed line. Alternatively, the driverwill first coordinate the detailed pickup location with thepassenger after receiving the task schedule and sometimesmay reposition it to a new location that is easier to access.For example, the passenger could be asked to walk a shortdistance (shown as the green chain line) to the major roadand then picked up at location 2. Furthermore, to deliverthe passenger to the opposite side of S Halsted St., which isshown as location 3 in Figure 1(b), the passenger could be firstdropped at location 4 and then walk to location 3 by crossingthe crosswalk or overpass. Otherwise, the vehicle has to turnaround at the crossing of S Halsted St. and W Harrison St. andthen take another U turn back to north. Since mainly basedon the drivers’ personal experience and not involved in thewhole system plan, such rescheduling operations are usuallyunreliable and may seriously disturb the task schedules. Thisis also one of the main limitations of the optimized vehiclerouting planning in practical applications.From the system-wide operation perspective, slightlyrepositioning the pickup and delivery locations of passengerswill somehow reduce the vehicle traveling cost and avoid therisks of unexpected transportation delays. Besides, properlyadjusting the relative positions of these locations may alsoincrease the matching rate between vehicles and passengers.In the best cases, passengers could be gathered to the samepickup or delivery location and simultaneously served by onevehicle. Therefore, a reliable and flexible vehicle routing strategy for on-demand ridesharing service system is expected tobalance the service quality and system cost considering thenetwork complexity and operational dynamics.Nevertheless, existing studies about the on-demandridesharing problem with flexible pickup and delivery locations are very few. Different from the ridesharing problemwith respect to developing the carpooling matching strategy,the on-demand ridesharing problem is also known in theliterature as pickup and delivery problem with time windows(PDPTW), which is a much more complicated problem dueto the complex coupling constraints among the vehicle routing, passenger assigning, and vehicle capacity limitations.On the other hand, the concept of flexible serving strategiesis mostly introduced to classify and cluster the passengersin matching procedure of carpooling problems. To best ofour knowledge, only a few of recent studies have made theattempt to integrate the ride-share matching strategy andvehicle dispatching plan with flexible pickup and deliverylocations for the on-demand ridesharing systems.To bridge the research gap, this paper aims to develop amathematical model for the on-demand ridesharing operations with flexible pickup and delivery locations. By employing the space-time presentation and the concept of spacetime window, the problem is further formulated as the pickupand delivery problem with space-time windows (PDPSW).By this, an integer linear programming (ILP) model is furtherproposed to simultaneously determine the optimal numberof dispatched vehicles, routing plan, and detailed servingstrategy, so as to minimize the fixed operation cost, vehicle traveling cost, and passengers’ inconvenience cost withrespect to the space-time flow balance constraints, passengerserving constraints, and vehicle capacity constraints.Considering the complexity of the model, we present acustomized solution approach based on Lagrangian relaxation (LR) algorithm. Specifically, we dualize two set of coupling constraints to separate two parts of the problem, i.e., theride-share matching strategy and vehicle routing operation,by introducing different Lagrangian multipliers. The relaxedmodel is then decomposed into two sets of subproblems thatcan be seen as knapsack problem and shortest path problem,respectively. To efficiently obtain a feasible solution adapting
Journal of Advanced Transportationfrom the relaxed solution, a hybrid method is speciallydeveloped based on greedy algorithm and dynamic programming (DP). Eventually, a subgradient search is adoptedto iteratively update the feasible and relaxed solutions toan acceptable tolerance of optimality gap. The performanceof the LR based solution algorithm is then demonstratedthrough a multiscale experience comparing with that ofCPLEX, a widely used commercial solver. Besides, we canalso see from the sensitivity result that adopting the operationstrategy of flexible pickup and delivery locations significantlyreduces the system cost and yet guarantees the servicequality.2. Literature ReviewRidesharing has been widely studied ever since the 1970s,when carpooling attracted more and more attention for itsenergy efficiency and environmental protection. Particularlyin recent years, the considerable improvement of communication capabilities and e-payment allow for a more accessibleand secure online ridesharing service provide by TNCs. Asystematic review can be seen in Furuhata et al. [1], wherea classification is provided to better understand the existingridesharing systems. Some key challenges are also introducedin this paper to clarify the development of the area ofridesharing problem and indicate the directions of futurestudies.Mathematically, the ridesharing problem can be formulated as the PDPTW, or more specifically, the Dial-ARide Problem (DARP) when transporting passengers. As ageneralized version of the vehicle routing problem (VRP), thePDPTW aims at determining the optimal routs of vehiclesto satisfy the requests of pickup and delivery under thelimitation of vehicle capacities, corresponding time windows,and coupling constraints (Savelsbergh and Sol [2], Berbegliaet al. [3], and Dumas et al. [4]). Since the VRP is a NPhard problem, the PDPTW is also NP-hard and more difficultto solve. Therefore, there are number of studies focusingon developing efficient solution algorithms. Studies such asRopke and Pisinger [5], Li and Lim [6], Baldacci et al. [7],Hosni et al. [8], Küçükoğlu and Öztürk [9], Hu and Chang[10], and Mahmoudi and Zhou [11] all consider the generalPDPTW and provide customized heuristic or exact solutionapproach to efficiently solve certain scales of the problem.Hosni et al. [8] formulated the shared-taxi problem into amixed interprogram, in which an optimized taxi dispatchingstrategy is designed to assign the passengers’ reservationsto a fleet of taxis with optimal routing plans. Furthermore,a LR based solution approach was presented to solve theproblem efficiently with relatively small gaps comparing withCPLEX. Despite using the similar algorithmic framework,Mahmoudi and Zhou [11] decomposed the primal problem,which is simplified by adopting the state-space-time networkrepresentation, into a series of single PDPTWs. This allows aforward DP solution algorithm to solve the subproblems efficiently and accurately. Furthermore, a serious of numericalstudies were conducted to demonstrate the performance ofthe proposed solution algorithm in solving the on-demandridesharing problem in large-scales.3On the other hand, many studies have been conducted onride-share matching problem that specially aims to improvethe matching rate between vehicles and passengers or satisfythe passengers’ reservations with the minimum fleet size(Brownstone and Golob [12], Ferrari et al. [13], Herbawi andWeber [14], Xu et al. [15], Pelzer et al. [16], Stiglic et al. [17],and Masoud and Jayakrishnan [18]). Herbawi and Weber [14]considered the ride matching problem with time windows,which optimizes the assignments of passengers to vehicleswith respect to the serving order and detailed visiting timesof passengers’ pickup and delivery locations. A genetic andinsertion based heuristic algorithm was further proposed andapplied in real-time ride matching and iteratively improvesthe solution quality according to the realistic data. Stiglic etal. [17] introduced the concept of “meeting point” to increaseflexibility of pickup and delivery points of passengers. Thena customized algorithm was designed and implemented tooptimally match the vehicles and passengers in large-scaleridesharing system. The proposed modeling framework wasfurther performed in a simulation study to show the benefitsof adopting meeting point strategy in ridesharing systems.It is worth noting that Tong et al. [19] developed a jointoptimization model to integrate the passenger-to-vehicleassignment plan and the bus routing schedule design forthe customized bus service system. Based on the spacetime network modeling framework, they formulated theproposed problem into a multicommodity network flowbased optimization model. To improve the performance ofthe proposed algorithm in solving large-scale instances of theproblem, an LR based algorithm framework was employedto first reduce the solution space and then decomposed theproblem into two sets of subproblems. Besides, two numericalexperiences are performed to present the performance of thedeveloped model and algorithm.The rest of this paper is organized as follows. Section 3presents the detail of the PDPSW that is further formulatedinto an integer programming model. Then the LR basedsolution algorithm is developed in Section 4. Section 5presents a series of numerical experiments to demonstrate theperformance of the proposed solution approach and discussthe experiment results in the system operation strategyperspective. Section 6 concludes this paper and offers somefuture research directions.3. Problem FormulationThe framework of the proposed on-demand ridesharingoperations is shown in Figure 2. The application of mobileInternet and apps allow the TNCs to collect the travelplans from user reservations, which involve the detailedlocation and corresponding picking up and delivery timewindows. According to these pieces of information, the walkin catchment area by each timestamp in the relevant timewindows can be obtained with respect to the topologicalstructure of urban network. Then, based on the practical traffic conditions and regulations, the potential pickup/deliverylocations are further selected within these areas. Here, wedefine the space-time window as the set that contains allthe potential locations at timestamps of the relevant time
4Journal of Advanced TransportationInformation PlatformTravel InformationSpace-time syFleet Managing StrategyServing PlanVehicle-passengerAssignment PlanxVehicle RoutingplanTask ScheduleRecommendedRoutDispatchingPlan Figure 2: The framework of the on-demand ridesharing operations.window. We consider that all the location-time pairs includedin the space-time windows can be potentially selected toserve passengers. Therefore, the detailed vehicle-passengerassignment and vehicle routing plans, which involve the exactpickup and delivery locations and times of each passenger,will be determined by the modeling and decompositionmethod proposed in our study.Furthermore, the detailed vehicle dispatching strategieswill be sent to the corresponding vehicles in the form oftask schedules and recommended routs, while sent to thepassengers in the form of serving plans through the app,which involve the detailed pickup and delivery locations andtimes.In contrast to the PDPTW, the extension on spatialdimension is considered in this study to further enhancethe efficiency and reliability of the on-demand ridesharingsystem. To solve the on-demand ridesharing problem withflexible pickup and delivery locations, the specified servingplan is expected with respect to the dynamic spatiotemporalreservations from passengers, limited vehicle capacity, andminimum system cost. Therefore, we can see that the ondemand ridesharing system proposed in our study is essentially generalized to the flexible transit systems with virtualstops since the former one aims to provide a more flexibledispatching strategy to ensure the efficiency of the operationsystem with respect to the complex topology of urban roadnetwork and unpredictable traffic conditions. Nevertheless,in some cases, passengers whose space-time windows (partly)overlap each other could be gathered to the same pickup ordelivery location and simultaneously served by one vehicle,which is a more general version comparing with the processof classifying and clustering the passengers in matchingprocedure of flexible transit systems.Therefore, a completely new aspect is to simultaneouslydetermine the optimal locations and times for picking upor delivering each passenger, which leads to obviously morecomplex formulations with respect to the passenger servingand vehicle dispatching plans. The adoption of space-timenetwork enables the physical transportation network tointegrate the vehicles’ space-time trajectories and passengers’potential space-time distribution. In this regard, comparingwith some classical modeling methods for solving Dial-ARide Problem (DRAP) (such as Baldacci et al. [7], Hosni etal. [8], and Hu and Chang [10]), our formulation provides amore explicit and compact modeling structure to representthe passengers serving and vehicle dispatching plans withoutadding the extra constraints, such as the subtour eliminationconstraints, temporal constraints, and coupling constraintsbetween space and time related variables. This allows thedevelopment of a computationally efficient Lagrangian relaxation solution approach that can solve the PDPSW to nearoptimum solutions.In this section, we first introduce the PDPSW in Section 3.1. Then a systematical introduction of the PDPSWmodeling framework with respect to the space-time network representation is present in Section 3.2. Eventually,Section 3.3 presents the model formulation of the PDPSW.3.1. Description of PDPSW. We initially consider a directedtransportation network denoted by S (I, L), where I(indexed by 𝑖 and 𝑗) denotes the set of spatial nodes (such asthe intersections in road network) and L (indexed by (𝑖, 𝑗)) isthe set of links representing the road segments. Let sequentialset T {𝑡0 , 𝑡0 𝛿, . . . , 𝑡0 ( T 1)𝛿} denote the timehorizon of the considered operation cycle, where t0 is theinitial timestamp and 𝛿 stands for the unit intervals betweeneach two adjacent timestamps. Note that the time horizonin this study is assumed to be properly discretized so thatall the activities, such as the trips of passengers or vehicles,can be considered starting at any timestamp and completewithin integer multiples of 𝛿. Figure 3 illustrates a 20 20grid network that denotes the transportation network and weassume that the time horizon is [1, 16] and the unit interval𝛿 1. Each reservation of passenger is associated with the𝑂𝐷origin and destination, which are denoted by 𝑖𝑝1and 𝑖𝑝1ofpassenger 𝑝 P, respectively. We can see in Figure 3 that
Journal of Advanced 12Oi11Oi14Oi13[1,3]Figure 3: Illustration for PDPSW in spatial transportation network.𝑂𝑂nodes 𝑖11and 𝑖21(marked as red dots), respectively, denote𝐷𝐷the origins of passengers 1 and 2, while 𝑖11and 𝑖21(marked asdark blue dots), respectively, represent the destination nodesof passenger 1 and 2. As shown in Figure 3, we choose nodes𝑂 𝑂𝑂𝑖𝑝2-𝑖𝑝5 that are topologically adjacent to 𝑖𝑝1as the expanded𝐷 𝐷pickup nodes. Correspondingly, nodes 𝑖𝑝2 -𝑖𝑝5 are selected as𝐷the expanded delivery nodes with respect to 𝑖𝑝1. Then we𝑂 𝑂define the set that consists nodes 𝑖𝑝1 -𝑖𝑝5 as the pickup space𝐷 𝐷window of passenger 𝑝 and denoted by I𝑂𝑝 , while 𝑖𝑝1 -𝑖𝑝5 isdefined as the delivery space window and denoted by I𝐷𝑝.In PDPSW, passengers are supported to be picked up (ordelivered) at any nodes within the corresponding pickup(or delivery) space windows. That is, within a predefinedmaximum walking distance, a passenger can be served atorigin nodes or the nodes nearby. Moreover, each reservationof passengers also contains a pair of preferred pickup anddelivery time windows with respect to the origin and destination nodes, which are denoted by sequential sets T𝑂𝑝 Tand T𝐷 T.AsshowninFigure3,thepickuptimewindows𝑝of passenger 1 and 2 are, respectively, set as [1, 3] and [3, 5],while the delivery time windows are [10, 12] and [13, 15].After receiving the passengers’ reservations, a certainnumber of vehicles (denoted by H and indexed by ℎ) are sentout to pick up the passengers from one of their candidate𝑂pickup nodes 𝑖𝑝𝑛 I𝑂𝑝 within the related pickup time window𝑂T𝑝 and then deliver them to one of their candidate delivery𝐷nodes 𝑖𝑝𝑛 I𝐷𝑝 within the related delivery time window𝐷T𝑝 . Note that, in the PDPSW, passengers are supported toshare their ride with the others, which means that vehiclescan simultaneously serve multiple passengers during theoperation cycle under the limitation of vehicle capacity 𝐶ℎ(ℎ H).3.2. Space-Time Network Representation. Space-time networkis able to explicitly depict and rigorously formulate thespatiotemporal movement of commodities with compactmodel formulations, and it has been widely used in manytransportation modeling studies (Kliewer et al. [20], Yangand Zhou [21], Tong et al. [22], Zhen and Jing [23], Li et al.[24], and Zhang et al. [25]). Since the PDPSW is essentiallythe generalization of PDPTW and aims to simultaneouslydetermine the ride-share matching strategy and routingschedules of vehicles within the space-time dimension, wecan formulate the PDPSW by using the space-time networkrepresentation.In particular, a space-time network can be obtainedby extending the space network on the time horizon. Anillustration example can be seen in Figure 4, where gridnetwork S in Figure 3 is partly shown as the x-y plane. Timehorizon T is shown as t-axis vertical on the x-y plane. Letset G (V, A) denote the space-time network, where V(indexed by (𝑖, 𝑗)) is the set of space-time vertexes and A(indexed by (𝑖, 𝑡, 𝑗, 𝑠)) is the set of space-time arcs. Basedon the space-time network, we can intuitively present thepassengers’ reservations by combining the space windowand time window. Specifically, we denote the pickup anddelivery space-time windows of passenger 𝑝 by set V𝑂𝑝 and𝐷V𝑝 , which are shown as red and blue polygons in Figure 4.Each space-time window contains all the candidate pickupor delivery space-time vertexes. Considering the duration oftime that passengers spend to walk from the origin to theextended pickup nodes, there is only the origin vertex at theearliest timestamp in the pickup time window. As shownin Figure 4, the red dots represent the origin vertexes ofpassengers. To simplify the illustration, we here assume that ittakes passengers one time interval from origin node to all theadjacent pickup nodes. Hence there are five potential pickupvertexes from the second to the last timestamps in the pickuptime window (marked as orange and yellow dots). Similarly,there is only the destination vertex (marked as dark bluedotes) at the latest timestamp in delivery time window andfive potential pickup vertexes from the earliest to the secondlast timestamps in the delivery time window.To serve passengers 1 and 2, vehicle ℎ1 (𝐶ℎ1 2) is sentout to travel according to a feasible routing plan, which isdenoted by the space-time path marked as the green line inFigure 4. We can see that ℎ1 initially picks up passengers 1 and𝑂𝑂2 at space-time vertexes (𝑖13, 2) and (𝑖24, 4) and then delivers𝐷passenger 1 when passing (𝑖13, 10) and eventually delivers𝐷passenger 2 at (𝑖21, 13).3.3. Model Formulations. Based on the constructed spacetime network, an ILP model is roughly formulated in thissection. The following assumptions are initially proposed tofocus the model on the essence of PDPSW.Demand. All passengers’ reservations are considered to bedynamic and deterministic. That is, all the reservations aregiven before the operation cycle and cannot be canceledor delayed. In this sense, the detailed serving schedule ofvehicles can be obtained based on the serving requests,
6Journal of Advanced TransportationO(i25; 5)O; 5) (iO ; 4)(i2125O; 5)(i22O(i24; 5)O; 4)(i22O(i23, 5)O; 4)(i21O; 4)(i23O(i21; 3)O(i25; 0)O; 0)(i23O; 0)(i22O(i21; 0)O; 0)(i24O(i15; 3)O; 3)(i11O; 3)(i12O; 2)(i12O; 3)(i14O; 2)(i14D(i21; 15)D; 14)(i24D(i25; 13)D; 14)(i23D; 14)(i25D(i22; 14)D(i21; 14)D; 13)(i22D; 13)(i23D, 13)(i21D(i24; 13)D(i25; 0)D(i23; 0)D; 0)(i22D; 0)(i21y0D; 12)(i11O(i15; 2)O(i11; 2)t16151413121110987654321O(i13; 3)O; 2)(i13D(i15; 11)D; 10)(i15D; 11)(i12D(i14; 11)O; 1)(i11D(i24; 0)D(i12; 10)D; 11)(i13D(i11; 11)D(i11; 10)D(i13; 10)D(i14; 10)O; 0)(i15D(i15; 0)O; 0)(i13O; 0)(i12O; 0)(i11O; 0)(i14D(i12; 0)xD; 0)(i11D; 0)(i13D; 0)(i14Figure 4: Representation for PDPSW in space-time network.i.e., the pickup and delivery space-time windows in theformulation.Space-Time Window. We assume that the pickup and deliveryrequests of all the passengers are executable. It means that,for each passenger, the time intervals between pickup anddelivery space-time windows shall be no less than the vehicle’sshortest traveling time along the fastest routing between thecloset pickup and delivery nodes.Vehicle. To simplify the problem without generalization, thevehicles are assumed to be identical; i.e., they have the samecapacity and no passengers is onboard at the beginning andending of the operation cycle.Besides, for reader’s convenience, the major notations ofsets, parameters, and decision variables related to the modelformulation are listed below.Sets and ParametersA: set of space-time arcs in the space-time network,indexed by (𝑖, 𝑡, 𝑗, 𝑠)H: set of vehicles, indexed by ℎI: set of spatial transportation nodes, indexed by 𝑖 and𝑗I𝑂𝑝 : pickup space window of passenger 𝑝I𝐷𝑝 : delivery space window of passenger 𝑝P𝐷𝑝 : set of passengers whose arrival time windowcontains timestamp 𝑡T: set of timestamps in the considered operationcycle, indexed by 𝑡 and 𝑠T𝑂𝑝 : pickup time window of passenger 𝑝T𝐷𝑝 : delivery time window of passenger 𝑝V𝑂𝑝 : pickup space-time window of passenger 𝑝V𝐷𝑝 : delivery space-time window of passenger 𝑝𝐶ℎ : capacity of a vehicle ℎ𝑐𝑓 : fixed cost of dispatching a vehicle𝑐𝑖𝑗𝑙 : vehicle traveling cost through link (𝑖, 𝑗)𝑂: inconvenience costs for picking up passenger 𝑝 at𝑐𝑝𝑖pickup node 𝑖𝐷: inconvenience costs for delivering passenger 𝑝 at𝑐𝑝𝑖delivery node 𝑖Decision Variablesℎ𝑝𝑊𝑖𝑡 : whether vehicle ℎ drops off passenger 𝑝 at spacetime vertex (𝑖, 𝑡)ℎ𝑋𝑖𝑡𝑗𝑠: whether vehicle ℎ travels through space-time arc(𝑖, 𝑡, 𝑗, 𝑠)P: set of passengers, indexed by passenger 𝑝𝑌ℎ : whether vehicle ℎ is usedP𝑂𝑝 : set of passengers whose departure time windowcontains timestamp 𝑡𝑍𝑖𝑡 : whether vehicle ℎ picks up passenger 𝑝 at spacetime vertex (𝑖, 𝑡)ℎ𝑝
Journal of Advanced Transportation7Based on the above assumptions, the mathematical modelfor PDPSW is formulated as follows. We first propose a seriesof systemic constraints, such as the space-time flow balance constraints, passenger serving constraints, and vehiclecapacity constraints. Then, the objective function, which isessentially a summation of all cost components, is furtherdeveloped.Space-Time Flow Balance Constraints. To precisely capture thespace-time path of each vehicle, we initially introduce thespace-time flow balance constraints: (𝑗,𝑠) V:(𝑖,𝑡,𝑗,𝑠) Aℎ𝑝𝑍𝑖𝑡 (𝑗,𝑠) V:(𝑖,𝑡,𝑗,𝑠) Aℎ𝑋𝑖𝑡𝑗𝑠 0,(4) 𝑝 P, ℎ H, (𝑖, 𝑡) ℎ𝑝𝑊𝑖𝑡 (𝑗,𝑠) V:(𝑗,𝑠,𝑖,𝑡) A(5) 𝑝 P, ℎ H, (𝑖, 𝑡) (1) ℎ H,ℎwhere binary variables X fl {𝑋𝑖𝑡𝑗𝑠}ℎ H,(𝑖,𝑡,𝑗,𝑠) A and Y fl{𝑌ℎ }ℎ H determine the space-time path of vehicles and theℎ 1 ifselection of vehicles, respectively. Specifically, 𝑋𝑖𝑡𝑗𝑠and only if space-time arc (𝑖, 𝑡, 𝑗, 𝑠) is involved in the spacetime path of vehicle ℎ and 𝑌ℎ 1 if and only if vehicleℎ is dispatched to serve passengers. Note that space-timevertexes (𝑖𝑂, 𝑡𝑂) and (𝑖𝐷, 𝑡𝐷) are defined as the dummy originand destination vertexes of all the vehicles, respectively. Weassume that the distance and travel time from dummy originto any physical space-time vertex are 0 and infinity the otherway round, while those from physical space-time vertexesto dummy destination are 0 and also infinity the other wayround.Passenger Serving Constraints. For any TNC, fulfilling allthe reservations of the passengers is actually critical forguaranteeing the serving quality. Therefore, we assume thatthe proposed PDPSW formulation is based on the undersaturated condition. That is, the total fleet size is assumed to besufficient for serving all the passengers. We define binary variℎ𝑝ℎ𝑝ables Z fl {𝑍𝑖𝑡 }ℎ H,𝑝 P,(𝑖,𝑡) V𝑂𝑝 and W fl {𝑊𝑖𝑡 }ℎ H,𝑝 P,(𝑖,𝑡) V𝐷𝑝ℎ𝑝to denote the passenger serving plan, i.e., 𝑍𝑖𝑡 1 if andonly if vehicle ℎ picks up passenger 𝑝 at pickup space-timeℎ𝑝vertex (𝑖, 𝑡) and 𝑊𝑖𝑡 1 if and only if vehicle ℎ deliverpassenger 𝑝 at delivery space-time vertex (𝑖, 𝑡). Thus, thefollowing constraints are proposed to guarantee that all thepassengers’ reservations are fulfilled:ℎ𝑝 𝑍𝑖𝑡 1, 𝑝 P,ℎ H (𝑖,𝑡) V𝑂𝑝ℎ𝑝 𝑍𝑖𝑡 (𝑖,𝑡) V𝑂𝑝(2)ℎ𝑝
ResearchArticle Ridesharing Problem with Flexible Pickup and Delivery Locations for App-Based Transportation Service: Mathematical Modeling and Decomposition Methods
