Pup Matching: Model Formulations and Solution Approaches
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | en_US |
| Published: |
2003
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/4007 |
| _version_ | 1811089067340726272 |
|---|---|
| author | Bossert, J.M. Magnanti, Thomas L. |
| author_facet | Bossert, J.M. Magnanti, Thomas L. |
| author_sort | Bossert, J.M. |
| collection | MIT |
| description | 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%. |
| first_indexed | 2024-09-23T14:13:15Z |
| format | Article |
| id | mit-1721.1/4007 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:13:15Z |
| publishDate | 2003 |
| record_format | dspace |
| spelling | mit-1721.1/40072019-04-10T08:59:58Z Pup Matching: Model Formulations and Solution Approaches Bossert, J.M. Magnanti, Thomas L. network loading network design cutting planes 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) 2003-12-23T02:45:18Z 2003-12-23T02:45:18Z 2002-01 Article http://hdl.handle.net/1721.1/4007 en_US High Performance Computation for Engineered Systems (HPCES); 205898 bytes application/pdf application/pdf |
| spellingShingle | network loading network design cutting planes Bossert, J.M. Magnanti, Thomas L. Pup Matching: Model Formulations and Solution Approaches |
| title | Pup Matching: Model Formulations and Solution Approaches |
| title_full | Pup Matching: Model Formulations and Solution Approaches |
| title_fullStr | Pup Matching: Model Formulations and Solution Approaches |
| title_full_unstemmed | Pup Matching: Model Formulations and Solution Approaches |
| title_short | Pup Matching: Model Formulations and Solution Approaches |
| title_sort | pup matching model formulations and solution approaches |
| topic | network loading network design cutting planes |
| url | http://hdl.handle.net/1721.1/4007 |
| work_keys_str_mv | AT bossertjm pupmatchingmodelformulationsandsolutionapproaches AT magnantithomasl pupmatchingmodelformulationsandsolutionapproaches |