For a given cost matrix and a given communication requirement matrix, the OCSTP is defined as finding a spanning tree that minimizes the operational cost of the network. OCST can be used to design of more efficient communication and transportation networks, but appear also, as a subproblem, in hub location and sequence alignment problems.
This thesis studies several mixed integer linear optimization formulations of the OCSTP and proposes a new one. Then, an efficient Branch & Cut algorithm derived from the Benders decomposition of one of such formulations is used to successfully solve medium-sized instances of the OCSTP.
Additionally, two new combinatorial lower bounds, two new heuristic algorithms and a new family of spanning tree neighborhoods based on the Dandelion Code are presented and tested.
| Identifer | oai:union.ndltd.org:TDX_UPC/oai:www.tdx.cat:10803/387546 |
| Date | 01 February 2016 |
| Creators | Luna Mota, Carlos |
| Contributors | Fernández, Elena (Fernández Aréizaga), Universitat Politècnica de Catalunya. Departament d'Estadística i Investigació Operativa |
| Publisher | Universitat Politècnica de Catalunya |
| Source Sets | Universitat Politècnica de Catalunya |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | 113 p., application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc/3.0/es/, info:eu-repo/semantics/openAccess |
Page generated in 0.0018 seconds