Create VRP model without using the routing model

481 views
Skip to first unread message

SW.P

unread,
Mar 3, 2024, 7:42:36 PM3/3/24
to or-tools-discuss
Dear ortools teams, 
Is there any tutorial about how to create a VRP model without using the Routing Library?
I take a look at the `AddCircuit` in TSP examples, but in VRP there's no predefined circuit in hand, so maybe I need to embed it into some branching framework?
Thanks for your advice.

SW

arnaban...@gmail.com

unread,
Mar 4, 2024, 5:02:27 AM3/4/24
to or-tools-discuss
Have you looked at AddMultipleCircuit?

Shanwen Pu

unread,
Mar 8, 2024, 6:43:27 AM3/8/24
to or-tools...@googlegroups.com
Ah, I just found it. Do you know whether it supports VRP? Because in TSP, you just put all arcs into `AddCircuit`, but in VRP, you have no idea which arc belongs to which vehicle. I'm still confused. But thank you for pointing that out.

--
You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/w_E7tzRrPhU/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/43231b35-7d62-4a72-8ffc-b3f6383bcb9bn%40googlegroups.com.

sascha...@gmail.com

unread,
Mar 8, 2024, 7:13:07 AM3/8/24
to or-tools-discuss
That's where the concept of self-loops / self-arcs come into play.

If there are 3 active routes, each node / visit has an active self-arc in exactly 2 out of 3 circuits and no self-loop in the third one.

Or some alternative view: node n assigned to vehicle v IMPLIES self-arc of node n at circuit of vehicle v is ZERO / inactive

Of course some care has to be taken in terms of propagation power: implication / equivalence and such. 

  /**
   * Adds a multiple circuit constraint, aka the "VRP" (Vehicle Routing Problem)
   * constraint.
   *
   * The direct graph where arc #i (from tails[i] to head[i]) is present iff
   * literals[i] is true must satisfy this set of properties:
   * - #incoming arcs == 1 except for node 0.
   * - #outgoing arcs == 1 except for node 0.
   * - for node zero, #incoming arcs == #outgoing arcs.
   * - There are no duplicate arcs.
   * - Self-arcs are allowed except for node 0.
   * - There is no cycle in this graph, except through node 0.
   */
  MultipleCircuitConstraint AddMultipleCircuitConstraint();

Shanwen Pu

unread,
Mar 8, 2024, 7:16:10 AM3/8/24
to or-tools...@googlegroups.com
Thank you. I dont want to use the routing library. Baes on your suggestions, I think maybe i can solve vrp via CPSAT not routing lib. How can i deal with dimension in routing library? Thanks a lot for your help

sascha...@gmail.com

unread,
Mar 8, 2024, 7:30:10 AM3/8/24
to or-tools-discuss
I don't understand your question: "I dont want to use the routing library. [...] solve VRP via CPSAT [...] How can i deal with dimension in routing library".

What i told you about the circuit-constraint has nothing to do with the chosen solver. This is an abstraction used in many solvers, not only or-tools (well... not too many are supporting this constraint in such a general way).

- Handling dimensions aka arc-accumulations of some tour in the routing-solver is relatively simple as there are well-designed abstractions.
- Handling dimensions aka arc-accumulations of some tour in the cp-sat solver is VERY hard and i would not recommend that to people with less experience:
  - A good (solver-unspecific) intro would be "Ascheuer, Norbert, Matteo Fischetti, and Martin Grötschel. "Solving the asymmetric travelling salesman problem with time windows by branch-and-cut." Mathematical programming 90 (2001): 475-506."
  - or-tools also has some code which does something like that (routing-solver initial-solution construction using cp-sat for small instances): converting a routing-model with dimensions to some cp-sat model (relaxing it a bit): but this won't be easy to read.
  - PopulateGeneralizedRouteModelFromRoutingModel might be enough to convince you not to do it ;-)

Summary: The routing-solver brings lots of nice abstractions which are not available in cp-sat solver. CP-SAT has some very expressive global-constraints (opposed to pure MILP solvers; e.g. circuits), but there is still a lot one needs to decompose into smaller things. Accumulations over arcs are something like that.

Laurent Perron

