Dealing with residual energy when transmitting data in energy-constrained capacitated networks

Herminia I. Calvete, Lourdes del-Pozo and José A. Iranzo

European Journal of Operational Research, 2018, vol. 269, issue 2, 602-620

Abstract: This paper addresses several problems relating to the energy available after the transmission of a given amount of data in a capacitated network. The arcs have an associated parameter representing the energy consumed during the transmission along the arc and the nodes have limited power to transmit data. In the first part of the paper, we consider the problem of designing a path which maximizes the minimum of the residual energy remaining at the nodes. After formulating the problem and proving the main theoretical results, a polynomial time algorithm is proposed based on computing maxmin paths in a sequence of non-capacitated networks. In the second part of the paper, the problem of obtaining a quickest path in this context is analyzed. First, the bi-objective variant of this problem is considered in which we aim to minimize the transmission time and to maximize the minimum residual energy. An exact polynomial time algorithm is proposed to find a minimal complete set of efficient solutions which amounts to solving shortest path problems. Second, the problem of computing an energy-constrained quickest path which guarantees at least a given residual energy at the nodes is reformulated as a variant of the energy-constrained quickest path problem. The algorithms are tested on a set of benchmark problems providing the optimal solution or the Pareto front within reasonable computing times.

Keywords: Networks; Quickest path; Energy constraint; Minsum-maxmin; Bi-objective optimization (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718301747
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:269:y:2018:i:2:p:602-620

DOI: 10.1016/j.ejor.2018.02.041

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().