Á. Corberán, M. Landete, J. Peiró, F. Saldanha-da-Gama
p-hub location problems in transportation networks are NP-hard combinatorial optimization problems with many industrial applications. In the r-allocation variant, three optimization subproblems are involved: a service facility location problem, an assignment problem, and a routing problem.
In this work we focus on finding new valid inequalities for this variant. Some of them have been adapted from inequalities proposed for related problems, while other inequalities are new contributions.
The intersection of many of them defines a set packing polyhedron, which has an associated conflict graph that we have studied in order to generate new valid inequalities for the problem, especially those of the clique and odd-hole classes.
Computational results will be provided showing that the new inequalities help in strengthen the linear relaxation of the original formulation.
Keywords: hub location, non-stop services, set packing problem, clique, odd hole, branch and cut
Scheduled
GT1-1 Location
September 3, 2019 3:30 PM
I3L8. Georgina Blanes building