Loading...
Please wait, while we are loading the content...
Metaheurísticas para el problema de ruteo de vehículos con ventanas de tiempo (VRP-TW)
| Content Provider | Semantic Scholar |
|---|---|
| Author | Orozco, Edwin Montes |
| Copyright Year | 2017 |
| Abstract | Metaheuristics for the vehicle routing problem with time windows (VRP-TW) In this work, 7 techniques based on four metaheuristics and two exact methods are presented, which are: Ant System (AS), Harmonic Search (HS), Genetic Algorithm (GA), Iterated Local Search (ILS), Primal-Dual Algorithm (PDA) and Dual Simplex Method (DSM) to solve the vehicle routing problem with time windows (VRP-TW), emphasizing the hybrid algorithms between these techniques, which are called AS-GA, AS-HS and DSM-AS-PDA; where, with the exception of DSM-AS-PDA, these work in an interlaced way. In order to analyze and characterize the behavior of the developed techniques, used a set of test instances for the VRP-TW. In AS-GA, the GA is used to find a better solution with the population generated by one cycle of n ants within AS, with which the level of the pheromone matrix for the next cycle of ants is updated. With this it is possible to guide the construction of a more effective way, and the GA helps to avoid the premature converge way, but due to the codification it diversifies the space of search. Within AS-HS, the HS technique is used to guide the behavior of AS through the changes in the pheromone matrix, since it takes advantage of the information of m executions of the HS stored in the harmonic memory (HM). In the proposed procedure, the best solutions for the updating of the pheromone level are taken up. Finally, in DSM-AS-PDA is used the optimizer called Gurobi executing the dual simplex method to solve two linear relaxations of the original problem. With the solutions returned by Gurobi the pheromone level for AS are initialized and once the execution of AS is terminated, based on the best solution delivered, the PDA is used to check if this solution is optimal. The results show that the hybrid algorithms developed have a more robust behavior than the techniques reported in the literature and, are able to generate better solutions with a smaller number of calls to the objective function in large instances using less computational resources. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://zaloamati.azc.uam.mx/bitstream/handle/11191/5699/Metaheuristicas_problema_de_ruteo_de_vehiculos_2017_Montes_MOPT.pdf?isAllowed=y&sequence=1 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
