VRPTW BIGM problem

Answered

天 景

January 02, 2024 06:20

• 
• 
• 

Hi,

When I referred to Ruthmain's code to learn the VRPTW problem, I used the BIGM scheme. Even if maxNumVehicles is set to a large value after numCustomers>141, the model still has no solution. IIS prompts that there are some variables that are unbounded, and the constraints violated are also related to these variables. However, I have not yet analyzed what the problem is. I would like to ask for advice.

Thanks,

Related to

• VRP

0

• 

  Mario Ruthmair

  • Gurobi Staff

  January 09, 2024 11:23

  Hi,

  Indeed, there was a bug in the instance generation. In rare cases, the time windows have been created in a way that does not allow a feasible solution.
  It has been fixed already in the Git repo.
  Thanks for the hint!

  Best regards,
  Mario

  0
• 

  天 景

  January 10, 2024 06:09 Edited

  • 
  • 
  • 

  Hi Mario,

  Thank you for your reply. Regarding the actual scenario, I have another question. According to common sense, if I provide enough vehicles, then 100% of the customer's time can be met (at worst, each customer uses one vehicle). No matter what data is randomly generated, there should be a solution. Why is there infeasible？

  0
• 

  Mario Ruthmair

  • Gurobi Staff

  January 10, 2024 10:30

  If the time window of some customer has been set in a way that does not allow the vehicle to go back to the depot before the time horizon ends, then it could be infeasible. The time horizon can be seen as the time window of the depot. This is not always part of the problem definition, but in my case, I added it.

  1
• 

  天 景

  January 11, 2024 03:42

  • 
  • 
  • 

  Thank you Mario Ruthmair

  0
• 

  Giovanni Rossi

  November 24, 2024 13:31

  • 

  Good morning Mario, what's news about VRP resolution wlll give us the 12 Gurobi's release?

  What can we expect from Gurobi's research and development sector to eleiminar e the GAP with Hexaly?

  Hexaly, Gurobi, OR-Tools, OptaPlanner, jsprit on the Capacitated Vehicle Routing Problem (CVRP)

   

  0
• 

  Mario Ruthmair

  • Gurobi Staff

  November 25, 2024 11:52

  Hi Giovanni,

  Gurobi provides a general-purpose solver, while Hexaly provides specific interfaces to particular problem types, e.g., routing problems, which allows the use of problem-specific solution approaches. This is a significant difference in the product strategy.
  For now, Gurobi has decided to stay general, but this may change in the future (or not).
  In v12, the overall MIP performance improved (based on our internal benchmark set), so there might also be improvements for particular VRP models.

  Best regards,
  Mario

  0

Please sign in to leave a comment.