Grid Platform Applied to the Vehicle Routing Problem with Time Windows for the Distribution of Products

Introduction

The problems of resource assignment based on scheduling are well-known combinatorial problems in the computer science research community. Complexity theory classifies them as a very difficult set of problems to solve; they are the NP-complete problems (Garey & Johnson, 1979). This complexity is due to the combinatorial feature of these problems to handle only discrete variables in their formulation, and because the number of solutions to the problem grows exponentially with increasing size of the instance to solve. At times, the instance of a problem containing a small number of variables is an unknown solution; we have only knowledge of an upper or lower bound close to the solution. This behavior occurs in scheduling problems, for example, in transportation problems with time windows for 1000 clients, as proposed by Homberger and Gehring (1999), there is currently no known solution due to the hardness of this problem (NP-complete), as mentioned by Toth and Vigo (2001). For this type of symmetrical transport problems, the solution space size is bound as ((1+n/r)!)^r, much like a multiple traveling salesman problem as presented by Mitrovic-Minic and Krishnamurti (2006), where n is the number of customers that need attention and r indicates the number of paths that must be traveled, the symmetry indicates that there are the same number of customers per path.

Due to the hardness of solving problems of resource assignment, it is necessary use nondeterministic Meta heuristics to bind in polynomial time the search for the best possible solution with good performance in both efficacy and efficiency for the algorithm. For this reason, the scientific community has worked to improve the performance of Meta heuristics in several ways. For example, one way is the hybridization of two or more methods, one of which is an exact method, thereby taking advantage of the best features of each. Another way to improve the performance of the Meta heuristic is to improve the neighborhood structure for local search, because several of these methods work with iterated local search, as suggested in Hansen and Mladenovic (2001) and Cruz-Chavez et al. (2010). Another way is the partial or total parallelization of the algorithm. All these alternatives have been successful, resulting in the improvement of the upper/lower bounds of solutions for unsolved instances. The main Meta heuristics that have been applied to VRPTW are genetic algorithms, used to solve constraint satisfaction models, ant colony and simulated annealing.

The industry needs a transport to distribute their products and the savings achieved through the efficient scheduling of distribution paths. This in turn could lead to a decrease in transportation costs, resulting in a substantial savings for the company, making it more competitive nationally and/or internationally, due to decreased price for the same product quality. Good resource assignment will result in savings in several ways: less gasoline, fewer transport units and therefore savings in depreciation of the units, fewer expenses in payment to drivers who have a smaller number of paths to meet (every driver completes their daily work in a single path). In this type of resource assignment, good use of the storage capacity of the units is also involved. Better use of the transport units’ space and a better selection of merchandise to be transported lead to the transportation optimum.