| Summary: | 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 <i>c</i> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>CS</mi><mrow><mi>s</mi><mi>u</mi><mi>m</mi></mrow></msub></semantics></math></inline-formula>) and to serve the maximum number of requests with the minimum total latency (called <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>CS</mi><mrow><mi>l</mi><mi>a</mi><mi>t</mi></mrow></msub></semantics></math></inline-formula>). In addition, we studied the special case where the pick-up and drop-off locations of a request coincide. Both problems <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>CS</mi><mrow><mi>s</mi><mi>u</mi><mi>m</mi></mrow></msub></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>CS</mi><mrow><mi>l</mi><mi>a</mi><mi>t</mi></mrow></msub></semantics></math></inline-formula> are APX-hard when <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>c</mi><mo>≥</mo><mn>2</mn></mrow></semantics></math></inline-formula>. We propose an algorithm, called the transportation algorithm (TA), which is a <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mn>2</mn><mi>c</mi><mo>−</mo><mn>1</mn><mo>)</mo></mrow></semantics></math></inline-formula>-approximation (resp. <i>c</i>-approximation) algorithm for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>CS</mi><mrow><mi>s</mi><mi>u</mi><mi>m</mi></mrow></msub></semantics></math></inline-formula> (resp. <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>CS</mi><mrow><mi>l</mi><mi>a</mi><mi>t</mi></mrow></msub></semantics></math></inline-formula>); these bounds are shown to be tight. We also considered the special case where each car serves exactly two requests, i.e., <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>c</mi><mo>=</mo><mn>2</mn></mrow></semantics></math></inline-formula>. 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. <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>5</mn><mo>/</mo><mn>3</mn></mrow></semantics></math></inline-formula>) for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>CS</mi><mrow><mi>s</mi><mi>u</mi><mi>m</mi></mrow></msub></semantics></math></inline-formula> (resp. <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>CS</mi><mrow><mi>l</mi><mi>a</mi><mi>t</mi></mrow></msub></semantics></math></inline-formula>), and these ratios are better than the ratios of the individual algorithms, the TA and MA.
|
|---|