-
|
First of all, thank you very much for this package. It is very easy to understand and great to dive into vehicle routing. I wanted to ask if it is possible to use PyVRP in a dynamic way. |
Beta Was this translation helpful? Give feedback.
Replies: 2 comments 5 replies
-
|
Hi @johege! 👋 We do not support this directly, unfortunately. But it should not be hard to do, following the example on how to write your own def solve(data, prev_best=None):
rng = RandomNumberGenerator(seed=42)
pm = PenaltyManager.init_from(data)
pop = Population(broken_pairs_distance)
neighbours = compute_neighbours(data)
ls = LocalSearch(INSTANCE, rng, neighbours)
for node_op in NODE_OPERATORS:
ls.add_node_operator(node_op(data))
for route_op in ROUTE_OPERATORS:
ls.add_route_operator(route_op(data))
init = [Solution.make_random(data, rng) for _ in range(25)]
if prev_best:
init.append(prev_best)
algo = GeneticAlgorithm(data, pm, rng, pop, ls, srex, init)
return algo.run(stop=MaxRuntime(10))Suppose we have some initial data object, res0 = solve(data0)then add some clients to obtain res1 = solve(data1, res0.best)This should work. With new clients, I hope this helps. Please let us know if you have any further questions! |
Beta Was this translation helpful? Give feedback.
-
|
Hi @N-Wouda, Thanks for the quick reply. It's really cool how quickly you respond to the issues and discussions in this repo. 😄 if prev_best:
init.append(prev_best)added the original best solution to the Here's the adapted code. Maybe it helps someone else as well 😄 def solve(new_data, prev_data=None, prev_best=None):
rng = RandomNumberGenerator(seed=42)
pm = PenaltyManager.init_from(new_data)
pop = Population(broken_pairs_distance)
neighbours = compute_neighbours(new_data)
ls = LocalSearch(new_data, rng, neighbours)
for node_op in NODE_OPERATORS:
ls.add_node_operator(node_op(new_data))
for route_op in ROUTE_OPERATORS:
ls.add_route_operator(route_op(new_data))
init = [Solution.make_random(new_data, rng) for _ in range(25)]
if prev_best:
num_old_clients = prev_data.num_clients prev_data.num_depots
num_new_clients = new_data.num_clients new_data.num_depots
new_clients_ids = list(range(num_old_clients, num_new_clients))
new_route = Route(
data=new_data,
visits=new_clients_ids,
vehicle_type=0
)
new_routes = prev_best.routes()
new_routes.append(new_route)
adapted_prev_best = Solution(new_data, new_routes)
init.append(adapted_prev_best)
algo = GeneticAlgorithm(new_data, pm, rng, pop, ls, srex, init)
return algo.run(stop=MaxRuntime(10), display=True)There are probably smarter ways to integrate the new clients into the previous routes. But this works for now. |
Beta Was this translation helpful? Give feedback.
-
|
That's a nice solution! Looking at it again, I think the local search can also do these insertions for you, as well as a bit of further optimisation with the newly adjusted data. That should reduce the code a bit: if prev_best:
adapted_prev_best = ls(prev_best, pm.cost_evaluator())
init.append(adapted_prev_best) |
Beta Was this translation helpful? Give feedback.
-
|
Ah yes. That seems to work as well at least on a small example. Thanks again. When using this approach, it seems that the inserted solution is taken as the Feas. best at the beginning. But it takes about the same time for the Feas. avg. to reach similar values as if the prev. best solution wasn't used.
Both approaches seem to take about the same amount of time to converge to a near-best value in this example. |
Beta Was this translation helpful? Give feedback.
-
|
That's one of the reasons we don't spend a lot of time improving our initial pool of solutions: it rarely matters whether we started from good or random solutions after a few hundred iterations. In your case, since you add only a few clients compared to the overall problem size, perhaps you can restart from the population at the end of your previous run? Running the local search over each of the feasible and infeasible solutions in the old population before inserting them into the new one would essentially warm-start the entire algorithm. But whether that makes much of a difference I cannot say. |
Beta Was this translation helpful? Give feedback.
-
|
That's right. I thought about using the whole previous population. I just wasn't familiar enough with the code yet to do that. def solve(new_data, prev_pop=None, max_runtime=60, seed=42):
rng = RandomNumberGenerator(seed=seed)
pm = PenaltyManager.init_from(new_data)
pop = Population(broken_pairs_distance)
neighbours = compute_neighbours(new_data)
ls = LocalSearch(new_data, rng, neighbours)
for node_op in NODE_OPERATORS:
ls.add_node_operator(node_op(new_data))
for route_op in ROUTE_OPERATORS:
ls.add_route_operator(route_op(new_data))
if prev_pop:
init = []
for sol in prev_pop:
adapted_prev_sol = ls(sol, pm.cost_evaluator())
init.append(adapted_prev_sol)
else:
init = [Solution.make_random(new_data, rng) for _ in range(25)]
algo = GeneticAlgorithm(new_data, pm, rng, pop, ls, srex, init)
return algo.run(stop=MaxRuntime(max_runtime), display=True), algo._popIn my small example, this actually seems to bring some improvement. The warm-start variant seems to converge to a good solution faster within the first couple of iterations than starting from scratch. (I gave the calculations a higher MaxRuntime this time)
I only tested this with one dataset and a random seed. So this may not be generalizable. But it seems promising for my case, if you want to get good solutions for a slightly adapted problem relatively fast. |
Beta Was this translation helpful? Give feedback.
-
|
That looks correct to me, yes. Nice to see it speed up convergence quite a bit! If you want, a small improvement could be to just return Thanks for sharing! |
Beta Was this translation helpful? Give feedback.
That's right. I thought about using the whole previous population. I just wasn't familiar enough with the code yet to do that.
I think I have that implemented now: