15,921,716 members
Home / Discussions / Algorithms

# Algorithms

 Re: String reversal algorithm Member 147935355-Apr-20 19:52 Member 14793535 5-Apr-20 19:52
 Travelling Salesman Problem wscwt0118-Mar-20 7:39 wscwt01 18-Mar-20 7:39
 Re: Travelling Salesman Problem k505418-Mar-20 8:48 k5054 18-Mar-20 8:48
 Re: Travelling Salesman Problem wscwt0118-Mar-20 11:12 wscwt01 18-Mar-20 11:12
 Re: Travelling Salesman Problem Member 147935355-Apr-20 19:53 Member 14793535 5-Apr-20 19:53
 Re: Travelling Salesman Problem Greg Utas18-Mar-20 9:28 Greg Utas 18-Mar-20 9:28
 Re: Travelling Salesman Problem wscwt0118-Mar-20 11:11 wscwt01 18-Mar-20 11:11
 Vehicle routing problem for large graph Member 147325527-Mar-20 12:23 Member 14732552 7-Mar-20 12:23
 Hello, I would like to ask for some hint about a problem that I am trying to solve. I have 3 cars that have to "explore" a map, I discretized the map with a graph. So now the problem is that I want to find a path, to visit all the nodes in the graph (the graph is very sparse with more or less 200 nodes) with 3 agents "exploring" in parallel. So I tried to formulate it with a vehicle routing problem (the equivalent of tsp but with more agents). To solve the VRP I implemented a tabu search. Problem is: it perform very poorly because a VRP (or even a TSP) problem with 200 nodes have a solution space too large So I was wondering if someone could suggest another approach. The problem, in short, is "visit all nodes of a graph, along the shortest path possible", passing more than 1 time on the same node is allowed, but of course not optimal, And yhea would be nice to have something that makes "easy" to split the "path" in n subpath since I have more than one agent that can explore at the same time you could imagine the problem as N cleaning robots that want to clean the floor, trying to clean it all, without overlapping. I don't need the optimal solution, just a "good one" that's why I tried with tabu search. I will be thankful for any suggestions! Edit: I would like to add some extra notes: - The tabu search that I implemented, for each solution, generate 500 neighbours (randomly permuting 2 nodes in the vector "node to visit"), I search for the best neighbor, an I store it in the tabu list. The tabu-list contains up to 10'000 solutions, and I ran 100'000 iterations. It took 12h and the solution is something like 10 times worse then optimality. - sadly, I am not allowed to formulate the problem with linear programming, because apparently it would be "too easy". (It doesn't depend on me) - I know that there's a solution that involves creating a minimum spanning tree from the graph, and just follow it, but I would like to try something more advanced than this :/
 Re: Vehicle routing problem for large graph harold aptroot7-Mar-20 13:35 harold aptroot 7-Mar-20 13:35
 Re: Vehicle routing problem for large graph Member 147325528-Mar-20 0:51 Member 14732552 8-Mar-20 0:51
 Re: Vehicle routing problem for large graph harold aptroot8-Mar-20 4:28 harold aptroot 8-Mar-20 4:28
 Re: Vehicle routing problem for large graph Member 147325528-Mar-20 6:41 Member 14732552 8-Mar-20 6:41
 Re: Vehicle routing problem for large graph harold aptroot8-Mar-20 7:48 harold aptroot 8-Mar-20 7:48
 Re: Vehicle routing problem for large graph Member 147325528-Mar-20 8:07 Member 14732552 8-Mar-20 8:07
 Re: Vehicle routing problem for large graph Hailu Worku Obsse17-Mar-20 20:15 Hailu Worku Obsse 17-Mar-20 20:15
 Recursion Member 1475643326-Feb-20 10:10 Member 14756433 26-Feb-20 10:10
 Re: Recursion Daniel Pfeffer26-Feb-20 21:22 Daniel Pfeffer 26-Feb-20 21:22
 Re: Recursion Member 1475643326-Feb-20 22:39 Member 14756433 26-Feb-20 22:39
 Re: Recursion Daniel Pfeffer26-Feb-20 23:25 Daniel Pfeffer 26-Feb-20 23:25
 Re: Recursion Member 1475643326-Feb-20 23:33 Member 14756433 26-Feb-20 23:33
 Negating a number Nand3219-Feb-20 2:53 Nand32 19-Feb-20 2:53
 Re: Negating a number Richard MacCutchan19-Feb-20 3:04 Richard MacCutchan 19-Feb-20 3:04
 Re: Negating a number Nand3219-Feb-20 3:08 Nand32 19-Feb-20 3:08
 Re: Negating a number Richard MacCutchan19-Feb-20 3:47 Richard MacCutchan 19-Feb-20 3:47
 Re: Negating a number Richard Deeming19-Feb-20 3:23 Richard Deeming 19-Feb-20 3:23
 Last Visit: 31-Dec-99 18:00     Last Update: 23-Jun-24 0:02 Refresh ᐊ Prev1...14151617181920212223 Next ᐅ

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.