Network Design with Routing Requirements

Anantaram Balakrishnan (), Thomas L. Magnanti (), Prakash Mirchandani () and Richard T. Wong ()
Additional contact information
Anantaram Balakrishnan: University of Texas at Austin
Thomas L. Magnanti: Massachusetts Institute of Technology
Prakash Mirchandani: University of Pittsburgh

Chapter Chapter 8 in Network Design with Applications to Transportation and Logistics, 2021, pp 209-253 from Springer

Abstract: Abstract Many practical applications of network design, particularly in transportation and logistics, require designing a cost-effective network configuration to meet all demand at total fixed and flow costs, subject to additional constraints on routing decisions to ensure good end-to-end service performance. For instance, in settings such as package delivery, rail freight operations, vehicle routing, and crew scheduling, these service requirements include upper limits on the permissible end-to-end transit time or number of intermediate transshipments. This chapter discusses modeling and methodological issues for effectively solving fixed-charge network design problems with routing requirements (NDRR). As a generalization of various well-known and difficult optimization problems, this problem is NP-hard; the added routing restrictions increase computational difficulty even to find feasible solutions. The literature on the general NDRR problem is relatively sparse. We first discuss some recent results and a composite algorithm that combines problem reduction, valid inequalities, and heuristics with branch-and-bound to effectively solve problem instances with varying characteristics. Next, we review theoretical developments, modeling strategies, and algorithms for two well-studied special cases of the NDRR problem, namely, constrained shortest path and hop-constrained network design models. Researchers have developed approximation algorithms, polyhedral results, extended model formulations, and specialized algorithms for these special cases. These results and methods point to possible avenues for further research on generalizing the approaches to the NDRR problem. The chapter concludes by outlining decomposition solution methods, and summarizing some key observations and learnings regarding the NDRR problem.

Date: 2021
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:sprchp:978-3-030-64018-7_8

Ordering information: This item can be ordered from
http://www.springer.com/9783030640187

DOI: 10.1007/978-3-030-64018-7_8

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().