unread,
Mar 8, 2024, 8:10:05 AM3/8/24
to or-tools...@googlegroups.com
Handling dimensions aka arc-accumulations of some tour in the cp-sat solver is VERY hard and i would not recommend that to people with less experience:

??

one cumul var per node.

arc i -> j implies cumul(j) == cumul(i) + transit(i)

there are examples that already implement this.
Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00



You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/42fffcde-b5c1-4bba-b32d-832e19ccc578n%40googlegroups.com.

sascha...@gmail.com

unread,
Mar 8, 2024, 9:15:32 AM3/8/24
to or-tools-discuss
But does it scale out of the box (after those presolve / reformulation steps happening) compared to other a-priori formulations (opposed to cuts) like MTZ-constraints (have bigMs) or Maffioli/Sciomachen style constraints (no bigMs) as the solver will probably have a hard-time to get a tight formulation.
 
Additionally, one probably quickly converges to a point where GLOP won't like the numerics.

This might be an interesting playground for experiments. If i had to guess, i would expect that the shown (simple) approach is nice for the LS/LNS workers (constraint-based structure) but not that nice for the LP-relaxation (at least not out of the box).
 

Shanwen Pu

unread,
Mar 8, 2024, 9:17:09 AM3/8/24
to or-tools...@googlegroups.com
Is there ready to test implementation about vrptw in ortools using cpsat?

Vincent Furnon

unread,
Mar 8, 2024, 9:37:11 AM3/8/24
to or-tools...@googlegroups.com
You actually have one within the routing solver (model in routing_sat.cc) which you can activate from RoutingSearchParameters (use_cp_sat).

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAO7dmmwa9GWLUmMwU0sORXWhvZUO%2Bq789vk82JDhy1aXtJQTDw%40mail.gmail.com.

blind.lin...@gmail.com

unread,
Mar 8, 2024, 11:45:10 AM3/8/24
to 'Vincent Furnon' via or-tools-discuss

My two cents:

I've used CP-Sat for VRP problems.

I agree it is tricky to set up. All of the notions of dimensions etc
that are in the routing solver are gone...you have to make everything
yourself.

I've used both single circuit constraints, and the multiple circuit
constraint APIs.

What helped me the most thinking about how to use the circuit
constraint is to track the literals that indicate if an arc between
two nodes, say A and B, is active. If it is active, then that means
the vehicle (or whatever) goes from A to B. If it is not active, then
the vehicle does not go from A to B. That seems obvious, but keeping
that front-of-mind helps to understand what needs to be done when
building the multiple circuit, and also how to use the results once
you are done.

I have had zero success trying to persuade the routing solver API to
use the cpsat internals via the RoutingSearchParameters (use_cp_sat).

I cannot find the example routing_sat.cc. I'm positive I've seen it
in the past, but grepping the v9.9 code just now for "use_cp_sat"
turns up nothing interesting.

The examples in the code that helped me the most were

The last one is interesting in the context of deciding between one
multiple circuit constraint or multiple regular circuit constraints.
The prize collecting VRP sat is set up with one circuit constraint per
vehicle.

    for v in range(num_vehicles):  
        ...  
        arcs = []  
        for i in all_nodes:  
            arcs.append((i, i, ~is_visited))  
            ...  
            for j in all_nodes:  
                ...  
                arcs.append((i, j, arc_is_used))  
        ...  
        model.add_circuit(arcs)

That's usually how I've done it (one circuit per vehicle). I keep
meaning to test out the difference between a single multiple circuit
and this approach, but I never get around to it.

As to the question of scalability, I haven't seen too much doom and
gloom. It seems from experience (and without having dug into the code
internals too much) that the routing solver has a lot of accumulated
knowledge embedded into it to speed up the job of solving the TSP and
VRP problems. It seems that the circuit constraint code in cpsat is
not yet as evolved as the routing solver in that regard. On the other
hand, it isn't too hard to set up constraints that "help" the solver
prune the circuit constraint--if your problem has such features.

In short, if it is a problem that is reasonable in the routing solver,
then you can expect a reasonable running time in the cp-sat solver
with circuit constraints.

In my opinion, if you are working on a routing problem, stick to the
routing solver as long as you can, until you hit a requirement that
cannot be done. Only switch to cp-sat if you find you can't express
something in the old constraint-solver API.

