IIUM Engineering Journal, Vol. 22, No. 1, 2021 Hamim et al. https://doi.org/10.31436/iiumej.v22i1.1520 MODEL DEVELOPMENT OF RIDE SPLITTING SERVICE WITH RESOURCE SHARING SCHEME ON RIDE SOURCING (ONLINE TAXI) SERVICES IN JAKARTA HELEN BURHAN1*, SUTANTO SOEHODHO2, NAHRY1 1 Department of Mathematics, Universitas Indonesia, Depok, Indonesia 2 Department of Civil Engineering, Universitas Indonesia, Depok, Indonesia *Corresponding author: helen.burhan@sci.ui.ac.id (Received: 21st June 2020; Accepted: 24th October 2020; Published on-line: 4th January 2021) ABSTRACT: This study aims to solve the increasing number of vehicles for ride-sourcing or online taxi service on the road and the operational issues in those services by developing an optimization model of ride-splitting services in the online taxi with a resource sharing (sharing platform) scheme. Ride-splitting service is a ride-sourcing service where one vehicle can serve two or more request customers at a similar time. Meanwhile, the resource-sharing scheme interlinks drivers from different platforms in providing services to the customers. That is, a driver from platform X can serve customers from platform Y and vice versa, with a predetermined profit sharing. We formulate the optimization problem as a new modified weighted bipartite matching and solve the problem using a greedy heuristic method. Based on the simulation, the proposed model can generate higher overall profit for all vehicles serving passengers, use fewer vehicles, and lower passengers’waiting time. ABSTRAK: Kajian ini bertujuan menyelesaikan jumlah penambahan kenderaan angkutan- berpusat atau servis teksi dalam talian di atas jalan raya dan isu operasi dalam perkhidmatan dengan membangunkan model pengoptimuman pada servis angkutan-pecahan bagi teksi dalam talian dengan skim perkongsian sumber (platform bersama). Servis angkutan-pecahan adalah servis angkutan-berpusat di mana satu kenderaan menyediakan perkhidmatan kepada dua atau lebih permintaan pengguna pada satu-satu masa. Manakala, perkongsian sumber menghubungkan pemandu dengan platform berlainan dalam menyediakan servis untuk penumpang. Iaitu, pemandu platform X boleh mengangkut penumpang platform Y dan sebaliknya, dengan menentukan terlebih dahulu keuntungan bersama. Kajian ini diformulasi dengan pengoptimuman masalah sebagai perubahan terbaru dalam menilai kesesuian kedua- dua pihak dan menyelesaikan masalah menggunakan kaedah heuristik rakus. Berdasarkan simulasi ini, model yang dicadangkan dapat menghasilkan keuntungan keseluruhan lebih tinggi bagi semua kenderaan perkhidmatan, dengan mengurangkan jumlah kenderaan dan masa menunggu penumpang. KEYWORDS: Ride Sourcing (Online Taxi) Services, Ride Splitting Service, Resource Sharing Scheme, Modified Weighted Bipartite Matching, Greedy Heuristic Method. 1. INTRODUCTION In line with the increasing usage of ride-sourcing service, which is more commonly known as online taxi, new problems stemming from the increasing usage of the service are also arising. One of those problems is the increased number of private vehicles on the road. This is due to the attractive idea of online taxi as a new business potential, so that idle private vehicles are now utilized as the online taxi fleet, some business owners even buy new cars purposely to be 175 IIUM Engineering Journal, Vol. 22, No. 1, 2021 Hamim et al. https://doi.org/10.31436/iiumej.v22i1.1520 rented for online taxi services [1]. The increased usage of private vehicles for the online taxi services is not in accordance with the initial purpose of ride-sourcing service, which was initially a ride-sharing concept that was designed to minimize the usage of private vehicles in order to reduce traffic [2, 3]. On the other hand, one of the many services offered by the online taxi provider is ride-splitting, a service that is unfortunately still underused. Ride-splitting service is a ride-sourcing service that is in line with the actual concept of ride sharing, where one vehicle (single driver) can serve two or more riders (multi-riders) at a similar time [4]. Currently, there are two big companies providing online taxi services in Jakarta whose operational services are not yet optimized. This can be concluded from the long waiting time for customers to be picked up, which is sometimes a lot longer that the estimate time shown on the app; and also from the surge pricing system, where the fare will be higher than the standard fare when the demand for services is high and the vehicle availability is low, the surge pricing system is deemed as non-transparent so that it can disadvantage consumers [5]. In the previous research, Burhan et.al [6] developed an optimized model of pure ride-sourcing service (single driver - single rider) with a resource sharing scheme to tackle the operational problems. Therefore, this study aims to solve the increasing number of vehicles for online taxi on the road and the operational issues in online taxi services, by developing an optimization model of ride- splitting services in online taxi with a resource sharing (sharing platform) scheme. To optimize the ride-splitting service with resource sharing scheme, an optimized route is sought to pick up and drop off two or more customer requests (in this research is limited to only two requests) from the nearby or adjacent area at the similar travel time. The resource sharing scheme here is the same one as defined by Burhan et.al [6], which is interlinking drivers from different operators (platforms) in providing services to the customers, where a driver from platform X can serve customers from platform Y and vice versa, with a predetermined profit sharing. The mathematical model in optimizing issues in this study will be using a new modified weighted bipartite matching problem, while the solving method will be using greedy heuristic method. The rest of the paper is organized as follows. Section 2 presents a literature review, while section 3 describes the problem formulation, and section 4 describes the solution method, section 5 present the computational experiment, and finally, section 6 concludes and illustrates future research directions. 2. LITERATURE REVIEW Ride-sourcing service, which is more commonly known as online taxi, is a public transportation service using private owned vehicles as fleet to serve customers as taxi service using technology of smartphones, GPS and GIS [2,3]. Based on the type of service offered, the service can be grouped into two types [4], pure ride-sourcing (single driver, single rider) and ride splitting (single driver, multi riders). In pure ride sourcing, a driver of personal vehicle is connected to one request customer, and in the ride-splitting service, a driver is connected to two or more request customers in which customers can choose to split (share) a ride and fare. Based on that classification, ride- splitting is the appropriate form of ride-sourcing based on the ride-sharing concept for single driver - multi rider, so that the problem of optimizing the ride-splitting service is the optimization problem in finding the vehicle route to pick up and drop off passengers [7]. The optimization problem in finding the vehicle route to pick up and and drop off passengers on ride-splitting service is similar to dynamic pick up and delivery problem with time windows [8]. Generally, the pick up and delivery problems with time windows is one 176 IIUM Engineering Journal, Vol. 22, No. 1, 2021 Hamim et al. https://doi.org/10.31436/iiumej.v22i1.1520 variant of vehicle routing problem which aims to find the optimal vehicle route to deliver and pick up a number of customers in an interval of time (time windows), taking into account a number of constraints such as vehicle capacity and some other precedent constraints, with minimum costs [9]. The dynamic term here refers to the requests which gradually revealed throughout the day, so that vehicle routes are constructed in real-time [10]. Several previous studies that discussed the problem of optimizing ride-sharing services for the case of a single driver-multi rider, some of which are, Hosni et al. [11] use mixed integer programming to model the problem of maximize profit for shared taxi problem and present a Lagrangian decomposition approach as well as two heuristics to solve the problem, Wang et.al [12] use binary integer programming to model the problem of minimize cost and travel time for a pickup and delivery problem with the use of HOV lanes and use Tabu search heuristic to solve the problem, Santos and Xavier [13] use mixed integer programming to model the problem of maximize the number of served requests and minimize the cost for the ride-sharing problem and solved the problem by a greedy randomized adaptive search procedure, Mahmoudi and Zhou [14] propose a new time discretized multi-commodity network flow model for ride-sharing problem within state space-time network to minimize cost and using a forward dynamic programming solution algorithm and Lagrangian approach to solve the problem. While Bei and Zhang [15] use a three-dimensional matching problem to minimize cost for the ride-sharing problem and use a two-phase greedy approach to solve the problem. To the best of our knowledge, the previous studies have never been including maximizing profit and minimizing waiting time in the objective function simultaneously and explicitly. Therefore, in this study, we will use a new modified weighted bipartite graph problem to formulate the optimization problem of ride splitting service to maximize the driver’s profit while minimizing passenger’s waiting time. In the meantime, researches relating to the operational problems in ride-sourcing services are discussing more of the surge pricing problems; because surge pricing is considered as lack transparency and is harmful to the consumer [16-18]. However, since the price for ride service cannot be unlimited, there is usually a reasonable or legitimate range of prices in practice. Such a constrained surge pricing strategy fails to balance demand and supply in certain cases, e.g., even adopting the maximum allowed price cannot reduce the demand to an affordable level during peak hours [19]. Therefore, this study is developing a resource sharing scheme based on research conducted by Burhan, H, et.al [6] to solve the surge pricing problems in ride- sourcing services. 3. PROBLEM FORMULATION In ride-splitting service with resource sharing scheme, customer from platform X can be served by vehicle from platform Y, and the other way around, with a profit sharing between platforms that is predetermined beforehand. With the predetermined scheme, characteristics of the ride-splitting service with the resource sharing scheme in this paper, are as follows: - Customer will get less waiting time - Driver will get more profit due to less operational cost by picking up customer from the different platform, whose pick-up location is closer to the driver’s position, rather than picking up customer from the same platform but whose pick-up location is quite far from the driver's position. - Matching rate between driver and passenger/customer is also increasing, because the probability is bigger for the customer whose pick-up time and location is similar to the driver, as opposed to when compared to the possibility from only the same platform. 177 IIUM Engineering Journal, Vol. 22, No. 1, 2021 Hamim et al. https://doi.org/10.31436/iiumej.v22i1.1520 Assume, there are two different operators (platforms) providing ride-splitting services, where it can be enlarged to n platforms and a homogenous fleet of vehicles with the same capacities. The request from a customer in this study arrives dynamically, thus the customer’s requests and available vehicles will be grouped first, based on a period of time, and then the optimization process to assign vehicle and passengers is done statically per period. The period length is based on an acceptable time limit of a customer to wait for a decision to be picked up and time for the optimization process. The first period starts at the time, at which the first request from a customer arrived. In the optimization process, initially, we must pair potential vehicles which feasible to serve a request customer by generating the first weighted bipartite graph. Then, we will get a set of feasible vehicle and the first customer pairs. In this study, the ride splitting service is limited to serving only two request customers in one trip. Thus, next stage is to generate a second weighted bipartite graph to pair a vehicle and the first customer with a potential second request customer. The objective of the optimization problem is to maximize the total profit earned by drivers (vehicles) while minimizing the total passenger's waiting time. Then, we model the problem using a new modified weighted bipartite matching. The final stage, use a greedy heuristic method to solve the problem. Next, we present the process of generating first weighted bipartite graph as the first stage for the optimization process. 3.1. First Weighted Bipartite Graph Let k and r be the number indexes for platform which requested by customer, where 𝒌,𝒓 = 𝟏,𝟐 and 𝝉 be the period for optimization process. Let 𝑷𝒌𝒍 𝝉 be the 𝒍 − 𝒕𝒉 passenger of platform 𝒌 in period 𝝉 and 𝑽𝒓𝒔 𝝉 be the s−𝒕𝒉 available vehicle of platform 𝒓 in period 𝝉. Then: - 𝑃𝑘 𝜏 be a set of customers who request vehicle from platform 𝑘 in period 𝜏, where: 𝑃𝑘 𝜏 = {𝑃𝑘𝑙 𝜏 |the 𝑙 − 𝑡ℎ passenger of platform 𝑘 in period 𝜏; 𝑙 = 1,2,…,𝑛𝑘}, for 𝑘 = 1,2 and 𝑃𝜏 be the set of customers who request vehicle in period 𝜏. - 𝑉𝑟 𝜏 be a set of available vehicles from platform 𝑟 in period 𝜏, where: 𝑉𝑟 𝜏 = {𝑉𝑟𝑠 𝜏|the 𝑠 − th vehicle of platform 𝑟 in period 𝜏; 𝑠 = 1,2,…,𝑚𝑟} , for 𝑟 = 1,2 and 𝑉𝜏 be the set of available vehicles in period 𝜏. Note that 𝑃𝜏𝑖 consists of all new customer requests in period 𝜏𝑖 and all assigned passengers in the previous period 𝜏𝑖−1, but still not get a passenger pair to share a ride, for 𝑖 = 2,3,…. Likewise, 𝑉𝜏𝑖 consists of all newly available vehicles in period 𝜏𝑖 and all available vehicles which still eligible to serve a customer from the previous period 𝜏𝑖−1, for 𝑖 = 2,3,…. Each passenger 𝑃𝑘𝑙 𝜏 is associated with time at which customer request a vehicle 𝑡𝑟𝑒𝑞𝑢𝑒𝑠𝑡_𝑃𝑘𝑙 𝜏 , origin or pick up location 𝑜𝑃𝑘𝑙 𝜏 , destination or drop off location 𝑑𝑃𝑘𝑙 𝜏 , an earliest departure time 𝑒𝑑𝑒𝑝𝑡 𝑃𝑘𝑙 𝜏 , a latest departure time 𝑙𝑑𝑒𝑝𝑡 𝑃𝑘𝑙 𝜏 , and the number of passenger 𝑞𝑃𝑘𝑙 𝜏 . Also, passenger 𝑃𝑘𝑙 𝜏 must arrive at destination at least on 𝑒𝑎𝑟𝑟_𝑃𝑘𝑙 𝜏 , and not after 𝑙𝑎𝑟𝑟_𝑃𝑘𝑙 𝜏 , and cannot ride a vehicle more than 𝑡𝑚𝑎𝑥𝑟𝑖𝑑𝑒 _𝑃𝑘𝑙 𝜏 . While, each available vehicle 𝑉𝑟𝑠 𝜏 is associated with origin or current location 𝑖𝑉𝑟𝑠𝜏 , time to leave from or arrive at location on 𝑡𝑖𝑚𝑒𝑖𝑉𝑟𝑠𝜏 𝑉𝑟𝑠 𝜏 , maximum capacity 𝑄𝑉𝑟𝑠𝜏 , and vehicle’s occupation 𝑉𝑟𝑠 𝜏_𝑜𝑐𝑐. Let 𝐺1 𝜏 = (𝑁1 𝜏,𝐸1 𝜏) be the first weighted bipartite graph for optimization process, where 𝑁1 𝜏 be the set of nodes of 𝐺1 𝜏 and 𝐸1 𝜏 be the set of edges of 𝐺1 𝜏. Defined 𝑁1 𝜏 = 𝑉𝜏 ∪ 𝑃𝜏 be a bipartite node set of all request customers and available vehicles in period 𝜏. For each passenger 𝑃𝑘𝑙 𝜏 in 𝑃𝜏, the distance 𝐷𝑖 𝑉𝑟𝑠 𝜏 𝑂𝑃𝑘𝑙 𝜏 and the travel time 𝑇𝑇𝑖𝑉𝑟𝑠𝜏 𝑂𝑃𝑘𝑙 𝜏 be 178 IIUM Engineering Journal, Vol. 22, No. 1, 2021 Hamim et al. https://doi.org/10.31436/iiumej.v22i1.1520 a distance and a travel time of shortest path from origin 𝑜𝑃𝑘𝑙 𝜏 to destination 𝑑𝑃𝑘𝑙 𝜏 . For each vehicle 𝑉𝑟𝑠 𝜏 in 𝑉𝜏, the distance 𝐷𝑖 𝑉𝑟𝑠 𝜏 𝑂𝑃𝑘𝑙 𝜏 and the travel time 𝑇𝑇𝑖𝑉𝑟𝑠𝜏 𝑂𝑃𝑘𝑙 𝜏 be a distance and a travel time of shortest path from vehicle’s origin (current) location 𝑖𝑉𝑟𝑠𝜏 to passenger’s origin 𝑜𝑃𝑘𝑙 𝜏 . For each passenger 𝑃𝑘𝑙 𝜏 , earliest and latest departure time, earliest and latest arrival time, and maximum ride time are determined with the following formula: 𝑒𝑑𝑒𝑝𝑡 𝑃𝑘𝑙 𝜏 := 𝑡𝑟𝑒𝑞𝑢𝑒𝑠𝑡_𝑃𝑘𝑙 𝜏 + 𝜆𝑒𝑎𝑟𝑙𝑦 (1) 𝑙𝑑𝑒𝑝𝑡 𝑃𝑘𝑙 𝜏 := 𝑒𝑑𝑒𝑝𝑡 𝑃𝑘𝑙 𝜏 + 𝜆𝑙𝑎𝑡𝑒 (2) 𝑒𝑎𝑟𝑟_𝑃𝑘𝑙 𝜏 ≔ 𝑡𝑖𝑚𝑒𝑖 𝑉𝑟𝑠 𝜏 𝑉𝑟𝑠 𝜏 +((1 + 𝜀) 𝑇𝑇𝑖 𝑉𝑟𝑠 𝜏 𝑂𝑃𝑘𝑙 𝜏 )+ 𝑡𝑠𝑒𝑟𝑣𝑖𝑐𝑒_ 𝑃𝑘𝑙 𝜏 𝑉𝑟𝑠 𝜏 +𝑇𝑇𝑜𝑑 𝑃𝑘𝑙 𝜏 (3) 𝑙𝑎𝑟𝑟_𝑃𝑘𝑙 𝜏 ≔ 𝑒𝑎𝑟𝑟 𝑃𝑘𝑙 𝜏 + 𝜆𝑙𝑎𝑡𝑒 (4) 𝑡𝑚𝑎𝑥𝑟𝑖𝑑𝑒 _𝑃𝑘𝑙 𝜏 ≔ ((1 + 𝜇)𝑇𝑇𝑜𝑑 𝑃𝑘𝑙 𝜏 ) (5) where 𝜆𝑒𝑎𝑟𝑙𝑦 be a level of service for early departure time; 𝜆𝑙𝑎𝑡𝑒 be a level of service for early departure or arrival time; 𝑡𝑠𝑒𝑟𝑣𝑖𝑐𝑒_ 𝑃𝑘𝑙 𝜏 𝑉𝑟𝑠 𝜏 be time for passenger to get into (get off from) a vehicle; (1 + 𝜀) and (1 + 𝜇) be multiplier factor for tolerance time deviation, with 0 < 𝜀,𝜇 < 1. Vehicle 𝑉𝑟𝑠 𝜏 is feasible to serve a passenger 𝑃𝑘𝑙 𝜏 , if the following criteria are met. 1) Time Constraints: a) Vehicle must arrive at passenger’s origin on departure time windows: 𝑒𝑑𝑒𝑝𝑡 𝑃𝑘𝑙 𝜏 ≤ 𝑡𝑖𝑚𝑒𝑖 𝑉𝑟𝑠 𝜏 𝑉𝑟𝑠 𝜏 +((1 + 𝜀) 𝑇𝑇𝑖 𝑉𝑟𝑠 𝜏 𝑂𝑃𝑘𝑙 𝜏 ) ≤ 𝑙𝑑𝑒𝑝𝑡 𝑃𝑘𝑙 𝜏 (6) b) Vehicle must arrive at passenger’s destination on arrival time windows: 𝑒𝑎𝑟𝑟_𝑃𝑘𝑙 𝜏 ≤ 𝑡𝑖𝑚𝑒𝑖 𝑉𝑟𝑠 𝜏 𝑉𝑟𝑠 𝜏 +((1 + 𝜀) 𝑇𝑇𝑖 𝑉𝑟𝑠 𝜏 𝑂𝑃𝑘𝑙 𝜏 )+ 𝑡𝑠𝑒𝑟𝑣𝑖𝑐𝑒_ 𝑃𝑘𝑙 𝜏 𝑉𝑟𝑠 𝜏 +𝑇𝑇𝑜𝑑 𝑃𝑘𝑙 𝜏 ≤ 𝑙𝑎𝑟𝑟_𝑃𝑘𝑙 𝜏 (7) 2) Capacity Constraint: The number of passengers in each request must be less than or equal to available vehicle’s capacity: 𝑞𝑃𝑘𝑙 𝜏 ≤ 𝑄𝑉𝑟𝑠𝜏 (8) Let 𝑃𝑘𝑙 𝜏 in 𝑃𝜏 and 𝑉𝑟𝑠 𝜏 in 𝑉𝜏. Defined an edge in 𝐸1 𝜏 be a pair of (𝑉𝑟𝑠 𝜏 ,𝑃𝑘𝑙 𝜏 ), where vehicle 𝑉𝑟𝑠 𝜏 is met the feasible criterion in (6) – (8) to serve passenger 𝑃𝑘𝑙 𝜏 . Then, 𝐸1 𝜏 = {(𝑉𝑟𝑠 𝜏 ,𝑃𝑘𝑙 𝜏 )|𝑃𝑘𝑙 𝜏 and 𝑉𝑟𝑠 𝜏 are feasible match; 𝑉𝑟𝑠 𝜏 ∈ 𝑉𝜏, 𝑃𝑘𝑙 𝜏 ∈ 𝑃𝜏}. The weight of each edge (𝑉𝑟𝑠 𝜏 ,𝑃𝑘𝑙 𝜏 ) in 𝐸1 𝜏 is defined as the fare that has to be paid by passenger 𝑃𝑘𝑙 𝜏 served by vehicle 𝑉𝑟𝑠 𝜏 , where the fare is calculated by using the following formula: 𝐹𝑃𝑘𝑙 𝜏 = 𝑇𝑎𝑟𝑖𝑓𝑓𝑘 × 𝐷𝑜𝑑_𝑃𝑘𝑙 𝜏 (9) where 𝑇𝑎𝑟𝑖𝑓𝑓𝑘 is tariff of platform k for ride splitting service per 1 distance unit. Next, mathematical model for the optimization problem of ride splitting service with resource sharing scheme will be presented. Before that, we generate a second weighted bipartite graph. 3.2. New Modified Weighted Bipartite Matching Problem 179 IIUM Engineering Journal, Vol. 22, No. 1, 2021 Hamim et al. https://doi.org/10.31436/iiumej.v22i1.1520 Let 𝐺2 𝜏 = (𝑁2 𝜏,𝐸2 𝜏) be the second weighted bipartite graph for optimization process, where 𝑁2 𝜏 be the set of nodes of 𝐺2 𝜏 and 𝐸2 𝜏 be the set of edges of 𝐺2 𝜏. Let 𝑁2 𝜏 = 𝑉𝜏𝑃𝜏 ∪ 𝐷𝑉𝜏𝑃𝜏, be a bipartite set of nodes of graph 𝐺2 𝜏. For 𝑉𝑟𝑠 𝜏 ∈ 𝑉𝜏 and 𝑃𝑘𝑙 𝜏 ∈ 𝑃𝜏, defined 𝑉𝑟𝑠 𝜏𝑃𝑘𝑙 𝜏 be a node in 𝑉𝜏𝑃𝜏 if only if (𝑉𝑟𝑠 𝜏 ,𝑃𝑘𝑙 𝜏 ) is an edge in 𝐸1 𝜏. Thus, 𝑉𝜏𝑃𝜏 = {𝑉𝑟𝑠 𝜏𝑃𝑘𝑙 𝜏 |(𝑉𝑟𝑠 𝜏 ,𝑃𝑘𝑙 𝜏 ) is an edge in 𝐸1 𝜏;𝑉𝑟𝑠 𝜏 ∈ 𝑉𝜏,𝑃𝑘𝑙 𝜏 ∈ 𝑃𝜏} and 𝐷𝑉𝜏𝑃𝜏 is a duplication set of 𝑉𝜏𝑃𝜏 where 𝐷𝑉𝜏𝑃𝜏 = {𝑉𝑟′𝑠′ 𝜏 𝑃𝑘′𝑙′ 𝜏 |if 𝑉𝑟𝑠 𝜏𝑃𝑘𝑙 𝜏 ∈ 𝑉𝜏𝑃𝜏}. Let 𝑉𝑟𝑠 𝜏𝑃𝑘𝑙 𝜏 be a node in 𝑉𝜏𝑃𝜏 and 𝑉𝑟′𝑠′ 𝜏 𝑃𝑘′𝑙′ 𝜏 be a node in 𝐷𝑉𝜏𝑃𝜏, defined, an edge in 𝐸2 𝜏 be a pair of (𝑉𝑟𝑠 𝜏𝑃𝑘𝑙 𝜏 ,𝑉𝑟′𝑠′ 𝜏 𝑃𝑘′𝑙′ 𝜏 ), where 𝑟 = 𝑟′,𝑠 = 𝑠′ and 𝑉𝑟𝑠 𝜏 is feasible to serve customers 𝑃𝑘𝑙 𝜏 and 𝑃𝑘′𝑙′ 𝜏 . Note that, in the edge (𝑉𝑟𝑠 𝜏𝑃𝑘𝑙 𝜏 ,𝑉𝑟′𝑠′ 𝜏 𝑃𝑘′𝑙′ 𝜏 ), 𝑉𝑟𝑠 𝜏 and 𝑉𝑟′𝑠′ 𝜏 have to be the same vehicles. Thus,𝐸2 𝜏 = {(𝑉𝑟𝑠 𝜏𝑃𝑘𝑙 𝜏 ,𝑉𝑟′𝑠′ 𝜏 𝑃𝑘′𝑙′ 𝜏 )| 𝑟 = 𝑟′,𝑠 = 𝑠′ and 𝑉𝑟𝑠 𝜏 is feasible match with 𝑃𝑘𝑙 𝜏 and 𝑃𝑘′𝑙′ 𝜏 ; 𝑉𝑟𝑠 𝜏𝑃𝑘𝑙 𝜏 ∈ 𝑉𝜏𝑃𝜏,𝑉𝑟′𝑠′ 𝜏 𝑃𝑘′𝑙′ 𝜏 ∈ 𝐷𝑉𝜏𝑃𝜏}. Route of vehicle 𝑉𝑟𝑠 𝜏 to pick up and drop off customers 𝑃𝑘𝑙 𝜏 and 𝑃𝑘′𝑙′ 𝜏 , 𝑅𝑜𝑢𝑡𝑒𝑉𝑟𝑠𝜏 _𝑃𝑘𝑙 𝜏 _𝑃𝑘′𝑙′ 𝜏 is defined as the shortest path from vehicle’s current location 𝑖𝑉𝑟𝑠𝜏 to the first passenger’s origin 𝑜𝑃𝑘𝑙 𝜏 , then to the second passenger’s origin 𝑜𝑃 𝑘′𝑙′ 𝜏 and next to passenger’s destination 𝑑𝑃𝑘𝑙 𝜏 or 𝑑𝑃𝑘′𝑙′ 𝜏 for which one is the closest. Then, 𝑅𝑜𝑢𝑡𝑒𝑉𝑟𝑠𝜏 _𝑃𝑘𝑙 𝜏 _𝑃𝑘′𝑙′ 𝜏 is the shortest path between route 𝑖𝑉𝑟𝑠𝜏 − 𝑜𝑃𝑘𝑙 𝜏 − 𝑜𝑃 𝑘′𝑙′ 𝜏 − 𝑑𝑃𝑘𝑙 𝜏 − 𝑑𝑃𝑘′𝑙′ 𝜏 and route 𝑖𝑉𝑟𝑠𝜏 − 𝑜𝑃𝑘𝑙 𝜏 − 𝑜𝑃 𝑘′𝑙′ 𝜏 − 𝑑𝑃 𝑘′𝑙′ 𝜏 − 𝑑𝑃𝑘𝑙 𝜏 . 𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒𝑉𝑟𝑠𝜏 _𝑃𝑘𝑙 𝜏 _𝑃𝑘′𝑙′ 𝜏 and 𝑇𝑇𝑉𝑟𝑠𝜏 _𝑃𝑘𝑙 𝜏 _𝑃𝑘′𝑙′ 𝜏 are defined as the distance and the travel time of 𝑅𝑜𝑢𝑡𝑒𝑉𝑟𝑠𝜏 _𝑃𝑘𝑙 𝜏 _𝑃𝑘′𝑙′ 𝜏 . Vehicle 𝑉𝑟𝑠 𝜏 is feasible to serve customers 𝑃𝑘𝑙 𝜏 and 𝑃𝑘′𝑙′ 𝜏 , if the following criteria are met: 1) Time feasibility: a) Vehicle must arrive at passenger’s origin on passenger’s departure time windows: - For first passenger, 𝑃𝑘𝑙 𝜏 : 𝑒𝑑𝑒𝑝𝑡 𝑃𝑘𝑙 𝜏 ≤ 𝑊𝑇𝑉𝑟𝑠𝜏 𝑃𝑘𝑙 𝜏 ≤ 𝑙𝑑𝑒𝑝𝑡 𝑃𝑘𝑙 𝜏 (10) where 𝑊𝑇 𝑉𝑟𝑠 𝜏 𝑃𝑘𝑙 𝜏 is passenger 𝑃𝑘𝑙 𝜏 ’s waiting time to be picked up by vehicle 𝑉𝑟𝑠 𝜏 , with 𝑊𝑇 𝑉𝑟𝑠 𝜏 𝑃𝑘𝑙 𝜏 = 𝑡𝑖𝑚𝑒𝑖 𝑉𝑟𝑠 𝜏 𝑉𝑟𝑠 𝜏 +((1 + 𝜀) 𝑇𝑇𝑖 𝑉𝑟𝑠 𝜏 𝑂𝑃𝑘𝑙 𝜏 ) (11) - For second passenger, 𝑃𝑘′𝑙′ 𝜏 : 𝑒𝑑𝑒𝑝𝑡 𝑃𝑘′𝑙′ 𝜏 ≤ 𝑊𝑇𝑉𝑟𝑠𝜏 𝑃𝑘′𝑙′ 𝜏 ≤ 𝑙𝑑𝑒𝑝𝑡 𝑃𝑘′𝑙′ 𝜏 (12) where 𝑊𝑇 𝑉𝑟𝑠 𝜏 𝑃𝑘′𝑙′ 𝜏 is passenger 𝑃𝑘′𝑙′ 𝜏 ’s waiting time to be picked up by vehicle 𝑉𝑟𝑠 𝜏 , with 𝑊𝑇 𝑉𝑟𝑠 𝜏 𝑃𝑘′𝑙′ 𝜏 =𝑊𝑇 𝑉𝑟𝑠 𝜏 𝑃𝑘𝑙 𝜏 + 𝑡𝑠𝑒𝑟𝑣𝑖𝑐𝑒 𝑃𝑘𝑙 𝜏 𝑉𝑟𝑠 𝜏 + 𝑇𝑇𝑂 𝑃𝑘𝑙 𝜏 𝑂 𝑃𝑘′𝑙′ 𝜏 (13) b) Vehicle must arrive at passenger’s destination on passenger’s arrival time windows: If 𝑅𝑜𝑢𝑡𝑒𝑉𝑟𝑠𝜏 _𝑃𝑘𝑙 𝜏 _𝑃𝑘′𝑙′ 𝜏 is 𝑖𝑉𝑟𝑠𝜏 − 𝑜𝑃𝑘𝑙 𝜏 − 𝑜𝑃 𝑘′𝑙′ 𝜏 − 𝑑𝑃𝑘𝑙 𝜏 − 𝑑𝑃𝑘′𝑙′ 𝜏 , then: - For first passenger, 𝑃𝑘𝑙 𝜏 : 𝑒𝑎𝑟𝑟_𝑃𝑘𝑙 𝜏 ≤ 𝑊𝑇 𝑉𝑟𝑠 𝜏 𝑃𝑘′𝑙′ 𝜏 + 𝑡𝑠𝑒𝑟𝑣𝑖𝑐𝑒 𝑃𝑘′𝑙′ 𝜏 𝑉𝑟𝑠 𝜏 + 𝑇𝑇𝑜 𝑃𝑘′𝑙′ 𝜏 𝑑 𝑃𝑘𝑙 𝜏 ≤ 𝑙𝑎𝑟𝑟_𝑃𝑘𝑙 𝜏 (14) - For second passenger, 𝑃𝑘′𝑙′ 𝜏 : 𝑒𝑎𝑟𝑟_𝑃𝑘′𝑙′ 𝜏 ≤ 𝑡𝑠𝑒𝑟𝑣𝑖𝑐𝑒_𝑃𝑘𝑙 𝜏 𝑉𝑟𝑠 𝜏 + 𝑇𝑇𝐼 ≤ 𝑙𝑎𝑟𝑟_𝑃𝑘′𝑙′ 𝜏 (15) where 𝑇𝑇𝐼 = 𝑇𝑇𝑖 𝑉𝑟𝑠 𝜏 − 𝑜𝑃𝑘𝑙 𝜏 −𝑜 𝑃 𝑘′𝑙′ 𝜏 − 𝑑 𝑃𝑘𝑙 𝜏 −𝑑 𝑃𝑘′𝑙′ 𝜏 (16) Else if 𝑅𝑜𝑢𝑡𝑒𝑉𝑟𝑠𝜏 _𝑃𝑘𝑙 𝜏 _𝑃𝑘′𝑙′ 𝜏 is 𝑖𝑉𝑟𝑠𝜏 − 𝑜𝑃𝑘𝑙 𝜏 − 𝑜𝑃 𝑘′𝑙′ 𝜏 − 𝑑𝑃 𝑘′𝑙′ 𝜏 − 𝑑𝑃𝑘𝑙 𝜏 , then: 180 IIUM Engineering Journal, Vol. 22, No. 1, 2021 Hamim et al. https://doi.org/10.31436/iiumej.v22i1.1520 - For first passenger, 𝑃𝑘𝑙 𝜏 : 𝑒𝑎𝑟𝑟_𝑃𝑘′𝑙′ 𝜏 ≤ 𝑊𝑇 𝑉𝑟𝑠 𝜏 𝑃𝑘′𝑙′ 𝜏 + 𝑡𝑠𝑒𝑟𝑣𝑖𝑐𝑒_ 𝑃𝑘′𝑙′ 𝜏 𝑉𝑟𝑠 𝜏 + 𝑇𝑇𝑜 𝑃𝑘′𝑙′ 𝜏 𝑑 𝑃𝑘′𝑙′ 𝜏 ≤ 𝑙𝑎𝑟𝑟_𝑃𝑘′𝑙′ 𝜏 (17) - For second passenger, 𝑃𝑘′𝑙′ 𝜏 : 𝑒𝑎𝑟𝑟_𝑃𝑘𝑙 𝜏 ≤ 𝑡𝑠𝑒𝑟𝑣𝑖𝑐𝑒_𝑃𝑘𝑙 𝜏 𝑉𝑟𝑠 𝜏 + 𝑇𝑇𝐼𝐼 ≤ 𝑙𝑎𝑟𝑟_𝑃𝑘𝑙 𝜏 (18) where 𝑇𝑇𝐼𝐼 = 𝑇𝑇𝑖 𝑉𝑟𝑠 𝜏 − 𝑜𝑃𝑘𝑙 𝜏 −𝑜 𝑃 𝑘′𝑙′ 𝜏 − 𝑑 𝑃 𝑘′𝑙′ 𝜏 −𝑑 𝑃𝑘𝑙 𝜏 (19) c) The time spent by a customer in a vehicle cannot exceed a given value (maximum ride time) : If 𝑹𝒐𝒖𝒕𝒆𝑽𝒓𝒔𝝉 _𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 = 𝒊𝑽𝒓𝒔𝝉 − 𝒐𝑷𝒌𝒍 𝝉 − 𝒐𝑷 𝒌′𝒍′ 𝝉 − 𝒅𝑷𝒌𝒍 𝝉 − 𝒅𝑷𝒌′𝒍′ 𝝉 then: - For passenger 𝑷𝒌𝒍 𝝉 : 𝑻𝑻𝒐 𝑷𝒌𝒍 𝝉 𝒐𝑷𝒌′𝒍′ 𝝉 + 𝒕𝒔𝒆𝒓𝒗𝒊𝒄𝒆_ 𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 + 𝑻𝑻𝒐 𝑷𝒌′𝒍′ 𝝉 𝒅𝑷𝒌𝒍 𝝉 ≤ 𝒕𝒎𝒂𝒙𝒓𝒊𝒅𝒆 𝑷𝒌𝒍 𝝉 (20) - For passenger 𝑷𝒌′𝒍′ 𝝉 : 𝑻𝑻𝒐 𝑷𝒌′𝒍′ 𝝉 𝒅𝑷𝒌𝒍 𝝉 +𝒕𝒔𝒆𝒓𝒗𝒊𝒄𝒆_𝑷𝒌𝒍 𝝉 𝑽𝒓𝒔 𝝉 + 𝑻𝑻𝒅 𝑷𝒌𝒍 𝝉 𝒅𝑷𝒌′𝒍′ 𝝉 ≤ 𝒕𝒎𝒂𝒙𝒓𝒊𝒅𝒆 𝑷𝒌′𝒍′ 𝝉 (21) Else if 𝑹𝒐𝒖𝒕𝒆𝑽𝒓𝒔𝝉 _𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 is 𝒊𝑽𝒓𝒔𝝉 − 𝒐𝑷𝒌𝒍 𝝉 − 𝒐𝑷 𝒌′𝒍′ 𝝉 − 𝒅𝑷 𝒌′𝒍′ 𝝉 − 𝒅𝑷𝒌𝒍 𝝉 , then: - For passenger 𝑷𝒌𝒍 𝝉 : 𝑻𝑻𝒐 𝑷𝒌𝒍 𝝉 𝒐𝑷𝒌′𝒍′ 𝝉 + (𝟐 × 𝒕𝒔𝒆𝒓𝒗𝒊𝒄𝒆_ 𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 ) + 𝑻𝑻𝒐 𝑷𝒌′𝒍′ 𝝉 𝒅𝑷𝒌′𝒍′ 𝝉 + 𝑻𝑻𝒅𝑷𝒌′𝒍′ 𝝉 𝒅𝑷𝒌𝒍 𝝉 ≤ 𝒕𝒎𝒂𝒙𝒓𝒊𝒅𝒆 𝑷𝒌𝒍 𝝉 (22) - For passenger 𝑷𝒌′𝒍′ 𝝉 : 𝑻𝑻𝒐 𝑷𝒌′𝒍′ 𝝉 −𝒅𝑷𝒌′𝒍′ 𝝉 ≤ 𝒕𝒎𝒂𝒙𝒓𝒊𝒅𝒆 _𝑷𝒌′𝒍′ 𝝉 (23) 2) Capacity feasibility: The number of passengers in each request must be less than or equal to available vehicle’s capacity: 𝒒𝑷𝒌𝒍 𝝉 + 𝒒𝑷𝒌′𝒍′ 𝝉 ≤ 𝑸𝑽𝒓𝒔𝝉 (24) Next, we define model of the optimization problem of ride splitting service with resource sharing scheme on graph 𝑮𝟐 𝝉 = (𝑵𝟐 𝝉,𝑬𝟐 𝝉), and we use the following decision variables: 𝒙 𝑷𝒌𝒍 𝝉 ,𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 = { 𝟏 , 𝐢𝐟 𝐩𝐚𝐬𝐬𝐞𝐧𝐠𝐞𝐫𝐬 𝑷𝒌𝒍 𝝉 𝐚𝐧𝐝 𝑷𝒌′𝒍′ 𝝉 𝐬𝐞𝐫𝐯𝐞𝐝 𝐛𝐲 𝐯𝐞𝐡𝐢𝐜𝐥𝐞 𝑽𝒓𝒔 𝝉 𝟎,𝐨𝐭𝐡𝐞𝐫𝐰𝐢𝐬𝐞 𝑧 𝑉𝑟𝑠 𝜏 𝑃𝑘𝑙 𝜏 = { 1 , if vehicle 𝑉𝑟𝑠 𝜏 serves passenger 𝑃𝑘𝑙 𝜏 0, otherwise 𝒘 𝑽𝒓𝒔 𝝉 𝑷𝒌𝒍 𝝉 = { 𝟏, 𝐢𝐟 𝐩𝐥𝐚𝐭𝐟𝐨𝐫𝐦 𝐢𝐧𝐝𝐞𝐱 𝒌 = 𝒓 𝜶, 𝐨𝐭𝐡𝐞𝐫𝐰𝐢𝐬𝐞 𝜶 is profit sharing multiplier, where 𝟎 < 𝜶 < 𝟏 𝑉𝑟𝑠 𝜏_𝑜𝑐𝑐 = { 2,if 𝑥𝑃𝑘𝑙 𝜏 _𝑃𝑘′𝑙′ 𝜏 𝑉𝑟𝑠 𝜏 = 1 and 𝑃𝑘𝑙 𝜏 ≠ 𝑃𝑘′𝑙′ 𝜏 1, if 𝑥 𝑃𝑘𝑙 𝜏 _𝑃𝑘′𝑙′ 𝜏 𝑉𝑟𝑠 𝜏 = 1 and 𝑃𝑘𝑙 𝜏 = 𝑃𝑘′𝑙′ 𝜏 0,else 𝑄𝑉𝑟𝑠𝜏 = { 4, if 𝑉𝑟𝑠 𝜏 𝑜𝑐𝑐 = 0 4 − 𝑞𝑃𝑘𝑙 𝜏 , if 𝑉𝑟𝑠 𝜏 𝑜𝑐𝑐 = 1 0,else 181 IIUM Engineering Journal, Vol. 22, No. 1, 2021 Hamim et al. https://doi.org/10.31436/iiumej.v22i1.1520 For each feasible match (𝑽𝒓𝒔 𝝉 𝑷𝒌𝒍 𝝉 ,𝑽𝒓′𝒔′ 𝝉 𝑷𝒌′𝒍′ 𝝉 ) 𝐢𝐧 𝑬𝟐 𝝉, calculate: 1) The operational cost of 𝑹𝒐𝒖𝒕𝒆𝑽𝒓𝒔𝝉 _𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 : 𝒐𝒑.𝒄𝒐𝒔𝒕 𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 = 𝒄𝑽𝒓𝒔𝝉 × 𝑫𝒊𝒔𝒕𝒂𝒏𝒄𝒆𝑽𝒓𝒔𝝉 _𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 (25) where 𝒄𝑽𝒓𝒔𝝉 is vehicle 𝑽𝒓𝒔 𝝉 ’s operational cost per one distance unit 2) The profit of 𝑹𝒐𝒖𝒕𝒆𝑽𝒓𝒔𝝉 _𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 : 𝒑𝒓𝒐𝒇𝒊𝒕 𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 = (𝒘 𝑽𝒓𝒔 𝝉 𝑷𝒌𝒍 𝝉 𝒛 𝑽𝒓𝒔 𝝉 𝑷𝒌𝒍 𝝉 𝑭𝑷𝒌𝒍 𝝉 ) + (𝒘 𝑽𝒓𝒔 𝝉 𝑷𝒌′𝒍′ 𝝉 𝒛 𝑽𝒓𝒔 𝝉 𝑷𝒌′𝒍′ 𝝉 𝑭 𝑷𝒌′𝒍′ 𝝉 ) − 𝒐𝒑.𝒄𝒐𝒔𝒕 𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 (26) 3) The total waiting time of passenger for a ride on 𝑹𝒐𝒖𝒕𝒆𝑽𝒓𝒔𝝉 _𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 : 𝑾𝑻 𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 = 𝑾𝑻 𝑽𝒓𝒔 𝝉 𝑷𝒌𝒍 𝝉 + 𝑾𝑻 𝑽𝒓𝒔 𝝉 𝑷𝒌′𝒍′ 𝝉 (27) 4) The money value of total passenger’s waiting time: 𝑾𝑻̅̅̅̅̅ 𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 = 𝒘𝒕̿̿̿̿ 𝒎𝒐𝒏𝒆𝒚 × 𝑾𝑻𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 (28) where 𝒘𝒕̿̿̿̿ 𝒎𝒐𝒏𝒆𝒚 is money value of passenger’s waiting time per one time unit 5) The weight of edge (𝑽𝒓𝒔 𝝉 𝑷𝒌𝒍 𝝉 ,𝑽𝒓′𝒔′ 𝝉 𝑷𝒌′𝒍′ 𝝉 ): 𝑾𝒈 𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 = 𝒑𝒓𝒐𝒇𝒊𝒕 𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 𝑾𝑻̅̅̅̅̅ 𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 (29) The weight 𝑾𝒈 𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 is defined as a ratio between the profit gained by a vehicle and the money value of total passenger’s waiting time. The mathematical model for the problem is: 𝑴𝒂𝒙 ∑ 𝑾𝒈̅̅ ̅̅̅ 𝑷𝒌𝒍 𝝉 ,𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 ((𝑽𝒓𝒔 𝝉 ,𝑷𝒌𝒍 𝝉 ),(𝑽𝒓𝒔 𝝉 ,𝑷𝒌′𝒍′ 𝝉 ))∈𝑬𝟐 𝝉 𝒙 𝑷𝒌𝒍 𝝉 ,𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 (30) Subject to: ∑ 𝒙 𝑷𝒌𝒍 𝝉 ,𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 𝑽𝒓𝒔 𝝉 ∈𝑽𝝉,𝑷𝒌′𝒍′ 𝝉 ∈𝑷𝝉:((𝑽𝒓𝒔 𝝉 ,𝑷𝒌𝒍 𝝉 ),(𝑽𝒓𝒔 𝝉 ,𝑷𝒌′𝒍′ 𝝉 ))∈𝑬𝟐 𝝉 + ∑ 𝒙 𝑷𝒂𝒃 𝝉 𝑷𝒂′𝒃′ 𝝉 𝑽𝒓𝒔 𝝉 𝑽𝒓𝒔 𝝉 ∈𝑽𝝉,𝑷𝒂𝒃 𝝉 ∈𝑷𝝉:((𝑽𝒓𝒔 𝝉 ,𝑷𝒂𝒃 𝝉 ),(𝑽𝒓𝒔 𝝉 ,𝑷𝒂′𝒃′ 𝝉 ))∈𝑬𝟐 𝝉 ≤ 𝟏, ∀ 𝑷𝒌𝒍 𝝉 ,𝑷 𝒌𝒍′ 𝝉 ,𝑷𝒂𝒃 𝝉 ,𝑷 𝒂′𝒃′ 𝝉 ∈ 𝑷𝝉, 𝐟𝐨𝐫 𝒌 = 𝒂′, 𝒍 = 𝒃′ (31) ∑ 𝒙 𝑷𝒌𝒍 𝝉 ,𝑷𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 𝑷𝒌𝒍 𝝉 ,𝑷𝒌′𝒍′ 𝝉 ∈𝑷𝝉:((𝑽𝒓𝒔 𝝉 ,𝑷𝒌𝒍 𝝉 ),(𝑽𝒓𝒔 𝝉 ,𝑷𝒌′𝒍′ 𝝉 ))∈𝑬𝟐 𝝉 ≤ 𝟏 , ∀ 𝑽𝒓𝒔 𝝉 ∈ 𝑽𝝉 (32) 𝒙 𝑷𝒌𝒍 𝝉 ,𝑷 𝒌′𝒍′ 𝝉 𝑽𝒓𝒔 𝝉 ∈ {𝟎,𝟏}, ∀ 𝑷𝒌𝒍 𝝉 ,𝑷𝒌′𝒍′ 𝝉 ∈ 𝑷𝝉;∀ 𝑽𝒓𝒔 𝝉 ∈ 𝑽𝝉 (33) The objective function (30) maximizes the total weight. Constraints (31) ensures each passenger at most in one feasible match, and (32) ensures each vehicle at most in one feasible match. Finally, constraints (33) enforce the binary condition. In the next section, we will present the solution algorithm to solve the optimization problem in each period. 4. SOLUTION METHODOLOGY The optimization problem will be solved in three stages. At first, algorithm 1 is performed to obtain a set of feasible pair of a vehicle and the first customer by generating the first weighted 182 IIUM Engineering Journal, Vol. 22, No. 1, 2021 Hamim et al. https://doi.org/10.31436/iiumej.v22i1.1520 bipartite graph. Algorithm 2 in the second stage is performed to obtain the set of feasible pair of a vehicle and two request customers by generating second modified weighted bipartite graph. Finally, algorithm 3 is performed to obtain the optimal assignment of vehicle and passenger pair. Procedure to generate first weighted bipartite graph is presented in the following algorithm. Algorithm 1. Generating first weighted bipartite graph Step 1: Node construction. Initially, there is no node in graph 𝑮𝟏 𝝉 .Let 𝒕 be time at which the first request from a customer arrived. Set period 𝝉 = 𝝉𝟏, where the first period 𝝉𝟏 = [𝒕,𝒕 + 𝜹 − 𝑶𝒑𝒕_𝑻), 𝜹 be an acceptable time limit for a customer waiting for a decision to be picked up; and 𝑶𝒑𝒕𝑻 be time to do assignment optimization. For the next period, set 𝝉𝒊 = [𝒕 + (𝒊 − 𝟏)𝜹 − 𝑶𝒑𝒕𝑻, 𝒕 + 𝒊 ∗ 𝜹 − 𝑶𝒑𝒕𝑻), for 𝒊 = 𝟐,𝟑,… . In this study we set 𝜹 = 60” and 𝑶𝒑𝒕𝑻 = 𝟏𝟎”. Create a set 𝑷 𝝉consisting of all request customers with request time 𝒕𝒓𝒆𝒒𝒖𝒆𝒔𝒕_𝑷𝒌𝒍 𝝉 in period 𝝉𝒊 and all assigned customers in the previous period 𝝉𝒊−𝟏 who still not get a customer pair to share a ride in ride splitting service. Create a set 𝑽𝝉consisting of all available vehicle in period 𝝉𝒊 including all vehicle which still only assigned to one request customer in the previous period 𝝉𝒊−𝟏. Then set 𝑵𝟏 𝝉 = 𝑽𝝉 ∪ 𝑷𝝉, be the set of nodes of graph 𝑮𝟏 𝝉. Step 2: Shortest path, distance and travel time determination. For each customer in 𝑷𝝉 and each vehicle in 𝑽𝝉, determine shortest path passenger’s origin-destination to get 𝒓𝒐𝒖𝒕𝒆𝒐𝒅 𝑷𝒌𝒍 𝝉 and from vehicle’s current location to passenger’s origin to get 𝒓𝒐𝒖𝒕𝒆𝒊𝑽𝒓𝒔𝝉 𝒐𝑷𝒌𝒍 𝝉 . Then, calculate the distance 𝑫𝒐𝒅 𝑷𝒌𝒍 𝝉 and 𝑫𝒊𝑽𝒓𝒔𝝉 𝑶𝑷𝒌𝒍 𝝉 , travel time 𝑻𝑻𝒐𝒅𝑷𝒌𝒍 𝝉 and 𝑻𝑻𝒊𝑽𝒓𝒔𝝉 𝑶𝑷𝒌𝒍 𝝉 . Step 3: Departure time windows, arrival time windows, and max ride time calculation. For each customer in 𝑷𝝉, calculate earliest and latest departure time, earliest and latest arrival time and maximum ride time using equation (1)-(5). In this study we set 𝜺,𝝁 = 𝟎.𝟐, 𝝀𝒆𝒂𝒓𝒍𝒚 = 𝟓′, 𝝀𝒍𝒂𝒕𝒆 = 𝟏𝟓′ and 𝒕𝒔𝒆𝒓𝒗𝒊𝒄𝒆_ 𝑷𝒌𝒍 𝝉 𝑽𝒓𝒔 𝝉 = 𝟏′. Step 4: Feasible match determination and edge construction. For each vehicle in 𝑽𝝉 and for each customer in 𝑷𝝉, determine whether a vehicle is feasible to serve a customer by using feasible criterion (6)-(8). Then node 𝑽𝒓𝒔 𝝉 in 𝑽𝝉 is adjacent to node 𝑷𝒌𝒍 𝝉 in 𝑷𝝉, or (𝑽𝒓𝒔 𝝉 ,𝑷𝒌𝒍 𝝉 ) is an edge in 𝑬𝟏 𝝉 if and only if vehicle 𝑽𝒓𝒔 𝝉 is met the feasible criterion in (6) – (8) to serve customer 𝑷𝒌𝒍 𝝉 . Then 𝑬𝟏 𝝉 = {(𝑽𝒓𝒔 𝝉 ,𝑷𝒌𝒍 𝝉 )|𝑷𝒌𝒍 𝝉 𝐚𝐧𝐝 𝑽𝒓𝒔 𝝉 𝐚𝐫𝐞 𝐟𝐞𝐚𝐬𝐢𝐛𝐥𝐞 match; 𝑽𝒓𝒔 𝝉 ∈ 𝑽𝝉, 𝑷𝒌𝒍 𝝉 ∈ 𝑷𝝉}. Step 5: Weight calculation. For each edge in 𝑬𝟏 𝝉 calculate its weight, where the weight is the fare that has to be paid by passenger 𝑷𝒌𝒍 𝝉 if served by vehicle 𝑽𝒓𝒔 𝝉 , using equation (9). Step 6: Output. From step 1 to step 5, set graph 𝑮𝟏 𝝉 = (𝑵𝟏 𝝉,𝑬𝟏 𝝉). The next stage is to perfomed Algorithm 2 with the following procedure. Algorithm 2. Generating The Second Weighted Bipartite Graph Step 1: Node construction. Initially, there is no node in graph 𝑮𝟐 𝝉. Let 𝑵𝟏 𝝉 and 𝑬𝟏 𝝉 be the set of nodes and the set of edges of 𝑮𝟏 𝝉 from algorithm 1 For 𝑽𝒓𝒔 𝝉 ∈ 𝑽𝝉 and 𝑷𝒌𝒍 𝝉 ∈ 𝑷𝝉, create a set 𝑽𝝉𝑷𝝉 consisting all pairs of 𝑽𝒓𝒔 𝝉 𝑷𝒌𝒍 𝝉 , where (𝑽𝒓𝒔 𝝉 ,𝑷𝒌𝒍 𝝉 ) is an edge in 𝑬𝟏 𝝉. Create a set 𝑫𝑽𝝉𝑷𝝉, a duplication set of 𝑽𝝉𝑷𝝉. That is 𝑫𝑽𝝉𝑷𝝉 = {𝑽𝒓′𝒔′ 𝝉 𝑷𝒌′𝒍′ 𝝉 |𝐢𝐟 𝑽𝒓𝒔 𝝉 𝑷𝒌𝒍 𝝉 ∈ 𝑽𝝉𝑷𝝉}. Then set 𝑵𝟐 𝝉 = 𝑽𝝉𝑷𝝉 ∪ 𝑫𝑽𝝉𝑷𝝉 be a bipartite set of nodes of graph 𝑮𝟐 𝝉. 183 IIUM Engineering Journal, Vol. 22, No. 1, 2021 Hamim et al. https://doi.org/10.31436/iiumej.v22i1.1520 Step 2: Vehicle route, distance and travel time determination. For each pair of nodes 𝑽𝒓𝒔 𝝉 𝑷𝒌𝒍 𝝉 in 𝑽𝝉𝑷𝝉 and 𝑽𝒓′𝒔′ 𝝉 𝑷𝒌′𝒍′ 𝝉 in 𝑫𝑽𝝉𝑷𝝉, with 𝒓 = 𝒓′ 𝐚𝐧𝐝 𝒔 = 𝒔′, determine shortest path from vehicle’s current location to the first passenger’s origin, then to the second passenger’s origin and next to the closest passenger’s destination to get 𝑹𝒐𝒖𝒕𝒆𝑽𝒓𝒔𝝉 _𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 . Then, 𝑹𝒐𝒖𝒕𝒆𝑽𝒓𝒔𝝉 _𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 is the shortest path between route 𝒊𝑽𝒓𝒔𝝉 − 𝒐𝑷𝒌𝒍 𝝉 − 𝒐𝑷 𝒌′𝒍′ 𝝉 − 𝒅𝑷𝒌𝒍 𝝉 − 𝒅𝑷𝒌′𝒍′ 𝝉 and route 𝒊𝑽𝒓𝒔𝝉 − 𝒐𝑷𝒌𝒍 𝝉 − 𝒐𝑷 𝒌′𝒍′ 𝝉 − 𝒅𝑷 𝒌′𝒍′ 𝝉 − 𝒅𝑷𝒌𝒍 𝝉 . Next, calculate the distance: 𝑫𝒊𝒔𝒕𝒂𝒏𝒄𝒆𝑽𝒓𝒔𝝉 _𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 and travel time: 𝑻𝑻𝑽𝒓𝒔𝝉 _𝑷𝒌𝒍 𝝉 _𝑷𝒌′𝒍′ 𝝉 . Step 3: Feasible match determination and edge construction. For nodes 𝑉𝑟𝑠 𝜏𝑃𝑘𝑙 𝜏 in 𝑉𝜏𝑃𝜏 and 𝑉𝑟′𝑠′ 𝜏 𝑃𝑘′𝑙′ 𝜏 in 𝐷𝑉𝜏𝑃𝜏, with 𝑟 = 𝑟′ and 𝑠 = 𝑠′, check if the vehicle 𝑉𝑟𝑠 𝜏 is feasible to serve customers 𝑃𝑘𝑙 𝜏 and 𝑃𝑘′𝑙′ 𝜏 by using feasible criterion in (10)-(24), then node 𝑉𝑟𝑠 𝜏𝑃𝑘𝑙 𝜏 is adjacent to node 𝑽𝒓′𝒔′ 𝝉 𝑷𝒌′𝒍′ 𝝉 , or (𝑽𝒓𝒔 𝝉 𝑷𝒌𝒍 𝝉 ,𝑽𝒓′𝒔′ 𝝉 𝑷𝒌′𝒍′ 𝝉 ) is an edge in 𝑬𝟐 𝝉. Step 4: Weight calculation. For each edge in 𝑬𝟐 𝝉, calculate vehicle’s operational cost and profit gained, passenger’s total waiting time and its money value, and the edge weight using formula (25)-(29). Step 5: Output. From step 1-step 4, set graph 𝑮𝟐 𝝉 = (𝑵𝟐 𝝉,𝑬𝟐 𝝉). Finally, performed The Greedy Heuristic Algorithm based on [20] to solve the mathematical model (30)-(33) for the optimization problem. Algorithm 3. The Greedy Heuristic Algorithm Step 1: Select the edge in graph 𝑮𝟐 𝝉 with the largest weight and add it to the matching. Let the edge with the largest weight in 𝑬𝟐 𝝉 is (𝑽𝒓𝒔 𝝉 𝑷𝒌𝒍 𝝉 ,𝑽𝒓′𝒔′ 𝝉 𝑷𝒌′𝒍′ 𝝉 ), then set the vehicle 𝑽𝒓𝒔 𝝉 serves customers 𝑷𝒌𝒍 𝝉 and 𝑷𝒌′𝒍′ 𝝉 . Update the vehicle 𝑽𝒓𝒔 𝝉 ’ s occupation: 𝑽𝒓𝒔 𝝉 _𝒐𝒄𝒄 and capacity: 𝑸𝑽𝒓𝒔𝝉 . Step 2: Delete the endpoints of the edge selected in step 1, all nodes related to vehicles 𝑽𝒓𝒔 𝝉 and 𝑽𝒓′𝒔′ 𝝉 , customers 𝑷𝒌𝒍 𝝉 and 𝑷𝒌′𝒍′ 𝝉 , and all edges incident to these nodes. If the graph contains at least two nodes, return to step 1; otherwise stop. 5. COMPUTATIONAL EXPERIMENTS To test the model and its solution methodology, in this paper we use two periods of time, which consists of six request customers and six available vehicles and three values for parameter 𝜶 (profit sharing multiplier factor) as comparation, those are 85%,90% and 95%. The consideration to use three 𝜶 values is based on the willingness of the driver (and the operator) to share profit with the initial operator requested by the customer and to keep being profitable for the serving driver (operator). All experiments in this study is coded with Python 3.7. In the meantime, the number of operators (platforms) providing online taxi services used is two platforms, while the tariff for the ride-splitting service charged to each passenger from each platform is using three cases as a comparison. Those cases are the equal tariff, 5% and 10% difference in tariff. Table 1 describes the fare charged by platform 1 and 2 for all cases. In the first case, the fare charged by platform 1 and 2 is 2$/ distance unit. At the second case, the difference in tariff between platform 1 and 2 is 5%, whereas the fare charged by platform 1 to the customer in ride-splitting service is 2$ /distance unit, while in platform 2, it is 2.1$ /distance unit. While in the last case, the difference in tariff between platform 1 and 2 is 10%, whereas the fare charged by platform 1 to the customer in ride-splitting service is 2$ /distance unit while in platform 2, it is 2.2$ /distance unit. With the three fare difference cases, it will be seen that the resource sharing scheme used with a certain limit value of profit share, can still be profitable for the driver (and operator) even though there is a difference for the 184 IIUM Engineering Journal, Vol. 22, No. 1, 2021 Hamim et al. https://doi.org/10.31436/iiumej.v22i1.1520 cheaper fare paid by the customer. Next, the optimization of the ride-splitting service with the resource sharing scheme compared to the optimization without using the scheme, by taking the value of 𝒘 𝑽𝒓𝒔 𝝉 𝑷𝒌𝒍 𝝉 = 𝟏 Table 1. Fare charged by Platform 1 and 2 Case Fare of Platform 1 per distance unit Fare of Platform 2 per distance unit For Equal tariff 2$ 2$ For 5% difference 2$ 2.1$ For 10% difference 2$ 2.2$ Gradually, there come four request customers in the first period and two request customers in the second period, where there are four available vehicles in the first period and two new available vehicles in the second period. Let figure 1 ilustrates example of a road transportation network where the passenger’s origin and vehicle location are located in the first period. Assume that one distance unit can be traveled in one time unit. The weight of each link describes the distance between two different nodes, for example the distance between node 1 and 4 is 16 distance unit. Fig.1 Ilustration of Road Transportation Network in The First Period Let the first period start at 700 and end at 701, and the list of customer requests given in the table 2. From table 2, in the first period, there are four customers: 𝑃11,𝑃21,𝑃12 and 𝑃22 which request ride splitting services. Let 𝑃11 be the first customer which request a service (vehicle) from platform 1, 𝑃21 be the first customer which request a service from platform 2. The origin (pick up) location of 𝑃11 is at node 2, meanwhile the origin of 𝑃21 is at node 14. The destination (drop off) location of 𝑃11 is at node 8 and 𝑃21 is at node 6. The number of passengers per request of customer 𝑃11 is 1 passenger, which has to be picked up between 7 01 - 716, meanwhile a request of customer 𝑃21 consists of 2 passengers, which has to be picked up between 7 01 - 716. Table 2. List of Customer Requests in The First Period 185 IIUM Engineering Journal, Vol. 22, No. 1, 2021 Hamim et al. https://doi.org/10.31436/iiumej.v22i1.1520 customer 𝒕𝒓𝒆𝒒𝒖𝒆𝒔𝒕_𝑷𝒌𝒍 𝒐𝑷𝒌𝒍 𝒅𝑷𝒌𝒍 𝒆𝒅𝒆𝒑𝒕_𝑷𝒌𝒍 𝒍𝒅𝒆𝒑𝒕_𝑷𝒌𝒍 𝒒𝑷𝒌𝒍 𝑷𝟏𝟏 7 00 2 8 701 716 1 𝑷𝟏𝟐 7 00 5 15 701 716 2 𝑷𝟐𝟏 7 00 14 6 701 716 2 𝑷𝟐𝟐 7 00 13 7 701 716 1 There are four available vehicles in the first period, which are vehicle 𝑉11 and 𝑉12 from platform 1, and vehicle 𝑉21 and 𝑉22 from platform 2. Data of available vehicle’s locations and capacities between 700-701 is given by table 3. Table 3. Data of Available Vehicles in The First Period vehicle 𝒊𝑽𝒓𝒔 𝒕𝒊𝑽𝒓𝒔 𝑽𝒓𝒔 𝑸𝑽𝒓𝒔 𝑽𝟏𝟏 4 7 00 4 𝑽𝟐𝟏 1 7 00 4 𝑽𝟏𝟐 15 7 00 4 𝑽𝟐𝟐 12 7 00 4 Let 𝑐𝑉𝑟𝑠𝜏 , the vehicle cost per distance unit, is 1$ and 𝑤𝑡 ̿̿̿̿ 𝑚𝑜𝑛𝑒𝑦, the money value of passenger’s waiting time, is 1$ per minute. Using the solution method in section 4 with three fare difference cases, the optimum assignment result in the first period is described on table 4 and the profit gained by driver is described in figure 2. Table 4. The Optimum Assignment Result in Period 1 Ride Splitting with resource sharing scheme, for 𝜶 = 𝟖𝟓%, 90% and 95% Ride Splitting without resource sharing scheme Assignment Result in Period 1 𝑉21 is serving 𝑃11and 𝑃21 𝑉22 is serving 𝑃22 𝑉11 is serving 𝑃12 𝑉12 is not yet serving any customer 𝑉22 is serving 𝑃21 and 𝑃22 𝑉12 is serving 𝑃11 𝑉11 is serving 𝑃12 . 𝑉21 is not yet serving any customer Total vehicle used 3 3 Total passenger’s waiting time 17 minutes 31 minutes It can be seen from table 4, total passenger’s waiting time to be picked up by a vehicle for the ride splitting service with sharing platform scheme in the first period is 17 minutes, while in the ride splitting service without sharing platform scheme is 31 time unit. 186 IIUM Engineering Journal, Vol. 22, No. 1, 2021 Hamim et al. https://doi.org/10.31436/iiumej.v22i1.1520 Fig.2 Profit gained comparison in the first period Based on figure 2, the profit gained by ride splitting service without sharing platform scheme (A) for equal tariff case is 116$, while ride splitting service with sharing platform scheme for 𝛼 =85% (B), 𝛼 =90% (C) and 𝛼 =95% (D) are 113,7$, 116,8$ and 119,9$ respectively. It can be seen that profit gained by ride splitting service with sharing platform scheme using 𝛼 =90% (C) and 95% (D) for all fare difference cases are higher than ride splitting service without sharing platform scheme (A). While, ride splitting service with sharing platform scheme using 𝛼 =85% (B) for all fare difference cases is gaining profit lower than ride splitting service without sharing platform scheme (A). Based on the simulation, the parameter value for profit sharing platform scheme will result in higher profit than without sharing platform scheme when the value is greater than or equal to 0.9 ( 𝛼 =90%). In the second period, there are two new customer requests, summarized in the following table 5. Table 5. List of Customer Requests in Second Period customer 𝒕𝒓𝒆𝒒𝒖𝒆𝒔𝒕_𝑷𝒌𝒍 𝒐𝑷𝒌𝒍 𝒅𝑷𝒌𝒍 𝒆𝒅𝒆𝒑𝒕_𝑷𝒌𝒍 𝒍𝒅𝒆𝒑𝒕_𝑷𝒌𝒍 𝒒𝑷𝒌𝒍 𝑷𝟏𝟑 7 01 16 7 702 717 1 𝑷𝟐𝟑 7 01 11 15 702 717 2 Meanwhile, available vehicles in the second period is summarized in table 6, where there are three vehicles originating from the first period and two new vehicles from the second period. Based on the assignment result in the first period, vehicle 𝑉11 is serving passenger 𝑃12, so that available seat left is only 2, while vehicle 𝑉22 is serving passenger 𝑃22, so that vehicle capacity left is only 3 seats. Table 6. Data of Available Vehicles in The Second Period vehicle 𝒊𝑽𝒓𝒔 𝒕𝒊𝑽𝒓𝒔 𝑽𝒓𝒔 𝑸𝑽𝒓𝒔 𝑽𝟏𝟏 4 7 00 2 𝑽𝟏𝟐 15 7 00 4 𝑽𝟐𝟐 12 7 00 3 𝑽𝟏𝟑 3 7 01 4 𝑽𝟐𝟑 10 7 01 4 Using the solution method in section 4, the optimum assignment results in the first and second period is described on table 7 and profit gained comparison for three fare difference cases is described in figure 3. 187 IIUM Engineering Journal, Vol. 22, No. 1, 2021 Hamim et al. https://doi.org/10.31436/iiumej.v22i1.1520 Table 7.The Optimum Assignment Results in Two Periods Ride Splitting with resource sharing scheme, for 𝜶 = 𝟖𝟓%, 90% or 95% Ride Splitting without resource sharing scheme Assignment Result in Period 1 and 2 𝑉21 is serving 𝑃11 and 𝑃21 𝑉22 is serving 𝑃22 𝑉11 is serving 𝑃12 and 𝑃23 𝑉23 is serving 𝑃13 𝑉12 and 𝑉13 are not yet serving any customer 𝑉22 is serving 𝑃21 and 𝑃22 𝑉12 is serving 𝑃11 𝑉11 is serving 𝑃12 . 𝑉13 is serving 𝑃13 𝑉23 is serving 𝑃23 𝑉21 is not yet serving any customer Total vehicle used 4 (or 66,7% of vehicle availability) 5 (or 83,3% of vehicle availability) Total passenger’s waiting time 33 minutes 50 minutes From table 7, it can be seen that total passenger’s waiting time for ride splitting service with sharing platform scheme case is only 33 minutes, lower than without sharing platform scheme case, which is 50 minutes, and so is the total vehicle used, the ride splitting service with the scheme only use 66,7% of available vehicles, while the ride splitting service without the scheme use 83,3% of available vehicles. Fig.3 Total Profit Gained Comparison For Total Two Periods Based on figure 3, total profit gained by ride splitting service without sharing platform scheme (A) for equal tariff case is 144$, while ride splitting service with sharing platform scheme for 𝛼 =85% (B), 𝛼 =90% (C) and 𝛼 =95% (D) are 158,9$, 166,6$ and 174,3$ respectively. It can be seen that profit gained by ride splitting service with sharing platform scheme using 𝛼 =85% (B), 90%(C) and 95% (D) for all fare difference cases are higher than ride splitting service without sharing platform scheme (A). 6. CONCLUSIONS Based on the experiment, it can be concluded that the optimization of ride-splitting service with resource-sharing scheme can reduce the vehicle used for online taxi services. Moreover, it can generate higher overall profit for all vehicles serving passenger, and the parameter value A B C D equal tariff 144 158.9 166.60 174.30 5% tariff difference 152.3 166.915 174.71 182.51 10% tariff difference 160.6 174.93 182.82 190.71 0 50 100 150 200 250 P R O F IT P E R I O D 1 - 2 A B C D equal tariff 144 158.9 166.60 174.30 5% tariff difference 152.3 166.915 174.71 182.51 10% tariff difference 160.6 174.93 182.82 190.71 0 50 100 150 200 250 P R O F IT P E R I O D 1 - 2 188 IIUM Engineering Journal, Vol. 22, No. 1, 2021 Hamim et al. https://doi.org/10.31436/iiumej.v22i1.1520 for profit sharing platform scheme is better greater than or equal to 0,9 (𝛼 = 90%). Meanwhile, total passenger’s waiting time to be picked up by a vehicle for ride splitting service with sharing platform scheme case is lower than without sharing platform scheme case. This study is still using small instance as an experiment to prove that the optimization of ride-splitting service with resource-sharing scheme is possible to be utilized, so that for the next research, bigger data usage is required ACKNOWLEDGEMENT The authors would like to thank to Kemenristek Dikti and LPDP for scholarship in order the completion of doctoral studies at Universitas Indonesia. REFERENCES [1] Burhan, H., Soehodho, S., and Nahry. (2017). Review on the Development of Ride Sharing System using Online Transportation Service in Jakarta. Proceeding of 6th IEEE International Conference on Advanced Logistics and Transport, pp.173-178. [2] Anderson, D. N.,(2014). “Not Just A Taxi’? For-Profit Ridesharing, Driver Strategies, and VMT. Transportation 41, pp.1099–1117. http://dx.doi.org/10.1007/ s11116-014-9531-8. [3] Rayle, L., Dai, D., Chan, N., Cervero,R., and Shaheen, S. (2015). Just a better taxi? A survey- based comparison of taxis, transit, and ridesourcing services in San Francisco. Transp. Policy, pp.168–178. [4] Shaheen, S., Cohen, a., and Zohdy, I. (2016). Shared Mobility: Current Practices and Guiding Principles. U.S. Department of Transportation, Federal Highway Administration. Report No. FHWA-HOP-16-022. [5] Chen, L., Mislove, A., and Wilson, C. (2015). Peeking Beneath the Hood of Uber. In Proc. of the ACM Conference on Internet Measurement Conference, ACM. [6] Burhan, H., Soehodho, S., and Nahry. (2019). A Resource Sharing (Sharing Platform) Scheme on Online Taxi Services. MATEC Web of Conferences,vol. 270, art.no.03010. [7] Agatz, N.A.H., Erera, A.L., Savelsbergh, M.W.P., and Wang, X. (2012). Optimization for dynamic ride-sharing: a review. European Journal of Operational Research, vol.223 (2), pp.295–303. [8] Lu, Q., and Dessouky, M. (2006). A new insertion-based construction heuristic for solving the pickup and delivery problem with hard time windows. European Journal of Operational Research, vol.175 (2), pp.672–687. [9] Dumas, Y., Desrosiers, J., and Soumis, F. (1991). The pickup and delivery problem with time windows. European Journal of Operations Research, vol.54, pp.7–22. [10] Toth,P. and Vigo, D. (2002). The Vehicle Routing Problem. Siam, Philadelphia http://dx.doi.org/10.1137/1.9780898718515. [11] Hosni, H., Naoum-Sawaya, J., and Artail, H. (2014). The shared-taxi problem: Formulation and solution methods. Transp. Res. Part B: Methodol. 70, pp. 303–318. [12] Wang, X., Dessouky, M., and Ordonez, F. (2015). A pickup and delivery problem for ridesharing considering congestion. Transp. Lett.: Int. J. Transp. Res.,1942787515Y- 000000002. [13] Santos, D.O., and Xavier, E.C. (2015). Taxi and Ride Sharing: A Dynamic Dial-a-Ride Problem with Money as an Incentive. Expert Systems with Applications, vol. 42, pp.6728–6737. [14] Mahmoudi, M., and Zhou, X. (2017). Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: a dynamic programming approach based on state-space-time network representations. Transport. Res. Part B: Methodol. Vol.89, pp.19– 42. [15] Bei, X., and Zhang, S. (2018). Algorithms for trip-vehicle assignment in ride-sharing. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pp. 3–9. 189 IIUM Engineering Journal, Vol. 22, No. 1, 2021 Hamim et al. https://doi.org/10.31436/iiumej.v22i1.1520 [16] Banerjee, S., Johari, R., and Riquelme, C. (2015). Pricing in ride-share platforms: A queueing- theoretic approach. Working Paper. Available at SSRN: https://ssrn.com/abstract=2568258 or http://dx.doi.org/10.2139/ssrn.2568258. [17] Chen, Y., and Hu, M. (2017). Pricing and Matching with Forward-Looking Buyers and Sellers. Working Paper. Available at SSRN: https://ssrn.com/abstract=2859864 or http://dx.doi.org/10.2139/ssrn.2859864. [18] Zha, L., Yin, Y., and Xu, Z. (2018). Geometric matching and spatial pricing in ride-sourcing markets. Transportation Research Part C: Emerging Technologies, Vol.92, pp.58-75. [19] Yang, H., Shao, C., Wang, H., and Ye, J. (2018). Integrated Reward Scheme and Surge Pricing in a Ride Sourcing Market. Report, June 18, 2018. Available at SSRN: https://ssrn.com/abstract=3198081 or http://dx.doi.org/10.2139/ssrn.3198081. [20] Evans, J.R., and Minieka, E. (1992). Optimization algorithms for networks and graphs, 2nd edition Revised. New York. 190 https://ssrn.com/abstract=3198081