1173. Two-index formulations for the traveling purchaser problem with incompatibily constraints
Invited abstract in session WD-58: Exact Algorithms for Vehicle Routing, stream Vehicle Routing and Logistics.
Wednesday, 14:30-16:00Room: Liberty 1.13
Authors (first author is the speaker)
| 1. | Raquel Bernardino
|
| ISEG, CEMAPRE, UL | |
| 2. | Daniel Santos
|
| CEGIST, Instituto Superior Técnico, Universidade de Lisboa |
Abstract
The Traveling Purchaser Problem with Incompatibility Constraints (TPP-IC) generalizes the classical Traveling Purchaser Problem (TPP) by introducing constraints that prevent certain items from being transported together. This problem arises in various real-world applications, such as hazardous materials transportation, where incompatible products must be handled separately to ensure safety and compliance.
In this study, we propose a novel mixed-integer programming (MIP) formulation that models item incompatibilities using compatibility graphs. Compatibility graphs are used to model the incompatibility constraints implicitly, which makes it possible to use two-index formulations rather than a traditional three-index formulation to formulate the TPP-IC. Several compact and non-compact formulations are proposed for the TPP-IC, which are compared both theoretically and empirically. Additionally, valid inequalities are used to improve the quality of the linear programming relaxation values obtained by the formulations. A branch-and-cut framework is used to address the non-compact models.
Preliminary computational results show that the two-index formulations provide better linear programming relaxation values than the three-index formulation, which we hope will contribute to the two-index models being more efficient than the three-index models in obtaining the optimal values.
Keywords
- Vehicle Routing
- Mathematical Programming
- Branch and Cut
Status: accepted
Back to the list of papers