I am currently working on lineplanning problems (linear progamming), f.e. described in https://www.researchgate.net/publication/225218930_Models_for_Line_Planning_in_Public_Transport.
I tried to implement a version that creates a (weightend) sum of direct travlers and costs in Python and tried to solve it via Gurobi. For further applications I want to check all feasable solutions for this problem via Gurobi Pool Search: https://www.gurobi.com/documentation/current/refman/poolsearchmode.html. The code solves the optimal solution and also gives out the correct line plan, but doesnt find all feasable solutions and their respective combined_obj values and rather outputs same solutions multiple times. I am not sure how easy it is to understand the code and/or find the mistake here.
This is my code:
if __name__ == '__main__':
if len(sys.argv) < 2:
raise ConfigNoFileNameGivenException()
logger.info("Start reading configuration")
config = ConfigReader.read(sys.argv[1])
#parameters = SolverParameters(config, "lc_")
parameters = DirectParameters(config)
logger.info("Finished reading configuration")
logger.info("Begin reading input data")
ptn = PTNReader.read(read_loads=True)
od = DictOD()
#od = ODReader.read(od)
ods = ODReader.readMultiple(od)
logger.info(f"Read in {len(ods)} OD matrices")
logger.info("Finished reading input data")
for index_of_od_matrix,od in enumerate(ods):
logger.info(f"Begin execution of robust multicrieteria line planning model for OD-Matrix {index_of_od_matrix}")
line_pool = LineReader.read(ptn, read_frequencies=False)
solver = Solver.createSolver(parameters.getSolverType())
model = solver.createModel()
logger.debug("Add variables")
# ToDo: add variables
frequencies = {}
for line in line_pool.getLines():
frequency = model.addVariable(0, float('inf'), VariableType.INTEGER, name=f"f_{line.getId()}")
frequencies[line] = frequency
acceptableLineIds = compute_acceptable_line_ids(line_pool, compute_shortest_paths(ptn, od, parameters), ptn)
d = {}
for origin in ptn.getNodes():
d[origin.getId()] = {}
for destination in ptn.getNodes():
d[origin.getId()][destination.getId()] = {}
sumOfAllVariablesPerODPair = None
if origin == destination or od.getValue(origin.getId(), destination.getId()) == 0:
continue
for lineId in acceptableLineIds[(origin.getId(), destination.getId())]:
d[origin.getId()][destination.getId()][lineId] = model.addVariable(0, od.getValue(origin.getId(),
destination.getId()),
VariableType.INTEGER,
name=f"d{origin.getId()}{destination.getId()}{lineId}")
if sumOfAllVariablesPerODPair is None:
sumOfAllVariablesPerODPair = d[origin.getId()][destination.getId()][lineId]
else:
sumOfAllVariablesPerODPair += d[origin.getId()][destination.getId()][lineId]
if not sumOfAllVariablesPerODPair:
sumOfAllVariablesPerODPair = 0
model.addConstraint(sumOfAllVariablesPerODPair, ConstraintSense.LESS_EQUAL,
od.getValue(origin.getId(), destination.getId()),
name=f"od_constraint{origin.getId()}_{destination.getId()}")
logger.debug("Adding more constraints")
# ToDo: add constraints
for link in ptn.getEdges():
sum_freq_per_line = model.createExpression()
for line in line_pool.getLines():
if link in line.getLinePath().getEdges():
sum_freq_per_line.add(frequencies[line])
model.addConstraint(sum_freq_per_line, ConstraintSense.LESS_EQUAL, link.getUpperFrequencyBound(),
f"u_{link.getId()}")
model.addConstraint(sum_freq_per_line, ConstraintSense.GREATER_EQUAL, link.getLowerFrequencyBound(),
f"l_{link.getId()}")
logger.debug("Add capacity constraints")
# Constraint 3.7 -> Ensure that the capacity of each line is not exceeded
capacity = parameters.get_capacity()
for link in ptn.getEdges():
direct_travellers_on_line_and_edge = {}
for line in line_pool.getLines():
if link not in line.getLinePath().getEdges():
continue
for origin in ptn.getNodes():
for destination in ptn.getNodes():
if origin == destination or od.getValue(origin.getId(), destination.getId()) == 0:
continue
od_pair = (origin.getId(), destination.getId())
if line.getId() not in acceptableLineIds.get(od_pair):
continue
if link not in acceptableLineIds.get(od_pair).get(line.getId()).getEdges():
continue
if line.getId() not in direct_travellers_on_line_and_edge:
direct_travellers_on_line_and_edge[line.getId()] = model.createExpression()
direct_travellers_on_line_and_edge[line.getId()].multiAdd(1,
d.get(origin.getId()).get(
destination.getId()).get(
line.getId()))
capacity_of_line = model.createExpression()
capacity_of_line.multiAdd(capacity, frequencies.get(line))
# There may be a line that is not acceptable for anybody
direct_travellers_on_line = direct_travellers_on_line_and_edge.get(line.getId())
if direct_travellers_on_line is not None:
model.addConstraint(direct_travellers_on_line, ConstraintSense.LESS_EQUAL, capacity_of_line,
"capacity_constraint_" + str(link.getId()) + "_" + str(line.getId()))
logger.debug("Add parameters")
parameters.setSolverParameters(model)
# model.setSense(OptimizationSense.MINIMIZE)
#objectives = list()
model.getObjective().clear()
obj = None
for line, frequency in frequencies.items():
if obj is None:
obj = line.getCost() * frequency
else:
obj += line.getCost() * frequency
#objectives.append(obj)
obj2 = None
for origin, destinations in d.items():
for destination, lines in destinations.items():
for line, variable in lines.items():
if obj2 is None:
obj2 = variable
else:
obj2 += variable
#objectives.append(obj2)
if obj2:
combined_obj = obj - obj2
else:
combined_obj = obj
I tried to output all parameters of feasable solutions, but couldnt find any differences in the output data. All direct tavlers and costs are identical aswell as the final combined_obj value. I think it has to do with the constraints I am giving, since they dont allow a specific assignment for the direct travlers?
-> Maybe there is a workaround for Gurobi to only output same results with equal given parameters only once?
