Hi, everyone. Welcome back to operations research. So this is our second course we're talking about algorithms. In this lecture we will give you a case study which is about service-facility location selection. So for today, just as we always do for a case study or for an OR study, we start from the background and motivation for our research questions. So we will specifically tell you what we want in this particular research, and try to convince you that OR is a reasonable techniques. We then go to model formulation. Try to create a model to describe our problem and try to utilize the model to generate a solution. We'll show you what's the result, what's is practical implication, and because in this series in this course we're talking about algorithms. So we will give you one example about heuristic algorithm and about its evaluation. So the story is here, the company that we collaborated with is NEC Taiwan. So NEC is originally a Japanese company, stand for Nippon Electronics and Communications. So somehow in 1983, the company established subsidiary or branch in Taiwan. But somehow NEC Taiwan now is an independent company in some sense. So this company provides integrated IT and IS services to many customers like Taiwan Railways, 7-11, post offices, and so on. So for example, if you go to 7-11 and try to pay with your NEC card with post machines, those machines are built and maintained by an NEC Taiwan. Okay, you go to those Ibon or whatever things or you go to some systems in post office. Those are built and maintained by NEC Taiwan. So these customers, they purchase hardware and the software in some sense integrated services from NEC. And therefore, these customers they rely on NEC to provide what? Provide after-sales service. So sometimes you go to a 7-11 and you'll see, hey, the Ibon is broken, okay? Temporarily not functional. So if that's the case and if you really need to use Ibon to purchase some tickets or something you will feel angry, right? Or sometimes you see the post machine is not functional. So if that's the case then 7-11 would feel uncomfortable. And then 7-11 would call NEC Taiwan to require some technical services to have some engineers go to the store and the fix the machine, or to do some maintenance, okay? So those technical services are needed if you really want to do business to provide services to these customers. So as of 2017, that's the year when we started to do the project, the company operates 12 service facilities around Taiwan. To host more than 140 engineers to serve more than 14,000 customers sites. So each 7-11 store is a customer site. Each post office is a customer site, for example. So you may see the Taiwan map here. So if you cannot read Chinese characters, that is fine because somehow you still know that this is Taipei, this is Taichung, Kaosiung, something like that. Or if that does not make any sense for you, that's also fine, somehow this is Taiwan. And around the whole island there are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 facilities hosted by NEC Taiwan. And you may see that here in the right hand side we have a lot of dots. And then whenever you see that they are dots in the same color, that means all these dots are customers sites. And then they are all served by a single facility, for example, the barshere are served by the Tai Jong facility, okay? So somehow you may see that the reason to have a lot of facilities, okay? A lot of facilities all around Taiwan is because somehow you feel that if some 7-11, some convenience stores here, if the machine there gets broken, then you need to send someone to travel from here to there to do the service. You don't want to have an engineer to travel too long distance. So that's why traditionally they build a lot of offices around Taiwan. Okay, so that makes sense. But there is also something that you may want to take a look at. For example, if you are hired as a new CEO, maybe you will take a look at how costly it is to provide all these services. So that's assume you are newly hired and you are presented with this table. So this table shows you that from north to south, from east to west, you have these 12 facilities. For each facility, first, you can see the office rent. So that's the rent. That's the amount of money you need to pay to the landlord so that you may run this office for one year, okay? So for example, Nangang is somewhere center in Taipei so you need to pay a lot. Also that's some kind of the base for all these services. So that office is so very large. So you need to pay a lot of money for that particular large office. There are some other expensive places like Taichung, or like Kaohsiung because they are also large in some sense. There are also some other places where like Pingtung, Yilan, Huanlien. All these locations they are not in the middle of a big city. And you also don't need a huge space. So that's why the rents are cheap in some sense. Okay, so one cost to provide all these services are office rents. There are also some other costs. For example, there are utility fee. So if you have an office, there are some people working around, and they need to use electricities, they need to use waters, they need to drink coffees. So that's why you need some utility fee, okay? So there are some fees that are related to the location and also related to the number of engineers, number of people you put in each location. Finally, there is a set of costs called service costs. So what's that? That's the cost you pay to send engineers go back and forth between your location and the customer sites. So for example, if you have a facility here, and then there are all kinds of customers around you. So if today, one machine is broken you have someone go there and then go back. Another machine is broken there, you'll have someone to go there and go back. So you need to send someone to travel. And you cannot do that those engineers pay their own traveling costs, right? At different places you have different ways to send those engineers. But typically, they drive company cars from here to there and go back and forth. So for those company cars, you need to pay for the oils, you need to pay for the car maintenance fees, and so on. And that those fees are called service cost. That's the cost for you to provide the services or to specifically travel between your facility and the customer sites. All in all, this, this and that all together is roughly $100 million. So one thing I need to tell you is that because the real numbers are a secret for the company. So we are not allowed to reveal the true numbers for you. But that's pretty much the same, pretty much close to the real practice. So somehow you may still think about, well, that's not a small number. Maybe there are some ways to think about whether we may cut down some facilities to save some office rents, right? For example, if you know he situation of Taiwan, you probably know that Kaohsiung and Pingtung are close to each other. Maybe we may close one facility, for example, the facility in Pingtung. You may also know that in the Nangang and Tamsui, they are close to each other. Maybe we may close the Tamsui facility. Maybe that's a good idea. But once you close some facilities, for example Hsinchu facility maybe. Once you do that, those customers near Hsinchu, they must be sent to Taoyuan or for example, Taichung. Then in that case the traveling distances would become larger. And then you need to somehow increase your service cost. So here comes a very natural trade off between office rent and the service cost. If you cut down some facilities, then you save office rent. But then you need to pay more service costs or traveling costs. Or if you build a lot of facilities, then service cost is low, but then you need to pay a lot of office rents. So here comes an optimization problems, specifically among all these 12 facilities. Should we keep all of them or should we cut down some of them? So that's the issue.