Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems - Kelin Luo; Frits C. R. Spieksma (Algorithms, 2022)
Motivated by applications in ride-sharing and truck-delivery, we study the problem of matching a number of requests and assigning them to cars. A number of cars are given, each of which consists of a location and a speed, and a number of requests are given, each of which consists of a pick-up location and a drop-off location. Serving a request means that a car must first visit the pick-up location of the request and then visit the drop-off location. Each car can only serve at most c requests. Each assignment can yield multiple different serving routes and corresponding serving times, and our goal was to serve the maximum number of requests with the minimum travel time (called <semantics>CSsum</semantics>) and to serve the maximum number of requests with the minimum total latency (called <semantics>CSlat</semantics>). In addition, we studied the special case where the pick-up and drop-off locations of a request coincide. Both problems <semantics>CSsum</semantics> and <semantics>CSlat</semantics> are APX-hard when <semantics>c≥2</semantics>. We propose an algorithm, called the transportation algorithm (TA), which is a <semantics>(2c−1)</semantics>-approximation (resp. c-approximation) algorithm for <semantics>CSsum</semantics> (resp. <semantics>CSlat</semantics>); these bounds are shown to be tight. We also considered the special case where each car serves exactly two requests, i.e., <semantics>c=2</semantics>. In addition to the TA, we investigated another algorithm, called the match-and-assign algorithm (MA). Moreover, we call the algorithm that outputs the best of the two solutions found by the TA and MA the CA. We show that the CA is a two-approximation (resp. <semantics>5/3</semantics>) for <semantics>CSsum</semantics> (resp. <semantics>CSlat</semantics>), and these ratios are better than the ratios of the individual algorithms, the TA and MA.