0:00

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.