VRP Planning over multiple days
Erik De Kuyffer
blind.line
On Apr 15, 2023, at 15:22, Erik De Kuyffer <ede...@gmail.com> wrote:
Hello,
--
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/175312d1-ef63-410f-81f7-3cba0d101635n%40googlegroups.com.
Erik De Kuyffer
blind.line
Many thanks for your reply.I try to explain a bit more:* First of all I have put a constraint so that the routing for each vehicle is limited to 480 minutes (corresponding to 8 working hours).
* So every vehicle needs to be back at the depot before the end of the day.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f739a815-fa5d-4219-b9a6-63ef5003fc06n%40googlegroups.com.
Erik De Kuyffer
0 Load(0) -> 40 Load(0) -> 30 Load(0) -> 20 Load(0) -> 10 Load(0) -> 17 Load(120) -> 12 Load(480) -> 11 Load(630) -> 28 Load(775) -> 21 Load(1105) -> 0 Load(1105)
Time of the route: 1275m
Load of the route: 1105
blind.lin...@gmail.com
Well, first, do search this forum as there was a long discussion of this a few years ago. I actually wrote up my ideas in a blog post here: https://activimetrics.com/blog/ortools/multiday_tsp/ I probably won't have time today to look at this more closely. Basically, the idea is that days end every 480 minutes. So the window for visiting the depot nodes to "return home" should be exactly 480, 960, etc. From a quick scan of your reply, below, it is clear that if the dummy depot nodes are all visited at time 0, then you have not set up the constraints properly on those nodes. You need to make time windows on those nodes, and add enough slack to allow for any gaps in time. hopefully my post or the other ways of doing this that were discussed at the time will give you more insights. James
On Tue, Apr 18, 2023 at 12:38:35PM -0700, Erik De Kuyffer wrote: >
Hello, > > {.quotesubsequent}Apparently my last post did not
apprear in the discussion. > > I am afraid that I don't fully
understand what you mean. :-( > I have added several dummy depots, in
my attached example, these extra > depots are nodes 10, 20, 30, 40.
> > When I run the algorithm, I get the following result, meaning
that node 20, > 30 and 40 are all at the same vehicle... > >
Route for vehicle 3: > 0 Load(0) -> 40 Load(0) -> 30 Load(0)
-> 20 Load(0) -> 10 Load(0) -> > 17 Load(120) -> 12
Load(480) -> 11 Load(630) -> 28 Load(775) -> 21 > Load(1105)
-> 0 Load(1105) > Time of the route: 1275m > Load of the route:
1105 > > Could you perhaps help me? If you could tell me how to
add the extension to > the code? > > Two remarks: > * I make
sure that nodes 1, 5, 8 and 32 are all visited by the same vehicle >
0 > * I indicate that some vehicles start at another node than the
depot (node > 0) > > Thanks! > Erik > > > Op zondag
16 april 2023 om 19:59:58 UTC+2 schreef blind.lin...@gmail.com: >
> > > > On Apr 16, 2023, at 04:36, Erik De Kuyffer
<ede...@gmail.com> wrote: > > > > Hello James, >
> > > > > Many thanks for your reply. > > > >
I try to explain a bit more: > > * First of all I have put a
constraint so that the routing for each > > vehicle is limited to
480 minutes (corresponding to 8 working hours). > > > > >
> So you need multiple such periods. The vehicle maximum time is
480days > > > > So every vehicle needs to be back
at the depot before the end of the day. > > > > > > So
make one dummy node per vehicle per day, that cannot be dropped. If day
> > is a zero based list [0,1,2], then time windows for these
dummy nodes are > > (day480, (day+1)480). > > >
> This way, each of the vehicles must return home to the daily depot
before > > time runs out. > > > > You have to add
slack in there to make sure the times add up. when the > > vehicle
“leaves” the daily depot the time is really (day+1)480, otherwise
> > you might get strange results. > > > > Usually I
find it easier to make two dummy nodes, one for night return, > >
one for morning depart, so that the slack variables add up and I don’t
get > > too confused. > > > > This way I get the
planning for all vehicles for 1 day. > > > > However, there
are too many locations to be visited to put them all in one > >
day. > > So, I would like to make a planning that spreads over a
few days, but for > > each day the travel (+service time) remains
limited to 480 minuts and at > > the end of each day, the vehicle
needs to return to the depot. > > > > Hope this clarifies a
bit more? > > Thanks! > > Erik > > > > Op zondag
16 april 2023 om 08:44:03 UTC+2 schreef blind.lin...@gmail.com: >
> > >> Yes I’ve done that many times on several ways. >
>> > >> If the days are exactly the same, you can just
skip the off time, and put > >> in a dummy “return home” node
that has a time window that ends at the start > >> of the next
day and that cannot be dropped. > >> > >> Lots of
other strategies too, but it all depends on your requirements. >
>> > >> And I’m pretty sure there was a discussion in
this forum a few years back > >> on using slack variables to
accomplish this. > >> > >> James > >> >
>> On Apr 15, 2023, at 15:22, Erik De Kuyffer
<ede...@gmail.com> wrote: > >> > >> Hello, >
>> > >> > >> Does anyone have some experience in
the use of the VRP solver for a > >> planning spread over
multiple days? > >> > >> I can make an excellent
planning for one day (8 working hours), but I > >> would like
to extend this to more days (working days of 8 hours, with a gap >
>> op 16h). > >> > >> Many thanks for your help,
> >> Erik > >> > >> -- > >> 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/175312d1-ef63-410f-81f7-3cba0d101635n%40googlegroups.com
> >> https://groups.google.com/d/msgid/or-tools-discuss/175312d1-ef63-410f-81f7-3cba0d101635n%40googlegroups.com?utm_medium=email&utm_source=footer
> >> . > >> > >> -- > > 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/f739a815-fa5d-4219-b9a6-63ef5003fc06n%40googlegroups.com
> > https://groups.google.com/d/msgid/or-tools-discuss/f739a815-fa5d-4219-b9a6-63ef5003fc06n%40googlegroups.com?utm_medium=email&utm_source=footer
> > . > > > > > > -- > 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/0b6a8672-f59d-4b36-9e52-93284b07cefan%40googlegroups.com.
> """Capacited Vehicles Routing Problem (CVRP).""" > > from
lzma import is_check_supported > from tkinter import BooleanVar >
from ortools.constraint_solver import routing_enums_pb2 > from
ortools.constraint_solver import pywrapcp > import numpy as np >
> > def create_data_model(): > """Stores the data for the
problem.""" > data = {} > data['distance_matrix'] = [ > [ 0,
82, 47, 108, 136, 6, 4, 42, 54, 54, 0, 65, 75, 10, 5, 47, 12, 51, 88,
21, 0, 57, 60, 36, 55, 30, 20, 25, 62, 59, 0, 48, 59, 8, 90, 10, 59, 7,
49, 37, 0 ], > [ 82, 0, 128, 184, 211, 81, 78, 63, 135, 27, 82, 140,
154, 79, 78, 39, 81, 133, 165, 66, 82, 132, 23, 117, 129, 71, 75, 101,
137, 133, 82, 129, 140, 76, 165, 85, 134, 80, 114, 104, 82 ], > [ 47,
128, 0, 67, 93, 47, 50, 78, 12, 101, 47, 31, 33, 50, 50, 91, 48, 11, 47,
63, 47, 28, 106, 12, 30, 65, 59, 31, 29, 32, 47, 1, 16, 52, 51, 46, 29,
48, 43, 40, 47 ], > [108, 184, 67, 0, 28, 105, 110, 123, 70, 157,
108, 44, 34, 107, 109, 145, 104, 71, 20, 118, 108, 52, 161, 78, 55, 114,
125, 84, 47, 51, 108, 66, 68, 111, 19, 110, 50, 107, 71, 80, 108 ], >
[136, 211, 93, 28, 0, 133, 138, 151, 95, 185, 136, 72, 61, 135, 137,
172, 132, 96, 47, 145, 136, 80, 188, 105, 83, 141, 152, 112, 75, 79,
136, 92, 92, 139, 47, 137, 78, 134, 98, 107, 136 ], > [ 6, 81, 47,
105, 133, 0, 5, 37, 55, 54, 6, 62, 73, 4, 4, 45, 5, 53, 86, 17, 6, 54,
59, 36, 51, 25, 25, 21, 59, 56, 6, 47, 60, 6, 87, 16, 56, 2, 44, 32, 6
], > [ 4, 78, 50, 110, 138, 5, 0, 39, 57, 51, 4, 66, 77, 7, 2, 43,
10, 55, 90, 17, 4, 58, 56, 39, 56, 27, 20, 26, 63, 60, 4, 50, 62, 4, 92,
13, 60, 5, 49, 37, 4 ], > [ 42, 63, 78, 123, 151, 37, 39, 0, 88, 41,
42, 81, 96, 33, 37, 25, 33, 87, 106, 22, 42, 73, 41, 70, 69, 13, 53, 47,
79, 73, 42, 79, 93, 35, 105, 51, 75, 36, 53, 45, 42 ], > [ 54, 135,
12, 70, 95, 55, 57, 88, 0, 108, 54, 39, 37, 59, 57, 100, 57, 2, 50, 72,
54, 38, 113, 19, 41, 75, 63, 42, 38, 43, 54, 12, 5, 60, 57, 50, 40, 56,
55, 52, 54 ], > [ 54, 27, 101, 157, 185, 54, 51, 41, 108, 0, 54, 114,
127, 51, 51, 16, 54, 106, 139, 40, 54, 105, 7, 90, 102, 45, 50, 74, 111,
106, 54, 102, 113, 48, 138, 58, 107, 53, 89, 78, 54 ], > [ 0, 82, 47,
108, 136, 6, 4, 42, 54, 54, 0, 65, 75, 10, 5, 47, 12, 51, 88, 21, 0, 57,
60, 36, 55, 30, 20, 25, 62, 59, 0, 48, 59, 8, 90, 10, 59, 7, 49, 37, 0
], > [ 65, 140, 31, 44, 72, 62, 66, 81, 39, 114, 65, 0, 16, 63, 66,
101, 60, 39, 25, 74, 65, 8, 117, 39, 12, 71, 82, 41, 3, 9, 65, 30, 40,
67, 25, 68, 7, 63, 31, 37, 65 ], > [ 75, 154, 33, 34, 61, 73, 77, 96,
37, 127, 75, 16, 0, 75, 77, 115, 72, 38, 14, 87, 75, 24, 130, 44, 28,
85, 91, 53, 18, 25, 75, 32, 36, 79, 20, 76, 23, 75, 47, 52, 75 ], > [
10, 79, 50, 107, 135, 4, 7, 33, 59, 51, 10, 63, 75, 0, 6, 41, 4, 57, 88,
13, 10, 55, 56, 40, 53, 20, 27, 23, 60, 57, 10, 51, 64, 5, 89, 20, 57,
3, 44, 32, 10 ], > [ 5, 78, 50, 109, 137, 4, 2, 37, 57, 51, 5, 66,
77, 6, 0, 43, 8, 55, 90, 16, 5, 58, 56, 39, 55, 25, 22, 25, 63, 59, 5,
51, 62, 3, 91, 14, 60, 3, 48, 36, 5 ], > [ 47, 39, 91, 145, 172, 45,
43, 25, 100, 16, 47, 101, 115, 41, 43, 0, 44, 98, 126, 28, 47, 93, 16,
81, 89, 31, 48, 62, 98, 93, 47, 92, 105, 40, 126, 53, 95, 43, 75, 65, 47
], > [ 12, 81, 48, 104, 132, 5, 10, 33, 57, 54, 12, 60, 72, 4, 8, 44,
0, 55, 85, 15, 12, 52, 59, 38, 49, 20, 30, 19, 57, 53, 12, 48, 62, 8,
85, 21, 54, 5, 40, 28, 12 ], > [ 51, 133, 11, 71, 96, 53, 55, 87, 2,
106, 51, 39, 38, 57, 55, 98, 55, 0, 51, 70, 51, 38, 111, 17, 41, 73, 61,
40, 38, 42, 51, 11, 7, 58, 57, 48, 39, 54, 54, 50, 51 ], > [ 88, 165,
47, 20, 47, 86, 90, 106, 50, 139, 88, 25, 14, 88, 90, 126, 85, 51, 0,
99, 88, 34, 142, 58, 37, 96, 104, 65, 28, 34, 88, 46, 49, 92, 9, 90, 32,
87, 55, 62, 88 ], > [ 21, 66, 63, 118, 145, 17, 17, 22, 72, 40, 21,
74, 87, 13, 16, 28, 15, 70, 99, 0, 21, 66, 43, 53, 63, 13, 31, 34, 71,
67, 21, 64, 77, 13, 99, 29, 68, 16, 51, 39, 21 ], > [ 0, 82, 47, 108,
136, 6, 4, 42, 54, 54, 0, 65, 75, 10, 5, 47, 12, 51, 88, 21, 0, 57, 60,
36, 55, 30, 20, 25, 62, 59, 0, 48, 59, 8, 90, 10, 59, 7, 49, 37, 0 ],
> [ 57, 132, 28, 52, 80, 54, 58, 73, 38, 105, 57, 8, 24, 55, 58, 93,
52, 38, 34, 66, 57, 0, 109, 34, 5, 62, 75, 33, 5, 4, 57, 27, 40, 59, 33,
60, 2, 55, 24, 29, 57 ], > [ 60, 23, 106, 161, 188, 59, 56, 41, 113,
7, 60, 117, 130, 56, 56, 16, 59, 111, 142, 43, 60, 109, 0, 95, 105, 47,
56, 78, 114, 109, 60, 106, 118, 53, 142, 64, 110, 57, 91, 81, 60 ], >
[ 36, 117, 12, 78, 105, 36, 39, 70, 19, 90, 36, 39, 44, 40, 39, 81, 38,
17, 58, 53, 36, 34, 95, 0, 35, 57, 48, 25, 36, 38, 36, 13, 24, 42, 62,
34, 36, 38, 43, 37, 36 ], > [ 55, 129, 30, 55, 83, 51, 56, 69, 41,
102, 55, 12, 28, 53, 55, 89, 49, 41, 37, 63, 55, 5, 105, 35, 0, 59, 73,
30, 10, 4, 55, 30, 44, 57, 36, 59, 5, 53, 19, 25, 55 ], > [ 30, 71,
65, 114, 141, 25, 27, 13, 75, 45, 30, 71, 85, 20, 25, 31, 20, 73, 96,
13, 30, 62, 47, 57, 59, 0, 44, 34, 68, 63, 30, 66, 80, 23, 95, 40, 64,
24, 44, 34, 30 ], > [ 20, 75, 59, 125, 152, 25, 20, 53, 63, 50, 20,
82, 91, 27, 22, 48, 30, 61, 104, 31, 20, 75, 56, 48, 73, 44, 0, 44, 79,
77, 20, 61, 68, 23, 107, 14, 77, 25, 69, 57, 20 ], > [ 25, 101, 31,
84, 112, 21, 26, 47, 42, 74, 25, 41, 53, 23, 25, 62, 19, 40, 65, 34, 25,
33, 78, 25, 30, 34, 44, 0, 38, 34, 25, 32, 47, 27, 66, 31, 35, 22, 26,
15, 25 ], > [ 62, 137, 29, 47, 75, 59, 63, 79, 38, 111, 62, 3, 18,
60, 63, 98, 57, 38, 28, 71, 62, 5, 114, 36, 10, 68, 79, 38, 0, 7, 62,
28, 39, 64, 28, 65, 4, 60, 29, 34, 62 ], > [ 59, 133, 32, 51, 79, 56,
60, 73, 43, 106, 59, 9, 25, 57, 59, 93, 53, 42, 34, 67, 59, 4, 109, 38,
4, 63, 77, 34, 7, 0, 59, 31, 44, 61, 32, 63, 3, 57, 22, 29, 59 ], > [
0, 82, 47, 108, 136, 6, 4, 42, 54, 54, 0, 65, 75, 10, 5, 47, 12, 51, 88,
21, 0, 57, 60, 36, 55, 30, 20, 25, 62, 59, 0, 48, 59, 8, 90, 10, 59, 7,
49, 37, 0 ], > [ 48, 129, 1, 66, 92, 47, 50, 79, 12, 102, 48, 30, 32,
51, 51, 92, 48, 11, 46, 64, 48, 27, 106, 13, 30, 66, 61, 32, 28, 31, 48,
0, 16, 53, 51, 47, 29, 49, 43, 40, 48 ], > [ 59, 140, 16, 68, 92, 60,
62, 93, 5, 113, 59, 40, 36, 64, 62, 105, 62, 7, 49, 77, 59, 40, 118, 24,
44, 80, 68, 47, 39, 44, 59, 16, 0, 65, 55, 55, 41, 61, 58, 56, 59 ],
> [ 8, 76, 52, 111, 139, 6, 4, 35, 60, 48, 8, 67, 79, 5, 3, 40, 8,
58, 92, 13, 8, 59, 53, 42, 57, 23, 23, 27, 64, 61, 8, 53, 65, 0, 93, 17,
61, 4, 48, 37, 8 ], > [ 90, 165, 51, 19, 47, 87, 92, 105, 57, 138,
90, 25, 20, 89, 91, 126, 85, 57, 9, 99, 90, 33, 142, 62, 36, 95, 107,
66, 28, 32, 90, 51, 55, 93, 0, 93, 31, 88, 52, 61, 90 ], > [ 10, 85,
46, 110, 137, 16, 13, 51, 50, 58, 10, 68, 76, 20, 14, 53, 21, 48, 90,
29, 10, 60, 64, 34, 59, 40, 14, 31, 65, 63, 10, 47, 55, 17, 93, 0, 63,
17, 56, 45, 10 ], > [ 59, 134, 29, 50, 78, 56, 60, 75, 40, 107, 59,
7, 23, 57, 60, 95, 54, 39, 32, 68, 59, 2, 110, 36, 5, 64, 77, 35, 4, 3,
59, 29, 41, 61, 31, 63, 0, 57, 24, 30, 59 ], > [ 7, 80, 48, 107, 134,
2, 5, 36, 56, 53, 7, 63, 75, 3, 3, 43, 5, 54, 87, 16, 7, 55, 57, 38, 53,
24, 25, 22, 60, 57, 7, 49, 61, 4, 88, 17, 57, 0, 45, 33, 7 ], > [ 49,
114, 43, 71, 98, 44, 49, 53, 55, 89, 49, 31, 47, 44, 48, 75, 40, 54, 55,
51, 49, 24, 91, 43, 19, 44, 69, 26, 29, 22, 49, 43, 58, 48, 52, 56, 24,
45, 0, 12, 49 ], > [ 37, 104, 40, 80, 107, 32, 37, 45, 52, 78, 37,
37, 52, 32, 36, 65, 28, 50, 62, 39, 37, 29, 81, 37, 25, 34, 57, 15, 34,
29, 37, 40, 56, 37, 61, 45, 30, 33, 12, 0, 37 ], > [ 0, 82, 47, 108,
136, 6, 4, 42, 54, 54, 0, 65, 75, 10, 5, 47, 12, 51, 88, 21, 0, 57, 60,
36, 55, 30, 20, 25, 62, 59, 0, 48, 59, 8, 90, 10, 59, 7, 49, 37, 0 ],
> ] > > data['demands'] = [0, 45, 120, 160, 210, 190, 320, 120,
90, 220, 0, 150, 360, 90, 190, 290, 75, 120, 80, 150, 0, 330, 45, 75,
260, 240, 135, 110, 145, 180, 0, 150, 75, 95, 250, 65, 240, 170, 105,
230, 0] > data['time_matrix'] = np.array(data['distance_matrix']) +
data['demands'] > data['num_vehicles'] = 6 > data['depot'] = 0
> data['two_workers'] = [1, 5, 8, 32] > data['vehicle_capacities']
= [2400, 2400, 2400, 2400, 2400, 2400] > data['starts'] = [0, 0, 0,
0, 0, 0] > data['ends'] = [0, 0, 0, 0, 0, 0] >
data['time_windows'] = [
> (0, 480), # depot > (0, 6240), # 1 > (0, 6240), # 2 > (0,
6240), # 3 > (0, 6240), # 4 > (0, 6240), # 5 > (0, 6240), # 6
> (0, 6240), # 7 > (0, 6240), # 8 > (0, 6240), # 9 > (0,
480), # depot > (0, 6240), # 1 > (0, 6240), # 2 > (0, 6240), #
3 > (0, 6240), # 4 > (0, 6240), # 5 > (0, 6240), # 6 > (0,
6240), # 7 > (0, 6240), # 8 > (0, 6240), # 9 > (0, 480), #
depot > (0, 6240), # 1 > (0, 6240), # 2 > (0, 6240), # 3 >
(0, 6240), # 4 > (0, 6240), # 5 > (0, 6240), # 6 > (0, 6240), #
7 > (0, 6240), # 8 > (0, 6240), # 9 > (0, 480), # depot >
(0, 6240), # 1 > (0, 6240), # 2 > (0, 6240), # 3 > (0, 6240), #
4 > (0, 6240), # 5 > (0, 6240), # 6 > (0, 6240), # 7 > (0,
6240), # 8 > (0, 6240), # 9 > (0, 480), # depot > ] > return
data > > def print_solution(data, manager, routing, assignment):
> """Prints assignment on console.""" > print(f'Objective:
{assignment.ObjectiveValue()}') > # Display dropped nodes. >
dropped_nodes = 'Dropped nodes:' > for node in range(routing.Size()):
> if routing.IsStart(node) or routing.IsEnd(node): > continue >
if assignment.Value(routing.NextVar(node)) == node: > dropped_nodes
+= ' {}'.format(manager.IndexToNode(node)) > print(dropped_nodes)
> > # Display routes > total_distance = 0 > total_load = 0
> for vehicle_id in range(data['num_vehicles']): > index =
routing.Start(vehicle_id) > plan_output = 'Route for vehicle
{}:'.format(vehicle_id) > route_distance = 0 > route_load = 0 >
while not routing.IsEnd(index): > node_index =
manager.IndexToNode(index) > route_load +=
data['demands'][node_index] > plan_output += ' {0} Load({1}) ->
'.format(node_index, route_load) > previous_index = index > index
= assignment.Value(routing.NextVar(index)) > route_distance +=
routing.GetArcCostForVehicle( > previous_index, index, vehicle_id)
> plan_output += ' {0} Load({1})'.format(manager.IndexToNode(index),
> route_load) > plan_output += 'Time of the route:
{}m'.format(route_distance) > plan_output += 'Load of the route:
{}'.format(route_load) > print(plan_output) > total_distance +=
route_distance > total_load += route_load > print('Total Distance
of all routes: {}m'.format(total_distance)) > print('Total Load of
all routes: {}'.format(total_load)) > > > def main(): >
"""Solve the CVRP problem.""" > # Instantiate the data problem. >
data = create_data_model() > > # Create the routing index manager
with different depots > manager =
pywrapcp.RoutingIndexManager(len(data['time_matrix']), >
data['num_vehicles'], data['starts'], > data['ends']) > # Create
Routing Model. > routing = pywrapcp.RoutingModel(manager) > > #
Create and register a transit callback. > def
distance_callback(from_index, to_index): > """Returns the distance
between the two nodes.""" > # Convert from routing variable Index to
distance matrix NodeIndex. > from_node =
manager.IndexToNode(from_index) > to_node =
manager.IndexToNode(to_index) > return
data['time_matrix'][from_node][to_node] > > transit_callback_index
= routing.RegisterTransitCallback(distance_callback) > > # Define
cost of each arc. >
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) >
> # Add Time Dimension: The total route + work cannot be longer than
480min (8h work) > routing.AddDimension( > transit_callback_index,
> 6240, # null capacity slack > 6240, # vehicle maximum time of
route > True, # start cumul to zero > 'Time',) > >
time_dimension = routing.GetDimensionOrDie('Time') >
time_dimension.SetGlobalSpanCostCoefficient(10) > > # Add time
window constraints for each location except depot. > for
location_idx, time_window in enumerate(data['time_windows']): > if
location_idx == data['depot']: > continue > index =
manager.NodeToIndex(location_idx) >
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
> > # Add time window constraints for each vehicle start node.
> depot_idx = data['depot'] > for vehicle_id in
range(data['num_vehicles']): > index = routing.Start(vehicle_id) >
time_dimension.CumulVar(index).SetRange( >
data['time_windows'][depot_idx][0], >
data['time_windows'][depot_idx][1]) > > # Instantiate route start
and end times to produce feasible times. > for i in
range(data['num_vehicles']): >
routing.AddVariableMinimizedByFinalizer( >
time_dimension.CumulVar(routing.Start(i))) >
routing.AddVariableMinimizedByFinalizer( >
time_dimension.CumulVar(routing.End(i))) > > # Assign jobs for two
workers to the same vehicle > for node in range(1,
len(data['time_matrix'])): > if node in data['two_workers']: >
index = manager.NodeToIndex(node) >
routing.VehicleVar(index).SetValues([0]) > else:
> index = manager.NodeToIndex(node) >
routing.VehicleVar(index).SetValues([1,2,3,4,5]) > >
#time_dimension = routing.GetDimensionOrDie('Time') > > # Add
Capacity constraint: The capacity cannot be higher than the demand. This
can be used to indiocate that > # While the time dimension indicates
that the total route + work cannot be higher than 480min, > # In the
demand constraint can be noted that for example the total working hours
cannot be higher than 330min. > # The rest would be transport.
>
> def demand_callback(from_index): > """Returns the demand of the
node.""" > # Convert from routing variable Index to demands
NodeIndex. > from_node = manager.IndexToNode(from_index) > return
data['demands'][from_node] > > demand_callback_index =
routing.RegisterUnaryTransitCallback( > demand_callback) >
routing.AddDimensionWithVehicleCapacity( > demand_callback_index,
> 0, # null capacity slack > data['vehicle_capacities'], # vehicle
maximum capacities > True, # start cumul to zero > 'Capacity')
>
> # Allow to drop nodes. > penalty = 1000 > for node in
range(1, len(data['time_matrix'])): >
routing.AddDisjunction([manager.NodeToIndex(node)], penalty) >
> # Setting first solution heuristic. > search_parameters =
pywrapcp.DefaultRoutingSearchParameters() >
search_parameters.first_solution_strategy = ( >
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) >
search_parameters.local_search_metaheuristic = ( >
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH) >
search_parameters.time_limit.FromSeconds(10) >
>
> # Solve the problem. > assignment =
routing.SolveWithParameters(search_parameters) > > # Print
solution on console. > if assignment: > print_solution(data,
manager, routing, assignment) > else: > print('No solution found
!') > > > if name == 'main':
> main()
James E. Marca
Activimetrics LLC
Erik De Kuyffer
blind.lin...@gmail.com
That's a pretty clear python problem.
Just replace the usage of the single service time with a vector:
_service_time = node_service_time[from_node]I didn't test it, but I think that is all that is needed.
Note that you need to be careful about the correct node to use here. It is the from node, not the to node. The docs say, more or less, that:
if j == next(i)
cumuls(j) = cumuls(i) + service(i) + slacks(i) + transits(i,j)That is, the callback functions are computing the state of the system as the vehicle arrives at j. By recursion, cumuls(i) is the state upon arrival at i, so then you have to add in everything that changes the system once it arrives at i.
James
Erik De Kuyffer
Erik De Kuyffer
blind.line
On Apr 21, 2023, at 15:30, Erik De Kuyffer <ede...@gmail.com> wrote:
Hi James,
--
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/c49cbb0e-5aed-4bcf-8c29-c3170af86da8n%40googlegroups.com.
Erik De Kuyffer
blind.lin...@gmail.com
Hi Erik,
you are not creating multiple days.
You have to keep in mind that nothing here is magic...that is,
nothing
does what you expect, only what you actually tell it to do.
You said:
When the 'day_end' is large enough, some of the dummy nodes are taken into
account. However, the problem is that the days are not optimised for 8h.
You are almost on the right track there, but the 8h issue is
irrelevant.
When you create your time dimension, you have an upper bound of
data["day_end"]. That means no vehicle can have a time
greater than
960, or one day. (and as an aside, you should make the minimum 0
and
rely on the time window of the first node to force it to 480 or
whatever)
Dimensions are accumulators. They get bigger and smaller depending
on
what happens at the nodes.
Now in this case, for a dimension representing "time" you really
want
to just accumulate. You will get a big headache if you go
backwards.
So if you want 1 day, then the max time of 960 is okay. If you
want
two days, then the max time should by 2*960 (or whatever).
That's why it will pick up more nodes if you increase the day end.
Looking quickly at your time callback, I do not see any attempt
to
turn back the clock overnight. Since no vehicle can collect more
than
960 in the time dimension...that is, perform one day of work...then
of
course no vehicle will perform more than one day of work.
If you subtract time overnight, reset the clock back to 0, then
the
vehicles will appear to collect more than 960 in time, but they
are
just "unloading" time back at the depot. Which is fine, but I just
find that to be a source of bugs when I start to want to do things
like say "on wednesday, this demand is active", etc. I mean, I
guess
it is workable, but then you need more dimensions to track days
and
such, not so efficient.
This issue also applies to your time window constraints for the
dummy
depot nodes. You have to increment days, not just keep looping
over
day start to day end. So one depot is for day one, and it has a
time
window with a 960 in it. Another is day two, and so it needs to be
seeing 2*960, etc.
(And I'm sure you would have eventually seen this on your own had
you
struggled long enough.)
Regards,
James
On Sat, Apr 22, 2023 at 04:32:49AM -0700, Erik De Kuyffer wrote:
Hello James,
I fully understand. You must know that I am doing tests like minimum 3
hours per day, but I don't seem to find the solution.
Basically, the problem is that the solver drops nodes rather than offering
a multiday solution.When the 'day_end' is large enough, some of the dummy nodes are taken into
account. However, the problem is that the days are not optimised for 8h.So, in short, I am blocked... :-)
Kind regards,
ErikOp zaterdag 22 april 2023 om 01:51:14 UTC+2 schreef blind.lin...@gmail.com:
...
Erik De Kuyffer
blind.line
On Apr 24, 2023, at 15:11, Erik De Kuyffer <ede...@gmail.com> wrote:
Hi James,
--
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/9eaffac9-76c7-44ac-9fab-7ff0a375d9can%40googlegroups.com.
Erik De Kuyffer
blind.lin...@gmail.com
I took a look at your code, meaning I actually ran it and looked
at
things, but I could not get it to run and I don't have time to
debug
things properly, sorry.
It seems you chose to do the "subtract time overnight" approach.
Personally I don't like that at all. The problem is that the logic
of
the subtraction has to be exactly right, or you have to rely on
slack
variables making up the difference, and I hate that.
If you want to keep going down that path, I'd suggest reducing
the
problem further, with just one vehicle and just one or two nodes
more
than one day's worth of work.
The sequence should always be
[
vehicle_start,
morning_node_day0[vehicle0],
.. real nodes ..,
night_nodes_day0[vehicle0],
morning_node_day1[vehicle0],
.. real nodes ..,
night_nodes_day1[vehicle0],
vehicle_end
]Something somewhere is preventing this ordering, so stuff isn't
working. You have to figure out why the solver is not allowing the
vehicle to go from depot to morning0, or from the last node of day
0
to the night time node 0 (for the time reset), or from night 0 to
morning 1, etc etc. Something is up somewhere...probably if you do
the math (add the last dimension value plus travel time plus
service
time) you'll see that you exceed the time limit or some other bound.
I also notice your time callback function is NOT calling the
transit
callback function. It should, that way your infinite time in the
transit code will also be in the time code, and you can keep the
logic
compartmentalized.
I've had better success just increasing time forever, and taking
out
holes for each node to represent the operating times. In this case
if
you are careful you can skip nights, and just loop time from day*(0
to
480), so you don't even have to time holes to represent operating
hours. When I do that I just create a variable "model time" versus
"real time" so that I always know what I am dealing with. The
number
of days is model_time // one_day and then real time is
number of
days plus the morning offset plus model_time % one_day.
Or
something like that.
BUT, even easier, if you have a simple problem, it is easiest to
just
create multiple vehicles representing different days.
You have 3 vehicles, so v1, v2, v3 are day 1, v4, v5, v6 are day
2,
etc.
Then you can stick with your original formulation. The downside
is
that you can't really reason about days anymore, but for many
problems
this does not matter.
Hope that helps,
James
On Tue, Apr 25, 2023 at 05:02:40AM -0700, Erik De Kuyffer wrote:
Hi James,
Yes, I did. See the attached files...
Still don't see what I do wrong...Thanks,
ErikOp dinsdag 25 april 2023 om 01:29:55 UTC+2 schreef blind.lin...@gmail.com:
Did you increase the maximum size (time) of the dimension?
James
James E. Marca
Activimetrics LLC
--
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/9eaffac9-76c7-44ac-9fab-7ff0a375d9can%40googlegroups.com
--
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/0874823f-ddf3-4a64-b112-eee996e35a08n%40googlegroups.com.
"""Capacited Vehicles Routing Problem (CVRP)."""
from lzma import is_check_supported
from tkinter import BooleanVar
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import numpy as np
from functools import partial
from datetime import datetime, time, timedelta
import time_details_VRP as T'''
def create_data_model():
"""Stores the data for the problem."""
data = {}
data['distance_matrix'] = [
[ 0, 82, 47, 108, 136, 6, 4, 42, 54, 54, 57, 65, 75, 10, 5, 47, 12, 51, 88, 21, 83, 57, 60, 36, 55, 30, 20, 25, 62, 59, 72, 48, 59, 8, 90, 10, 59, 7, 49, 37, 47],
[ 82, 0, 128, 184, 211, 81, 78, 63, 135, 27, 25, 140, 154, 79, 78, 39, 81, 133, 165, 66, 163, 132, 23, 117, 129, 71, 75, 101, 137, 133, 26, 129, 140, 76, 165, 85, 134, 80, 114, 104, 108],
[ 47, 128, 0, 67, 93, 47, 50, 78, 12, 101, 103, 31, 33, 50, 50, 91, 48, 11, 47, 63, 39, 28, 106, 12, 30, 65, 59, 31, 29, 32, 118, 1, 16, 52, 51, 46, 29, 48, 43, 40, 48],
[108, 184, 67, 0, 28, 105, 110, 123, 70, 157, 160, 44, 34, 107, 109, 145, 104, 71, 20, 118, 30, 52, 161, 78, 55, 114, 125, 84, 47, 51, 179, 66, 68, 111, 19, 110, 50, 107, 71, 80, 77],
[136, 211, 93, 28, 0, 133, 138, 151, 95, 185, 188, 72, 61, 135, 137, 172, 132, 96, 47, 145, 55, 80, 188, 105, 83, 141, 152, 112, 75, 79, 207, 92, 92, 139, 47, 137, 78, 134, 98, 107, 104],
[ 6, 81, 47, 105, 133, 0, 5, 37, 55, 54, 57, 62, 73, 4, 4, 45, 5, 53, 86, 17, 82, 54, 59, 36, 51, 25, 25, 21, 59, 56, 74, 47, 60, 6, 87, 16, 56, 2, 44, 32, 42],
[ 4, 78, 50, 110, 138, 5, 0, 39, 57, 51, 53, 66, 77, 7, 2, 43, 10, 55, 90, 17, 86, 58, 56, 39, 56, 27, 20, 26, 63, 60, 69, 50, 62, 4, 92, 13, 60, 5, 49, 37, 47],
[ 42, 63, 78, 123, 151, 37, 39, 0, 88, 41, 44, 81, 96, 33, 37, 25, 33, 87, 106, 22, 106, 73, 41, 70, 69, 13, 53, 47, 79, 73, 68, 79, 93, 35, 105, 51, 75, 36, 53, 45, 46],
[ 54, 135, 12, 70, 95, 55, 57, 88, 0, 108, 110, 39, 37, 59, 57, 100, 57, 2, 50, 72, 40, 38, 113, 19, 41, 75, 63, 42, 38, 43, 123, 12, 5, 60, 57, 50, 40, 56, 55, 52, 60],
[ 54, 27, 101, 157, 185, 54, 51, 41, 108, 0, 3, 114, 127, 51, 51, 16, 54, 106, 139, 40, 136, 105, 7, 90, 102, 45, 50, 74, 111, 106, 28, 102, 113, 48, 138, 58, 107, 53, 89, 78, 83],
[ 57, 25, 103, 160, 188, 57, 53, 44, 110, 3, 0, 116, 129, 54, 53, 19, 57, 108, 141, 42, 138, 108, 8, 92, 105, 48, 51, 76, 113, 109, 25, 104, 115, 51, 141, 60, 110, 55, 92, 81, 86],
[ 65, 140, 31, 44, 72, 62, 66, 81, 39, 114, 116, 0, 16, 63, 66, 101, 60, 39, 25, 74, 26, 8, 117, 39, 12, 71, 82, 41, 3, 9, 135, 30, 40, 67, 25, 68, 7, 63, 31, 37, 38],
[ 75, 154, 33, 34, 61, 73, 77, 96, 37, 127, 129, 16, 0, 75, 77, 115, 72, 38, 14, 87, 10, 24, 130, 44, 28, 85, 91, 53, 18, 25, 147, 32, 36, 79, 20, 76, 23, 75, 47, 52, 54],
[ 10, 79, 50, 107, 135, 4, 7, 33, 59, 51, 54, 63, 75, 0, 6, 41, 4, 57, 88, 13, 85, 55, 56, 40, 53, 20, 27, 23, 60, 57, 72, 51, 64, 5, 89, 20, 57, 3, 44, 32, 40],
[ 5, 78, 50, 109, 137, 4, 2, 37, 57, 51, 53, 66, 77, 6, 0, 43, 8, 55, 90, 16, 86, 58, 56, 39, 55, 25, 22, 25, 63, 59, 70, 51, 62, 3, 91, 14, 60, 3, 48, 36, 45],
[ 47, 39, 91, 145, 172, 45, 43, 25, 100, 16, 19, 101, 115, 41, 43, 0, 44, 98, 126, 28, 124, 93, 16, 81, 89, 31, 48, 62, 98, 93, 43, 92, 105, 40, 126, 53, 95, 43, 75, 65, 69],
[ 12, 81, 48, 104, 132, 5, 10, 33, 57, 54, 57, 60, 72, 4, 8, 44, 0, 55, 85, 15, 81, 52, 59, 38, 49, 20, 30, 19, 57, 53, 75, 48, 62, 8, 85, 21, 54, 5, 40, 28, 37],
[ 51, 133, 11, 71, 96, 53, 55, 87, 2, 106, 108, 39, 38, 57, 55, 98, 55, 0, 51, 70, 42, 38, 111, 17, 41, 73, 61, 40, 38, 42, 121, 11, 7, 58, 57, 48, 39, 54, 54, 50, 59],
[ 88, 165, 47, 20, 47, 86, 90, 106, 50, 139, 141, 25, 14, 88, 90, 126, 85, 51, 0, 99, 12, 34, 142, 58, 37, 96, 104, 65, 28, 34, 159, 46, 49, 92, 9, 90, 32, 87, 55, 62, 62],
[ 21, 66, 63, 118, 145, 17, 17, 22, 72, 40, 42, 74, 87, 13, 16, 28, 15, 70, 99, 0, 96, 66, 43, 53, 63, 13, 31, 34, 71, 67, 63, 64, 77, 13, 99, 29, 68, 16, 51, 39, 46],
[ 83, 163, 39, 30, 55, 82, 86, 106, 40, 136, 138, 26, 10, 85, 86, 124, 81, 42, 12, 96, 0, 34, 140, 51, 38, 95, 98, 62, 28, 35, 155, 38, 38, 88, 21, 84, 33, 83, 57, 62, 64],
[ 57, 132, 28, 52, 80, 54, 58, 73, 38, 105, 108, 8, 24, 55, 58, 93, 52, 38, 34, 66, 34, 0, 109, 34, 5, 62, 75, 33, 5, 4, 127, 27, 40, 59, 33, 60, 2, 55, 24, 29, 30],
[ 60, 23, 106, 161, 188, 59, 56, 41, 113, 7, 8, 117, 130, 56, 56, 16, 59, 111, 142, 43, 140, 109, 0, 95, 105, 47, 56, 78, 114, 109, 30, 106, 118, 53, 142, 64, 110, 57, 91, 81, 85],
[ 36, 117, 12, 78, 105, 36, 39, 70, 19, 90, 92, 39, 44, 40, 39, 81, 38, 17, 58, 53, 51, 34, 95, 0, 35, 57, 48, 25, 36, 38, 106, 13, 24, 42, 62, 34, 36, 38, 43, 37, 46],
[ 55, 129, 30, 55, 83, 51, 56, 69, 41, 102, 105, 12, 28, 53, 55, 89, 49, 41, 37, 63, 38, 5, 105, 35, 0, 59, 73, 30, 10, 4, 124, 30, 44, 57, 36, 59, 5, 53, 19, 25, 26],
[ 30, 71, 65, 114, 141, 25, 27, 13, 75, 45, 48, 71, 85, 20, 25, 31, 20, 73, 96, 13, 95, 62, 47, 57, 59, 0, 44, 34, 68, 63, 71, 66, 80, 23, 95, 40, 64, 24, 44, 34, 38],
[ 20, 75, 59, 125, 152, 25, 20, 53, 63, 50, 51, 82, 91, 27, 22, 48, 30, 61, 104, 31, 98, 75, 56, 48, 73, 44, 0, 44, 79, 77, 60, 61, 68, 23, 107, 14, 77, 25, 69, 57, 67],
[ 25, 101, 31, 84, 112, 21, 26, 47, 42, 74, 76, 41, 53, 23, 25, 62, 19, 40, 65, 34, 62, 33, 78, 25, 30, 34, 44, 0, 38, 34, 95, 32, 47, 27, 66, 31, 35, 22, 26, 15, 26],
[ 62, 137, 29, 47, 75, 59, 63, 79, 38, 111, 113, 3, 18, 60, 63, 98, 57, 38, 28, 71, 28, 5, 114, 36, 10, 68, 79, 38, 0, 7, 132, 28, 39, 64, 28, 65, 4, 60, 29, 34, 35],
[ 59, 133, 32, 51, 79, 56, 60, 73, 43, 106, 109, 9, 25, 57, 59, 93, 53, 42, 34, 67, 35, 4, 109, 38, 4, 63, 77, 34, 7, 0, 129, 31, 44, 61, 32, 63, 3, 57, 22, 29, 29],
[ 72, 26, 118, 179, 207, 74, 69, 68, 123, 28, 25, 135, 147, 72, 70, 43, 75, 121, 159, 63, 155, 127, 30, 106, 124, 71, 60, 95, 132, 129, 0, 119, 128, 68, 160, 72, 129, 72, 113, 102, 108],
[ 48, 129, 1, 66, 92, 47, 50, 79, 12, 102, 104, 30, 32, 51, 51, 92, 48, 11, 46, 64, 38, 27, 106, 13, 30, 66, 61, 32, 28, 31, 119, 0, 16, 53, 51, 47, 29, 49, 43, 40, 48],
[ 59, 140, 16, 68, 92, 60, 62, 93, 5, 113, 115, 40, 36, 64, 62, 105, 62, 7, 49, 77, 38, 40, 118, 24, 44, 80, 68, 47, 39, 44, 128, 16, 0, 65, 55, 55, 41, 61, 58, 56, 63],
[ 8, 76, 52, 111, 139, 6, 4, 35, 60, 48, 51, 67, 79, 5, 3, 40, 8, 58, 92, 13, 88, 59, 53, 42, 57, 23, 23, 27, 64, 61, 68, 53, 65, 0, 93, 17, 61, 4, 48, 37, 45],
[ 90, 165, 51, 19, 47, 87, 92, 105, 57, 138, 141, 25, 20, 89, 91, 126, 85, 57, 9, 99, 21, 33, 142, 62, 36, 95, 107, 66, 28, 32, 160, 51, 55, 93, 0, 93, 31, 88, 52, 61, 59],
[ 10, 85, 46, 110, 137, 16, 13, 51, 50, 58, 60, 68, 76, 20, 14, 53, 21, 48, 90, 29, 84, 60, 64, 34, 59, 40, 14, 31, 65, 63, 72, 47, 55, 17, 93, 0, 63, 17, 56, 45, 55],
[ 59, 134, 29, 50, 78, 56, 60, 75, 40, 107, 110, 7, 23, 57, 60, 95, 54, 39, 32, 68, 33, 2, 110, 36, 5, 64, 77, 35, 4, 3, 129, 29, 41, 61, 31, 63, 0, 57, 24, 30, 31],
[ 7, 80, 48, 107, 134, 2, 5, 36, 56, 53, 55, 63, 75, 3, 3, 43, 5, 54, 87, 16, 83, 55, 57, 38, 53, 24, 25, 22, 60, 57, 72, 49, 61, 4, 88, 17, 57, 0, 45, 33, 42],
[ 49, 114, 43, 71, 98, 44, 49, 53, 55, 89, 92, 31, 47, 44, 48, 75, 40, 54, 55, 51, 57, 24, 91, 43, 19, 44, 69, 26, 29, 22, 113, 43, 58, 48, 52, 56, 24, 45, 0, 12, 7],
[ 37, 104, 40, 80, 107, 32, 37, 45, 52, 78, 81, 37, 52, 32, 36, 65, 28, 50, 62, 39, 62, 29, 81, 37, 25, 34, 57, 15, 34, 29, 102, 40, 56, 37, 61, 45, 30, 33, 12, 0, 11],
[ 47, 108, 48, 77, 104, 42, 47, 46, 60, 83, 86, 38, 54, 40, 45, 69, 37, 59, 62, 46, 64, 30, 85, 46, 26, 38, 67, 26, 35, 29, 108, 48, 63, 45, 59, 55, 31, 42, 7, 11, 0]
]# data['demands'] = [0, 45, 120, 160, 210, 190, 320, 120, 90, 40, 220, 150, 360, 90, 190, 290, 75, 120, 80, 60, 150, 330, 45, 75, 260, 240, 135, 110, 145, 180, 150, 50, 75, 95, 250, 65, 240, 170, 105, 30, 230]
# data['time_matrix'] = np.array(data['distance_matrix']) + data['demands']
# data['num_vehicles'] = 3
# data['depot'] = 0
# data['two_workers'] = [6, 33]
# data['vehicle_capacities'] = [3600, 3600, 3600, 3600, 3600, 3600]
# data['starts'] = [1, 4, 0]
# data['ends'] = [0, 4, 0]
# data['day_start'] = 480
# data['day_end'] = 960
# data['num_days'] = 2
# data['overnight_time'] = day_start - data['day_end']
# data['Slack_Max'] = (data['day_end'] - day_start) - day_start
return data
'''num_vehicles = 3
num_days = 3
day_start = 480
day_end = 960
overnight_time = (day_start - day_end)
Slack_Max = (day_end - day_start) - day_start
demands = [0, 45, 120, 100, 50, 190, 120, 120, 90, 40, 220, 150, 60, 90, 190, 90, 75, 120, 80, 60, 150, 30, 45, 75, 160, 240, 135, 110, 145, 180, 150, 50, 75, 95, 20, 65, 240, 170, 105, 30, 30]
starts = [0, 4, 0]
ends = [0, 4, 0]
two_workers = [35, 13]
num_nodes = T.num_nodes()
one_day = 1440def print_solution(manager, routing, assignment):
"""Prints assignment on console."""
print(f'Objective: {assignment.ObjectiveValue()}')
# Display dropped nodes.
dropped_nodes = 'Dropped nodes:'
for node in range(routing.Size()):
if routing.IsStart(node) or routing.IsEnd(node):
continue
if assignment.Value(routing.NextVar(node)) == node:
dropped_nodes += ' {}'.format(manager.IndexToNode(node))
print(dropped_nodes)
# Display routes total_distance = 0 total_load = 0 for vehicle_id in range(num_vehicles): index = routing.Start(vehicle_id) plan_output = 'Route for vehicle {}:\n'.format(vehicle_id) route_distance = 0 route_load = 0 while not routing.IsEnd(index): node_index = manager.IndexToNode(index) route_load += demands[node_index] plan_output += ' {0} Load({1}) -> '.format(node_index, route_load) previous_index = index index = assignment.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id) plan_output += ' Distance({1})\n'.format(manager.IndexToNode(index), route_distance) plan_output += 'Time of the route: {}m\n'.format(route_distance) plan_output += 'Load of the route: {}\n'.format(route_load) print(plan_output) total_distance += route_distance total_load += route_load print('Total Distance of all routes: {}m'.format(total_distance)) print('Total Load of all routes: {}'.format(total_load))
def main():
"""Solve the CVRP problem."""
# Instantiate the data problem.
for i in range(2num_daysnum_vehicles):
demands.append(0)#print (demands) # create dummy nodes for returning to the depot every night night_nodes = range(num_nodes, num_nodes+(num_vehicles*num_days)) # create dummy nodes linked to night nodes that fix the AM depart time morning_nodes = range(num_nodes+(num_vehicles*num_days), num_nodes+(num_vehicles*num_days)+(num_vehicles*num_days)) total_nodes = num_nodes + len(night_nodes) +len(morning_nodes) # Create the routing index manager with different depots manager = pywrapcp.RoutingIndexManager(total_nodes, num_vehicles, starts, ends) print('made manager with total nodes {} = {} + {} + {}'.format(total_nodes, num_nodes, len(night_nodes), len(morning_nodes))) # Create Routing Model. model_parameters = pywrapcp.DefaultRoutingModelParameters() model_parameters.max_callback_cache_size = 2 * total_nodes * total_nodes routing = pywrapcp.RoutingModel(manager, model_parameters) #routing = pywrapcp.RoutingModel(manager) transit_callback_fn = partial(T.transit_callback, manager, day_end, night_nodes, morning_nodes) transit_callback_index = routing.RegisterTransitCallback(transit_callback_fn) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) print('set the arc cost evaluator for all vehicles') time_callback_fn = partial(T.time_callback, manager, demands, overnight_time, night_nodes, morning_nodes) time_callback_index = routing.RegisterTransitCallback(time_callback_fn) routing.AddDimension( time_callback_index, one_day*num_days, # An upper bound for slack (the wait times at the locations). one_day*num_days, # An upper bound for the total time over each vehicle's route. False, # Determine whether the cumulative variable is set to zero at the start of the vehicle's route. 'Time') time_dimension = routing.GetDimensionOrDie('Time') print('created time dimension') #time_dimension.SetGlobalSpanCostCoefficient(100) # get rid of slack for all regular nodes, all morning nodes # but keep for depot, night nodes for node in range(1, num_nodes): index = manager.NodeToIndex(node) time_dimension.SlackVar(index).SetValue(0) for node in morning_nodes: index = manager.NodeToIndex(node) time_dimension.SlackVar(index).SetValue(0) # Allow all locations except the first two to be droppable. disjunction_penalty = 1000000000000000 for node in range(1, num_nodes): routing.AddDisjunction([manager.NodeToIndex(node)], disjunction_penalty) # Allow all overnight nodes to be dropped for free for node in night_nodes: routing.AddDisjunction([manager.NodeToIndex(node)], 0) for node in morning_nodes: routing.AddDisjunction([manager.NodeToIndex(node)], 0) # Add time window constraints for each regular node for node in range(1, num_nodes): index = manager.NodeToIndex(node) time_dimension.CumulVar(index).SetRange(day_start, day_end) # This also applies to the overnight nodes and morning nodes for node in range(num_nodes, total_nodes): index = manager.NodeToIndex(node) time_dimension.CumulVar(index).SetRange(day_start, day_end) # Add time window constraints for each vehicle start/end node. for veh in range(0,num_vehicles): index = routing.Start(veh) time_dimension.CumulVar(index).SetMin(day_start) index = routing.End(veh) time_dimension.CumulVar(index).SetMax(day_end) print('done with time constraints') # make sure the days happen in order. first end day 1, end day 2, etc, then node 1 # create counting dimension routing.AddConstantDimension(1, # increment by 1 total_nodes+1, # the max count is visit every node True, # start count at zero 'Counting') count_dimension = routing.GetDimensionOrDie('Counting') print('created count dim') ''' # Assign jobs for two workers to the same vehicle for node in range(1, len(demands)): if node in two_workers: index = manager.NodeToIndex(node) routing.VehicleVar(index).SetValues([0]) else: index = manager.NodeToIndex(node) routing.VehicleVar(index).SetValues([1,2,3,4,5]) ''' # use count dim to enforce ordering of overnight, morning nodes solver = routing.solver() for i in range(len(night_nodes)): inode = night_nodes[i] iidx = manager.NodeToIndex(inode) iactive = routing.ActiveVar(iidx) for j in range(i+1, len(night_nodes)): # make i come before j using count dimension jnode = night_nodes[j] jidx = manager.NodeToIndex(jnode) jactive = routing.ActiveVar(jidx) solver.Add(iactive >= jactive) solver.Add(count_dimension.CumulVar(iidx) * iactive * jactive <= count_dimension.CumulVar(jidx) * iactive * jactive) # if night node is active, AND night_node is not the last night, # must transition to corresponding morning node if i < len(morning_nodes): i_morning_idx = manager.NodeToIndex(morning_nodes[i]) i_morning_active = routing.ActiveVar(i_morning_idx) solver.Add(iactive == i_morning_active) solver.Add(count_dimension.CumulVar(iidx) + 1 == count_dimension.CumulVar(i_morning_idx)) for i in range(len(morning_nodes)): inode = morning_nodes[i] iidx = manager.NodeToIndex(inode) iactive = routing.ActiveVar(iidx) for j in range(i+1, len(morning_nodes)): # make i come before j using count dimension jnode = morning_nodes[j] jidx = manager.NodeToIndex(jnode) jactive = routing.ActiveVar(jidx) solver.Add(iactive >= jactive) solver.Add(count_dimension.CumulVar(iidx) * iactive * jactive <= count_dimension.CumulVar(jidx) * iactive * jactive) routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(0))) routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(0))) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION) #search_parameters.first_solution_strategy = ( # routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) search_parameters.local_search_metaheuristic = ( routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH) search_parameters.time_limit.FromSeconds(10) # Solve the problem. assignment = routing.SolveWithParameters(search_parameters) # Print solution on console. if assignment: print_solution(manager, routing, assignment) else: print('No solution found !')
if name == 'main':
main()
import numpy as np
Matrix = [
[ 0, 82, 47, 108, 136, 6, 4, 42, 54, 54, 57, 65, 75, 10, 5, 47, 12, 51, 88, 21, 83, 57, 60, 36, 55, 30, 20, 25, 62, 59, 72, 48, 59, 8, 90, 10, 59, 7, 49, 37, 47],
[ 82, 0, 128, 184, 211, 81, 78, 63, 135, 27, 25, 140, 154, 79, 78, 39, 81, 133, 165, 66, 163, 132, 23, 117, 129, 71, 75, 101, 137, 133, 26, 129, 140, 76, 165, 85, 134, 80, 114, 104, 108],
[ 47, 128, 0, 67, 93, 47, 50, 78, 12, 101, 103, 31, 33, 50, 50, 91, 48, 11, 47, 63, 39, 28, 106, 12, 30, 65, 59, 31, 29, 32, 118, 1, 16, 52, 51, 46, 29, 48, 43, 40, 48],
[108, 184, 67, 0, 28, 105, 110, 123, 70, 157, 160, 44, 34, 107, 109, 145, 104, 71, 20, 118, 30, 52, 161, 78, 55, 114, 125, 84, 47, 51, 179, 66, 68, 111, 19, 110, 50, 107, 71, 80, 77],
[136, 211, 93, 28, 0, 133, 138, 151, 95, 185, 188, 72, 61, 135, 137, 172, 132, 96, 47, 145, 55, 80, 188, 105, 83, 141, 152, 112, 75, 79, 207, 92, 92, 139, 47, 137, 78, 134, 98, 107, 104],
[ 6, 81, 47, 105, 133, 0, 5, 37, 55, 54, 57, 62, 73, 4, 4, 45, 5, 53, 86, 17, 82, 54, 59, 36, 51, 25, 25, 21, 59, 56, 74, 47, 60, 6, 87, 16, 56, 2, 44, 32, 42],
[ 4, 78, 50, 110, 138, 5, 0, 39, 57, 51, 53, 66, 77, 7, 2, 43, 10, 55, 90, 17, 86, 58, 56, 39, 56, 27, 20, 26, 63, 60, 69, 50, 62, 4, 92, 13, 60, 5, 49, 37, 47],
[ 42, 63, 78, 123, 151, 37, 39, 0, 88, 41, 44, 81, 96, 33, 37, 25, 33, 87, 106, 22, 106, 73, 41, 70, 69, 13, 53, 47, 79, 73, 68, 79, 93, 35, 105, 51, 75, 36, 53, 45, 46],
[ 54, 135, 12, 70, 95, 55, 57, 88, 0, 108, 110, 39, 37, 59, 57, 100, 57, 2, 50, 72, 40, 38, 113, 19, 41, 75, 63, 42, 38, 43, 123, 12, 5, 60, 57, 50, 40, 56, 55, 52, 60],
[ 54, 27, 101, 157, 185, 54, 51, 41, 108, 0, 3, 114, 127, 51, 51, 16, 54, 106, 139, 40, 136, 105, 7, 90, 102, 45, 50, 74, 111, 106, 28, 102, 113, 48, 138, 58, 107, 53, 89, 78, 83],
[ 57, 25, 103, 160, 188, 57, 53, 44, 110, 3, 0, 116, 129, 54, 53, 19, 57, 108, 141, 42, 138, 108, 8, 92, 105, 48, 51, 76, 113, 109, 25, 104, 115, 51, 141, 60, 110, 55, 92, 81, 86],
[ 65, 140, 31, 44, 72, 62, 66, 81, 39, 114, 116, 0, 16, 63, 66, 101, 60, 39, 25, 74, 26, 8, 117, 39, 12, 71, 82, 41, 3, 9, 135, 30, 40, 67, 25, 68, 7, 63, 31, 37, 38],
[ 75, 154, 33, 34, 61, 73, 77, 96, 37, 127, 129, 16, 0, 75, 77, 115, 72, 38, 14, 87, 10, 24, 130, 44, 28, 85, 91, 53, 18, 25, 147, 32, 36, 79, 20, 76, 23, 75, 47, 52, 54],
[ 10, 79, 50, 107, 135, 4, 7, 33, 59, 51, 54, 63, 75, 0, 6, 41, 4, 57, 88, 13, 85, 55, 56, 40, 53, 20, 27, 23, 60, 57, 72, 51, 64, 5, 89, 20, 57, 3, 44, 32, 40],
[ 5, 78, 50, 109, 137, 4, 2, 37, 57, 51, 53, 66, 77, 6, 0, 43, 8, 55, 90, 16, 86, 58, 56, 39, 55, 25, 22, 25, 63, 59, 70, 51, 62, 3, 91, 14, 60, 3, 48, 36, 45],
[ 47, 39, 91, 145, 172, 45, 43, 25, 100, 16, 19, 101, 115, 41, 43, 0, 44, 98, 126, 28, 124, 93, 16, 81, 89, 31, 48, 62, 98, 93, 43, 92, 105, 40, 126, 53, 95, 43, 75, 65, 69],
[ 12, 81, 48, 104, 132, 5, 10, 33, 57, 54, 57, 60, 72, 4, 8, 44, 0, 55, 85, 15, 81, 52, 59, 38, 49, 20, 30, 19, 57, 53, 75, 48, 62, 8, 85, 21, 54, 5, 40, 28, 37],
[ 51, 133, 11, 71, 96, 53, 55, 87, 2, 106, 108, 39, 38, 57, 55, 98, 55, 0, 51, 70, 42, 38, 111, 17, 41, 73, 61, 40, 38, 42, 121, 11, 7, 58, 57, 48, 39, 54, 54, 50, 59],
[ 88, 165, 47, 20, 47, 86, 90, 106, 50, 139, 141, 25, 14, 88, 90, 126, 85, 51, 0, 99, 12, 34, 142, 58, 37, 96, 104, 65, 28, 34, 159, 46, 49, 92, 9, 90, 32, 87, 55, 62, 62],
[ 21, 66, 63, 118, 145, 17, 17, 22, 72, 40, 42, 74, 87, 13, 16, 28, 15, 70, 99, 0, 96, 66, 43, 53, 63, 13, 31, 34, 71, 67, 63, 64, 77, 13, 99, 29, 68, 16, 51, 39, 46],
[ 83, 163, 39, 30, 55, 82, 86, 106, 40, 136, 138, 26, 10, 85, 86, 124, 81, 42, 12, 96, 0, 34, 140, 51, 38, 95, 98, 62, 28, 35, 155, 38, 38, 88, 21, 84, 33, 83, 57, 62, 64],
[ 57, 132, 28, 52, 80, 54, 58, 73, 38, 105, 108, 8, 24, 55, 58, 93, 52, 38, 34, 66, 34, 0, 109, 34, 5, 62, 75, 33, 5, 4, 127, 27, 40, 59, 33, 60, 2, 55, 24, 29, 30],
[ 60, 23, 106, 161, 188, 59, 56, 41, 113, 7, 8, 117, 130, 56, 56, 16, 59, 111, 142, 43, 140, 109, 0, 95, 105, 47, 56, 78, 114, 109, 30, 106, 118, 53, 142, 64, 110, 57, 91, 81, 85],
[ 36, 117, 12, 78, 105, 36, 39, 70, 19, 90, 92, 39, 44, 40, 39, 81, 38, 17, 58, 53, 51, 34, 95, 0, 35, 57, 48, 25, 36, 38, 106, 13, 24, 42, 62, 34, 36, 38, 43, 37, 46],
[ 55, 129, 30, 55, 83, 51, 56, 69, 41, 102, 105, 12, 28, 53, 55, 89, 49, 41, 37, 63, 38, 5, 105, 35, 0, 59, 73, 30, 10, 4, 124, 30, 44, 57, 36, 59, 5, 53, 19, 25, 26],
[ 30, 71, 65, 114, 141, 25, 27, 13, 75, 45, 48, 71, 85, 20, 25, 31, 20, 73, 96, 13, 95, 62, 47, 57, 59, 0, 44, 34, 68, 63, 71, 66, 80, 23, 95, 40, 64, 24, 44, 34, 38],
[ 20, 75, 59, 125, 152, 25, 20, 53, 63, 50, 51, 82, 91, 27, 22, 48, 30, 61, 104, 31, 98, 75, 56, 48, 73, 44, 0, 44, 79, 77, 60, 61, 68, 23, 107, 14, 77, 25, 69, 57, 67],
[ 25, 101, 31, 84, 112, 21, 26, 47, 42, 74, 76, 41, 53, 23, 25, 62, 19, 40, 65, 34, 62, 33, 78, 25, 30, 34, 44, 0, 38, 34, 95, 32, 47, 27, 66, 31, 35, 22, 26, 15, 26],
[ 62, 137, 29, 47, 75, 59, 63, 79, 38, 111, 113, 3, 18, 60, 63, 98, 57, 38, 28, 71, 28, 5, 114, 36, 10, 68, 79, 38, 0, 7, 132, 28, 39, 64, 28, 65, 4, 60, 29, 34, 35],
[ 59, 133, 32, 51, 79, 56, 60, 73, 43, 106, 109, 9, 25, 57, 59, 93, 53, 42, 34, 67, 35, 4, 109, 38, 4, 63, 77, 34, 7, 0, 129, 31, 44, 61, 32, 63, 3, 57, 22, 29, 29],
[ 72, 26, 118, 179, 207, 74, 69, 68, 123, 28, 25, 135, 147, 72, 70, 43, 75, 121, 159, 63, 155, 127, 30, 106, 124, 71, 60, 95, 132, 129, 0, 119, 128, 68, 160, 72, 129, 72, 113, 102, 108],
[ 48, 129, 1, 66, 92, 47, 50, 79, 12, 102, 104, 30, 32, 51, 51, 92, 48, 11, 46, 64, 38, 27, 106, 13, 30, 66, 61, 32, 28, 31, 119, 0, 16, 53, 51, 47, 29, 49, 43, 40, 48],
[ 59, 140, 16, 68, 92, 60, 62, 93, 5, 113, 115, 40, 36, 64, 62, 105, 62, 7, 49, 77, 38, 40, 118, 24, 44, 80, 68, 47, 39, 44, 128, 16, 0, 65, 55, 55, 41, 61, 58, 56, 63],
[ 8, 76, 52, 111, 139, 6, 4, 35, 60, 48, 51, 67, 79, 5, 3, 40, 8, 58, 92, 13, 88, 59, 53, 42, 57, 23, 23, 27, 64, 61, 68, 53, 65, 0, 93, 17, 61, 4, 48, 37, 45],
[ 90, 165, 51, 19, 47, 87, 92, 105, 57, 138, 141, 25, 20, 89, 91, 126, 85, 57, 9, 99, 21, 33, 142, 62, 36, 95, 107, 66, 28, 32, 160, 51, 55, 93, 0, 93, 31, 88, 52, 61, 59],
[ 10, 85, 46, 110, 137, 16, 13, 51, 50, 58, 60, 68, 76, 20, 14, 53, 21, 48, 90, 29, 84, 60, 64, 34, 59, 40, 14, 31, 65, 63, 72, 47, 55, 17, 93, 0, 63, 17, 56, 45, 55],
[ 59, 134, 29, 50, 78, 56, 60, 75, 40, 107, 110, 7, 23, 57, 60, 95, 54, 39, 32, 68, 33, 2, 110, 36, 5, 64, 77, 35, 4, 3, 129, 29, 41, 61, 31, 63, 0, 57, 24, 30, 31],
[ 7, 80, 48, 107, 134, 2, 5, 36, 56, 53, 55, 63, 75, 3, 3, 43, 5, 54, 87, 16, 83, 55, 57, 38, 53, 24, 25, 22, 60, 57, 72, 49, 61, 4, 88, 17, 57, 0, 45, 33, 42],
[ 49, 114, 43, 71, 98, 44, 49, 53, 55, 89, 92, 31, 47, 44, 48, 75, 40, 54, 55, 51, 57, 24, 91, 43, 19, 44, 69, 26, 29, 22, 113, 43, 58, 48, 52, 56, 24, 45, 0, 12, 7],
[ 37, 104, 40, 80, 107, 32, 37, 45, 52, 78, 81, 37, 52, 32, 36, 65, 28, 50, 62, 39, 62, 29, 81, 37, 25, 34, 57, 15, 34, 29, 102, 40, 56, 37, 61, 45, 30, 33, 12, 0, 11],
[ 47, 108, 48, 77, 104, 42, 47, 46, 60, 83, 86, 38, 54, 40, 45, 69, 37, 59, 62, 46, 64, 30, 85, 46, 26, 38, 67, 26, 35, 29, 108, 48, 63, 45, 59, 55, 31, 42, 7, 11, 0]
]_num_nodes = len(Matrix)
def num_nodes():
return _num_nodes
Create and register a transit callback.
def transit_callback(manager,
day_end,
night_nodes,
morning_nodes,
from_index, to_index):
# Returns the travel time between the two nodes.
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
INFINITE_TIME = day_end*10000000000 # way more than ever possible # night nodes can *only* transition to morning nodes if len(morning_nodes) > 0: if from_node in night_nodes: if to_node in morning_nodes: return 0 else: return INFINITE_TIME # prevent movement to night nodes from morning nodes if from_node in morning_nodes: if to_node in night_nodes: return INFINITE_TIME # prevent movement to morning nodes from morning nodes if from_node in morning_nodes: if to_node in morning_nodes: return INFINITE_TIME # prevent movement to night nodes from night nodes if from_node in night_nodes: if to_node in night_nodes: return INFINITE_TIME # prevent movement to start or end nodes from morning nodes if to_node == 0: if from_node in morning_nodes: return INFINITE_TIME # adjust if either node is a night node if from_node in night_nodes or from_node in morning_nodes: from_node = 1 if to_node in night_nodes or to_node in morning_nodes: to_node = 1 return Matrix[from_node][to_node]def time_callback(manager,
node_service_time,
overnight_time,
night_nodes,
morning_nodes,
from_index, to_index):# Returns the travel plus service time between the two nodes. # Convert from routing variable Index to time matrix NodeIndex. from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) # service time is 0 if start or end depot, node_service_time # if a node, and overnight_time if an overnight node if from_node == 0: node_service_time[from_node] = 0 if from_node in night_nodes: node_service_time[from_node] = overnight_time if from_node in morning_nodes: node_service_time[from_node] = 0 # adjust if either node is a night node if from_node >= _num_nodes: from_node = 1 if to_node >= _num_nodes: to_node = 1# print(np.array(Matrix[from_node][to_node]) + node_service_time[from_node])
return Matrix[from_node][to_node] + node_service_time[from_node]
# return Matrix[from_node][to_node] + 60
Erik De Kuyffer
Agustina
Erik De Kuyffer
Hi, I am working with a similar problem with multiples day. I am trying to minimize the working hours in all day for all vehicles. But I have not been able to do it. Do you have any idea how can I do it? Thank you
--
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/0mBrWZxr62I/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/75f3b93e-f6e6-4d65-9ba3-2f42007a11cfn%40googlegroups.com.