## 4 GPS Application for Garbage Trucks Modeled as a Travelling Salesman Problem
### Our Approach  
In this paper, we describe a system offering a solution to the problem of garbage truck routing management. It is based on quantum-inspired metaheuristics applied on TSP and integrated to GIS/GPS technologies. Our approach is an integrated waste management solution. Based on the functional requirements and some case studies, [40], the components of our application are designed and decomposed into subsystems and smaller functional units. Operations and relationships between subsystems are defined for each subsystem:  
* Bin Sensors: equipment that estimates the waste bin fill level and collects, stores, and transmits bins data. This will help our main system to take into account specific bins and avoid computation on final route empty bins. * Data Gathering from Bins: a unit that communicates with the bin sensors and delivers the collected information to the central system. It can be installed on passing vehicles and consists of three components: 1. a communicator, which implements the communication with the bin; 2. a storage procedure, which temporarily stores the data until transferred to the central system; 3. a transfer procedure, which implements the data transfer to the central system. All these operations will be applied via the Global System for Mobile Communications (GSM) network. * GPS Navigation Applications Integrated in Trucks: a classic navigation application through GPS and will provide navigation guidance to a truck driver and instructions regarding which bins should be collected. * A Central System: the back-end system of our application. Its main part is the data storing, bin data, vehicle data, and all data needed to compute the most efficient routes. Furthermore, data storing will keep any information retrieved from other subsystems, particularly from the data mining subsystem and the routing optimizations subsystem. All generated spatial information for the current route will be stored locally in a spatial database. * A Map Substructure: A REST-ful API based on maps that will provide all the required functionality for creating rich-web applications based on geographic and descriptive data. * A Data Mining Subsystem: a system mainly used to estimate the fullness of bins when we do not have the available information updated. * A Routing Optimization Structure: Our main contribution is mainly based on implementing efficient routing algorithms for this application. We propose this novel metaheuristic, which provides optimal or close to optimal solutions over a short period of time. Our implementation of routing functionality gives an overall comparative advantage compared with the other implementations for two main reasons: 1. We can compute efficient solutions in a short period of time. This makes the application efficient because we can compute and re-compute, live and continuously, many times for the same route and feed the results to the application. 2. Our routing algorithm outperforms classic methods, such as the NN, that are used to find routes on GPS, and the solutions for every class of problem are near-optimal. A real-time system like ours must be able to give prompt replies to such queries because, in these situations, the response time is of vital importance. By using efficient local search structures and the novel GVNS for the problem tour, the metaheuristic algorithm can provide better results. Most GIS/GPS implementations use either the NN or one of its variations to compute routes. NN is a well known and widely used construction heuristic in network designing problems. Initially, in NN, an arbitrary node is inserted in the route as the starting node, and then, iteratively, the nearest to the last added node, selected to insert in the route. The procedure is terminated when all the nodes have been added in the route. Therefore, because of the popularity of NN, when we test the performance of our algorithm, we compare its results both with the optimal solution and the solutions achieved by NN.