So the last category, or the last application that we want to introduce is called vehicle routing problems. So let's see what's this. In many cases, what we need to do is to deliver, or to collect items to, or from customers in the most efficient way. So you may imagine about post officers, or post deliverers that need to ship packages, or mails to all the customers, okay? So in this graph, we are showing you a case that one post officer, this post officer needs to deliver to four different addresses. Okay, so this colored circle is the original point is the post office. The other four are customer addresses. So what we want to do is to find the shortest path between any pair of two addresses. So let's say we already know how to go from A to B, from B to C. That's pretty much something that we already obtained. We know from here to there, we need at least 5 minutes. If we do it in the fastest way, that's 5 minutes. From here to there, that says from there to here, that's 8, and so on and so on. Pretty much, that means on this graph, we have the traveling time we need for each link. Then this is a routing problem. Starting from the original point, we want to choose a route where the starting point is the office. And then it must go through each address exactly once, and then returning to the office. Okay, so this is a very natural work. I start from my office. I bring the items, bring the mails, and I travel through each customer points one by one. And then what I want to do is that I hope this particular route has the minimum distance, okay? So this is a particular route, right? So if that's the case, I finish all these four points, and then back to my office. There can be, of course, some other routes. For example, maybe you do it in this way, right, is also a route. So you don't know which one is good, in some sense. So in this case, what we want to do is that okay, we may want to sequence the visit. If that's the case, then again, you have 4 factorial. If you have 8 points to visit, you have 8 factorial, and so on and so on. When you have too many points to visit, there is no way for you to enumerate all these possibilities. So we want to, again, rely on integer programming to help us. So the problem described above is the famous traveling salesperson problem, okay? It assumes that the truck, or the car, or the motorcycle used by the post officer can bring the things that he needs to bring. There is no capacity issue, right? But of course, in many cases, we do have a capacity issue. For example, in NTU, from time to time, you will see trucks. They are trying to tow bicycles. So this must, because those bicycles, they are parked at some places that you cannot park bicycles. So the truck would come and bring the bicycles away. So basically, this looks like a traveling salesperson problem. It's just that actually, the truck capacity should be considered. So pretty much, the driver may need multiple routes to finish all the locations. That's possible, okay? So in this particular example, you may see your capacity is 10. And also, at each point, there is the number of demands that you want to satisfy. Then this is one route. This is another route. They are two feasible routes. And in this particular example, it may be optimal. So today we don't want to talk about vehicle routing problems. We will talk about traveling salesperson problem, because it's a special case of vehicle routing problems, right? But we don't have time to talk about the vehicle routing problems in general, so we will assume there is no capacity issue. And we simply want to find one route to travel through all customers, and then going back to the office. So to formulate this problem, pretty much, we need to start by considering the network. Let's say we have a directed network. This particular directed network, what everything means, we have a graph, or a network G. And we have a set of node V, and a set of directed edges, E. So both directed, that means from A to B, you may have a route, or you will have a link. From B to A, probably you don't, all right? So that's the case. So now we need to think about the structure. Let's say we have n nodes. If that's the case, then we have n times n- 1 arcs. Why is that? Suppose n is 3, then this is one link 2, 3, 4, 5, 6. All right, 3 x 2 is 6. So that's the idea. Basically, we are talking about directed edges, okay? And the arc weight for arc ij is dij. So this is somehow suggesting that from point 1 to point 2, you have d12. From 2 to 1, you have d21, and then they may be different in general. Okay, so we now want to select a few arcs and form a tour. So a tour is complete visit, coming back to your office, then that's a tour. To form a tour, of course, we need to select an arcs, just like the graph depicted at the right hand side. We select arc 1, 2, 3, 4, and 5. Once you have that, then you are done by having a tour, okay? So these an arcs should form a cycle passing all nodes. So somehow, we need to have a way to choose links. And then we write down some constraints to make sure that they really form a route. So I guess it's not too surprising for each arc, we're going to set xij to be 1. If that arc is considered, is selected as part of the tour, and if the arc is not selected, xij should be 0. Okay, so the objective value is here. Basically, is that we consider all those edges, all those arcs, and ask for which pair of arcs i, j, we have x i, j being 1. Once we want to select this arc, we need to take care of that dij, because dij is going to be added into our tour, all right? So this is the summation. This summation is the total traveling distance. And we try to minimize this one. Now, we need to ensure that we have the routing requirement, which satisfied the routing requirements. So we need to write it down. There are several proposals. The first proposal says that how about this? Let's say we need to select n edges, okay? If we want to select n edges, actually, there is a typo here. We don't have this one. So pretty much, we are asking that for all the edges, for all the arcs, let's say the number of arcs selected = n, okay? If you have 5 points here, then of course, you'll need 5 edges, so that you may form a route. So this looks fine. But unfortunately, this is not good enough, because only knowing this may give you weird solutions. For example, maybe this is your first, second, third, fourth, and the fifth. Okay, you may select these 5 arcs, and it is not a tour at all. So we need some more, okay? So we're going to impose the so-called flow balancing constraints. So for a note, we need to do this. For all those incoming arcs, we select exactly 1. For all those outgoing arcs, we select exactly 1. So what does that mean? Think about the example I just wrote, or I should just use this one. So suppose I look at a note. Let's say this is note k. Then the constraint here says that there are 3 entering arcs, or incoming arcs. All I can do is to choose exactly one of them. So that makes sense, because you need to travel through all the nodes. There must be 1 out of these 3 that should be selected. And then it also says that for each outgoing arcs, you need to select one of them. So for example, here and there, these two links, one of them must be selected. Because somehow, if that's really a tour, then for this particular node, for any node, you have an incoming selected. You have an outgoing selected, right? So that's pretty much the idea. If I can make sure that for each node on the graph, there is one entering, there's one leaving, then ideally, it should be collected and form a route, right? So pretty much, that's the idea. Unfortunately, there is nothing we have said about subtours. Okay, so subtours is the case that you don't really have one big cycle for your graph. You have multiple small circles, and they don't connect with each other. So pretty much, that's also not a feasible solution. So in the next video, we will show you how to deal with this.
