Skip to main content

How to improve solver solution time in VRP TW Optimization

Answered

Comments

6 comments

  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Hi, 

    Modeling and solving VRPs (with TW) is far from being trivial. State-of-the-art models require to implement a branch-and-price or a branch-and-cut algorithm. Compact models (with a polynomial number of variables and constraints) as you are using here can solve small to medium-sized instances but usually not much more than 50-100 customers.

    Your solver log tells me that the model you are using provides a very weak linear programming relaxation, I guess it is based on Big-M constraints for modeling the capacity and time constraints. Solver parameters can hardly compensate for these weak bounds.

    I would strongly recommend to improve your formulation instead of tuning parameters. One promising concept in compact VRP models is to use single-commodity flows for modeling capacity and time windows. The main idea is to use variables \(f_{ij}\) that denote the vehicle load at node \(i\) (including the demand at \(i\)) when immediately going to node \(j\) afterwards. With flow conservation constraints and linking constraints to your binary arc variables, this should provide a better dual bound than your current model. Similarly, time windows can be modeled with another set of flow variables \(g_{ij}\) that denote the starting time of service at node \(i\) when immediately going to node \(j\) afterwards.

    Best regards,
    Mario

    1
  • Rihot Gusron
    First Comment
    First Question

    my model was this, how can i accomodate to change the time windows constraint? Because they do have large number constraint

    1
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    First of all, you can safely remove the k index, since you visit each customer exactly once. You just limit the number of arcs going out of the depot by m.

    The capacity constraints 5.72 can be replaced by a single-commodity flows, as it is described in this paper by Letchford and Salazar in Section 3.1. Exactly the same modeling approach can be used for the time window constraints.

    This paper by the way gives a nice overview of VRP models.

    0
  • Rihot Gusron
    First Comment
    First Question

    Thanks, and i'm sorry to keep bothering you. I did change to single flow commodity flow but not sure if it is the correct one. The model became like this:

    0
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Please take a closer look at the paper I mentioned before. The flow conservation constraints (6) are defined per customer and sum up all incoming flow minus all outgoing flow.

    The same thing applies to the flow conservation constraints (8) for handling the time windows. Additionally, they have to be transformed to inequalities since you might have some waiting time if you arrive earlier, before the start of the time window.

    0
  • Rihot Gusron
    First Comment
    First Question

    Thanks for your insight sir. Gurobi support was top notch

    0

Please sign in to leave a comment.