Abhimanyu Das
ABSTRACT
Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles located at depots to serve requests located on a metric space so as to minimize the total latency. In this paper, we consider point-to-point requests that come with source-destination pairs and release-time constraints that restrict when each request can be served. The point-to-point requests and release-time constraints model taxi rides and deliveries. For all the variants considered, we show constant-factor approximation algorithms based on a linear programming framework. To the best of our knowledge, these are the first set of results for the aforementioned variants of the minimum latency problems. Furthermore, we provide an empirical study of heuristics based on our theoretical algorithms on a real data set of taxi rides.
- Hernán Abeledo, Ricardo Fukasawa, Artur Pessoa, and Eduardo Uchoa. 2013. The time dependent traveling salesman problem: polyhedra and algorithm. Mathematical Programming Computation 5, 1 (01 Mar 2013), 27--55.Google Scholar
- Aamena Alshamsi, Sherief Abdallah, and Iyad Rahwan. 2009. Multiagent Selforganization for a Taxi Dispatch System. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS '09).Google Scholar
- F. Angel-Bello, Y. Cardona-Valdé A. Á. 2017. Mixed integer formulations for the multiple minimum latency problem. Operational Research (08 Feb 2017).Google Scholar
- Aaron Archer and Anna Blasiak. 2010. Improved Approximation Algorithms for the Minimum Latency Problem via Prize-collecting Strolls. In Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 429--447. http://dl.acm.org/citation.cfm?id=1873601.1873637 Google ScholarDigital Library
- Aaron Archer, Asaf Levin, and David P. Williamson. 2008. A Faster, Better Approximation Algorithm for the Minimum Latency Problem. SIAM J. Comput. 37, 5 (2008), 1472--1498. Google ScholarDigital Library
- Sanjeev Arora and George Karakostas. 2003. Approximation Schemes for Minimum Latency Problems. SIAM J. Comput. 32, 5 (2003), 1317--1337. Google ScholarDigital Library
- Giorgio Ausiello, Stefano Leonardi, and Alberto Marchetti-Spaccamela. 2000. On Salesmen, Repairmen, Spiders, and Other Traveling Agents. Springer Berlin Heidelberg, Berlin, Heidelberg, 1--16. Google ScholarDigital Library
- Avrim Blum, Prasad Chalasani, Don Coppersmith, Bill Pulleyblank, Prabhakar Raghavan, and Madhu Sudan. 1994. The Minimum Latency Problem. In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing (STOC '94). ACM, New York, NY, USA, 163--171. Google ScholarDigital Library
- Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, and Kunal Talwar. 2003. Paths, Trees, and Minimum Latency Tours. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS '03). IEEE Computer Society, Washington, DC, USA, 36--. http://dl.acm.org/citation.cfm?id=946243. 946316 Chandra Chekuri, Nitish Korula, and Martin Pá2. Improved Algorithms for Orienteering and Related Problems. ACM Trans. Algorithms 8, 3, Article 23 (July 2012), 27 pages. Google ScholarDigital Library
- Chandra Chekuri and Amit Kumar. 2004. Maximum Coverage Problem with Group Budget Constraints and Applications. Springer Berlin Heidelberg, Berlin, Heidelberg, 72--83.Google Scholar
- Abhimanyu Das, Sreenivas Gollapudi, Anthony Kim, Debmalya Panigrahi, and Chaitanya Swamy. 2018. Minimizing Latency in Online Ride and Delivery Services. (Feb 2018). Available at https://arxiv.org/abs/1802.02744. Google ScholarDigital Library
- Willem E. de Paepe, Jan Karel Lenstra, Jiri Sgall, Ren A. Sitters, and Leen Stougie. 2004. Computer-Aided Complexity Classification of Dial-a-Ride Problems. INFORMS Journal on Computing 16, 2 (2004), 120--132. Google ScholarDigital Library
- Jittat Fakcharoenphol, Chris Harrelson, and Satish Rao. 2003. The K-traveling Repairman Problem. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '03). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 655--664. http://dl.acm.org/citation.cfm? id=644108.644215 Google ScholarDigital Library
- Michel Goemans and Jon Kleinberg. 1996. An Improved Approximation Ratio for the Minimum Latency Problem. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '96). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 152--158. http://dl.acm.org/citation.cfm? id=313852.313909 Google ScholarDigital Library
- R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G.Rinnooy Kan. 1979. Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. In Discrete Optimization II, P.L. Hammer, E.L. Johnson, and B.H. Korte (Eds.). Annals of Discrete Mathematics, Vol. 5. Elsevier, 287 -- 326.Google Scholar
- Elias Koutsoupias, Christos Papadimitriou, and Mihalis Yannakakis. 1996. Searching a fixed graph. Springer Berlin Heidelberg, Berlin, Heidelberg, 280--289. Google ScholarDigital Library
- Zhixing Luo, Hu Qin, and Andrew Lim. 2014. Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints. European Journal of Operational Research 234, 1 (2014), 49--60. https://EconPapers.repec.org/RePEc: eee:ejores:v:234:y:2014:i:1:p:49--60Google ScholarCross Ref
- Isabel Méndez-Diaz, Paula Zabala, and Abilio Lucena. 2008. A New Formulation for the Traveling Deliveryman Problem. Discrete Appl. Math. 156, 17 (Oct. 2008), 3223--3237. Google ScholarDigital Library
- Nenad Mladenović, Dragan Urosević, and Said Hanafi. 2013. Variable neighborhood search for the travelling deliveryman problem. 4 11, 1 (01 Mar 2013), 57--73.Google Scholar
- Samuel Nucamendi-Guillèn, Iris Martinez-Salazar, Francisco Angel-Bello, and J Marcos Moreno-Vega. 2016. A mixed integer formulation and an efficient metaheuristic procedure for the k-Travelling Repairmen Problem. Journal of the Operational Research Society 67, 8 (01 Aug 2016), 1121--1134.Google ScholarCross Ref
- Christos H. Papadimitriou and Mihalis Yannakakis. 1993. The Traveling Salesman Problem with Distances One and Two. Math. Oper. Res. 18, 1 (Feb. 1993), 1--11.Google ScholarCross Ref
- Ian Post and Chaitanya Swamy. 2015. Linear Programming-based Approximation Algorithms for Multi-vehicle Minimum Latency Problems. In Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '15). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 512--531. http://dl.acm.org/citation.cfm?id=2722129.2722164 Google ScholarDigital Library
- Shiyou Qian, Jian Cao, Frèdèric Le Mouël, Issam Sahel, and Minglu Li. 2015. SCRAM: A Sharing Considered Route Assignment Mechanism for Fair Taxi Route Recommendations. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '15). ACM, New York, NY, USA, 955--964. Google ScholarDigital Library
- Meng Qu, Hengshu Zhu, Junming Liu, Guannan Liu, and Hui Xiong. 2014. A Costeffective Recommender System for Taxi Drivers. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '14). ACM, New York, NY, USA, 45--54. Google ScholarDigital Library
- Sartaj Sahni and Teofilo Gonzalez. 1976. P-Complete Approximation Problems. J. ACM 23, 3 (July 1976), 555--565. Google ScholarDigital Library
- Douglas O. Santos and Eduardo C. Xavier. 2013. Dynamic Taxi and Ridesharing: A Framework and Heuristics for the Optimization Problem. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI '13). AAAI Press, 2885--2891. http://dl.acm.org/citation.cfm?id=2540128.2540544 Google ScholarDigital Library
- Marcos Melo Silva, Anand Subramanian, Thibaut Vidal, and Luiz Satoru Ochi. 2012. A simple and effective metaheuristic for the Minimum Latency Problem. European Journal of Operational Research 221, 3 (2012), 513 -- 520.Google ScholarCross Ref
- Renè Sitters. 2002. The Minimum Latency Problem Is NP-Hard forWeighted Trees. In Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization. Springer-Verlag, London, UK, UK, 230--239. http://dl.acm.org/citation.cfm?id=645591.660083 Google ScholarDigital Library
- Renè Sitters. 2014. Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems. In Proceedings of the Twentyfifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '14). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 604--616. http: //dl.acm.org/citation.cfm?id=2634074.2634120 Google ScholarDigital Library
- M. Skutella. 2006. List Scheduling in Order of a-Points on a Single Machine. In Efficient Approximation and Online Algorithms. Springer, 250--291. Google ScholarDigital Library
- John N. Tsitsiklis. 1992. Special cases of traveling salesman and repairman problems with time windows. Networks 22, 3 (1992), 263--282.Google ScholarCross Ref
- Xianyuan Zhan, Xinwu Qian, and Satish V. Ukkusuri. 2014. Measuring the Efficiency of Urban Taxi Service System. In The Third International Workshop on Urban Computing (UrbComp '14).Google Scholar
- Xudong Zheng, Xiao Liang, and Ke Xu. 2012. Where to Wait for a Taxi?. In Proceedings of the ACM SIGKDD International Workshop on Urban Computing (UrbComp '12). ACM, New York, NY, USA, 149--156. Google ScholarDigital Library
- Chenguang Zhu and Balaji Prabhakar. 2017. Reducing Inefficiencies in Taxi Systems. In Proceedings of the Fifty-Sixth IEEE Conference on Decision and Control (CDC '17).Google ScholarCross Ref
Index Terms
- Minimizing Latency in Online Ride and Delivery Services
Recommendations
Passenger Trip Planning using Ride-Sharing Services
CHI '18: Proceedings of the 2018 CHI Conference on Human Factors in Computing SystemsRide-sharing can potentially address transportation challenges such as traffic congestion and air pollution by letting drivers share their cars unused capacity with a number of passengers. However, even though multiple ride-sharing services exist and ...
Poster: Vehicle Routing with Pickup and Delivery: A Greedy Approach
CHANTS '17: Proceedings of the 12th Workshop on Challenged NetworksRecently, bicycles have become popular in large cities and many bicycle sharing companies have established their own bike sharing systems. Extra vehicles are used to transport bikes among different bike stations, such that the number of bikes in each ...
Minimum Makespan Multi-Vehicle Dial-a-Ride
Dial-a-Ride problems consist of a set V of n vertices in a metric space (denoting travel time between vertices) and a set of m objects represented as source-destination pairs {(si,ti)}mi=1, where each object requires to be moved from its source to ...
Comments