Search

International audience; Genetic Algorithms (GA) have long been used for ordering optimization problems with some considerable efforts to improve their exploration and exploitation abilities. A great number of GA implementations have been proposed varying from GAs applying simple or advanced variation operators to hybrid GAs combined with different heuristics. In this work, we propose a short review of genetic operators for ordering optimization with a classification according to the information used in the reproduction step. Crossover operators could be position ("blind") operators or heuristic operators. Mutation operators could be applied randomly or using local optimization. After studying the contribution of each class on solving two benchmark instances of the Capacitated Vehicle Routing Problem (CVRP), we explain how to combine the variation operators to allow simultaneously a better exploration of the search space with higher exploitation. We then propose the random and the balanced hybridization of the operators' classes. The hybridization strategies are applied to solve 24 CVRP benchmark instances. Results are analyzed and compared to demonstrate the role of each class of operators in the evolution process.

En la ciudad de Tunja no se cuenta con fuentes de información e indicadores exactos que establezcan la cantidad de llantas usadas y desechadas en tiraderos clandestinos, patios de casas y centros de acopio, las cuales generan impacto negativo en el medio ambiente y la salud de los habitantes, evidenciando la necesidad de generar una solución logística. Se presenta una investigación de enfoque cuantitativo de tipo estudio de caso; en esta se utilizó el método CVRP, que consiste en el diseño de un conjunto de rutas de menor coste, donde cada cliente se visite una única vez por un único vehículo y todas las rutas comienzan y finalizan en un centro de gravedad. Como resultados se logró la caracterización y diseño de un modelo logístico, que integró la ubicación de punto de acopio, demanda, rutas de recolección, capacidades, como herramienta sólida y actualizada que generara alternativas ambientales para la ciudad.

The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that has been of great interest for decades for both, science and industry. The CVRP is a variant of the vehicle routing problem characterized by capacity constrained vehicles. The aim is to plan tours for vehicles to supply a given number of customers as efficiently as possible. The problem is the combinatorial explosion of possible solutions, which increases superexponentially with the number of customers. Classical solutions provide good approximations to the globally optimal solution. D-Wave's quantum annealer is a machine designed to solve optimization problems. This machine uses quantum effects to speed up computation time compared to classic computers. The problem on solving the CVRP on the quantum annealer is the particular formulation of the optimization problem. For this, it has to be mapped onto a quadratic unconstrained binary optimization (QUBO) problem. Complex optimization problems such as the CVRP can be translated to smaller subproblems and thus enable a sequential solution of the partitioned problem. This work presents a quantum-classic hybrid solution method for the CVRP. It clarifies whether the implementation of such a method pays off in comparison to existing classical solution methods regarding computation time and solution quality. Several approaches to solving the CVRP are elaborated, the arising problems are discussed, and the results are evaluated in terms of solution quality and computation time.

Along this paper, we present a new multi agent-based system to gather waste on cities and villages. We have developed a low cost wireless sensor prototype to measure the volume level of the containers. Furthermore a route system is developed to optimize the routes of the trucks and a mobile application has been developed to help drivers in their working days. In order to evaluate and validate the proposed system a practical case study in a real city environment is modeled using open data available and with the purpose of identifying limitations of the system.

The capacitated vehicle routing problem (CVRP) is one of the most challenging problems in the optimization of distribution. Most approaches can solve case studies involving less than 100 nodes to optimality, but time-consuming. To overcome the limitation, this paper presents a novel two-phase heuristic approach for the capacitated vehicle routing problem. Phase I aims to identifying sets of cost-effective feasible clusters through an improved density-based clustering algorithm. Phase II assigns clusters to vehicles and sequences them on each tour. Max-min ant system is used to order nodes within clusters. The simulation results indicate efficiency of the proposed algorithm.

Many optimization problems require heuristic methods to solve the problem. Variable Neighborhood Search (VNS) is a metaheuristic form that systematically changes its “neighborhood” in search of solutions. One method in VNS is Variable Neighborhood Descent (VND), which performs a deterministic neighborhood change. The change of the neighborhood in VND can be done in a random and sequential order. This paper compares sequential and random neighborhood selection methods in solving Capacitated Vehicle Routing Problem (CVRP) problems. There are 6 intra-route neighborhood structures and 4 inter-route structures used. CVRP problems are taken from several dataset providers. The initial solution is formed by Sequential Insertion method. The experimental results show that the random selection of neighborhood operators can provide a more optimal route length (in 10 of 13 datasets used) than that of sequential selection (only better in 3 dataset). However, the random selection takes more iterations to reach convergent state than the sequential one. For sequential selection, determination of the neighborhood structure’s order affects the speed to the convergent state. Hence, a random selection in VND method is more preferable than sequential selection.

New solutions for managing waste have emerged due to the rise of Smart Cities and the Internet of Things. These solutions can also be applied in rural environments, but they require the deployment of a low cost and low consumption sensor network which can be used by different applications. Wireless technologies such as LoRa and low consumption microcontrollers, such as the SAM L21 family make the implementation and deployment of this kind of sensor network possible. This paper introduces a waste monitoring and management platform used in rural environments. A prototype of a low consumption wireless node is developed to obtain measurements of the weight, filling volume and temperature of a waste container. This monitoring allows the progressive filling data of every town container to be gathered and analysed as well as creating alerts in case of incidence. The platform features a module for optimising waste collection routes. This module dynamically generates routes from data obtained through the deployed nodes to save energy, time and consequently, costs. It also features a mobile application for the collection fleet which guides every driver through the best route—previously calculated for each journey. This paper presents a case study performed in the region of Salamanca to evaluate the efficiency and the viability of the system’s implementation. Data used for this case study come from open data sources, the report of the Castilla y León waste management plan and data from public tender procedures in the region of Salamanca. The results of the case study show a developed node with a great lifetime of operation, a large coverage with small deployment of antennas in the region, and a route optimization system which uses weight and volume measured by the node, and provides savings in cost, time and workforce compared to a static collection route approach.

The Capacitated Vehicle Routing Problem (CVRP) is a well known optimization problem applied in numerous applications. It consists of delivering items to some geographically dispersed customers using a set of vehicles operating from a single depot. As the CVRP is known to be NP -hard, approximate methods perform well when generating promising sub-optimal solutions in a reasonable computation time. In this paper, we develop a Decision Support System (DSS) for solving the CVRP that integrates a Geographical Information System (GIS) enriched by a Tabu search (TS) module. In order to demonstrate the performance of the proposed DSS in terms of CPU runtime and minimized traveled distance, we apply it on a large-sized real case. The results are then highlighted in a cartographic format using Google Maps.

Efficient vehicle routing is a major concern for any supply chain, especially when dealing with last-mile deliveries in highly urbanized areas. In this paper problems considering last-mile delivery in areas with the restrictions of motorized traffic are described and different types of cargo bikes are reviewed. The paper describes methods developed in order to solve a combination of problems for cargo bicycle logistics, including efficient packing, routing and load-dependent speed constraints. Proposed models apply mathematical descriptions of problems, including the Knapsack Problem, Traveling Salesman Problem and Traveling Thief Problem. Based on synthetically generated data, we study the efficiency of the proposed algorithms. Models described in this paper are implemented in Python programming language and will be further developed and used for solving the problems of electric cargo bikes’ routing under real-world conditions.