facebook

twitter

youtube

Virtual Tour

Prof. Muralidhara

"(a) Project Objectives and Deliverables: The Vehicle Routing Problem (VRP) is to design an optimal route for a eet of vehicles to service a set of customers, given a set of practical constraints. In general the vechiles could be of di_erent type and capacity located at di_erent locations. The customers have di_erent demands, they may be known in advance or could be dynamic. The optimal schedule is characterized by minimal eet size and operational costs including costs for under loaded trips and waiting time etc. There are many variants of the Vehicle Routing Problem (VRP), the proposal is to study few variants, arraising in real world. Here we summerise some of the results that we have on our theoretical study on various Vehicle Routing Problem on a Circle and present some of the ongoing work and future work on BMTC data and the Dial a ride problem

(b) Milestones and Outcomes accomplished so far: (include publications, patent applications, software, prototypes, events and any other relevant outcome) we consider a special case in which requests are located on the circumference of a circle and the server moves only along the circumference of that circle. Depending on the minimization objective, we study two speci_c problems. One is N-OLTSP-C (N for Nomadic) in which the server should _nd a tour which starts at the origin O, serves all the requests and minimizes the time to serve the last request. The other is H-OLTSP-C (H for Homing) where there is an additional requirement to end the tour at the origin and the objective is to minimize the time to reach the origin after serving all the requests. For both the problems, we study the online algorithms and lower bounds on the competitive ratio. An online algorithm is said to be zealous if the server that is used by the online algorithm does not wait when there are unserved requests. For H-OLTSP-C, we propose a 2:5-competitive zealous online algorithm and claim the lower bounds of 1:75 and 2 on the competitive ratio of any zealous and non-zealous online algorithm. For N-OLTSP-C, we propose a 2:5-competitive zealous online algorithm and claim the lower bounds of 28/13 and 2 on the competitive ratio of any zealous and non-zealous online algorithm. Online Travelling Salesman Problem on a Circle, Vinay A Jawgal, V.N. Muralidhara, and P.S. Srinivasan Submitted for publication. "