I encountered the problem below and the only solution I came up with is branch and bound like that is used in TSP and I don’t think the bound I used is good enough. Are there any better idea on this?
Consider a graph $G$ that consists of an undirected bipartite graph and another vertex $O$ that is connected to all the other vertices. Assume the weight of the edges are positive and the weights obey the triangle inequality. Find a cycle in $G$ that involves $O$ s.t. the total weight is $\leq$ some given value $t$ and maximize the total number of vertices it passes through.