Same nodes but different solution time (VRP Time Windows)

Answered

Rihot Gusron

• July 20, 2022 08:09
• Edited

Hi gurobi support,

i just modeled the VRP with Time Windows from this book.

The things is i did tried using dummy datas first, with 10 nodes and all the parameter needed for the model to run. The running time was short and can get the solution. But when i tried with the same nodes (10 nodes) but with real datas, the solver still running for like 8 hours. Is anyone can give me some advice about this?

My datas look like this:

Earliest time(at each nodes) : All zero

Latest time (at each nodes) : All 480 (in minutes)

Demand(at each nodes) : [0 50 50 60 50 90 50  50 48  50 ]

Vehicle Capacity (at each vehicle) : [2000 1000 500]

 

1

• 

  David Torres Sanchez

  Gurobi Staff

  • July 20, 2022 11:13
  • Edited

  Hi Rihot,
  
  Sounds like there is an error in your formulation.
  You can try writing it to a LP file and make sure that the constraints match the formulation in the book: \(\texttt{model.write("vrptw.lp")}\).
  
  Cheers, 
  David

  1
• 

  Rihot Gusron

  • July 20, 2022 16:47

  

  

  

  Hi Mr. Sanchez,

  Thanks for the response. I did double check the model and seems can't find the error. Actually the time windows constraint seems suspicious, as when i comment that out, the solver was found the solution in a matter of second. I just extracted the lp model and hosted on google drive. Do you mind to have a look and maybe give any insight/advice about this?

  The link to .lp : click here

  Best Regard.

  0
• 

  David Torres Sanchez

  Gurobi Staff

  • July 21, 2022 10:06
  • Edited

  Hi Rihot,

  You are right, as far as I can tell the time window constraints are fine. Looks like these:

  $$u_{ik} +s_i + t_{ij} - u_{jk} \leq M(1-x_{ijk})~~\forall (i,j)$$

  With \(M=1000\).
  
  Maybe try constraining the time windows a little bit more, e.g. provide a lower window and maybe a different upper window for each node.
  If you are struggling with data creation, you can try using some real instances available and just grab fewer nodes: http://web.cba.neu.edu/~msolomon/c101.htm
  
  Cheers, 
  David

  0

Please sign in to leave a comment.