Comparing the efficiency when using two VRP formulations for practical applications

Answered

Wei Wang

• December 18, 2023 05:35

Hello,

I'm currently investigating the efficiency issue when using two formulations (or a series of constraints) for the same purpose, e.g., for vehicle routing, in specific practical applications (for example, in a goods dispatching problem). Suppose that we have two MIP formulations for vehicle routing: VRP1 and VRP2, and VRP1 is considered 'stronger' than VRP2, meaning it has higher efficiency when solved independently (i.e., solving the pure VRP problem it forms without additional constraints). 

I'm curious: If we embed VRP1 and VRP2 into the model of this goods dispatching problem (meaning that besides the VRP part, there are other constraints related to goods dispatching), respectively, which one is likely to show higher efficiency? Is VRP1 expected to perform better?

Your insights on this would be invaluable. Thank you!

Related to

• VRP

0

• 

  Mario Ruthmair

  Gurobi Staff

  • December 20, 2023 12:40

  Hi Wei Wang,

  It is difficult to make a general statement, but yes, I would expect that VRP1 also works better than VRP2 if additional constraints are present.
  The main question is, why does VRP1 perform better than VRP2 for the pure VRP without additional constraints?

  • Is it because it is theoretically stronger, i.e., it provides dual bounds that are at least as good as the other formulation? In this case, the hope is that the bounds are also better in the richer problem variant. But this does not need to be the case if the additional constraints are the restricting ones.
  • Is it because the solver finds better solutions (primal bounds) with the built-in heuristics? This could even be the case if VRP1 is theoretically weaker than VRP2. Then, the hope is that the solver can also find better solutions for the richer problem variant. But again, this does not need to be the case if the additional constraints make the VRP really tough.

  Finally, the size of the model might play a role in your considerations. Theoretically stronger models are often larger since they have additional variables or constraints to achieve the stronger bounds.

  In the end, you probably should try both.

  Best regards,
  Mario

  0
• 

  Wei Wang

  • December 31, 2023 14:50

  

  

  

  Dear Mario,

  Thank you very much for your insightful and detailed response to my query. Your expert perspectives are incredibly instructive and will be invaluable in my ongoing research.

  I appreciate the time and effort you took to address my concerns.

  Best,

  Wei

  0

Please sign in to leave a comment.