Garbage Collection with FOSS4G

Video in TIB AV-Portal: Garbage Collection with FOSS4G

Formal Metadata

Garbage Collection with FOSS4G
Title of Series
Part Number
Number of Parts
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Release Date

Content Metadata

Subject Area
Garbage collection is a topic for sustainable cities that are moving from picking up on individual houses to pick up garbage stored on containers. Minimizing trucks on the street, minimizing the travel times, while maximizing the number of containers that are picked up are desirable of the routes planned. This kind of problems have different types of constraints, for example, capacity constraints: limited number of trucks and each of different capacity. Some are time constraints, for example, a set of driver might have the morning shift, while some others work the night shift. Some constraints are topology based: a truck can not make a U-turn or an acute turn. This presentation you will learn the concepts behind this kind of optimization problems and how FOSS4G can facilitate finding a solution.
presentation binds effective program
scheduler time ones function energy different core organizations library multi network programming Capacity open source energy types mean bridges different website iOS variations open source software developers Capacity field number plane root Garbage Collector environmental integer structure iOS optimization projection content plane core Exponentialfunktionen Application URLs Computer animation Case function Tabulated optimization route frame library Garbage Collector
Strömungsverlauf principals point track effective scheduler map time Real Capacity sources ones break databases average certification types core Query configurable exceptions areas time multi Relation Capacity map interface software developers core databases Limit Application URLs Computer animation Case Ordering different website speech rights exceptions route variations frame results Garbage Collector
slides Intel Implementierung time directives Integrationen analysis distance part rules versions web Mathematical evaluation loops different Operationen operation video Matrix series website optimization Classes World Wide Web Consortium services interface projection Theories code databases URLs Computer animation function cost function interface versions Classes Tabulated route Matrix loops results
types different Green ones form
Biomedical Imaging demos RIP
man CAN raw root URN demos RIP complete ARM globaler Computernetze
default Computer animation demos website rights measurement
man pointers Computer animation demos 3rd browsers structure Sum of
man Computer animation networks time demos part Sum of
runtimes code graphs Gap time demos open energy usability Mathematical Case Matrix Stateful functionality abstractions library family man point traction Frequency response Ordering p-values point functionality nos Real driver students distance Approximate Theories versions periodicity evaluation Trees rights Sum of optimization bots time graphs projection code Theories driver Application Approximate Mathematical URLs Computer animation Case function family euclidean abstractions library
areas map Computer animation URN cluster
default track Computer animation
Headers Implementierung existence functionality graphs code help models Twitter pointers Computer animation Mats's patterns information optimization optimization
Headers Algorithmen Computer animation terms time interior rights part distance Application product
Headers Computer animation
there have everyone on this talk I was actually in the program does written his by the keyboard so I want to say hi to Mexico probably you what you know about this presentation and it was supposed to be a very funny presentation a song or something but I'm not funny so indicate that the different probably so what is
the what what what did you have in mind what was what was the missions and of this project so we wanted to develop an open source library to optimize the fleet of garbage collection trucks for a city in the world wide was Montevideo and it was supported should be done this for for the tools and so I have I did some some optimization project already before so I don't like to see who was contacted if it was still good British army and he was contacted if it's possible to do this is feuding and so on we found this very exciting and we said yes and then the budget was very low and we will see people in the team and so then I slowly disappear so maybe the work was done by making the and they didn't really great and I think it was a very challenging project i'm value there's every talks about sustainable cities and you have to consider the environmental impact and we try to minimize the required input of energy that waste output the pollution so we optimization is a big topic the days and especially we our topic was how to optimize the collection of waste and there's a lot of ways to to connect this household waste this industry dry waste which wastes and recycling recycle waste so that many many types I'm not from this field are not so expert in this and for garbage collection and there's uh we use something called the eagle route planning and they include planning means you have a fleet of trucks I think it was about 500 600 trucks for the city and there were a lot of content applications I think about 10 thousand locations and we should optimize the schedule and plans that good roots from which they like so actually the appear looks very simple this is a simple structure so it starts at the table it picks up containers that it goes to dump site integer returns to the poor so this is how you think is all the easy but but it's not a problem that number undermines not polynomial problem solved it works quite easy for a a small amount of locations and small amount of vehicles but when you're your fleet increases it becomes a very difficult to solve problems so and there are many variants of the API and so for example you can have a capacity of this is then called the see the European so the vehicles have a limited carrying capacity and therefore they have to be empty then you have something called the our until it's 1 big again you can do more than 1 route so you have multiple trips and another 1 another variation is Europe's time windows so a certain location has to be visited at a certain time so but in case of in our case and 1 trial should visit as should make as many trips as possible so at you start the core and then you go to pick up containers and then you go to the site and you go again and pick up containers and you go to the site and and until you're working days over and then you go to the table but we also have trucks with different
capacities so you have small ones and you pick 1 so that they are not the same they don't look the same and they also have a different driving schedule I remember they also said there's always a truck
driving to pick up the containers that will be forgotten so that that had happened certificate 1 and so in our case and yet all 3 of variations and applied so the vehicles had limited to carrying capacity obviously the American can do more than 1 route and they some of these locations also has a certain time windows we have to get about so talk all I really want something like a CBR PTW and T. maybe if that exist so capacitated including problem with time windows and with multiple trips and that's not all so unfortunately there even more restrictions for example a common a garbage truck that container could be in street market or they cannot make future so you can turn on the street was street or even bigger ones and sometimes as they stand on the right side on the other side of the street and unfortunately some garbage trucks can only pick up containers from the left so the source of all the work that more and more restrictions you you have in real world cases for example when with their municipalities and it's only possible that 1 truck picks up the containers that 1 municipality from another 1 and but they also exceptions for that sometimes also there is a relation between trucks so some ways and only picked up a certain trucks and some containers only can be only amounted to certain tracks the so it doesn't necessarily make it more complicated it's also sometimes like the municipalities it also helps you to uh already in the beginning that like that break you 10 thousand contain to containers into smaller smaller groups and there are others like access rigid restrictions like there are certain times you cannot go to market area for example then you have speed limits depending on the day and eventually even and you have to time restrictions that I mentioned already before so this is a big deal of the initial or is the not so complicated problem turns out to to be and that's really don't know really how to solve this and and 1st we we
classify the restrictions into some global restrictions like containers living with municipalities trucks busses principalities and also containers that work from fall municipalities for medical waste and we made some detailed restrictions and the limited to capacity right and left side the cup and speech so how how to solve this problem and of course there was some front from the development and the something good to us it was convenient that they wanted to use OpenStreetMap maps and on the for the application you have to select containers and you have to select trucks and so the point dump site you have to have an interface to query the database and to visualize the results like route on the map yeah schedules and handling restrictions but this was not our party and some some other company and I was working on this so we're only in charge of the of the current peace order and so we
try to solve it like this so because we we all came from the post rescue put puting background of and because trucks containers and locations were stored in a post database on top of this using the interface
with this an optimization algorithm and implementation in C + + that I did an initial solution and then run at the time and handles the restrictions and for to evaluate the rules rules you need a distance matrix and for that use the rest of decided to use was around because we thought that so fast so we can make even huge distance matrices uh no problem and so this project is not so new so it is not like the when it was but it was not that it was last year was the for last year it took quite some time so we use the mold version of also-rans somebody sees this video and then says now this has all changed and and yet that's very good but instead of calling direct PPI resource it's better to to use the C + + interface classes directly because we get better performance and it was also very very fast but all it was like things are changing so often so frequently so we were kind of stuck with this version so that web API is metastable but internally when the changes all the time and so on we also have problems the results so we get strange loops in the strange routes for example this be be made many small small distance requests and from here and went to here and then to the red 1 of which in it should be possible to make a U-turn because trucks can do that it should actually go around and we have this issue others so we have many issues with these very these micro micro distances like when you when you start at the at the middle of the street and you just go a few few also we had of course problems with bows and data as so altogether you it's hard to find out where the problem lies so we have that this was an implementation almost like that was searched and uh from that that operation is done by having separate 7 different initial solutions and optimization was done in terms of triple ordering and minimizing of the cost but the other important part of this is the cost function and then you have to break it match the series was visibility and so there's a lot of mathematical analyzes the necessary and and it's the part I don't know so well about so I before seeing something wrong from the table to the next slide
and so that's even if this is working so we'll this is like not really a beautiful Mind so it's it's just uh for what was for
debugging purposes and you can
see contain allocations for
quite a lot but with different different types of the forms of different types and in the green ones so that's and this is an
animated image so we we try to use so this is something you are
usually having interval search
you have to this best pair clean trip and and uh this is the
the initial an initial solution
you got and there was this nice animation and you keep the
developers happy and so forth
this is this is a complete
complete roots and it starts at the date was side and then
it tries to the containers and
it picks up these containers and then drive to the site which is
there and drugs by default so
this is a measure of how easy it is to see but there is the previous 1 that the right 1 and then using some some other
and some some modifications
another solution was that the blue 1 for example I will try to
show that the but the more later in the browser the so this is now also this
structure uh with 3 kids 3
trips so and is only a part of a part of this of the network so you don't see the dump sites so at 1st it makes a trip the red 1 that it makes the green 1 and then the blue
1 and this is a summary so
after the time it takes and then you
run an optimization and they're
the order change so that after this
was completed so we have we have a many ideas so without a lot of things that the budget was very low so we have many ideas that could be implemented and a lot of coders was discarded so in the beginning to learn what is really required it's not so easy to to do this from Europe Japan North America was required so can only describe meetings and so we have a lot of unused code left over and am 1st you wanted to try a new version of the legislation was around and at the beginning it was possible to upgrade this before this talk and we try to do that then also some C + + that was used there was quite quite also there better ways to to implement this and so we want to improve the function library and also we think it's good to have some open front application because the current 1 that was that is not a of so fancy and that you know we we also think that that there's some because we use for stress can we we think and we there's also value for p you butane so we already brought some some function some ideas already implemented the currently available function is the family of this point functions with large functions means and you look at the questions locations containers are not at the start of the and before wrote there usually somewhere in between and you can visit them so there's some visiting concepts like you have to access them from the left side you have to access them from the right side up and that you can also start with is within and we have some the ability to modify the graph to in implemented to intake include temporary points so you might as well start point in the middle of just for this period will be at its temporary already from a table and if you are interested in this stuff this response function is actually quite well documented in the in the documentation of the you so there's something really needed for this project and so it it also depends on which country live the left the left side the right side and the couple of lessons learned but so if you use or surrender to evaluate their adherence to a distance matrix you store your data again somewhere else and on the other side we have posed questions and we would like I think everybody would like to not use or around and just student Putin and we already think about how to do do that that we we can maybe do we not as fast as those around but may be fast enough to to do this all this could be due to and so featured in the distance matrix and there theory and the theory is that this is an NP problem and execution time grows exponentially if you have more locations and what what end there's a lot of high-level abstraction when you look at the documentation of the of problems and they're not too many restrictions and very often and that the distances are Euclidean approximation and this is not not not possible to use this for real projects because in reality and going ready you also have energy problems but the user wants to have very fast execution time that users have many restrictions like when you don't know before and that even restrictions might change from case by case by case and some of them and they given implied in whole host city looks like and what I found very important drivers of humans so you can just send them zigzags through the city so they they they also want to to to drive the in which tell them and so maybe stay on the street even if it's not the perfect other than the best solution but it's a it's 1 that is to and if we have a little time I want to open this so so that you
can see some some trucks driving and you can OK so he didn't come in and so they in this area the to each
container and empty the containers and then drive back to the to the depot to to have to dump sites to to empty the track and then go to the default the so if if
you have a similar problem so that the funding was very low so I think we have a lot of many lessons learned many things that could be done better and there already other implementations of the like graph Apollo has for example uh um of some European BOP functions but like we find their their these mathematical models and the very the really apply to reality and customers have very specific specific demands and so it's quite common for a complicated to find some generic solution that works for everyone and there's a lot of code currently even did help but it needs more work to make this like understandable for everyone I think the timers off so if somebody and and you what is so the reference to the existence of search as a as a mathematical optimization
and like hundreds of it's it's a pattern how you how you try to
find the best solution for such a problem there there others as well but it's it's a very common common practice how to how to start with an initial solution and then try to prove this by minimizing the so part you have this is what we want to this is due to the in there or ceramicist really fast so you can't do that I don't know how they so we only deliver the this
this solving so I don't know in the real application if the story distances somewhere so we only we only I don't know how the the final product looks like and this was needed at the back and or even the that the algorithm that you can keep it but if you change all the time you have to do it again but also around really super fast but the problem is that you with what why why things are wrong and I saw crazy crazy mistakes and sometimes they fixed sometimes it was always a a prominent in terms of data problem so yeah it is from the I think this is a short distances are very that is not so common place maybe also run is not the right to OK the