Problem with A-n32-k5 instance

[FGE85]

Hello, I have been facing some issues with the library trying to solve the well know A-n32-k5 instance.

Here is my code:

import vrpy
import pandas as pd
from networkx import DiGraph
from vrpy import VehicleRoutingProblem
from scipy.spatial import distance_matrix

df = pd.read_excel("Instancias.xlsx", sheet_name = "A-n32-k5")
n = len(df)
demanda = df["Demanda"]
df.drop(["Demanda"], axis=1, inplace=True)
Q = 100
#Primero hay que generar la matriz de distancia

M = pd.DataFrame(distance_matrix(df.values, df.values), index=df.index, columns=df.index)

G = DiGraph()
#Definir las aristas del grafo
for i in range(n):
if i != 0:
G.add_edge("Source", i, cost=M.at[0, i].astype(int))
G.add_edge(i, "Sink", cost=M.at[i, 0].astype(int))
else:
continue

for i in range(n):
if i == 0:
continue
else:
for w in range(n):
if w==0:
continue
elif i<w:
G.add_edge(i, w, cost=M.at[i, w].astype(int))
else:
continue

#cargar las demandas
for v in G.nodes():
if v not in ["Source", "Sink"]:
G.nodes[v]["demand"] = demanda[v]

#Corro
prob = VehicleRoutingProblem(G)
prob.num_vehicles = 5
prob.load_capacity = Q
prob.solve(time_limit=5)

And this is what I'm getting:
Traceback (most recent call last):
File "C:\Users\agumo\AppData\Local\Programs\Python\Python310\lib\code.py", line 90, in runcode
exec(code, self.locals)
File "", line 32, in
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\vrpy\vrp.py", line 254, in solve
self._solve(dive, solver)
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\vrpy\vrp.py", line 493, in _solve
self._column_generation()
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\vrpy\vrp.py", line 516, in _column_generation
self._find_columns()
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\vrpy\vrp.py", line 570, in _find_columns
self._more_routes = self._solve_subproblem_with_heuristic(
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\vrpy\vrp.py", line 633, in _solve_subproblem_with_heuristic
more_columns = self._attempt_solve_best_edges1(
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\vrpy\vrp.py", line 676, in _attempt_solve_best_edges1
self.routes, self._more_routes = subproblem.solve(
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\vrpy\subproblem_cspy.py", line 246, in solve
alg = BiDirectional(
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\cspy\algorithms\bidirectional.py", line 110, in init
check(G, max_res, min_res, direction, REF_callback, name)
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\cspy\checking.py", line 78, in check
raise Exception('\n'.join('{}'.format(item) for item in errors))
Exception: Elements of input lists must be numbers

df has three columns one for longitude, another for latitude and the last for the demand of the node.

Thank you for your time. Hope this can be solved.

[Kuifje02]

This looks like an error returned by cspy. Which version of cspy are you using ? @torressa the check method seems unhappy about something.

[Halvaros]

Hi, I can have a look at it. Is it ok if I take a look this week-end, it has been a long time since I worked on this. 🙂 Best regards, Halvard 7. sep. 2022 kl. 14:27 skrev RomainM ***@***.***>:  This looks like an error returned by cspy. Which version of cspy are you using ? @Halvaros<https://github.com/Halvaros> the check method seems unhappy about something. — Reply to this email directly, view it on GitHub<#134 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AIZOVGTBNULZEKI25BO7WOLV5CC3DANCNFSM6AAAAAAQF2O6AE>. You are receiving this because you were mentioned.Message ID: ***@***.***>

[FGE85]

Hi, I appreciate both of your answers.

I`m currently using the 1.02 version of cspy that happens to be the latest (according to python)

[torressa]

Hmm I've tried the standard vrp format (e.g. see here) with the parser in benchmarks/ and it works as expected.
Can you please share your Instancias.xlsx file so we can reproduce it, it is very likely just some format error from converting from a data frame (as indicated in the error).

Also, very nice to see that you are still around and keen @Halvaros! :)

[torressa]

@FGE85, particularly, when setting the cost attribute for each edge, you are converting data frame entries to numpy.int64.

>>> c = df.at[0,0].astype(int)
>>> type(c)
<class 'numpy.int64'>

this should be a Python standard int, not a numpy.int64. You can do

>>> c = int(df.at[0,0])
>>> type(c)
<class 'int'>

Sorry but this interfaces with another language and I need it to be Python standard int otherwise I would have to interface numpy.int64 as well.

[FGE85]

Hello,

I have tried your solution, but now I'm getting:
INFO:vrpy.vrp:new upper bound : max num stops = 16
INFO:vrpy.vrp:Clarke & Wright solution found with value 1513 and 8 vehicles
INFO:vrpy.vrp:Greedy solution found with value 1929 and 10 vehicles
INFO:vrpy.vrp:iteration 0, 300000
Traceback (most recent call last):
File "C:\Users\agumo\AppData\Local\Programs\Python\Python310\lib\code.py", line 90, in runcode
exec(code, self.locals)
File "", line 5, in
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\vrpy\vrp.py", line 254, in solve
self._solve(dive, solver)
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\vrpy\vrp.py", line 493, in _solve
self._column_generation()
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\vrpy\vrp.py", line 516, in _column_generation
self._find_columns()
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\vrpy\vrp.py", line 570, in _find_columns
self._more_routes = self._solve_subproblem_with_heuristic(
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\vrpy\vrp.py", line 633, in _solve_subproblem_with_heuristic
more_columns = self._attempt_solve_best_edges1(
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\vrpy\vrp.py", line 676, in _attempt_solve_best_edges1
self.routes, self._more_routes = subproblem.solve(
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\vrpy\subproblem_cspy.py", line 246, in solve
alg = BiDirectional(
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\cspy\algorithms\bidirectional.py", line 110, in init
check(G, max_res, min_res, direction, REF_callback, name)
File "C:\Users\agumo\PycharmProjects\Lupin\venv\lib\site-packages\cspy\checking.py", line 78, in check
raise Exception('\n'.join('{}'.format(item) for item in errors))
Exception: Elements of input lists must be numbers

This is the instancias file:
Instancias.xlsx

[torressa]

You just need to convert all the occurrences. The following works:
(there is a different issue now unrelated to this one, but I will open a separate item for this).

import vrpy
import pandas as pd
from networkx import DiGraph
from vrpy import VehicleRoutingProblem
from scipy.spatial import distance_matrix

df = pd.read_excel("tests/Instancias.xlsx", sheet_name="A-n32-k5")
n = len(df)
demanda = df["Demanda"]
df.drop(["Demanda"], axis=1, inplace=True)
Q = 100
# Primero hay que generar la matriz de distancia

M = pd.DataFrame(
    distance_matrix(df.values, df.values), index=df.index, columns=df.index
)

G = DiGraph()
# Definir las aristas del grafo
for i in range(n):
    if i != 0:
        G.add_edge("Source", i, cost=int(M.at[0, i]))
        G.add_edge(i, "Sink", cost=int(M.at[i, 0]))
    else:
        continue

for i in range(n):
    if i == 0:
        continue
    else:
        for w in range(n):
            if w == 0:
                continue
            elif i < w:
                G.add_edge(i, w, cost=int(M.at[i, w]))
            else:
                continue

# cargar las demandas
for v in G.nodes():
    if v not in ["Source", "Sink"]:
        G.nodes[v]["demand"] = demanda[v]

# Corro
prob = VehicleRoutingProblem(G)
prob.num_vehicles = 5
prob.load_capacity = Q
prob.solve(time_limit=5)