Problem Statement: Request Request: r=(Or, dr,tr, er, pr, Kr) Or: origIn ●dr: destination tr: release time o er: expired time (deadline) pr: penalty if the request is rejected Kr sIze 12(24)sr=(v4,2,8am,8:15am,20,2) 1(0,1 59(52) v2(0,2) 24(10,2) U3(30)
Problem Statement: Request ⚫ Request: 𝑟 = 𝑜𝑟 , 𝑑𝑟 ,𝑡𝑟 , 𝑒𝑟 , 𝑝𝑟 ,𝐾𝑟 ⚫ 𝑜𝑟 : origin ⚫ 𝑑𝑟 : destination ⚫ 𝑡𝑟 : release time ⚫ 𝑒𝑟 : expired time (deadline) ⚫ 𝑝𝑟 : penalty if the request is rejected ⚫ 𝐾𝑟 : size 11 𝑣2(0,2) 𝑣7(2,4) 𝑣3(3,0) 𝑣8(5,2) 𝑣6(6,5) 𝑣4(10,2) 𝑣5(8,4) 5 5 7 8 4 5 5 3 3 5 𝑣1 (0,1) 1 𝑟 = 𝑣4 , 𝑣2 ,8am, 8: 15am,20, 2
Problem Statement: Request Request: r=Or,dr, tr,er, pr,Kr) Or: origIn ●dr: destination tr: release time o er: expired time (deadline) pr: penalty if the request is rejected sIze ● A set of requests r a set of served requests rt o a set of rejected requests r RUR-= R and r+∩R-=0
Problem Statement: Request ⚫ Request: 𝑟 = 𝑜𝑟 , 𝑑𝑟 ,𝑡𝑟 , 𝑒𝑟 , 𝑝𝑟 ,𝐾𝑟 ⚫ 𝑜𝑟 : origin ⚫ 𝑑𝑟 : destination ⚫ 𝑡𝑟 : release time ⚫ 𝑒𝑟 : expired time (deadline) ⚫ 𝑝𝑟 : penalty if the request is rejected ⚫ 𝐾𝑟 : size ⚫ A set of requests 𝑅 ⚫ a set of served requests 𝑅 + ⚫ a set of rejected requests 𝑅 − ⚫ 𝑅 + ∪ 𝑅 − = 𝑅 and 𝑅 + ∩ 𝑅 − = ∅ 12
Problem statement: route ● Route of worker:Sw=(ow,W…ls-1 o Rw: the set of requests served by w lw: either origin or destination ofrE Rw O D(Sw): distance of the route
Problem Statement: Route ⚫ Route of worker： S𝑤 = 𝑜𝑤, 𝑙𝑤 1 , ⋯ , 𝑙𝑤 𝑆𝑤 −1 ⚫ 𝑅𝑤: the set of requests served by 𝑤 ⚫ 𝑙𝑤 𝑖 : either origin or destination of 𝑟 ∈ 𝑅𝑤 ⚫ 𝐷 𝑆𝑤 : distance of the route 13
Problem statement: URPSM Unified RPSM(URPSM) problem Given o a road network g o a set of workers w o a set of requests r which are dynamically arrived o a weight parameter a o plan route su for each worker w to minimize unified cost oUC(W,R)=a·∑ w D(Sw)+∑reR-pr ● Constraints o each route is feasible o once requests are rejected, they can not be revoked
Problem Statement： URPSM ⚫ Unified RPSM (URPSM) problem ⚫ Given: o a road network 𝐺 o a set of workers 𝑊 o a set of requests 𝑅 which are dynamically arrived o a weight parameter 𝛼 ⚫ Plan route S𝑤 for each worker 𝑤 to minimize unified cost o 𝑈𝐶 𝑊,𝑅 = 𝛼 ∙ σ𝑤𝜖𝑊 𝐷(𝑆𝑤) + σ𝑟𝜖𝑅− 𝑝𝑟 ⚫ Constraints: o each route is feasible o once requests are rejected, they can not be revoked 14
Problem statement: Unified cost ●UC(W,R)=a·∑wewD(S)+∑rer-pr a:weight, pr: penalty for rejecting the request Minimize Total Distance lpr=big constant c=0 lPr=1 O Maximize Served Request a= unit pavment Pr=fare of request ss MAximize Total Revenue 1
Problem Statement: Unified Cost ⚫ 𝑈𝐶 𝑊, 𝑅 = 𝛼 ∙ σ𝑤𝜖𝑊 𝐷(𝑆𝑤) + σ𝑟𝜖𝑅− 𝑝𝑟 ⚫ 𝛼: weight, 𝑝𝑟 : penalty for rejecting the request ⚫ ቊ 𝛼 = 1 𝑝𝑟 = big constant ⚫ ቊ 𝛼 = 0 𝑝𝑟 = 1 ⚫ ቊ 𝛼 = unit payment 𝑝𝑟 = fare of request 15 Minimize Total Distance Maximize Served Request Maximize Total Revenue