Title: Approximation Algorithms for Cumulative VRP with Stochastic Demands
Speaker: Rishi Ranjan Singh, Department of Information Technology, Indian Institute of Information Technology Allahabad (IIT – Allahabad), India.
Location and time: B716, Friday Feb 12, 9 am
Abstract: In this talk we describe randomized approximation algorithms for metric stochastic cumulative VRP for split and unsplit deliveries. The approximation ratios are \(2(1 + \alpha)\) and 7 respectively, where \(\alpha\) is the approximation ratio for the metric TSP. The approximation factor is further reduced for trees and paths. We use and extend the results in [Technical note - approximation algorithms for VRP with stochastic demands. Operations Research, 2012] and [Routing vehicles to minimize fuel consumption. Operations Research Letters, 2013].
This work, to appear in the proceedings of CALDAM 2016, is jointly with D.R. Gaur and A. Mudgal.
Bio: Mr. Singh is a Visiting Faculty in the Department of Information Technology at IIIT Allahabd, India. He submitted his PhD in the Department of Computer Science and Engineering at IIT Ropar, India in 2015. He received his B. Tech (Hons.) in Computer Science and Engineering from UPTU Lucknow, India in 2011. He is interested in approximation algorithms for vehicle routing problems, social and complex network analysis, discrete optimization.