Minimum concave cost multicommodity network design

Date

2007-12-01

Author

Bazlamaçcı, Cüneyt Fehmi

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

151
views

0
downloads

The minimum concave cost multicommodity network design problem (MCMNDP) arises in many application areas, such as transportation planning, energy distribution systems and especially in the design of both packet and circuit switching backbone networks. Exact concave cost optimization algorithms have been developed but they are applicable only if the network size is small. Therefore, MCMNDP is usually solved using non-exact iterative methods. In this paper, such heuristic techniques proposed within the context of circuit switching and packet switching network design are evaluated in detail. Following a comprehensive literature survey, Yaged's linearization, Minoux's greedy and Minoux's accelerated greedy methods have been selected for the circuit switching network design case for further investigation. Minoux's greedy methods are found to create routes that include cycles causing degradation in the quality of the solution; therefore, we propose a simple but effective modification scheme as a cycle elimination strategy. Similarly, but within the context of packet switching network design, Gerla and Kleinrock's concave branch elimination, Gersht's greedy, and Stacey's concave link elimination methods have been selected for further investigation. All of these methods consider aggregate flows on each link, simultaneously re-routing more than one commodity in one step. In this paper, we propose an alternative disaggregate approach, where only one commodity is handled at a time. Our final proposal is the adaptation of the algorithms proposed for circuit switching network design to the packet switching case. Then an extensive comparative computational study is performed for a number of networks and cost structures to help establish the best method with respect to time and solution quality. Our computational results have shown that the performances of the MCMNDP algorithms heavily depend on the network type and the cost structure. The results have also revealed that our proposed modification to Minoux greedy to eliminate cycles leads to considerable improvements and our proposed disaggregate approach gives the best result in some networks with certain cost structures.

Subject Keywords

Electrical and Electronic Engineering

URI

https://hdl.handle.net/11511/56487

Journal

TELECOMMUNICATION SYSTEMS

DOI

https://doi.org/10.1007/s11235-008-9068-2

Collections

Department of Electrical and Electronics Engineering, Article

Suggestions

OpenMETU
Core

Minimum concave cost multicommodity network design Say, Fatih; Bazlamaçcı, Cüneyt Fehmi; Department of Electrical and Electronics Engineering (2005) Minimum Concave Cost Multicommodity Network Design Problem arises in many application areas, such as transportation planning, distributed energy system and especially both circuit and packet switching backbone network design. Exact concave optimization algorithms have been developed, but these methods are applicable if the network size is small. Therefore, these problems are usually solved by non-exact iterative methods. In this thesis work, methods proposed for circuit switching and packet switching networ...
Adaptive controller based on grid impedance estimation for stable operation of grid-connected inverters under weak grid conditions Temiz, Hakan; Keysan, Ozan; Demirok, Erhan (Institution of Engineering and Technology (IET), 2020-10-01) An electric grid having high impedance seen from the connection point is considered as a weak grid and it adversely affects the system stability of grid-tied voltage source inverters in renewable power devices. In this study, an adaptive controller is proposed by configuring the settling time of the phase-locked loop based on the estimated grid impedance. Pseudorandom binary sequence injection and Fourier techniques are carried out for grid impedance estimation. Impedance-based stability analysis is perform...
TECHNICAL AND ECONOMIC-FEASIBILITY OF CONVERSION TO A HIGHER VOLTAGE DISTRIBUTION OZAY, N; Güven, Ali Nezih; TURELI, A; DEMIROGLU, M (Institution of Engineering and Technology (IET), 1995-09-01) The proper selection of the voltage level combinations when uprating voltages in an existing distribution system is very important as this would result in significant economics. The paper discusses the effects of high-voltage and distribution system primary voltage on the system characteristics and performance as practised in the Turkish system. It is shown that a higher primary distribution voltage minimises the investments on the high-voltage system and a completely new primary distribution system provide...
Fully Integrated Autonomous Interface With Maximum Power Point Tracking for Energy Harvesting TEGs With High Power Capacity Tabrizi, Hamed Osouli; Jayaweera, Herath M. P. C.; Muhtaroglu, Ali (Institute of Electrical and Electronics Engineers (IEEE), 2020-05-01) In this article, a novel fully autonomous and integrated power management interface circuit is introduced for energy harvesting using thermoelectric generators (TEGs) to supply power to Internet of Thing nodes. The circuit consists of a self-starting dc & x2013;dc converter based on a dual-phase charge pump with LC-tank oscillator, a digital MPPT unit, and a 1-V LDO regulator. The novel maximum power point tracking (MPPT) algorithm avoids open-circuit state, and accommodates varying input power and ultra-lo...
OPTIMAL CONTROLLER DESIGN FOR SPEED GOVERNORS OF HYDROELECTRIC POWER PLANT Altinoz, Okkes Tolga; KOŞALAY, İLHAN; Gezer, Derya (VSB - Technical University of Ostrava, 2020-06-01) Speed governors have critical importance on hydroelectric power plants, which are adjusted to the rotating speed of hydroelectric generation based on load demand of the grid. The rotating speed is the main factor to balance power generation and load demand. The well-designed controller is needed to control speed governors with high accuracy. A well-defined model is needed to obtain desired control structure. Therefore, in this study, initially, the mathematical model of a hydroelectric power plant is obtain...

Citation Formats

C. F. Bazlamaçcı, “Minimum concave cost multicommodity network design,” TELECOMMUNICATION SYSTEMS, pp. 181–203, 2007, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/56487.