Important: This instance is deprecated and will be closed soon! Please visit this platform
26-29 May 2015
Fürstenberghaus
Europe/Berlin timezone
Home > Timetable > Session details > Contribution details

Contribution Complete Research Paper

Fürstenberghaus - F33
03 - Decision Support

The Multi-commodity Cable Trench Problem

Speakers

  • Silvia SCHWARZE

Primary authors

Description

In the design of wire-based networks, the implementation of infrastructure is a major cost component. One way to obtain cost savings is to coordinate trenching activities of different network operators, e.g., telecommunication providers may join forces with local communities when digging roads or pavements. In this work, the Multi-Commodity Cable Trench Problem (MC-CTP) is introduced that aims at detecting cost minimizing network structures including the option to reduce trenching costs by a joint realization for different cable types. A mixed-integer linear programming model is proposed and strengthened through the development of valid inequalities. Moreover, complexity and solution properties, like the existence of rings are discussed. The numerical study includes two parts. First, the effect of the valid inequalities on the LP-relaxation is studied experimentally. Second, the impact of the trenching cost reduction on the degree of joint activities and on total costs is investigated.