Vehicle routing problem for large graph
-
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. :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 :/
-
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. :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 :/
Member 14732552 wrote:
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)
Does that mean you can't use LP *at all*, or just that you can't simply formulate the whole thing as a big ILP model and make eg Gurobi or GLPK solve the whole thing? I ask this because if you can use LP as part of a bigger solution, you could still use it as a very effective heuristic to base a Branch and Bound algorithm on.
-
Member 14732552 wrote:
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)
Does that mean you can't use LP *at all*, or just that you can't simply formulate the whole thing as a big ILP model and make eg Gurobi or GLPK solve the whole thing? I ask this because if you can use LP as part of a bigger solution, you could still use it as a very effective heuristic to base a Branch and Bound algorithm on.
Well maybe I could use it if it is part of something bigger, could you explain more how ti B&B works with LP? (Or also give me some reference)
-
Well maybe I could use it if it is part of something bigger, could you explain more how ti B&B works with LP? (Or also give me some reference)
It's on wikipedia as well. The basic idea is to recursively construct all solutions, but at every step down the recursion tree also optimistically estimate (using eg LP) how good the best possible solution in this sub-tree could be. If the estimate is worse than the best solution found thus far, there is no point exploring that sub-tree, and that lets you skip a (usually) huge amount of exploration. With LP based estimations, it can also easily happen that it actually gives an integer solution (that doesn't tend to happen early on, but it does tend to happen before the bottom of the search tree is reached) and in that case it would be the *actual* best solution in this sub-tree. There is an ILP formulation of VRP on the wikipedia page of VRP, dropping the integrality constraint turns it into an LP formulation suitable for such estimates. Some extras that strenthen the linear relaxation are also mentioned. Using just the "basic" formulation works, but the estimates are not very good then.
-
It's on wikipedia as well. The basic idea is to recursively construct all solutions, but at every step down the recursion tree also optimistically estimate (using eg LP) how good the best possible solution in this sub-tree could be. If the estimate is worse than the best solution found thus far, there is no point exploring that sub-tree, and that lets you skip a (usually) huge amount of exploration. With LP based estimations, it can also easily happen that it actually gives an integer solution (that doesn't tend to happen early on, but it does tend to happen before the bottom of the search tree is reached) and in that case it would be the *actual* best solution in this sub-tree. There is an ILP formulation of VRP on the wikipedia page of VRP, dropping the integrality constraint turns it into an LP formulation suitable for such estimates. Some extras that strenthen the linear relaxation are also mentioned. Using just the "basic" formulation works, but the estimates are not very good then.
Mmh that's very interesting, thanks a lot! So if I understood correctly I explore all solutions with recursion, using B&B to cut the branch that would lead (up to a gentle estimation) to solutions that are worse than "so far optimal". Plus when I am deep enough i "freeze" the solution found so far and I use LP to solve what's left. Is that right? Do you think this could be solved in less than 5 minutes considering that the size of the graph is ~250 nodes? And if I just use the B&B approach without the linear programming (which I am not 100% familiar) do you think this approach could work as well? Would It make sense to create a heuristic that makes explore first "hypothetically better solutions"? (not sure if I am able to do it) I am afraid that after the failure with the tabu search I could implement this and end up with something-not-working because of the size of the problem
-
Mmh that's very interesting, thanks a lot! So if I understood correctly I explore all solutions with recursion, using B&B to cut the branch that would lead (up to a gentle estimation) to solutions that are worse than "so far optimal". Plus when I am deep enough i "freeze" the solution found so far and I use LP to solve what's left. Is that right? Do you think this could be solved in less than 5 minutes considering that the size of the graph is ~250 nodes? And if I just use the B&B approach without the linear programming (which I am not 100% familiar) do you think this approach could work as well? Would It make sense to create a heuristic that makes explore first "hypothetically better solutions"? (not sure if I am able to do it) I am afraid that after the failure with the tabu search I could implement this and end up with something-not-working because of the size of the problem
Member 14732552 wrote:
Plus when I am deep enough i "freeze" the solution found so far and I use LP to solve what's left.
I wouldn't put it like that, it's more that the LP solution naturally tends to become integral at some point (meaning it's a "real solution", not just an estimate) and then you can use it directly. It's just something that happens automatically and you can use it as a shortcut when it does.
Member 14732552 wrote:
Do you think this could be solved in less than 5 minutes considering that the size of the graph is ~250 nodes?
IDK, I've solved TSP of that size and a bit faster. But VRP is a bit different. For both of them goes, how fast it is depends a lot on how good the estimates are. There are many advanced techniques to improve the basic LP, mostly techniques that look at a fractional solution and then generate a "cut" that adds a constraint to the LP such that it brings the new optimal solution closer to what the integer solution would be. Gomory cuts can be used, but the really high quality stuff is specific to the problem.
Member 14732552 wrote:
use the B&B approach without the linear programming
You can do that, you just need some optimistic estimate. It doesn't matter how you get it, but it should be optimistic: a pessimistic estimate (eg doing a quick greedy search or whatever) would mean that the sub-tree with the optimal solution in it might be skipped because the estimate said the sub-tree is bad.
Member 14732552 wrote:
Would It make sense to create a heuristic that makes explore first "hypothetically better solutions"? (not sure if I am able to do it)
There is a lot of freedom in the B&B framework. Nodes can be explored in basically whatever order, you can order the variables however you want (with an LP based estimate, an interesting strategy is picking a variable to branch on that the LP solution was "least sure about" - closest to 0.5 - rather than a variable that was close to 0 or 1), you can dynamically change the strategies even.
-
Member 14732552 wrote:
Plus when I am deep enough i "freeze" the solution found so far and I use LP to solve what's left.
I wouldn't put it like that, it's more that the LP solution naturally tends to become integral at some point (meaning it's a "real solution", not just an estimate) and then you can use it directly. It's just something that happens automatically and you can use it as a shortcut when it does.
Member 14732552 wrote:
Do you think this could be solved in less than 5 minutes considering that the size of the graph is ~250 nodes?
IDK, I've solved TSP of that size and a bit faster. But VRP is a bit different. For both of them goes, how fast it is depends a lot on how good the estimates are. There are many advanced techniques to improve the basic LP, mostly techniques that look at a fractional solution and then generate a "cut" that adds a constraint to the LP such that it brings the new optimal solution closer to what the integer solution would be. Gomory cuts can be used, but the really high quality stuff is specific to the problem.
Member 14732552 wrote:
use the B&B approach without the linear programming
You can do that, you just need some optimistic estimate. It doesn't matter how you get it, but it should be optimistic: a pessimistic estimate (eg doing a quick greedy search or whatever) would mean that the sub-tree with the optimal solution in it might be skipped because the estimate said the sub-tree is bad.
Member 14732552 wrote:
Would It make sense to create a heuristic that makes explore first "hypothetically better solutions"? (not sure if I am able to do it)
There is a lot of freedom in the B&B framework. Nodes can be explored in basically whatever order, you can order the variables however you want (with an LP based estimate, an interesting strategy is picking a variable to branch on that the LP solution was "least sure about" - closest to 0.5 - rather than a variable that was close to 0 or 1), you can dynamically change the strategies even.
Thank you very much, I will try this approach!
-
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. :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 :/
I have tried similar problem using Genetic Algorithm and the results were astonishing. I think trying Genetic Algorithm may be wonderful for you too in speeding the search time.