Okay. 
Guys I want to cover the vehicle routing 
assignment. 
Okay? 
For the, for the discrete optimization 
class. 
Okay? 
So the vehicle routing problem is one of 
the most fascinating problem. 
Okay? 
it's, it's, it's a beautiful research 
area. 
There are, it's very, you know, 
applicable in practice. 
There are a lot of practical application. 
There are many variants. 
You know, people have spent their lives 
you know, working on these things. 
You know, this is one of the areas of, 
you know, optimization that I like the 
most. 
Okay, so what we're going to see in, and 
this is also very difficult in general, 
okay, so what you're going to see here is 
that we're going to look the assignment 
is going to be one particular type which 
is called the capacitated VRP. 
This is, by far, none of the most 
difficult, you know, VRP problems, but is 
very challenging, it's still very, very 
challenging. 
So you have to think about it as, like 
the TSP except that you know, on 
steroids, okay. 
So we have many vehicles and we have 
these additional constraints on what 
these vehicles can do, okay. 
So, vehicle warning, okay. 
So this is a simple, you know, 
formulation here that we're going to see 
where we already see some of the input 
data, okay. 
So you have a bunch of. 
Different sites here, okay, one of them 
is the warehouse, that's where the 
vehicles are starting, okay? 
So this is for Caltain and Victor. 
I want to call it a depot but they like 
warehouse so I'm very friendly with my 
collaborator so we're going to call that 
a warehouse, okay? 
So for everyone of them, you see a 
coordinate, okay? 
So that's where the lie on the plane, 
okay? 
And you see also some demand there, that, 
think of it as. 
You know, this is the you know the kind 
of way that you are collecting at every 
one of these at every one of these 
location. 
Okay. 
So so you will have four vehicles for 
instance in this particular area. 
The capacity of this vehicle is going to 
be 10. 
So, the way that you are picking up at 
every one of these location can never 
exceed 10. 
Okay. 
This is the warehouse I told you, 
warehouse not depot, warehouse, okay. 
And so this is essentially one tour okay, 
which is a cost of 80.6, okay, that's the 
distance which is traveled by the 
vehicles. 
You see one vehicle here, I believe this 
is green, right, and another one which is 
probably purple, okay. 
And so that's what the vehicles are 
doing. 
They satisfy the capacity constraints 
okay, and obviously they visit every 
customers exactly once. 
So this is another of this tool which is 
actually better okay. 
So the cost is only 68.3 and once again 
it satisfies the capacity constraint. 
So the goal of the assignment is to find 
these better tools for everyone one of 
the vehicles satisfying the capacity 
constraint. 
Minimizing the total travel distance. 
Okay? 
So formally, this is how you can describe 
the problem. 
Now, this is an impossible formulation, 
right. 
So don't try to run this, this will 
almost never run anywhere. 
Okay. 
But this is, you know, stating what the 
problem is. 
So you have n vehicles, okay. 
And you have n customers, and n 
locations, sorry, and v vehicles. 
for everyone of the location okay, so we 
have the demand for that location di, and 
we have the location in the plane, you 
know given by xi, yi okay. 
Now, the capacity of the vehicle is this 
constant c, they all have the same 
capacity, for simplicity you can 
generalize that if you want okay, and 
essentially a solution to this problem is 
going to be a sequence. 
Of customer visit, okay or location visit 
for everyone of the vehicles. 
So we're going to call that Ti, that's 
the sequence of locations that are 
visited, except from the warehouse, 
except the warehouse, by everyone of 
these vehicles, okay? 
So what you are minimizing is essentially 
the traveled distance, okay? 
So this is essentially moving from the, 
the, the warehouse to the first customer, 
then this is the travelled distance 
between you know every one of the 
customers that you are visiting. 
And at the end of the day you have to get 
back to the depot such that truck can 
start on the subsequent date. 
Okay now the customer, the sequence of 
customers that you are picking for one 
particular vehicle has to be smaller than 
the capacity of the vehicle at the, 
should be such the demand of the customer 
is smaller than the capacity of the 
vehicle. 
And then you want to be sure that every 
one of the location, every one of the 
location is visited exactly once. 
Okay, so that's what this constraint is 
expressing. 
Okay, basically you look at j which is a 
particular location. 
You know the constraint j belongs to Ti 
is telling you if that particular 
location is visited by vehicle i and when 
you sum over the vehicle. 
That has to be equal to one. 
Okay? 
Of course, you know, there are very few, 
no solvers that I know, well, actually, 
no, they can be. 
Well, no, no real solver that I know 
which would actually express that 
constraints directly like it is stated 
here. 
Okay? 
So, essentially, this is, this is the 
formulation, we have input output, right? 
The input for this problem is going to be 
simple, right? 
So, that's all the stuff that I have been 
going through in the previous slide. 
We have the number of location, we have 
the number of vehicles, we have the 
capacity of the vehicles, and then for 
every one of these locations, we have the 
x and y coordinate, even for the depot. 
It's not necssariy 0,0. 
And we have the, and, and the first 
number is actually the demand of that 
particular location. 
For the warehouse, okay, that value is 0. 
Okay so basically what you get here is a 
long list of demand location, demand 
location, demand location, and so on, for 
all the locations. 
Okay? 
The output that we want, okay, for this 
particular problem, is the value of the 
objective function, that's the first 
line, option, the value. 
Okay? 
And then we want the sequence of 
customers that are visited by every one 
of these of these vehicles. 
So you see the first vehicle's going to 
start from zero, then visit a number of 
customers, and go back to zero, okay? 
So that's basically the sequence of visit 
of that particular vehicle, same thing 
for the subsequent one and for all the 
vehicles that we have. 
That's the output that we need to check. 
Okay. 
So that's essentially the input output 
specification. 
so for instance, this is the input for 
this particular simple example. 
Okay? 
So we have five locations. 
Okay? 
So we have four vehicles and the capacity 
of the vehicle is 10 okay. 
And this essentially the demand to 
everyone of these locations and the 
various points okay. 
So the first one is the warehouse zero 
demand the location of this point is 0, 0 
and then you see the other one the demand 
are basically 3 for every one of them and 
you see in this particular case. 
The various location of these points in 
the in the plane. 
Okay so 0, 10 minus 10 10, 0 minus 10 and 
10 minus 10. 
Okay. 
that's the input. 
This is the output which is provided by 
the first bad tool that we saw okay bad 
side of tools that we saw. 
The value is 80.6 and it's not optimal 
okay so that's why you have the 0 flag 
over there. 
Okay, what you see here is basically the 
sequence of the first, of the first 
picture, okay? 
It starts at 0, okay, it goes to 1 and 
then it goes to 2 and then it goes to 3 
and then go back, okay? 
So that's what you see in this particular 
1 0 1 2 3 0, okay? 
The next one is 0 4 0, you know this is 
going to 4 and then going back. 
And the two other vehicles. 
The drivers are very happy. 
They can sleep that you know, they can 
spend the day sleeping. 
Okay so that's essentially the output for 
this particular for this particular 
example. 
Okay yup and this is explaining which of 
these two is actually covering the 
output, okay. 
So no this assignment is really really 
hard. 
It's very close to real application, 
there are real applications based on 
these actually. 
so there are ways, there are various to 
model it. 
You can use the CP approach, you can look 
at the MIP approach, you can look at the 
Local Search approach, or a hybridization 
of these things. 
Okay? 
they are all connected to the TSP in some 
fashion. 
You can see that is a color CIP, 
Multi-Colored TSP, okay. 
And so you will have to be kind of 
creative and, and every one of these 
solutions is going to be interesting, 
okay. 
Now if you use a CP model in general, one 
of the things that is nice here, is 
modeling everything as a big, as looking 
for one large tool, okay. 
And the key point here is that you would 
duplicate the warehouse, you would 
consider that you have four warehouses 
all in the same location. 
Okay? 
And then essentially you will do a first 
two which is going to be the first 
vehicle. 
It's going to start from the first depot. 
Do the tour and go back to the, you know, 
go back to the second depot. 
From there, the second vehicle is 
going to stop, okay, and go back to the 
third thing, okay? 
And to the third depot. 
And then the third depot here is going to 
go to the fourth, and the fourth is 
going to is going to go back to the first 
one. 
Okay? 
So what this shows you, essentially, is 
that you can, you know, turn this basic, 
you know, multi vehicle problem into 
finding a big circuit where the vehicles 
here are linked. 
Okay, they would be not linked in time, 
it's just a modelling trick here. 
Okay? 
Of A CP, you'll want to make sure that 
the capacity of the first two you know 
going from the first warehouse to the 
second one here. 
Is going to be, is going to be the 
capacity constraint is going to be 
satisfied. 
You also want to make sure that the 
various, you know, knows how is it at 
exactly once and things like this. 
Okay? 
So, in the MIP model okay. 
So what you will after resolve about this 
is flows okay. 
So, think again the way we have modeled, 
you know the TSP's and all the and all 
the things like this. 
Okay. 
So if you have four vehicles, what you 
are going to do is basically multiply the 
number of edges, that you multiply, 
you're going to quadruplicate in four 
vehicle every one of the nodes, every one 
of the lanes, okay. 
So, so that's what you do, that's what 
this picture is showing you here. 
Okay. 
Obviously, you know you will want to make 
sure that there is only one, at most one 
vehicle traveling between one and two, 
they may be zero, right. 
Because you know one and two may never be 
you know connected in a particular tour, 
on any particular vehicle. 
And you also want to make sure that for 
every one of these vertices exactly two 
of these edges are going to be exactly 
two of these edges are going to be you 
know linked to that vertex. 
You have to go there and you have to get 
out. 
And in this particular case you have to 
make sure that this is done by you know 
the same vehicle. 
So you will have to express that 
constraint okay but once again if a 
particular node can be visited by several 
of these vehicles. 
Okay so this is giving you some hints on 
how you can actually do this. 
Okay so you will have to figure out the 
details by yourself. 
Right? 
yes, so local search is probably the most 
intuitive way of actually solving this 
problem. 
It's actually also an interesting way to 
solve that problem. 
I don't want to give you too many hints, 
right? 
So so the, one of the ways to do this is 
to find the first solution. 
You can start saying, okay, so where can 
I insert a particular customer? 
And this is one of the way. 
As soon as you do that, and you look at 
the second customer. 
There are many insertion points here, 
there are one more actually. 
You can still insert it in the vehicle 
but you can insert it before the 
previous, you know the customer one or 
after customer one okay. 
So you have many more, or one more 
insertion point in this particular case. 
Okay, and now when you look at you know, 
customer three, now customer three can be 
put you know here, you know in between 
these two customers after them both and 
once again on the other vehicles as well 
okay. 
So, you have many, you know insertion 
point for these things okay. 
So, once you have a solution like this 
okay, so what you can stop doing is also 
moving customers around, you can decide 
to take them from one vehicle, insert 
them into another one. 
Once again you can view that is a variety 
of insertion points. 
Where that particular customers can be 
relocated. 
Okay? 
They can be relocated inside the same 
vehicle because that could actually 
decrease, you know, the traveling time 
the distance that you are basically 
doing. 
And they can be inserted in other 
vehicles. 
And so on and so forth. 
Okay? 
So that's the kind of things that you can 
do. 
Okay? 
And so this is this is the various, this 
is the various technologies if you use 
them independently. 
So what all these methods that I've shown 
you are doing, is that they are solving 
the problem globally, and they are 
considering the routing, and the 
assignments of. 
customers to the various truck at the 
same time, okay? 
Now, some of the things that we saw in 
this class is that sometimes you can 
break these things into parts, okay. 
So, you could first assign the the the 
the customers to the vehicle, okay, while 
trying to ensure that the capacity 
constraints are are satisfied, and then 
you can start routing these things, okay. 
So, you could say oh I'm going to do an 
assignment of these things, okay and then 
I'm going to see oh even in the 
assignment how best can I do the various 
you know tricks. 
Okay, so once again you can decide to use 
a popular method for doing this 
assignment and then use various kinds of 
methods for solving the second step okay. 
So you're basically decoupling the two 
aspects of the two aspects of the 
problem, the objective function and the 
capacity constraint. 
So so even the even the first appearing 
isn't not necessarily easy okay. 
So for instance if you have four 
customers of size 40 and you have 
vehicles of capacity 40. 
Okay you may say oh but how many of these 
vehicles do I need okay and so you may 
say that in the best case I need 
basically 120 as a capacity. 
So I probably need three vehicles. 
But in this particular case three 
vehicles is not going to be you know 
sufficient because once you place this, 
you know you can't break that particular 
demand in terms of the three different 
trucks. 
Okay? 
So you have to serve the demand entirely 
by your truck. 
Okay? 
So what you do what you would need in 
this particular case is at least four 
vehicles okay so we have a problem here, 
okay. 
So you need another vehicle. 
So in a sense in this particular case you 
won't have to find the minimum number of 
vehicles, this is typically something 
that you have to do in vehicle routing 
problem. 
You always one phase where you are trying 
to minimize your fleet size. 
Here the fleet size is given to you, you 
don't have to worry about this okay. 
You just have to find out how you can 
actually pack them with the various 
customers that you have to satisfy the 
capacity constraints, okay. 
Let's go to multi-knapsack, okay. 
It's linked to bin packing as well. 
Okay? 
But you need to solve that. 
Okay? 
And then afterwards, essential, 
essentially, you need to solve the 
various sub-tools, the various tools for 
the various vehicles. 
So in a sense, the capacity VRP can be 
seen as two, you know, optimization 
problems, kind of a multi-knapsack and at 
the same time it's a TSP. 
Okay. 
So many of the optimization problems 
start combining these things. 
Different parts of the problems which are 
themselves sometimes [UNKNOWN] and that's 
what make them very difficult and very 
interesting in practice. 
Okay. 
So many approach can work. 
You know, you know, you, you have to try 
various things on this, on this 
particular area. 
Okay? 
So you can reuse some of the solvers that 
you have seen. 
There are a lot of symmetries in this 
problems. 
These vehicles are interchangeable. 
Okay? 
So you need to think about how to break 
that in any kind of methods that you 
have. 
if you use local search, you have to 
think how quickly you can evaluate you 
know, local moves. 
That's always critical as I told you 
before. 
Okay, so I find this is a really nice 
assignment, is really close to a real 
product, is really close to things that 
we do in disaster management. 
That we do in logistic and supply chain. 
So, it's going to give you a real taste 
of what it takes to actually solve these 
problems in practice. 
Okay, thank you guys.