We model Pup Matching, the logistics problem of matching or pairing semitrailers known as pups to cabs able to tow one or two pups simultaneously, as an NP-complete version of the Network Loading Problem (NLP). We examine a branch and bound solution approach tailored to the NLP formulation through the use of three families of cutting planes and four heuristic procedures. Theoretically, we specify facet defining conditions for a cut family that we refer to as odd flow inequalities and show that each heuristic yields a 2-approximation. Computationally, the cheapest of the four heuristic values achieved an average error of 1.3% among solved test problems randomly generated from realistic data. The branch and bound method solved to optimality 67% of these problems. Application of the cutting plane families reduced the average relative difference between upper and lower bounds prior to branching from 18.8% to 6.4%. / Singapore-MIT Alliance (SMA)
| Identifer | oai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/4007 |
| Date | 01 1900 |
| Creators | Bossert, J.M., Magnanti, Thomas L. |
| Source Sets | M.I.T. Theses and Dissertation |
| Language | en_US |
| Detected Language | English |
| Type | Article |
| Format | 205898 bytes, application/pdf |
| Relation | High Performance Computation for Engineered Systems (HPCES); |
Page generated in 0.002 seconds