Garbage Collection with FOSS4G
Formal Metadata
Title 
Garbage Collection with FOSS4G

Title of Series  
Part Number 
53

Number of Parts 
193

Author 

License 
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. 
Identifiers 

Publisher 

Release Date 
2016

Language 
English

Content Metadata
Subject Area  
Abstract 
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 Uturn 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.

Related Material
00:00
Presentation of a group
Scheduling (computing)
Open source
Software developer
Multiplication sign
Channel capacity
Function (mathematics)
Food energy
Field (computer science)
Computer programming
Number
Planning
Root
Speicherbereinigung
Integrated development environment
Integer
Data structure
output
Organic computing
Library (computing)
Multiplication
Mathematical optimization
Broadcast programming
Channel capacity
Keyboard shortcut
Projective plane
Open source
Content (media)
Planning
Food energy
Exponential function
Group action
Cartesian coordinate system
Type theory
Uniform resource locator
Arithmetic mean
Computer animation
Personal digital assistant
Function (mathematics)
Bridging (networking)
output
Table (information)
Mathematical optimization
Routing
Bounded variation
Window
Library (computing)
Speicherbereinigung
04:02
Computer animation
Personal digital assistant
Different (Kate Ryan album)
Core dump
Different (Kate Ryan album)
Website
Core dump
Table (information)
Speicherbereinigung
04:28
Trail
Scheduling (computing)
Group action
Real number
Multiplication sign
Channel capacity
Source code
1 (number)
Control flow
Average
Public key certificate
Type theory
Different (Kate Ryan album)
Exception handling
Area
Multiplication sign
Multiplication
Theory of relativity
Channel capacity
Core dump
Limit (category theory)
Uniform resource locator
Computer animation
Personal digital assistant
Different (Kate Ryan album)
Exception handling
Routing
Bounded variation
Window
Speicherbereinigung
07:14
Ocean current
Principal ideal
Point (geometry)
Intel
Scheduling (computing)
Mapping
Channel capacity
Database
Performance appraisal
Core dump
Query language
Configuration space
Mapping
Channel capacity
Interface (computing)
Software developer
Core dump
Database
Cartesian coordinate system
Uniform resource locator
Computer animation
Order (biology)
Interface (computing)
Website
Speech synthesis
Right angle
Routing
Resultant
08:45
Slide rule
Implementation
Multiplication sign
Direction (geometry)
Disintegration
1 (number)
Mathematical analysis
Mereology
Distance
Rule of inference
Revision control
Web 2.0
Mathematics
Performance appraisal
Programmschleife
Different (Kate Ryan album)
Military operation
Operator (mathematics)
Green's function
Matrix (mathematics)
Videoconferencing
Series (mathematics)
Website
Mathematical optimization
Social class
Form (programming)
World Wide Web Consortium
Service (economics)
Interface (computing)
Projective plane
Memory management
Theory
Code
Type theory
Computer animation
Function (mathematics)
Cost curve
Interface (computing)
Revision control
Social class
Table (information)
Routing
Matrix (mathematics)
Programmschleife
Resultant
11:54
Medical imaging
Demo (music)
Ripping
12:18
Metropolitan area network
CAN bus
Default (computer science)
Raw image format
Root
Uniform resource name
Demo (music)
Website
Complete metric space
Arm
Wide area network
12:39
Metropolitan area network
Computer animation
Demo (music)
3 (number)
Right angle
Web browser
Measurement
13:11
Metropolitan area network
Pointer (computer programming)
Computer animation
Software
Demo (music)
Data structure
Mereology
Summierbarkeit
13:30
Metropolitan area network
Code
Network operating system
Multiplication sign
Demo (music)
Code
Open set
Cartesian coordinate system
Usability
Revision control
Mathematics
Computer animation
Function (mathematics)
Order (biology)
Summierbarkeit
Library (computing)
Mathematical optimization
Library (computing)
14:47
Point (geometry)
Functional (mathematics)
Run time (program lifecycle phase)
Graph (mathematics)
Mountain pass
Real number
Multiplication sign
Device driver
Student's ttest
Distance
Approximation
Food energy
Theory
Frequency
Performance appraisal
Personal digital assistant
Zustandsgröße
Matrix (mathematics)
Right angle
Abstraction
Family
Robot
Multiplication sign
Graph (mathematics)
Point (geometry)
Projective plane
Stress (mechanics)
Theory
Device driver
Approximation
Frequency response
Mathematics
Uniform resource locator
Computer animation
Personal digital assistant
Function (mathematics)
Family
Pvalue
Euklidischer Raum
Abstraction
18:00
Computer animation
Network topology
Computer cluster
18:30
Area
Default (computer science)
Trail
Mapping
Computer animation
Uniform resource name
19:14
Email
Functional (mathematics)
Existence
Implementation
Graph (mathematics)
Code
Online help
Mathematical model
Twitter
Pointer (computer programming)
Computer animation
Moving average
Mathematical optimization
Mathematical optimization
20:34
Email
Computer animation
Interior (topology)
Pattern language
Information
Mereology
Mathematical optimization
21:31
Email
Algorithm
Computer animation
Term (mathematics)
Multiplication sign
Right angle
Cartesian coordinate system
Distance
Product (business)
22:32
Computer animation
00:11
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
04:05
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
04:27
also have trucks with different
04:28
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
04:41
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
07:17
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
08:30
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
08:45
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 alsorans 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 Uturn 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
11:41
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
11:59
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
12:11
the initial an initial solution you got and there was this nice animation and you keep the
12:19
developers happy and so forth
12:24
this is this is a complete
12:25
complete roots and it starts at the date was side and then
12:29
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
12:45
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
12:54
and some some modifications
12:56
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
13:11
structure uh with 3 kids 3
13:13
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
13:26
1 and this is a summary so
13:31
after the time it takes and then you
13:36
run an optimization and they're
13:39
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
14:51
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
16:01
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 highlevel 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
18:13
can see some some trucks driving and you can OK so he didn't come in
18:38
and so they in this area the to each
18:42
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
19:26
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
20:35
and like hundreds of it's it's a
20:40
pattern how you how you try to
20:44
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
21:32
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