FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
mage/python/vrp.py at main · memgraph/mage · GitHub
This repository was archived by the owner on Jan 23, 2026. It is now read-only.
memgraph
/
mage
Public archive
Notifications
You must be signed in to change notification settings
Fork
35
Star
331
Code
Issues
0
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
mage
/
python
/
vrp.py
Copy path
More file actions
More file actions
Latest commit
History
History
History
114 lines (83 loc) · 2.95 KB
Breadcrumbs
mage
/
python
/
vrp.py
Copy path
File metadata and controls
114 lines (83 loc) · 2.95 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
from
mage
.
geography
import
(
create_distance_matrix
,
LATITUDE
,
LONGITUDE
,
)
from
mage
.
constraint_programming
import
VRPConstraintProgrammingSolver
from
typing
import
Dict
,
List
import
mgp
__distance_matrix
=
None
__depot_index
=
None
MAX_DISTANCE_MATRIX_SIZE
=
100
def
get_distance_matrix
(
vertices
):
"""
Assigns distance matrix global object or returns if its already there.
"""
global
__distance_matrix
if
__distance_matrix
is
not
None
:
return
__distance_matrix
vertex_positions
:
List
[
Dict
[
str
,
float
]]
=
[]
for
vertex
in
vertices
:
vertex_positions
.
append
(
{
LATITUDE
:
vertex
.
properties
.
get
(
LATITUDE
),
LONGITUDE
:
vertex
.
properties
.
get
(
LONGITUDE
),
}
)
__distance_matrix
=
create_distance_matrix
(
vertex_positions
)
return
__distance_matrix
def
get_depot_index
(
vertices
:
mgp
.
Vertices
,
depot_node
:
mgp
.
Vertex
):
"""
Assigns depot index global variable or returns if its already there.
"""
global
__depot_index
if
__depot_index
is
not
None
:
return
__depot_index
for
i
,
vertex
in
enumerate
(
vertices
):
if
vertex
==
depot_node
:
__depot_index
=
i
break
if
__depot_index
is
None
:
raise
DepotUnspecifiedException
(
"No depot location specified!"
)
return
__depot_index
def
cleanup
():
global
__distance_matrix
,
__depot_index
if
(
__distance_matrix
is
not
None
and
len
(
__distance_matrix
)
>=
MAX_DISTANCE_MATRIX_SIZE
):
__distance_matrix
=
None
__depot_index
=
None
@
mgp
.
read_proc
def
route
(
context
:
mgp
.
ProcCtx
,
depot_node
:
mgp
.
Vertex
,
number_of_vehicles
:
mgp
.
Nullable
[
int
]
=
None
,
)
->
mgp
.
Record
(
from_vertex
=
mgp
.
Vertex
,
to_vertex
=
mgp
.
Vertex
):
"""
The VRP routing returns 2 fields.
* `from_vertex` represents the starting nodes out of all selected routes (edges) in the complete graph
* `to_vertex` represents the ending nodes out of all selected routes (edges) in the complete graph
The input arguments are:
* `number_of_vehicle` represents the cardinality of fleet with which the problem is going to be solved
* `depot_label` represents the name of the label which contains the depot node
"""
if
number_of_vehicles
is
None
:
number_of_vehicles
=
1
if
number_of_vehicles
<=
0
:
raise
Exception
(
"Number of vehicles must be greater than 0."
)
vertices
=
[
v
for
v
in
context
.
graph
.
vertices
]
distance_matrix
=
get_distance_matrix
(
vertices
)
depot_index
=
get_depot_index
(
vertices
,
depot_node
)
solver
=
VRPConstraintProgrammingSolver
(
number_of_vehicles
,
distance_matrix
,
depot_index
)
solver
.
solve
()
result
=
solver
.
get_result
()
cleanup
()
return
[
mgp
.
Record
(
from_vertex
=
vertices
[
x
.
from_vertex
],
to_vertex
=
vertices
[
x
.
to_vertex
])
for
x
in
result
.
vrp_paths
]
class
DepotUnspecifiedException
(
Exception
):
pass
Back
|
FazBrowse Home
|
New Git URL