Title: Cumulative Vehicle Routing Problem: A Column Generation Approach
Speaker: Rishi Ranjan Singh, Department of Computer Sc. and Engg., Indian Institute of Technology Ropar (IIT – Ropar), India.
Time & location: Wednesday Jan 28, 2015, 9 am in D511. This talk is presented by video conference.
In this talk, aimed at senior undergraduate and graduate students, we describe a computational approach for constructing approximate solutions to cumulative vehicle routing problems based on rounding solutions to a linear program. The linear program is based on the set cover formulation, and is solved using column generation. The pricing sub-problem is solved using dynamic programming. Simulation results show that the simple scalable strategy computes solutions with cost close to the lower bound given by the linear programming relaxation. We also give theoretical bounds on the integrality gap of the set cover formulation. This work, to appear in the proceedings of CALDAM 2015, is jointly with D. Gaur.
Bio: Mr. Singh is a PhD Scholar in the Department of Computer Science and Engineering at IIT Ropar. 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, network analysis and operations research.