Network Models
Connection
OperationsResearchModels.Network.Connection — Type ConnectionDescription
A structure to hold a directed connection between two nodes in a network.
Fields
from::Int64: The starting node of the connection.to::Int64: The ending node of the connection.value::Real: The value associated with the connection (e.g. distance, time, capacity).
Example
# Create a connection from node 1 to node 2 with a distance of 5 kms.
conn = Connection(1, 2, 5)ShortestPathProblem
OperationsResearchModels.ShortestPath.ShortestPathProblem — TypeShortestPathProblemDescription
Defines the shortest path problem.
Fields
connections::Vector{Connection}: The connections (edges) in the network.
Shortest Path
OperationsResearchModels.solve — Methodsolve(problem)Description
Solves a shortest path problem given by an object of in type ShortestPathProblem.
Arguments
problem::ShortestPathProblem: The problem in type of ShortestPathProblem
Output
ShortestPathResult: The custom data type that holds path and cost.
Example
julia> conns = [
Connection(1, 2, 3),
Connection(1, 3, 2),
Connection(1, 4, 4),
Connection(2, 5, 3),
Connection(3, 5, 1),
Connection(3, 6, 1),
Connection(4, 6, 2),
Connection(5, 7, 6),
Connection(6, 7, 5),
];
julia> solve(ShortestPathProblem(conns));
julia> result.path
3-element Vector{Connection}:
Connection(1, 3, 2)
Connection(3, 6, 1)
Connection(6, 7, 5)
julia> result.cost
8.0In this function it's assumed that the problem has a unique start and finish node. A heuristic approach is used to find the start and finish nodes. If a node has only outcoming connections, it is considered the start node. If a node has only incoming connections, it is considered the finish node. Of course a network can have multiple start and finish nodes, but this heuristic simplifies the problem. Future implementations could explore more complex scenarios with multiple start and finish nodes.
ShortestPathResult
OperationsResearchModels.ShortestPath.ShortestPathResult — TypeShortestPathResultDescription
A structure to hold the result of the shortest path problem.
Fields
path::Vector{Connection}: The connections (edges) in the shortest path.cost::Float64: The total cost of the shortest path.
Maximum Flow Problem
OperationsResearchModels.MaximumFlow.MaximumFlowProblem — TypeMaximumFlowProblemDescription
Defines the maximum flow problem.
Fields
connections::Vector{Connection}: The connections (edges) in the network.
Maximum Flow
OperationsResearchModels.solve — Methodsolve(problem)Description
Solves a maximum flow problem given by an object of in type MaximumFlowProblem.
Arguments
problem::MaximumFlowProblem: The problem in type of MaximumFlowProblem
Output
MaximumFlowResult: The custom data type that holds path and flow.
Example
julia> conns = [
Connection(1, 2, 3),
Connection(1, 3, 2),
Connection(1, 4, 4),
Connection(2, 5, 3),
Connection(3, 5, 1),
Connection(3, 6, 1),
Connection(4, 6, 2),
Connection(5, 7, 6),
Connection(6, 7, 5),
];
julia> problem = MaximumFlowProblem(conns)
julia> result = solve(problem);
julia> result.path
9-element Vector{Connection}:
Connection(1, 2, 3.0)
Connection(1, 3, 2.0)
Connection(1, 4, 2.0)
Connection(2, 5, 3.0)
Connection(3, 5, 1.0)
Connection(3, 6, 1.0)
Connection(4, 6, 2.0)
Connection(5, 7, 4.0)
Connection(6, 7, 3.0)
julia> result.flow
7.0In this function it's assumed that the problem has a unique start and finish node. A heuristic approach is used to find the start and finish nodes. If a node has only outcoming connections, it is considered the start node. If a node has only incoming connections, it is considered the finish node. Of course a network can have multiple start and finish nodes, but this heuristic simplifies the problem. Future implementations could explore more complex scenarios with multiple start and finish nodes.
MaximumFlowResult
OperationsResearchModels.MaximumFlow.MaximumFlowResult — TypeMaximumFlowResultDescription
A structure to hold the result of the maximum flow problem.
Fields
path::Vector{Connection}: The connections (edges) in the flow path.flow::Float64: The total flow through the network.
MinimumCostFlowProblem
OperationsResearchModels.MinimumCostFlow.MinimumCostFlowProblem — TypeMinimumCostFlowProblemDescription
Defines the minimum cost flow problem.
Fields
connections::Vector{Connection}: The connections (edges) in the network.costs::Vector{Connection}: The costs associated with each connection.
Minimum Cost Flow
OperationsResearchModels.solve — Methodsolve(problem)Description
This function solves the Minimum Cost Flow problem by first solving the Maximum Flow problem and then using the flow value to solve the Minimum Cost Flow problem.
Arguments
problem::MinimumCostFlowProblem: The problem in type of MinimumCostFlowProblem
In this function it's assumed that the problem has a unique start and finish node. A heuristic approach is used to find the start and finish nodes. If a node has only outcoming connections, it is considered the start node. If a node has only incoming connections, it is considered the finish node. Of course a network can have multiple start and finish nodes, but this heuristic simplifies the problem. Future implementations could explore more complex scenarios with multiple start and finish nodes.
OperationsResearchModels.solve — Methodsolve(problem, flow)Description
This function solves the Minimum Cost Flow problem given a flow value.
Arguments
problem::MinimumCostFlowProblem: The problem in type of MinimumCostFlowProblemflow::Float64: The flow value to be used in the problem.
MinimumCostFlowResult
OperationsResearchModels.MinimumCostFlow.MinimumCostFlowResult — TypeMinimumCostFlowResultDescription
A structure to hold the result of the minimum cost flow problem.
Fields
path::Vector{Connection}: The connections (edges) in the flow path.cost::Float64: The total cost of the flow.
MstProblem
OperationsResearchModels.MinimumSpanningTree.MstProblem — TypeMstProblemDescription
Defines the minimum spanning tree problem.
Fields
connections::Vector{Connection}: The connections (edges) in the network.
Minimum Spanning Tree
OperationsResearchModels.solve — Methodsolve(problem::MstProblem)Description
Obtains the minimum spanning tree.
Arguments
problem::MstProblem: The problem in type of MstProblem
Output
::MstResult: A MstResult object that holds the results.
Details
- This function uses Prim's algorithm to find the minimum spanning tree. It maintains a set of assigned and unassigned nodes, expanding the tree by adding the nearest unassigned node.
Examples
julia> conns = Connection[
Connection(1, 2, 10),
Connection(2, 3, 10),
Connection(3, 4, 10),
Connection(1, 4, 10)
]
4-element Vector{Connection}:
Connection(1, 2, 10)
Connection(2, 3, 10)
Connection(3, 4, 10)
Connection(1, 4, 10)
julia> result = solve(MstProblem(conns))
MstResult(Connection[Connection(3, 4, 10), Connection(1, 4, 10), Connection(2, 3, 10)], 30.0)
julia> result.distance
30.0
julia> result.connections
3-element Vector{Connection}:
Connection(3, 4, 10)
Connection(1, 4, 10)
Connection(2, 3, 10)MstResult
OperationsResearchModels.MinimumSpanningTree.MstResult — TypeMstResultDescription
A structure to hold the result of the minimum spanning tree problem.
Fields
connections::Vector{Connection}: The connections (edges) in the minimum spanning tree.distance::Float64: The total distance (weight) of the minimum spanning tree.