Loading...
Please wait, while we are loading the content...
Algoritmos de colonia de hormigas para el problema del viajante de comercio por familias y para el problema de ruteo de vehículos por familias
| Content Provider | Semantic Scholar |
|---|---|
| Author | Soifer, Alexis Loiseau, Irene |
| Copyright Year | 2015 |
| Abstract | El problema básico de ruteo de veh́ıculos (VRP) consiste en determinar un conjunto de rutas para que una flota de veh́ıculos atienda a un conjunto de clientes a un costo mı́nimo. Estos problemas se encuentran dentro de los problemas de optimización combinatoria económicamente más importantes dado que el costo de transporte es una parte importante del costo final de los productos. El problema puede tener varios tipos de restricciones adicionales, como limitación en las capacidades de los camiones, en la cantidad y tipo de veh́ıculos disponibles, en la longitud de los recorridos, en los horarios de trabajo de los choferes, horarios en que los clientes deben ser servidos, etc. La mayoŕıa de los problemas de ruteo que aparecen en la práctica pertenecen a la clase NP-Hard. El conocido problema del viajante de comercio (TSP) puede considerarse como un caso particular de los problemas de ruteo. En nuestro caso abordamos el problema de Ruteo de Veh́ıculos por Familias (FVRP). En este caso los clientes están agrupados en clusters y se debe elegir un subconjunto de k clientes de cada cluster para ser visitado. En el caso en que haya que visitar uno solo de estos clientes se lo conoce como problema de ruteo de veh́ıculos generalizado (GVRP). El FVRP es una extensión del FTSP (Family Taveling Salesman Problem). Una aplicación motivadora del FTSP que aparece en la literatura es el problema de recoger pedidos de distintos productos en depósitos, en los cuales productos similares pueden estar guardados en espacios separados. En este trabajo desarrollamos tanto para el FVRP como para el FTSP una variante de la metaheuŕıstica Colonia de Hormigas (Ant Colony) basada en el sistema de la mejor-peor hormiga (SMPH). Los resultados obtenidos se compararon favorablemente con resultados de la literatura en el caso del FVRP y del GVRP. Superaron en muchos casos a los obtenidos por otras heuŕısticas (BRKGA, GRASP) sobretodo en problemas medianos o grandes. No hemos encontrado referencias de trabajos que aborden el FVRP por lo que se realizaron algunos experimentos preliminares en nuevas instancias definidas a partir de las instancias del FTSP. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://44jaiio.sadio.org.ar/sites/default/files/sio11-11.pdf |
| Alternate Webpage(s) | http://www.dc.uba.ar/inv/tesis/licenciatura/2015/soifer.pdf |
| Alternate Webpage(s) | http://sedici.unlp.edu.ar/bitstream/handle/10915/59301/Resumen.pdf-PDFA.pdf?isAllowed=y&sequence=1 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
