Algoritmo de busca dispersa aplicado ao problema clássico de roteamento de veículos
| Autor: | Roberto D. Galvão, Nélida Gladys Maquera Sosa, Dan Abensur Gandelman |
|---|---|
| Jazyk: | portugalština |
| Rok vydání: | 2007 |
| Předmět: |
Mathematical optimization
lcsh:Mathematics meta-heurísticas Construct (python library) Management Science and Operations Research lcsh:QA1-939 scatter search problema de roteamento de veículos meta-heuristics Search algorithm Vehicle routing problem vehicle routing problem Beam search Routing (electronic design automation) busca dispersa Mathematics |
| Zdroj: | Pesquisa Operacional v.27 n.2 2007 Pesquisa operacional Sociedade Brasileira de Pesquisa Operacional (SOBRAPO) instacron:SOBRAPO Pesquisa Operacional, Vol 27, Iss 2, Pp 293-310 (2007) Pesquisa Operacional, Volume: 27, Issue: 2, Pages: 293-310, Published: AUG 2007 |
| Popis: | Neste artigo apresentamos heurísticas usando o conceito da meta-heurística Busca Dispersa (BD), desenvolvidas para a solução do Problema de Roteamento de Veículos (PRV) Clássico, detalhando cada uma de suas etapas básicas quando aplicadas ao problema em questão. A Busca Dispersa é um método evolutivo que combina soluções com a finalidade de criar novas soluções de melhor qualidade; ainda que apresente similaridades com os algoritmos genéticos difere dos mesmos em princípios fundamentais. Um aspecto importante da BD é formar soluções com alta qualidade para dirigir a busca a regiões promissoras. Experimentos computacionais foram realizados em quatro conjuntos de dados disponíveis na literatura. Os resultados mostram que a BD é robusta e competitiva em termos de qualidade das soluções obtidas e tempo computacional para o PRV Clássico, para os conjuntos de dados testados.In this paper we present a Scatter Search algorithm designed for the solution of the Classical Vehicle Routing Problem, giving details of each of its basic phases when applied to the routing problem. Scatter Search is an evolutionary meta-heuristic that combines solutions with the objective of obtaining new solutions of higher quality; even though there are similarities between Scatter Search and Genetic Algorithms, the two methods differ in basic principles. An important aspect of Scatter Search is to construct high quality solutions in order to direct the search to promising regions. Computational experiments were conducted using four data sets available in the literature. The results show that Scatter Search is robust and competitive in terms of both the quality of solutions and computational times, for the VRP data sets we used. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|