Skip to main content

Vehicle Routing Problem with Time Windows with Gurobi and Python

Answered

Comments

7 comments

  • Mads Hoffmann
    First Question
    First Comment


    0
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Hi Mads,

    The Big-M model is known to provide only weak dual bounds. There are a few things that can be improved in this formulation, e.g., to avoid the vehicle index k if the fleet is homogeneous. You could take a look at my notebooks on the CVRP and the VRPTW here: https://github.com/ruthmair/vrp

    In this notebooks I also show different formulations that might provide better dual bounds.

    Still, VRPs are very tough to solve, even for small sizes with less than 100 customers. All the formulations in my notebooks above are NOT state-of-the-art, they are mainly easy to use. State-of-the-art solution approaches are based on branch-prize-and-cut algorithms that are very sophisticated to implement.

    Best regards,
    Mario

    1
  • Mads Hoffmann
    First Question
    First Comment

    Thank you Mario! Some very helpful information.

    Why is it important to linearize the MIP with big-M?

    Is it necessary to linearize VRPs?

    Im trying to work out why the big M is necessary.

    Have a lovely weekend.

    Kind regards,
    Mads

    0
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    In the formulation from your initial screenshot, constraints (5.6) ensure that the time windows are satisfied. But in this type of formulation, those constraints are quadratic. You could also add quadratic constraints to Gurobi but in most cases performance will be worse than linearizing those constraints via Big-Ms. But you could still try!

    There are other types of VRP formulations, e.g., the single-commodity flow model in the notebook I linked above. In this case you do not need to linearize since it is a different modeling concept.

    There are even better formulations based on route variables where one variable corresponds to a whole route. To solve such formulations you need to implement column (and cut) generation methods that are not easy to do. If you manage to implement them correctly, the solution performance will be much better though.

    0
  • Francisco Zenteno
    First Comment

    Mario Ruthmair correct me if I am wrong but Gurobi does not allow to do Branch-Price-Cut right? we can only apply the pricing at the root node.

    Best regards,

     

    0
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Indeed, Gurobi (and most other commercial solvers) do not provide a branch-price-and-cut framework. What people are usually doing is:

    • Use Gurobi (or another solver) only as LP solver and implement their own custom branch-and-bound framework. The benefit is that you have full control of branching, cutting, node selection, etc., and are able to customize it to your application.
    • As you mentioned already, it is possible with Gurobi to do column generation in the root node of the branch-and-bound tree and then keep the variable set fixed in the branch-and-bound phase. Note that this approach might not give you an optimal solution, this is just a heuristic.
    • Use an alternative solver like SCIP that implements branch-price-and-cut. You might not have the same performance as with commercial solvers, but there is no need for your own implementation.
    • There are other very successful approaches, e.g., by Baldacci et al., that do not require a branch-and-price framework to solve route-based formulations.
    0
  • YIHAN ZHOU
    First Comment
    First Question

    Can you I see how your cvs data looks like?

    0

Please sign in to leave a comment.