Modeling and solving variations of the Network Loading Problem

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.

Department dc:contributor.department

Sloan School of Management.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2002

Author dc:creator

• Bossert, John M. (John Meyer), 1973-

Advisor dc:contributor.advisor

• Thomas L. Magnanti.

• Sloan School of Management.

Statement dc:rights

• 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.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/29263

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/29263