Having a mechanism to mathematically model the problem of the optimal allocation of parking spots within cities could bring great benefits to society. According to the International Parking Institute, about 38% of the cars circulating throughout a city are looking for available parking spots, leading to increased pollution and subsequent health problems, as well as economic losses due to wasted man-hours. In the work presented here, a new mathematical model describing the problem of the optimal allocation of parking spots is proposed, along with an evolutionary algorithm to demonstrate how this model can be used in practice. A simulated annealing algorithm was implemented to test the effectiveness of this approach. The proposed strategy will allow users to find parking more quickly and easily, as well as lead to new services for the hot-topic of smart mobility. For the definition of the problem, a real map of the city of Malaga, Spain, was used along with Sumo software to carry out the simulations. The results clearly demonstrated that the proposed mechanism is capable of minimising the global cost of parking, implying a direct benefit for users.

This work presents a metaheuristic with distributed processing that finds solutions for an optimization model of the university course timetabling problem, where collective communication and point-to-point communication are applied, which are used to generate cooperation between processes. The metaheuristic performs the optimization process with simulated annealing within each solution that each process works. The highlight of this work is presented in the algorithmic design for optimizing the problem by applying cooperative processes. In each iteration of the proposed heuristics, collective communication allows the master process to identify the process with the best solution and point-to-point communication allows the best solution to be sent to the master process so that it can be distributed to all the processes in progress in order to direct the search toward a space of solutions which is close to the best solution found at the time. This search is performed by applying simulated annealing. On the other hand, the mathematical representation of an optimization model present in the literature of the university course timing problem is performed. The results obtained in this work show that the proposed metaheuristics improves the results of other metaheuristics for all test instances. Statistical analysis shows that the proposed metaheuristic presents a different behavior from the other metaheuristics with which it is compared.

This study addresses the Capacitated Vehicle Routing Problem (CVRP) known to be NP-hard. In this problem, a set of customers with varying demands is considered. To solve the problem, routes were generated for several vehicles with identical capacity, which were responsible for delivering products to a set of geographically dispersed customers. The purpose of the problem is to minimize the total cost of all routes. This problem was solved by applying the metaheuristic Simulated Annealing (SA) and incorporating four different neighborhoods to improve the initial solution generated randomly. In the SA, a set of cooling factors is used. The best solution obtained by SA is refined by the use of Hill Climbing using a double neighborhood. The algorithm was tested with instances from the literature in order to measure its effectiveness in solution quality and execution time. We tested the approach with 106 instances from the literature and obtained the optimum in 93 instances. The average time in most instances was less than five minutes. Delivery companies can benefit from this approach. They only need to identify the depot, the clients, and the distance between locations, and this approach can be used with relative ease.

We propose an approximation algorithm for scheduling jobs with release and delivery times on a single machine with the objective to minimize the makespan. The algorithm is based on an implicit enumeration of the set of complete solutions in a search tree. By analyzing specific structural properties of the solutions created in each branch of the solution tree, a certain approximation factor of each solution from that branch is calculated. Our algorithm guarantees approximation factor $1+1/\kappa$ for a generated solution if there are $\kappa$ jobs with a specified property in that solution (typically, the longer the length of the path from the root to the node representing that solution in the solution tree, the larger the $\kappa$ value). We have carried out an extensive computational study to verify the practical performance of our algorithm and the effectiveness of the approximation factor provided by us. While our problem instances are generated randomly, we have discarded a considerable number of the instances, ones which were already solved optimally by the earlier known dominance rules. For the vast majority of the tested problem instances, within a short running time of our algorithm parameter $\kappa$ becomes sufficiently large so that the approximation factor which the algorithm guarantees becomes better than that provided by the earlier known approximation algorithms.

TheNP-hard cover printing problem addressed here consists in determining the number and composition of equal size impression grids, as well as the number of times each grid is printed, in order to fulfill the demand of different book covers at minimum total printing cost. The considered costs come from printing sheets and for composing grids. Thus, to deal with this combinatorial optimization problem we investigated two heuristics: one combines simulated annealing and linear programming techniques and the other is a hybrid of Tabu Search and an ad hoc procedure. Through intensive testing on available instances, these algorithms proved to be superior to previous approaches.