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.