#🔒 Optimization Model Python
thorny briar
from gurobipy import *
import networkx as nx
import matplotlib.pyplot as plt
Function to read node data from SiouxFalls_node.txt or berlin-mitte-center_node.txt
def read_nodes(node_filename):
nodes = []
with open(node_filename, 'r') as file:
for line in file:
line = line.strip()
if line.startswith('NODES') or line.startswith('END') or line == '':
continue # Skip header lines, end, or empty lines
nodes.append(line)
return nodes
Function to read network data from SiouxFalls_net.txt or berlin-mitte-center_net.txt
def read_network_data(net_filename):
arcs = []
capacity = {}
with open(net_filename, 'r') as file:
for line in file:
line = line.strip()
if line.startswith('ARCS') or line.startswith('END') or line == '':
continue # Skip header lines, end, or empty lines
data = line.split()
if len(data) < 3:
continue # Ignore lines that do not have enough data
try:
start_node = data[0]
end_node = data[1]
cap = float(data[2])
arcs.append((start_node, end_node))
capacity[(start_node, end_node)] = cap
except ValueError:
continue # Ignore lines with conversion errors
return arcs, capacity
Function to read flow demands from SiouxFalls_trips.txt or berlin-mitte-center_trips.txt
def read_flow_data(flow_filename):
inflow = {}
with open(flow_filename, 'r') as file:
for line in file:
line = line.strip()
if line.startswith('ORIGIN') or line.startswith('END') or line == '':
continue # Skip header lines, end, or empty lines
data = line.split()
if len(data) < 2:
continue # Ignore lines that do not have enough data
heady domeBOT
Hey @thorny briar!
thorny briar
try:
node = data[0]
flow = float(data[1])
inflow[node] = flow
except ValueError:
continue # Ignore lines with conversion errors
return inflow
Function to create and solve the multi-commodity flow model
def solve_multi_commodity_flow(nodes, arcs, capacity, cost, inflow):
m = Model('multi_commodity_flow')
# Flow variables for each (commodity, arc) pair
flow = {}
for i, j in arcs:
for commodity in inflow.keys():
flow[commodity, i, j] = m.addVar(ub=capacity[i, j], obj=cost.get((i, j), 0), name=f'flow_{commodity}_{i}_{j}')
m.update()
# Capacity constraints on arcs
for i, j in arcs:
m.addConstr(quicksum(flow[commodity, i, j] for commodity in inflow.keys()) <= capacity[i, j], f'capacity_{i}_{j}')
# Flow conservation constraints
for node in nodes:
if node in inflow:
for commodity in inflow.keys():
inflow_term = inflow[node] if (commodity, node) in flow else 0
outflow_term = quicksum(flow[commodity, node, j] for i, j in arcs if i == node)
m.addConstr(inflow_term + outflow_term == quicksum(flow[commodity, i, node] for i, j in arcs if j == node), f'flow_conservation_{commodity}_{node}')
# Minimize total cost
m.modelSense = GRB.MINIMIZE
Optimize the model
m.optimize()
# Print the solution
if m.status == GRB.Status.OPTIMAL:
print("Optimal solution found!")
for i, j in arcs:
for commodity in inflow.keys():
if flow[commodity, i, j].x > 0:
print(f"Flow of {commodity} from {i} to {j}: {flow[commodity, i, j].x}")
# Visualize the transport network graphically
G = nx.DiGraph()
G.add_edges_from(arcs)
plt.figure(figsize=(10, 8))
pos = nx.spring_layout(G, seed=42)
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=500, font_size=10, font_weight='bold', arrows=True)
edge_labels = {(i, j): f'{capacity[i, j]}' for i, j in arcs}
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, label_pos=0.3, font_color='red')
plt.title('Transportation Network')
plt.show()
Example usage
nodes = read_nodes('SiouxFalls_node.txt') # Read nodes from SiouxFalls_node.txt or berlin-mitte-center_node.txt
arcs, capacity = read_network_data('SiouxFalls_net.txt') # Read arc and capacity data from SiouxFalls_net.txt or berlin-mitte-center_net.txt
cost = {} # You need to define arc costs based on required data
inflow = read_flow_data('SiouxFalls_trips.txt') # Read flow demands from SiouxFalls_trips.txt or berlin-mitte-center_trips.txt
Create and solve the multi-commodity flow model
solve_multi_commodity_flow(nodes, arcs, capacity, cost, inflow)
I need to do this: The exercise consists in the implementation of a minimum-cost multi-commodity flow model
and in the analysis of its results on classic instances related to urban transportation.
The model must be implemented using the Python language and Gurobi as MILP solver. The
model must be run on data from the classic SiouxFalls network and from the Berlin-Mitte-
Center network. The data concerning both cases can be retrieved from:
https://github.com/bstabler/TransportationNetworks
The model can be developed according to existing examples, like the following:
https://github.com/wurmen/Gurobi-Python/blob/master/python-
gurobi%20%20model/Netflow_problem.py
However, input must be read directly from the data files downloadable from the Github
repository. Moreover, at least for the Sioux-Falls example, the output must includes a
representation of the transportation network and the total flow assigned to each link.
heady domeBOT
@thorny briar
Python help channel closed