Click here to Skip to main content
15,921,716 members
Home / Discussions / Algorithms
   

Algorithms

 
GeneralRe: String reversal algorithm Pin
Member 147935355-Apr-20 19:52
Member 147935355-Apr-20 19:52 
QuestionTravelling Salesman Problem Pin
wscwt0118-Mar-20 7:39
wscwt0118-Mar-20 7:39 
AnswerRe: Travelling Salesman Problem Pin
k505418-Mar-20 8:48
mvek505418-Mar-20 8:48 
GeneralRe: Travelling Salesman Problem Pin
wscwt0118-Mar-20 11:12
wscwt0118-Mar-20 11:12 
GeneralRe: Travelling Salesman Problem Pin
Member 147935355-Apr-20 19:53
Member 147935355-Apr-20 19:53 
AnswerRe: Travelling Salesman Problem Pin
Greg Utas18-Mar-20 9:28
professionalGreg Utas18-Mar-20 9:28 
GeneralRe: Travelling Salesman Problem Pin
wscwt0118-Mar-20 11:11
wscwt0118-Mar-20 11:11 
QuestionVehicle routing problem for large graph Pin
Member 147325527-Mar-20 12:23
Member 147325527-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. D'Oh! | :doh:

- 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 :/
GeneralRe: Vehicle routing problem for large graph Pin
harold aptroot7-Mar-20 13:35
harold aptroot7-Mar-20 13:35 
GeneralRe: Vehicle routing problem for large graph Pin
Member 147325528-Mar-20 0:51
Member 147325528-Mar-20 0:51 
GeneralRe: Vehicle routing problem for large graph Pin
harold aptroot8-Mar-20 4:28
harold aptroot8-Mar-20 4:28 
GeneralRe: Vehicle routing problem for large graph Pin
Member 147325528-Mar-20 6:41
Member 147325528-Mar-20 6:41 
GeneralRe: Vehicle routing problem for large graph Pin
harold aptroot8-Mar-20 7:48
harold aptroot8-Mar-20 7:48 
GeneralRe: Vehicle routing problem for large graph Pin
Member 147325528-Mar-20 8:07
Member 147325528-Mar-20 8:07 
AnswerRe: Vehicle routing problem for large graph Pin
Hailu Worku Obsse17-Mar-20 20:15
professionalHailu Worku Obsse17-Mar-20 20:15 
QuestionRecursion Pin
Member 1475643326-Feb-20 10:10
Member 1475643326-Feb-20 10:10 
AnswerRe: Recursion Pin
Daniel Pfeffer26-Feb-20 21:22
professionalDaniel Pfeffer26-Feb-20 21:22 
GeneralRe: Recursion Pin
Member 1475643326-Feb-20 22:39
Member 1475643326-Feb-20 22:39 
GeneralRe: Recursion Pin
Daniel Pfeffer26-Feb-20 23:25
professionalDaniel Pfeffer26-Feb-20 23:25 
GeneralRe: Recursion Pin
Member 1475643326-Feb-20 23:33
Member 1475643326-Feb-20 23:33 
QuestionNegating a number Pin
Nand3219-Feb-20 2:53
Nand3219-Feb-20 2:53 
AnswerRe: Negating a number PinPopular
Richard MacCutchan19-Feb-20 3:04
mveRichard MacCutchan19-Feb-20 3:04 
GeneralRe: Negating a number Pin
Nand3219-Feb-20 3:08
Nand3219-Feb-20 3:08 
GeneralRe: Negating a number Pin
Richard MacCutchan19-Feb-20 3:47
mveRichard MacCutchan19-Feb-20 3:47 
AnswerRe: Negating a number PinPopular
Richard Deeming19-Feb-20 3:23
mveRichard Deeming19-Feb-20 3:23 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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