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

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

Marco Antonio Cruz-Chávez (Autonomous University of Morelos State, CIICAp, Mexico), Abelardo Rodríguez-León (Technological Institute of Veracruz, Mexico), Rafael Rivera-López (Technological Institute of Veracruz, Mexico), Fredy Juárez-Pérez (Autonomous University of Morelos State, CIICAp, Mexico), Carmen Peralta-Abarca (Autonomous University of Morelos State, FCQeI, Mexico) and Alina Martínez-Oropeza (Autonomous University of Morelos State, CIICAp, Mexico)
DOI: 10.4018/978-1-4666-0297-7.ch003


Around the world there have recently been new and more powerful computing platforms created that can be used to work with computer science problems. Some of these problems that are dealt with are real problems of the industry; most are classified by complexity theory as hard problems. One such problem is the vehicle routing problem with time windows (VRPTW). The computational Grid is a platform which has recently ventured into the treatment of hard problems to find the best solution for these. This chapter presents a genetic algorithm for the vehicle routing problem with time windows. The algorithm iteratively applies a mutation operator, first of the intelligent type and second of the restricting type. The algorithm takes advantage of Grid computing to increase the exploration and exploitation of the solution space of the problem. The Grid performance is analyzed for a genetic algorithm and a measurement of the latencies that affect the algorithm is studied. The convenience of applying this new computing platform to the execution of algorithms specially designed for Grid computing is presented.
Chapter Preview


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.

Complete Chapter List

Search this Book: