Aproximación para la Mejora Local 2-p-opt del Problema del Vendedor Viajero Probabilístico
Palabras clave:
Problema del Vendedor Viajero Probabilístico, 2-p-opt, Optimización a prioriResumen
Esta investigación propone un enfoque aproximado para evaluar
los ahorros asociados a cada intercambio de la mejora local de la
heurística 2-opt aplicada al Problema del Vendedor Viajero
Probabilístico, donde los nodos que conforman el problema
presentan una probabilidad homogénea de demanda. La
aproximación de los ahorros considera un subconjunto del total de
términos necesarios para su evaluación exacta. Las soluciones
obtenidas al utilizar el enfoque aproximado en la heurística 2-opt
presentan errores pequeños en comparación a las soluciones
obtenidas por medio de la evaluación exacta. Además, se
concluye que el número de términos requeridos para que la
heurística alcance un determinado nivel de error es
asintóticamente independiente del número de nodos que
conforman la instancia del problema, reduciendo la complejidad
de la heurística.
Citas
Bertsimas, D. J. (1988) Probabilistic Combinatorial Optimization
Problems. Operations Research Center.
Bertsimas, D. J. (1993) Further Results on the Probabilistic Traveling
Salesman Problem. European Journal of Operational Research, 65, 68-95.
Bertsimas, D. J., Jaillet, P.y Odoni, A. (1990) A Priori Optimization.
Operations Research, 38, 6, 1019-1033.
Bianchi, L.y Campbell, A. M. (2007) Extension of the 2-p-opt and 1-shift
Algorithms to the Heterogeneous Probabilistic Traveling Salesman
Problem. European Journal of Operational Research, 176, 131-144.
Bianchi, L., Knowles, J.y Bowler, N. (2005) Local Search for the
Probabilistic Traveling Salesman Problem: Correction to the 2-p-opt and
-shift Algorithms. European Journal of Operational Research, 162,
-219.
Campbell, A. M. (2005) Aggregation for the probabilistic traveling
salesman problem. Computers and Operations Research.
Jaillet, P. (1985) The Probabilistic Traveling Salesman Problems.
Operations Research Center.
Jaillet, P. (1988) A Priori Solution of a Traveling Salesman Problem in
which a Random Subset of the Customers are Visited. Operations
Research, 36(6), 929-36.
Laporte, G., Louveaux, F.y Mercure, H. (1994) An exact solution for the a
priori optimization of the probabilistic traveling salesman problem.
Operations Research, 42, 3, 543-549.
Lin, S. (1965) Computer solutions of the traveling salesman problem. Bell
System Tech. J., 2245-2269.
Powell, W. B., Jaillet, P.y Odoni, A. (1995) Stochastic and Dynamic
Networks and Routing. Elsevier ScienceB. V.
Tang, H.y Miller-Hooks, E. (2005) Aproximate Procedures for the
Probabilistic Traveling Salesman Problem. Transportation Research
Record (TRR), Journal of the Transportation Research Board,1882,
-36.
