Skip to main content

Vehicle Routing Problem on Python using Gurobi

Answered

Comments

2 comments

  • Thuy Anh Pham
    Gurobi-versary
    First Comment
    First Question

    I have set the time limit to 100 seconds and the report is following:

    Set parameter TimeLimit to value 100
    Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (win64)
    Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
    Optimize a model with 3301 rows, 7893 columns and 55427 nonzeros
    Model fingerprint: 0xa97ff95d
    Variable types: 231 continuous, 7662 integer (7623 binary)
    Coefficient statistics:
      Matrix range     [1e+00, 1e+05]
      Objective range  [6e-02, 6e+00]
      Bounds range     [1e+00, 1e+00]
      RHS range        [3e-01, 1e+05]
    Presolve removed 624 rows and 744 columns
    Presolve time: 0.16s
    Presolved: 2677 rows, 7149 columns, 51719 nonzeros
    Variable types: 33 continuous, 7116 integer (7077 binary)
    
    Root relaxation: objective 1.631622e+01, 647 iterations, 0.06 seconds (0.03 work units)
    
        Nodes    |    Current Node    |     Objective Bounds      |     Work
     Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
    
         0     0   16.31622    0   71          -   16.31622      -     -    0s
         0     0   18.02170    0   94          -   18.02170      -     -    0s
         0     0   18.03463    0  103          -   18.03463      -     -    1s
         0     0   18.74425    0  122          -   18.74425      -     -    1s
         0     0   18.74926    0  129          -   18.74926      -     -    1s
         0     0   18.75114    0  130          -   18.75114      -     -    1s
         0     0   18.75749    0  137          -   18.75749      -     -    1s
         0     0   18.89854    0  111          -   18.89854      -     -    2s
         0     0   18.99712    0   92          -   18.99712      -     -    2s
         0     0   18.99712    0   84          -   18.99712      -     -    2s
         0     0   19.08739    0   76          -   19.08739      -     -    2s
         0     0   19.09536    0   76          -   19.09536      -     -    2s
         0     0   19.09536    0   73          -   19.09536      -     -    2s
         0     0   19.09536    0   76          -   19.09536      -     -    2s
         0     0   19.10368    0   83          -   19.10368      -     -    3s
         0     0   19.10368    0   60          -   19.10368      -     -    3s
         0     2   19.12233    0   58          -   19.12233      -     -    4s
        11    16   19.12463    4   68          -   19.12233      -  69.1    5s
       456   444 infeasible   70               -   19.12233      -  45.3   10s
      1080   955   25.30838   89   60          -   19.12233      -  44.0   15s
      1086   959   19.41407   15  101          -   19.15521      -  43.7   20s
      1090   962   19.65402   26  140          -   19.23144      -  43.6   25s
      1097   966   19.49847   14   84          -   19.38201      -  43.3   30s
      1105   972   32.45293   88  104          -   19.50556      -  43.0   35s
      1112   976   33.33750   74  172          -   19.54711      -  42.7   40s
      1119   981   31.49252  132   96          -   19.54958      -  42.4   45s
      1128   987   19.55443   11  194          -   19.55443      -  42.1   50s
      1136   992   19.55739   18  126          -   19.55739      -  41.8   55s
      1145   999   20.27492   24  117          -   19.55739      -  74.4   61s
      1150  1003   35.98030  139  168          -   19.55739      -  74.0   65s
      1155  1006   19.97654   17  120          -   19.57099      -  73.7   70s
      1161  1010   28.11875  104  180          -   19.58055      -  73.3   76s
      1170  1016   19.58919   25  185          -   19.58919      -  72.8   80s
      1177  1021   34.82520   97  116          -   19.60531      -  72.3   88s
      1178  1024   19.60531   19  112          -   19.60531      -  50.0   93s
      1184  1030   19.66622   21  146          -   19.66622      -  50.8   96s
      1251  1079   19.80732   28  101          -   19.78275      -  58.5  100s
    
    Cutting planes:
      Learned: 4
      Gomory: 30
      Implied bound: 6
      Clique: 1
      MIR: 12
      StrongCG: 1
      Flow cover: 72
      Zero half: 26
      RLT: 103
      Relax-and-lift: 10
    
    Explored 1259 nodes (124060 simplex iterations) in 100.04 seconds (55.85 work units)
    Thread count was 8 (of 8 available processors)
    
    Solution count 0
    
    Time limit reached
    Best objective -, best bound 1.978274782307e+01, gap -
    No solution found.
    
     
     
    0
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Hi Thuy Anh Pham,

    Vehicle routing problems are in general very difficult combinatorial optimization problems. State-of-the-art solution approaches involve a highly-tuned and sophisticated branch-price-and-cut algorithm. You can read more details for example in the famous book:

    Toth, Paolo, and Daniele Vigo, eds. Vehicle routing: problems, methods, and applications. Society for industrial and applied mathematics, 2014.

    There are plenty of different ways to model the same vehicle routing problem, in particular to deal with subtour elimination and resource constraints like capacity or time. Your model is the classical Big-M model and this is known to provide very weak dual bounds.

    Additionally, the combinatorial structure of the problem makes it difficult to find feasible solutions by modern general-purpose MIP solvers like Gurobi (but this applies to others as well).
    There are different ways to at least improve the chance to find good solutions for this model:

    • You could create a solution with some simple heuristic and hand it over to Gurobi as MIP start. Then, the builtin improvement heuristics might be able to find better solutions more easily.
    • You could try the optional NoRel heuristic in Gurobi that often helps for highly combinatorial problems like scheduling, routing, or other graph problems. You can enable it with parameter NoRelHeurTime defining the time in seconds spent for this heuristic before the actual branch-and-bound part starts.

    Additionally, I would recommend to work on your formulation:

    • You could push the limits further by using stronger modeling techniques like commodity flows to avoid the Big-M constraints.
    • Additionally, adding connectivity or capacity cuts dynamically in callbacks (branch-and-cut approach) usually help to improve performance.
    • If the fleet is homogeneous, you can get rid of the vehicle index k in your variables (by using appropriate modeling techniques from the literature).

    Best regards,
    Mario

    1

Please sign in to leave a comment.