2
$\begingroup$

I am trying to solve Capacitated VRP with Time Window for 50 demand points. I was trying to optimize this in Gurobi Solver but it doesn't give good answer like optimality gap is 30% or more. Any idea how to rectify this?

$\endgroup$

5 Answers 5

4
$\begingroup$

If you are fine with using an heuristic solver, that does not provide you gaps or bounds, you can use PyVRP. It employs the current state-of-the-art heuristic for the VRPTW (Hybrid Genetic Search).

Wouda, Niels A., Leon Lan, and Wouter Kool. "PyVRP: A high-performance VRP solver package." INFORMS Journal on Computing (2024).

If you want to use an exact solver, then you can checkout VRPSolver.

Pessoa, A., Sadykov, R., Uchoa, E., Vanderbeck, F.: A generic exact solver for vehicle routing and related problems. Mathematical Programming B, 183:483-523, 2020.

$\endgroup$
2
  • $\begingroup$ Don't skip on googles or-tools routing-solver. It's a well-designed rich-VRP solver. While the former paper talks about non state-of-the-art performance, i somewhat doubt that and i'm often wondering why it's often exluded from benchmarks. It's actively mantained, probably has the biggest community + examples and is backing multiple commercial applications (at Google, nextmv). $\endgroup$
    – sascha
    Commented May 18 at 12:32
  • 2
    $\begingroup$ I agree that OR-Tools is useful for many problem types and nicely configurable. Checkout Vidal's Paper: "Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood" where he compares different heuristics for the CVRP. OR-Tools performs the worst most of the time. $\endgroup$
    – PeterD
    Commented May 18 at 19:53
1
$\begingroup$

I think it is important to note that even thought the gap is large (15%) the solution may still be very good, actually.

My experience is that the linear programming bound obtained for most models of the CVRP-TW is rather weak. Hence, you may have an optimal solution at hand (strong upper bound), but at the same time, you have a weak lower bound.

If you are trying to solve a MTZ-based model directly using a MILP solver, you are almost certainly bound for disappointment. These formulations are notoriously known for providing a weak lower bound.

$\endgroup$
0
$\begingroup$

It's hard to give a meaningful response without knowing more about the model. Two possibilities immediately come to mind. First, if you are using a "big M" type formulation, finding tighter (valid) values for $M$ may help tighten the lower bound. Second, if your model contains symmetry (for instance, because all vehicles are identical), either adding symmetry-breaking constraints or cranking up whatever parameter Gurobi has for symmetry mitigation might help.

$\endgroup$
0
$\begingroup$

Hexaly can solve your CVRPTW problem optimally in minutes or even seconds.

Hexaly relies on state-of-the-art Branch-Cut-Price techniques, such as those in VRPSolver, to deliver lower bounds and prove optimality. Depending on the nature of your instances, you can get optimality proofs for instances with 100-200 points.

Hexaly also relies on state-of-the-art heuristic techniques to deliver high-quality, feasible solutions to instances with 10,000 points in minutes of running time.

Check this benchmark here. Explore Hexaly online documentation to get code examples in Python, Java, C#, and C++ for the CVRPTW and other Vehicle Routing problems.

Disclaimer: Hexaly is a commercial mathematical optimization solver. Nevertheless, free academic licenses are available to students and academics.

$\endgroup$
0
$\begingroup$

Timefold Solver is an open source solver (Apache License) with a CVRPTW implementation (including a web UI) in our quickstarts.

enter image description here

It supports Java, Kotlin and soon Python.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.