1 00:00:00,190 --> 00:00:02,390 Okay. Guys I want to cover the vehicle routing 2 00:00:02,390 --> 00:00:03,270 assignment. Okay? 3 00:00:03,270 --> 00:00:05,520 For the, for the discrete optimization class. 4 00:00:05,520 --> 00:00:07,512 Okay? So the vehicle routing problem is one of 5 00:00:07,512 --> 00:00:09,741 the most fascinating problem. Okay? 6 00:00:09,741 --> 00:00:13,581 it's, it's, it's a beautiful research area. 7 00:00:13,581 --> 00:00:16,236 There are, it's very, you know, applicable in practice. 8 00:00:16,236 --> 00:00:18,490 There are a lot of practical application. There are many variants. 9 00:00:18,490 --> 00:00:21,900 You know, people have spent their lives you know, working on these things. 10 00:00:21,900 --> 00:00:25,460 You know, this is one of the areas of, you know, optimization that I like the 11 00:00:25,460 --> 00:00:27,750 most. Okay, so what we're going to see in, and 12 00:00:27,750 --> 00:00:31,220 this is also very difficult in general, okay, so what you're going to see here is 13 00:00:31,220 --> 00:00:34,519 that we're going to look the assignment is going to be one particular type which 14 00:00:34,519 --> 00:00:37,810 is called the capacitated VRP. This is, by far, none of the most 15 00:00:37,810 --> 00:00:41,270 difficult, you know, VRP problems, but is very challenging, it's still very, very 16 00:00:41,270 --> 00:00:44,450 challenging. So you have to think about it as, like 17 00:00:44,450 --> 00:00:47,020 the TSP except that you know, on steroids, okay. 18 00:00:47,020 --> 00:00:50,030 So we have many vehicles and we have these additional constraints on what 19 00:00:50,030 --> 00:00:53,900 these vehicles can do, okay. So, vehicle warning, okay. 20 00:00:53,900 --> 00:00:58,150 So this is a simple, you know, formulation here that we're going to see 21 00:00:58,150 --> 00:01:00,720 where we already see some of the input data, okay. 22 00:01:00,720 --> 00:01:03,830 So you have a bunch of. Different sites here, okay, one of them 23 00:01:03,830 --> 00:01:06,860 is the warehouse, that's where the vehicles are starting, okay? 24 00:01:06,860 --> 00:01:10,670 So this is for Caltain and Victor. I want to call it a depot but they like 25 00:01:10,670 --> 00:01:14,070 warehouse so I'm very friendly with my collaborator so we're going to call that 26 00:01:14,070 --> 00:01:16,680 a warehouse, okay? So for everyone of them, you see a 27 00:01:16,680 --> 00:01:19,310 coordinate, okay? So that's where the lie on the plane, 28 00:01:19,310 --> 00:01:22,900 okay? And you see also some demand there, that, 29 00:01:22,900 --> 00:01:25,660 think of it as. You know, this is the you know the kind 30 00:01:25,660 --> 00:01:30,500 of way that you are collecting at every one of these at every one of these 31 00:01:30,500 --> 00:01:31,580 location. Okay. 32 00:01:31,580 --> 00:01:35,660 So so you will have four vehicles for instance in this particular area. 33 00:01:35,660 --> 00:01:38,176 The capacity of this vehicle is going to be 10. 34 00:01:38,176 --> 00:01:42,256 So, the way that you are picking up at every one of these location can never 35 00:01:42,256 --> 00:01:43,290 exceed 10. Okay. 36 00:01:43,290 --> 00:01:46,800 This is the warehouse I told you, warehouse not depot, warehouse, okay. 37 00:01:46,800 --> 00:01:52,260 And so this is essentially one tour okay, which is a cost of 80.6, okay, that's the 38 00:01:52,260 --> 00:01:54,310 distance which is traveled by the vehicles. 39 00:01:54,310 --> 00:01:57,910 You see one vehicle here, I believe this is green, right, and another one which is 40 00:01:57,910 --> 00:02:01,040 probably purple, okay. And so that's what the vehicles are 41 00:02:01,040 --> 00:02:03,963 doing. They satisfy the capacity constraints 42 00:02:03,963 --> 00:02:07,520 okay, and obviously they visit every customers exactly once. 43 00:02:07,520 --> 00:02:12,790 So this is another of this tool which is actually better okay. 44 00:02:12,790 --> 00:02:17,930 So the cost is only 68.3 and once again it satisfies the capacity constraint. 45 00:02:17,930 --> 00:02:21,550 So the goal of the assignment is to find these better tools for everyone one of 46 00:02:21,550 --> 00:02:23,530 the vehicles satisfying the capacity constraint. 47 00:02:23,530 --> 00:02:26,610 Minimizing the total travel distance. Okay? 48 00:02:26,610 --> 00:02:29,760 So formally, this is how you can describe the problem. 49 00:02:29,760 --> 00:02:31,880 Now, this is an impossible formulation, right. 50 00:02:31,880 --> 00:02:34,595 So don't try to run this, this will almost never run anywhere. 51 00:02:34,595 --> 00:02:36,860 Okay. But this is, you know, stating what the 52 00:02:36,860 --> 00:02:39,700 problem is. So you have n vehicles, okay. 53 00:02:39,700 --> 00:02:44,070 And you have n customers, and n locations, sorry, and v vehicles. 54 00:02:44,070 --> 00:02:49,430 for everyone of the location okay, so we have the demand for that location di, and 55 00:02:49,430 --> 00:02:52,240 we have the location in the plane, you know given by xi, yi okay. 56 00:02:52,240 --> 00:02:57,180 Now, the capacity of the vehicle is this constant c, they all have the same 57 00:02:57,180 --> 00:03:00,830 capacity, for simplicity you can generalize that if you want okay, and 58 00:03:00,830 --> 00:03:04,620 essentially a solution to this problem is going to be a sequence. 59 00:03:04,620 --> 00:03:09,340 Of customer visit, okay or location visit for everyone of the vehicles. 60 00:03:09,340 --> 00:03:12,810 So we're going to call that Ti, that's the sequence of locations that are 61 00:03:12,810 --> 00:03:16,080 visited, except from the warehouse, except the warehouse, by everyone of 62 00:03:16,080 --> 00:03:19,030 these vehicles, okay? So what you are minimizing is essentially 63 00:03:19,030 --> 00:03:23,570 the traveled distance, okay? So this is essentially moving from the, 64 00:03:23,570 --> 00:03:27,540 the, the warehouse to the first customer, then this is the travelled distance 65 00:03:27,540 --> 00:03:31,070 between you know every one of the customers that you are visiting. 66 00:03:31,070 --> 00:03:34,720 And at the end of the day you have to get back to the depot such that truck can 67 00:03:34,720 --> 00:03:38,900 start on the subsequent date. Okay now the customer, the sequence of 68 00:03:38,900 --> 00:03:43,080 customers that you are picking for one particular vehicle has to be smaller than 69 00:03:43,080 --> 00:03:47,190 the capacity of the vehicle at the, should be such the demand of the customer 70 00:03:47,190 --> 00:03:49,350 is smaller than the capacity of the vehicle. 71 00:03:49,350 --> 00:03:55,400 And then you want to be sure that every one of the location, every one of the 72 00:03:55,400 --> 00:04:00,040 location is visited exactly once. Okay, so that's what this constraint is 73 00:04:00,040 --> 00:04:03,210 expressing. Okay, basically you look at j which is a 74 00:04:03,210 --> 00:04:07,630 particular location. You know the constraint j belongs to Ti 75 00:04:07,630 --> 00:04:12,680 is telling you if that particular location is visited by vehicle i and when 76 00:04:12,680 --> 00:04:15,290 you sum over the vehicle. That has to be equal to one. 77 00:04:15,290 --> 00:04:18,090 Okay? Of course, you know, there are very few, 78 00:04:18,090 --> 00:04:20,410 no solvers that I know, well, actually, no, they can be. 79 00:04:20,410 --> 00:04:23,590 Well, no, no real solver that I know which would actually express that 80 00:04:23,590 --> 00:04:25,430 constraints directly like it is stated here. 81 00:04:25,430 --> 00:04:28,690 Okay? So, essentially, this is, this is the 82 00:04:28,690 --> 00:04:33,105 formulation, we have input output, right? The input for this problem is going to be 83 00:04:33,105 --> 00:04:35,330 simple, right? So, that's all the stuff that I have been 84 00:04:35,330 --> 00:04:39,280 going through in the previous slide. We have the number of location, we have 85 00:04:39,280 --> 00:04:44,690 the number of vehicles, we have the capacity of the vehicles, and then for 86 00:04:44,690 --> 00:04:48,880 every one of these locations, we have the x and y coordinate, even for the depot. 87 00:04:48,880 --> 00:04:52,100 It's not necssariy 0,0. And we have the, and, and the first 88 00:04:52,100 --> 00:04:54,520 number is actually the demand of that particular location. 89 00:04:54,520 --> 00:04:59,265 For the warehouse, okay, that value is 0. Okay so basically what you get here is a 90 00:04:59,265 --> 00:05:04,370 long list of demand location, demand location, demand location, and so on, for 91 00:05:04,370 --> 00:05:05,920 all the locations. Okay? 92 00:05:05,920 --> 00:05:10,090 The output that we want, okay, for this particular problem, is the value of the 93 00:05:10,090 --> 00:05:12,610 objective function, that's the first line, option, the value. 94 00:05:12,610 --> 00:05:15,760 Okay? And then we want the sequence of 95 00:05:15,760 --> 00:05:20,190 customers that are visited by every one of these of these vehicles. 96 00:05:20,190 --> 00:05:23,470 So you see the first vehicle's going to start from zero, then visit a number of 97 00:05:23,470 --> 00:05:28,090 customers, and go back to zero, okay? So that's basically the sequence of visit 98 00:05:28,090 --> 00:05:31,410 of that particular vehicle, same thing for the subsequent one and for all the 99 00:05:31,410 --> 00:05:34,065 vehicles that we have. That's the output that we need to check. 100 00:05:34,065 --> 00:05:37,010 Okay. So that's essentially the input output 101 00:05:37,010 --> 00:05:41,100 specification. so for instance, this is the input for 102 00:05:41,100 --> 00:05:43,340 this particular simple example. Okay? 103 00:05:43,340 --> 00:05:45,540 So we have five locations. Okay? 104 00:05:45,540 --> 00:05:51,520 So we have four vehicles and the capacity of the vehicle is 10 okay. 105 00:05:51,520 --> 00:05:55,030 And this essentially the demand to everyone of these locations and the 106 00:05:55,030 --> 00:05:58,040 various points okay. So the first one is the warehouse zero 107 00:05:58,040 --> 00:06:03,090 demand the location of this point is 0, 0 and then you see the other one the demand 108 00:06:03,090 --> 00:06:07,230 are basically 3 for every one of them and you see in this particular case. 109 00:06:07,230 --> 00:06:09,380 The various location of these points in the in the plane. 110 00:06:09,380 --> 00:06:15,530 Okay so 0, 10 minus 10 10, 0 minus 10 and 10 minus 10. 111 00:06:15,530 --> 00:06:16,448 Okay. that's the input. 112 00:06:16,448 --> 00:06:22,130 This is the output which is provided by the first bad tool that we saw okay bad 113 00:06:22,130 --> 00:06:27,000 side of tools that we saw. The value is 80.6 and it's not optimal 114 00:06:27,000 --> 00:06:29,225 okay so that's why you have the 0 flag over there. 115 00:06:29,225 --> 00:06:35,250 Okay, what you see here is basically the sequence of the first, of the first 116 00:06:35,250 --> 00:06:39,460 picture, okay? It starts at 0, okay, it goes to 1 and 117 00:06:39,460 --> 00:06:43,230 then it goes to 2 and then it goes to 3 and then go back, okay? 118 00:06:43,230 --> 00:06:46,990 So that's what you see in this particular 1 0 1 2 3 0, okay? 119 00:06:46,990 --> 00:06:50,902 The next one is 0 4 0, you know this is going to 4 and then going back. 120 00:06:50,902 --> 00:06:53,520 And the two other vehicles. The drivers are very happy. 121 00:06:53,520 --> 00:06:54,330 They can sleep that you know, they can spend the day sleeping. 122 00:06:54,330 --> 00:06:59,378 Okay so that's essentially the output for this particular for this particular 123 00:06:59,378 --> 00:07:03,003 example. Okay yup and this is explaining which of 124 00:07:03,003 --> 00:07:07,989 these two is actually covering the output, okay. 125 00:07:07,989 --> 00:07:10,361 So no this assignment is really really hard. 126 00:07:10,361 --> 00:07:13,213 It's very close to real application, there are real applications based on 127 00:07:13,213 --> 00:07:16,910 these actually. so there are ways, there are various to 128 00:07:16,910 --> 00:07:18,950 model it. You can use the CP approach, you can look 129 00:07:18,950 --> 00:07:22,160 at the MIP approach, you can look at the Local Search approach, or a hybridization 130 00:07:22,160 --> 00:07:23,600 of these things. Okay? 131 00:07:23,600 --> 00:07:26,170 they are all connected to the TSP in some fashion. 132 00:07:26,170 --> 00:07:29,980 You can see that is a color CIP, Multi-Colored TSP, okay. 133 00:07:29,980 --> 00:07:32,780 And so you will have to be kind of creative and, and every one of these 134 00:07:32,780 --> 00:07:34,840 solutions is going to be interesting, okay. 135 00:07:34,840 --> 00:07:38,710 Now if you use a CP model in general, one of the things that is nice here, is 136 00:07:38,710 --> 00:07:44,210 modeling everything as a big, as looking for one large tool, okay. 137 00:07:44,210 --> 00:07:47,780 And the key point here is that you would duplicate the warehouse, you would 138 00:07:47,780 --> 00:07:50,350 consider that you have four warehouses all in the same location. 139 00:07:50,350 --> 00:07:53,170 Okay? And then essentially you will do a first 140 00:07:53,170 --> 00:07:54,590 two which is going to be the first vehicle. 141 00:07:54,590 --> 00:07:58,230 It's going to start from the first depot. Do the tour and go back to the, you know, 142 00:07:58,230 --> 00:08:01,150 go back to the second depot. From there, the second vehicle is 143 00:08:01,150 --> 00:08:04,399 going to stop, okay, and go back to the third thing, okay? 144 00:08:04,399 --> 00:08:07,810 And to the third depot. And then the third depot here is going to 145 00:08:07,810 --> 00:08:10,930 go to the fourth, and the fourth is going to is going to go back to the first 146 00:08:10,930 --> 00:08:11,730 one. Okay? 147 00:08:11,730 --> 00:08:17,140 So what this shows you, essentially, is that you can, you know, turn this basic, 148 00:08:17,140 --> 00:08:22,030 you know, multi vehicle problem into finding a big circuit where the vehicles 149 00:08:22,030 --> 00:08:24,780 here are linked. Okay, they would be not linked in time, 150 00:08:24,780 --> 00:08:26,551 it's just a modelling trick here. Okay? 151 00:08:26,551 --> 00:08:30,790 Of A CP, you'll want to make sure that the capacity of the first two you know 152 00:08:30,790 --> 00:08:33,440 going from the first warehouse to the second one here. 153 00:08:33,440 --> 00:08:36,057 Is going to be, is going to be the capacity constraint is going to be 154 00:08:36,057 --> 00:08:38,010 satisfied. You also want to make sure that the 155 00:08:38,010 --> 00:08:41,490 various, you know, knows how is it at exactly once and things like this. 156 00:08:41,490 --> 00:08:44,250 Okay? So, in the MIP model okay. 157 00:08:44,250 --> 00:08:47,780 So what you will after resolve about this is flows okay. 158 00:08:47,780 --> 00:08:51,719 So, think again the way we have modeled, you know the TSP's and all the and all 159 00:08:51,719 --> 00:08:53,400 the things like this. Okay. 160 00:08:53,400 --> 00:08:56,500 So if you have four vehicles, what you are going to do is basically multiply the 161 00:08:56,500 --> 00:09:00,680 number of edges, that you multiply, you're going to quadruplicate in four 162 00:09:00,680 --> 00:09:04,390 vehicle every one of the nodes, every one of the lanes, okay. 163 00:09:04,390 --> 00:09:07,500 So, so that's what you do, that's what this picture is showing you here. 164 00:09:07,500 --> 00:09:10,150 Okay. Obviously, you know you will want to make 165 00:09:10,150 --> 00:09:13,746 sure that there is only one, at most one vehicle traveling between one and two, 166 00:09:13,746 --> 00:09:17,246 they may be zero, right. Because you know one and two may never be 167 00:09:17,246 --> 00:09:21,560 you know connected in a particular tour, on any particular vehicle. 168 00:09:21,560 --> 00:09:25,860 And you also want to make sure that for every one of these vertices exactly two 169 00:09:25,860 --> 00:09:30,120 of these edges are going to be exactly two of these edges are going to be you 170 00:09:30,120 --> 00:09:33,090 know linked to that vertex. You have to go there and you have to get 171 00:09:33,090 --> 00:09:35,329 out. And in this particular case you have to 172 00:09:35,329 --> 00:09:38,250 make sure that this is done by you know the same vehicle. 173 00:09:38,250 --> 00:09:41,760 So you will have to express that constraint okay but once again if a 174 00:09:41,760 --> 00:09:45,170 particular node can be visited by several of these vehicles. 175 00:09:45,170 --> 00:09:48,930 Okay so this is giving you some hints on how you can actually do this. 176 00:09:48,930 --> 00:09:51,100 Okay so you will have to figure out the details by yourself. 177 00:09:51,100 --> 00:09:55,410 Right? yes, so local search is probably the most 178 00:09:55,410 --> 00:09:57,410 intuitive way of actually solving this problem. 179 00:09:57,410 --> 00:10:00,770 It's actually also an interesting way to solve that problem. 180 00:10:00,770 --> 00:10:02,250 I don't want to give you too many hints, right? 181 00:10:02,250 --> 00:10:06,760 So so the, one of the ways to do this is to find the first solution. 182 00:10:06,760 --> 00:10:10,280 You can start saying, okay, so where can I insert a particular customer? 183 00:10:10,280 --> 00:10:13,190 And this is one of the way. As soon as you do that, and you look at 184 00:10:13,190 --> 00:10:15,540 the second customer. There are many insertion points here, 185 00:10:15,540 --> 00:10:18,370 there are one more actually. You can still insert it in the vehicle 186 00:10:18,370 --> 00:10:22,440 but you can insert it before the previous, you know the customer one or 187 00:10:22,440 --> 00:10:25,610 after customer one okay. So you have many more, or one more 188 00:10:25,610 --> 00:10:29,240 insertion point in this particular case. Okay, and now when you look at you know, 189 00:10:29,240 --> 00:10:33,470 customer three, now customer three can be put you know here, you know in between 190 00:10:33,470 --> 00:10:36,860 these two customers after them both and once again on the other vehicles as well 191 00:10:36,860 --> 00:10:39,230 okay. So, you have many, you know insertion 192 00:10:39,230 --> 00:10:42,790 point for these things okay. So, once you have a solution like this 193 00:10:42,790 --> 00:10:48,030 okay, so what you can stop doing is also moving customers around, you can decide 194 00:10:48,030 --> 00:10:50,710 to take them from one vehicle, insert them into another one. 195 00:10:50,710 --> 00:10:53,990 Once again you can view that is a variety of insertion points. 196 00:10:53,990 --> 00:10:56,570 Where that particular customers can be relocated. 197 00:10:56,570 --> 00:10:58,450 Okay? They can be relocated inside the same 198 00:10:58,450 --> 00:11:02,430 vehicle because that could actually decrease, you know, the traveling time 199 00:11:02,430 --> 00:11:03,920 the distance that you are basically doing. 200 00:11:03,920 --> 00:11:05,940 And they can be inserted in other vehicles. 201 00:11:05,940 --> 00:11:07,860 And so on and so forth. Okay? 202 00:11:07,860 --> 00:11:09,260 So that's the kind of things that you can do. 203 00:11:09,260 --> 00:11:12,990 Okay? And so this is this is the various, this 204 00:11:12,990 --> 00:11:15,610 is the various technologies if you use them independently. 205 00:11:15,610 --> 00:11:18,480 So what all these methods that I've shown you are doing, is that they are solving 206 00:11:18,480 --> 00:11:21,260 the problem globally, and they are considering the routing, and the 207 00:11:21,260 --> 00:11:24,440 assignments of. customers to the various truck at the 208 00:11:24,440 --> 00:11:27,670 same time, okay? Now, some of the things that we saw in 209 00:11:27,670 --> 00:11:30,320 this class is that sometimes you can break these things into parts, okay. 210 00:11:30,320 --> 00:11:34,820 So, you could first assign the the the the customers to the vehicle, okay, while 211 00:11:34,820 --> 00:11:38,220 trying to ensure that the capacity constraints are are satisfied, and then 212 00:11:38,220 --> 00:11:41,120 you can start routing these things, okay. So, you could say oh I'm going to do an 213 00:11:41,120 --> 00:11:43,820 assignment of these things, okay and then I'm going to see oh even in the 214 00:11:43,820 --> 00:11:47,870 assignment how best can I do the various you know tricks. 215 00:11:47,870 --> 00:11:50,830 Okay, so once again you can decide to use a popular method for doing this 216 00:11:50,830 --> 00:11:54,814 assignment and then use various kinds of methods for solving the second step okay. 217 00:11:54,814 --> 00:11:58,485 So you're basically decoupling the two aspects of the two aspects of the 218 00:11:58,485 --> 00:12:01,856 problem, the objective function and the capacity constraint. 219 00:12:01,856 --> 00:12:05,850 So so even the even the first appearing isn't not necessarily easy okay. 220 00:12:05,850 --> 00:12:10,380 So for instance if you have four customers of size 40 and you have 221 00:12:10,380 --> 00:12:13,998 vehicles of capacity 40. Okay you may say oh but how many of these 222 00:12:13,998 --> 00:12:18,040 vehicles do I need okay and so you may say that in the best case I need 223 00:12:18,040 --> 00:12:22,620 basically 120 as a capacity. So I probably need three vehicles. 224 00:12:22,620 --> 00:12:25,270 But in this particular case three vehicles is not going to be you know 225 00:12:25,270 --> 00:12:29,395 sufficient because once you place this, you know you can't break that particular 226 00:12:29,395 --> 00:12:31,660 demand in terms of the three different trucks. 227 00:12:31,660 --> 00:12:33,530 Okay? So you have to serve the demand entirely 228 00:12:33,530 --> 00:12:34,600 by your truck. Okay? 229 00:12:34,600 --> 00:12:38,572 So what you do what you would need in this particular case is at least four 230 00:12:38,572 --> 00:12:41,190 vehicles okay so we have a problem here, okay. 231 00:12:41,190 --> 00:12:45,170 So you need another vehicle. So in a sense in this particular case you 232 00:12:45,170 --> 00:12:48,470 won't have to find the minimum number of vehicles, this is typically something 233 00:12:48,470 --> 00:12:50,130 that you have to do in vehicle routing problem. 234 00:12:50,130 --> 00:12:52,750 You always one phase where you are trying to minimize your fleet size. 235 00:12:52,750 --> 00:12:56,380 Here the fleet size is given to you, you don't have to worry about this okay. 236 00:12:56,380 --> 00:13:00,670 You just have to find out how you can actually pack them with the various 237 00:13:00,670 --> 00:13:03,720 customers that you have to satisfy the capacity constraints, okay. 238 00:13:03,720 --> 00:13:07,300 Let's go to multi-knapsack, okay. It's linked to bin packing as well. 239 00:13:07,300 --> 00:13:09,880 Okay? But you need to solve that. 240 00:13:09,880 --> 00:13:11,850 Okay? And then afterwards, essential, 241 00:13:11,850 --> 00:13:15,680 essentially, you need to solve the various sub-tools, the various tools for 242 00:13:15,680 --> 00:13:19,190 the various vehicles. So in a sense, the capacity VRP can be 243 00:13:19,190 --> 00:13:22,920 seen as two, you know, optimization problems, kind of a multi-knapsack and at 244 00:13:22,920 --> 00:13:25,470 the same time it's a TSP. Okay. 245 00:13:25,470 --> 00:13:28,450 So many of the optimization problems start combining these things. 246 00:13:28,450 --> 00:13:32,100 Different parts of the problems which are themselves sometimes [UNKNOWN] and that's 247 00:13:32,100 --> 00:13:35,200 what make them very difficult and very interesting in practice. 248 00:13:35,200 --> 00:13:38,150 Okay. So many approach can work. 249 00:13:38,150 --> 00:13:41,070 You know, you know, you, you have to try various things on this, on this 250 00:13:41,070 --> 00:13:42,800 particular area. Okay? 251 00:13:42,800 --> 00:13:45,790 So you can reuse some of the solvers that you have seen. 252 00:13:45,790 --> 00:13:47,900 There are a lot of symmetries in this problems. 253 00:13:47,900 --> 00:13:50,050 These vehicles are interchangeable. Okay? 254 00:13:50,050 --> 00:13:53,400 So you need to think about how to break that in any kind of methods that you 255 00:13:53,400 --> 00:13:56,330 have. if you use local search, you have to 256 00:13:56,330 --> 00:13:59,030 think how quickly you can evaluate you know, local moves. 257 00:13:59,030 --> 00:14:01,120 That's always critical as I told you before. 258 00:14:01,120 --> 00:14:06,070 Okay, so I find this is a really nice assignment, is really close to a real 259 00:14:06,070 --> 00:14:09,310 product, is really close to things that we do in disaster management. 260 00:14:09,310 --> 00:14:13,230 That we do in logistic and supply chain. So, it's going to give you a real taste 261 00:14:13,230 --> 00:14:15,745 of what it takes to actually solve these problems in practice. 262 00:14:15,745 --> 00:14:17,460 Okay, thank you guys.