The Story Of Our Time In Israel – SUSTAINERGY Testimonial
This testimonial was written by Adam Kiss from Hungary and by Nemanja Filipovic from Serbia. This is their story of participating in the 2014 SUSTAINERGY contest, winning 1st place and the surprising road they have taken since.
In the following couple of thoughts we would like to tell you a story about creating a solution for a problem which seemed to be interesting and unique, but later turned out to be an opportunity to decrease the real world costs and environmental toll of garbage collection.
In 2014 we both had the honor to participate on the 3rd Sustainergy Youth conference and competition as the delegates from Serbia and Hungary.
Long before the Conference, the organizers mailed us the list of project themes. We both chose “Vehicle automation for energy efficiency” and were assigned with the same team. Shortly after the team assignments were out we started talking over Skype and brainstorming the ideas for the project which was in connection with the theme that we got. We both agreed that it should include a practical demonstration of the idea either in software or in hardware, but we still had no idea what would the focus of the project actually be.
The idea which we eventually chose came from a University professor from Hungary. It was about improving the fuel efficiency of garbage trucks by redesigning the collection routes. Less distance to travel means less burnt fuel. We both agreed that it was a great idea and that we would solve this problem. The only trouble was how to actually implement it. Neither of us had experience with such problems, routing or algorithms suitable for this problem type. After a lot of googling we collected some knowledge regarding the vehicle routing. It turned out a hell of a problem to solve. It is a so-called np-complete problem which means that it would take ages to solve with a traditional computer. About the age of the Universe for any practical amount of data. Eventually we realized that all is not so dark. There are so-called heuristic algorithms that give solutions close to the best ones in just a fraction of the time, so we opted for an algorithm that is inspired by the theory of evolution, called genetic algorithm.
In the beginning it generates a series of random solutions (“animals”). Each “animal” is described by a set of genes and by its fitness which determines how good of a solution it represents for the initial problem. The algorithm then selects better solutions (ones with better fitness value) to create offspring by mixing their genes together. To keep the initial population size, worse solutions have to be deleted, thus ensuring only the best “animals” can pass on their genes. For example, our program should optimize the order in which the garbage bins are collected. Genes, in our case, represent that collection order and fitness is calculated using the fuel efficiency. After several tens of thousands of generations, there should be no more significant improvements through the generations of solutions which means that we have found an animal that is close to the best one.
The next trouble that we stumbled upon was writing all of that on the computer and making it work. We chose C++ as our main programing language because of its speed. In it we wrote our main genetic algorithm. The only downside was graphics. This is the user interface at its most alluring form:
Routes were represented using a connection matrix (a table which contains information about the connected streets and their length). In order to create that connection matrix, we created a small program in the processing programming language.
Our program output data in a textual form which looked like this:
Interestingly, our early attempts to output all data resulted in some 1.1Gb txt files. (Yes, Gigabytes, not typo 🙂 )
So we also had to create a program for visualizing this data, and displaying the statistics. For the statistics we chose LabView and for the visualization we chose to use the OpenCV library. To say the least, it wasn’t user friendly, needed constant tweaking and corrections to work properly. But, in spite all of the troubles and massive amount of coding that went into the project, we found out that we actually managed to make an improvement to the route lengths and that everything was working properly. We presented our project at the Sustainergy conference and we won the first prize.
(The process, what we described was approximately 2 months of intensive work)
The next chapter in our work on the project begins just after the conference. We agreed that we should continue work and try to implement our solution in real life. Of course, it’s never easy to do so. Mainly every project that you start working on is an artificially created problem and the solution -no matter how elegant it is- only functions in a “petri dish”. When you see enough potential in your work, you have to redesign the whole idea, to be able to stand in its place in the reality.
In the earlier stage of our work we requested data from a company in the city of Kecskemet (Hungary) responsible for the garbage management. After receiving news about the prize we won they asked us if we wanted to try and create a program which they could use to optimize their collection routes. It sounded like a big challenge. After several on site meetings with the director and project management team of the company, we set up the perimeters of out work. We had to create a user friendly, standalone program. It had to read the entries from the already existing database owned by the firm, incorporate them into a map of the city automatically, do the routing, display the data on the map and print it in the form for the driver to read and use. It also needed to handle changes in the data and to make them on request. At this stage we were talking about near 30000 (!) data points.
Also, we came across other factors we haven’t thought of during out initial work for the competition. An environmental manager at the City management company told us: “Optimization is great, but you can’t ask a citizen who got used to the garbage truck coming on Friday to expect it on Tuesday.” Many problems like that came up during the meetings with the heads of the company.
We decided to take the opportunity and create the use-ready program. So we changed our programming environment to C# which handled graphics really well even though it was a bit slower. First task was finding and using a map of the city. After some research, the so-called OpenStreetMap came up, which was perfect for us. As a next task we had to connect the data from the garbage company database to the streets on the virtual map. This sparked yet another unexpected hiccup. The database what we were given was loaded with errors, at least from the computers point of view. Every country has some pretty common street names. Place can be found in almost every city having these not-at-all unique designations. Kecskemét is no exception. That means there are two “Petőfi streets” in the vicinity of the settlement. One in downtown, one in the agglomeration. Since we didn’t really have any additional information about the garbage bin’s location, just the addresses, we had to build in some new functions to solve problems like these. The added functionality to change the connection manually between addresses and the location of an entity in the map seemed to work.
For the routing part, we decided to start from scratch. Our previous algorithm was too slow and wasn’t compatible with the new data format which contained bin size, address, unique ID, etc. We added several optimizations and combined the genetic algorithm with another heuristic technique in order to improve speed. It still takes a few minutes to create a route for several thousands of bins for each day. We also wanted to add flexibility to the program, so we added a language pack handling ability, thus making the program easily translatable into any language. Some work also went into making the interface user friendly and nice looking. Currently, the program has about 10000 lines of code, but we are constantly improving based on the suggestions from the garbage company. Also an error reporting framework built in the program helps our work. If something goes wrong, we get the diagnostics directly from the client computer and we can fix it quickly and efficiently.
As of yet the solution is in use by the city management company, currently in a trial stage. They are starting to assign the new, shorter routes to the drivers. With less fuel burned by the trucks and less working hours needed by the drivers we have really created a cheaper, environmentally friendly solution for a real world problem.