For example, a few years ago I had to switch a formulation from the
routing solver to the cpsat solver. Over time, the problem slowly
added more and more constraints and features until we had a bin
packing problem and a driver scheduling problem and a routing
problem (assign loads to trucks, schedule drivers and workers on board
the trucks to speed up load/unload service time, and also route the
trucks to customers). The part about scheduling drivers and on-board
workers was the kicker that I could not formulate in the routing
solver at all. After converting everything over, the running time was
a little bit slower than the previous routing version, but it was also
doing a lot more work. And it was able to successfully assign drivers
and workers based on their available schedules...something that I
could not figure out how to do in the routing solver.

Good luck,

James

53 00 <01%2042%2068%2053%2000>

Le ven. 8 mars 2024 à 13:30, sascha...@gmail.com <sascha...@gmail.com>
a écrit :

I don't understand your question: "I dont want to use the routing
library. [...] solve VRP via CPSAT [...] How can i deal with dimension in
routing library".

What i told you about the circuit-constraint has nothing to do with the
chosen solver. This is an abstraction used in many solvers, not only
or-tools (well... not too many are supporting this constraint in such a
general way).

  • Handling dimensions aka arc-accumulations of some tour in the

  • routing-solver is relatively simple as there are well-designed abstractions.
  • Handling dimensions aka arc-accumulations of some tour in the cp-sat
    solver is VERY hard and i would not recommend that to people with less
    experience:
    • A good (solver-unspecific) intro would be "Ascheuer, Norbert,
      Matteo Fischetti, and Martin Grötschel. "Solving the asymmetric travelling
      salesman problem with time windows by branch-and-cut." Mathematical
      programming       90 (2001): 475-506."
    • or-tools also has some code which does something like that
      (routing-solver initial-solution construction using cp-sat for small
      instances): converting a routing-model with dimensions to some cp-sat model
      (relaxing it a bit): but this won't be easy to read.
    • PopulateGeneralizedRouteModelFromRoutingModel might be enough to
      convince you not to do it ;-)

TSP, you just put all arcs into AddCircuit, but in VRP, you have no idea


which arc belongs to which vehicle. I'm still confused. But thank you for
pointing that out.

On Mon, Mar 4, 2024 at 11:02 AM arnaban...@gmail.com <
arnaban...@gmail.com> wrote:

Have you looked at AddMultipleCircuit?

On Monday 4 March 2024 at 06:12:36 UTC+5:30 SW.P wrote:

Dear ortools teams,
Is there any tutorial about how to create a VRP model without
using the Routing Library?
I take a look at the AddCircuit in TSP examples, but in VRP
there's no predefined circuit in hand, so maybe I need to embed it into
some branching framework?
Thanks for your advice.

SW

You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group. To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/w_E7tzRrPhU/unsubscribe . To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/43231b35-7d62-4a72-8ffc-b3f6383bcb9bn%40googlegroups.com https://groups.google.com/d/msgid/or-tools-discuss/43231b35-7d62-4a72-8ffc-b3f6383bcb9bn%40googlegroups.com?utm_medium=email&utm_source=footer .

You received this message because you are subscribed to a topic in
the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit
https://groups.google.com/d/topic/or-tools-discuss/w_E7tzRrPhU/unsubscribe
.
To unsubscribe from this group and all its topics, send an email to
or-tools-discu...@googlegroups.com.

To view this discussion on the web visit

You received this message because you are subscribed to the Google
Groups "or-tools-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send
an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/or-tools-discuss/42fffcde-b5c1-4bba-b32d-832e19ccc578n%40googlegroups.com

--
You received this message because you are subscribed to a topic in the
Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit
https://groups.google.com/d/topic/or-tools-discuss/w_E7tzRrPhU/unsubscribe
.
To unsubscribe from this group and all its topics, send an email to
or-tools-discu...@googlegroups.com.
To view this discussion on the web visit

--
You received this message because you are subscribed to the Google Groups
"or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an
email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit

-- You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

Laurent Perron

unread,
Mar 8, 2024, 12:31:20 PM3/8/24
to or-tools-discuss
Thanks James for that post. I could not agree more.

PS: the cp-sat routing code should be in the ortools/constraint_solver directory.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/ZetAjzSrDIsV6/p0%4062920e8ad954.
Reply all
Reply to author
Forward
0 new messages