Pup Matching: Model Formulations and Solution Approaches
We model Pup Matching, the logistics problem of matching or pairing semitrailers known as pups to cabs that are able to tow one or two of the pups simultaneously, as an AfP-complete version of the Network Loading Problem (NLP). We examine a branch and bound solution approach tailored to the NLP form...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5076 |
| _version_ | 1826213633228537856 |
|---|---|
| author | Bossert, John M. Magnanti, Thomas L. |
| author_facet | Bossert, John M. Magnanti, Thomas L. |
| author_sort | Bossert, John M. |
| collection | MIT |
| description | We model Pup Matching, the logistics problem of matching or pairing semitrailers known as pups to cabs that are able to tow one or two of the pups simultaneously, as an AfP-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. Branch and bound 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-23T15:52:21Z |
| format | Working Paper |
| id | mit-1721.1/5076 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:52:21Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/50762019-04-12T08:15:27Z Pup Matching: Model Formulations and Solution Approaches Bossert, John M. Magnanti, Thomas L. We model Pup Matching, the logistics problem of matching or pairing semitrailers known as pups to cabs that are able to tow one or two of the pups simultaneously, as an AfP-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. Branch and bound 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%. 2004-05-28T19:22:16Z 2004-05-28T19:22:16Z 2003-02 Working Paper http://hdl.handle.net/1721.1/5076 en_US Operations Research Center Working Paper;OR 366-03 1777625 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Bossert, John 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 |
| url | http://hdl.handle.net/1721.1/5076 |
| work_keys_str_mv | AT bossertjohnm pupmatchingmodelformulationsandsolutionapproaches AT magnantithomasl pupmatchingmodelformulationsandsolutionapproaches |