Optimal Network Design with End-to-End Service Requirements

Anantaram Balakrishnan (), Gang Li () and Prakash Mirchandani ()
Additional contact information
Anantaram Balakrishnan: McCombs School of Business, University of Texas at Austin, Austin, Texas 78712
Gang Li: Management Department, Bentley University, Waltham, Massachusetts 02452
Prakash Mirchandani: Katz Graduate School of Business, University of Pittsburgh, Pittsburgh, Pennsylvania 15260

Operations Research, 2017, vol. 65, issue 3, 729-750

Abstract: Long-term planning for transportation, telecommunications, and other service operations entails designing networks that are both cost effective and responsive. Because infrastructure networks are expensive and the network’s design determines its service capabilities, planners must address complex trade-offs between minimizing the total cost of the network while meeting end-to-end service requirements such as limits on transit time, latency, and transshipments. To address this problem, we study a minimum cost multicommodity network design model to select arcs and route the required flows along these arcs so that each origin-to-destination route satisfies limits on various service metrics. To effectively solve this service network design problem, we focus on a polyhedral approach to strengthen its arc flow formulation. We develop several classes of strong cuts, with appropriate separation procedures, and propose an optimization-based heuristic method. We characterize the dimension of the problem’s feasible region and show that two classes of inequalities are facet-defining under appropriate conditions. Our computational results demonstrate that our Composite method, incorporating the valid inequalities and heuristic algorithm, significantly reduces computational time and generates near-optimal solutions. The model and methods developed in this paper provide a valuable planning tool for service providers in transportation, telecommunication, and other sectors.

Keywords: service networks; polyhedral methods; integer programming (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/opre.2016.1579 (application/pdf)

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:inm:oropre:v:65:y:2017:i:3:p:729-750

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().