Modeling and solving variations of the Network Loading Problem
Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, 2002.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/29263 |
| _version_ | 1811089830050791424 |
|---|---|
| author | Bossert, John M. (John Meyer), 1973- |
| author2 | Thomas L. Magnanti. |
| author_facet | Thomas L. Magnanti. Bossert, John M. (John Meyer), 1973- |
| author_sort | Bossert, John M. (John Meyer), 1973- |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, 2002. |
| first_indexed | 2024-09-23T14:25:18Z |
| format | Thesis |
| id | mit-1721.1/29263 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T14:25:18Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/292632019-04-11T09:13:05Z Modeling and solving variations of the Network Loading Problem Bossert, John M. (John Meyer), 1973- Thomas L. Magnanti. Sloan School of Management. Sloan School of Management. Sloan School of Management. Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, 2002. Includes bibliographical references (p. 146-149). We examine three variations of a class of network design problems known as Network Loading Problems (NLP). For'each variation we develop a tailored branch and bound solution approach equipped with heuristic procedures and problem specific cutting planes. The first variation formulates a logistics problem known as Pup Matching that involves matching semitrailers to cabs that are able to tow one or two of the trailers simultaneously. Theoretically, we show that four heuristics each yield a 2-approximation and we specify facet defining conditions for a cut family that we refer to as odd flow inequalities. Computationally, we solved to optimality 67 percent of test instances randomly generated from realistic data. The average minimum heuristic error among solved instances was 1.3 percent. Cutting planes reduced the average relative difference between upper and lower bounds prior to branching from 18.8 percent to 6.4 percent. The second problem variation concerns three NLP generalizations (segregated, nested, and general compartments) that we refer to collectively as Compartmentalized Network Loading (CNLP). We model these problems, extend to the case of segregated compartments convex hull results of Magnanti, Mirchandani, and Vachani on single arc and three node problems, and employ the routine of Atamtiirk and Rajan to efficiently separate certain (residual capacity) inequalities for all three CNLP models. (cont.) On randomly generated instances, we conducted four series of tests designed to isolate the computational impact of problem parameters including graph density and model type. The third variation, Single Commodity Network Loading (SCNLP), requires loading discrete capacity units sufficient to satisfy the demand for standard network flow (multiple source, multiple destination problem). We cast the limiting case of large capacity within the constrained forest framework of Goemans and Williamson, characterize the optimal solution to the single cut special case, and describe cutset, residual capacity, and three partition inequalities for this variation. We solved five randomly generated 15 node SCNLP instances in an average of 19.1 CPU seconds, but only three of five similarly defined NLP instances. by John M. Bossert. Ph.D. 2005-10-14T19:31:19Z 2005-10-14T19:31:19Z 2002 2002 Thesis http://hdl.handle.net/1721.1/29263 51908711 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 170 p. 6533258 bytes 6533066 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Sloan School of Management. Bossert, John M. (John Meyer), 1973- Modeling and solving variations of the Network Loading Problem |
| title | Modeling and solving variations of the Network Loading Problem |
| title_full | Modeling and solving variations of the Network Loading Problem |
| title_fullStr | Modeling and solving variations of the Network Loading Problem |
| title_full_unstemmed | Modeling and solving variations of the Network Loading Problem |
| title_short | Modeling and solving variations of the Network Loading Problem |
| title_sort | modeling and solving variations of the network loading problem |
| topic | Sloan School of Management. |
| url | http://hdl.handle.net/1721.1/29263 |
| work_keys_str_mv | AT bossertjohnmjohnmeyer1973 modelingandsolvingvariationsofthenetworkloadingproblem |