Un método de programación mixta entera para un problema de transportación de movimiento continuo con restricciones de servicio
DOI:
https://doi.org/10.29105/rinn7.13-2Palabras clave:
Algoritmos Genéticos, Logística de Ruteo, Metahurística, Programación, Ventana de HorarioResumen
En la solución de problemas combinatorios, es importante evaluar el costobeneficio entre la obtención de soluciones de alta calidad en detrimento de los recursos computacionales requeridos. El problema planteado es para el ruteo de un vehículo con entrega y recolección de producto y con restricciones de ventana de horario. En la práctica, dicho problema requiere ser atendido con instancias de gran escala (nodos ≥100). Existe un fuerte porcentaje de ventanas de horario activas (≥90%) y con factores de amplitud ≥75%. El problema es NP-hard y por tal motivo la aplicación de un método de solución exacta para resolverlo en la práctica, está limitado por el tiempo requerido para la actividad de ruteo. Se propone un algoritmo genético especializado, el cual ofrece soluciones de buena calidad (% de optimalidad aceptables) y en tiempos de ejecución computacional que hacen útil su aplicación en la práctica de la logística. Para comprobar la eficacia de la propuesta algorítmica se desarrolla un diseño experimental el cual hará uso de las soluciones óptimas obtenidas mediante un algoritmo de ramificación y corte sin límite de tiempo. Los resultados son favorables.
Descargas
Métricas
Citas
Applegate, D; Bixby, R; Chvátal, V. (1998). On the solution of traveling salesman problems, Documenta Mathematica Extra Volume ICM III, USA.
Ascheuer, N; Fischetti, M; Grotschel, M. (2001). Solving ATSP with time windows by branchand-cut, Springer-Verlag, Germany.
Cook, W; Rich, Jennifer. (1999). A parallel cutting-plane algorithm for the vehicle routing problem with time windows, Computational and Applied Mathematics Rice University, Houston USA.
Cordeau, J.-F., Laporte, G., Savelsbergh, M.W.P., Vigo, D. (2007). “Vehicle Routing", Transportation, Handbooks in Operations Research and Management Science,
Volume 14, C. Barnhart and G. Laporte (eds), Elsevier, Amsterdam, 367-428.
Dumas, Y., Desrosiers, J. & Soumis, F.(1991). The pickup and delivery problem with time windows. European Journal of Operational Research, 54, 7-22.
Dumas, Y; Desrosiers, J; Solomon, M. (1995). An algorithm for the traveling salesman problem with time windows, Operations Research 43(2), USA, pp. 23-25.
Desrosiers, J., Dumas, Y., Solomon, M.M., & Soumis, F. (1995). Time constrained routing and scheduling. In: M.O. Ball, T.L. Magnanti, C.L. Monma, & G.L. Nemhauser (eds.), Network
Routing, Handbooks in Operations Research and Management Science, vol. 8 (pp. 35-139). INFORMS: Elsevier Science.
Dessouky, Lu, Zhao, Leachman. (2006). "An Exact Solution Procedure for Determining the Optimal Dispatching Times for Complex Rail Networks," IIE Transactions 38, 141-152.
Fisher, R. (1995). The Design of Experiments, Hafner Press & Macmillan Publishers, London England, pp. 25-50.
Mitrovic, Snezana. (1998). Pickup and Delivery Problem with Time Windows, Technical Report SFU CMPT TR 1998-12, Canada, pp 38-39.
Palmgren, Myrna. (2001). A Column Generation Algorithm for the Log Truck Scheduling Problem, Department of Science and Technology (ITN), Linköping University, Norrköping Sweden, pp 3.
Ropke, S., Cordeau, J.-F., Laporte, G. (2007). "Models and a Branch-and-Cut Algorithm for Pickup and Delivery Problems with
Time Windows", Networks 49, 258-272.
Savelsberg, M. (1995). Local search in Routing Problem with Time Windows, Annals of Operations Research, Rotherdam, the Netherlands, pp. 1-7.
Savelsbergh, Sol, M. (1995). The general pickup and delivery problem. Transportation Science, 29(1), 17-29.
Savelsbergh, M.W.P. & Sol, M.(1998). DRIVE: Dynamic routing of independent vehicles. Operations Research, 46(4), 474-490.
Solomon, M. (1984). On the worst-case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints, Report 83-05-03, The Wharton School, USA.
Tsitsiklis, J. (1992). Special cases of traveling salesman and repairman problems with time windows, Networks No. 22, US
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2017 Innovaciones de Negocios
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
La revista InnOvaciOnes de NegOciOs es sin fines de lucro y es una publicación de la Universidad Autónoma de Nuevo León en donde los autores ceden libremente los derechos sobre las obras que someten a evaluación y potencialmente a publicación.
Para efectos legales cada autor deberá llenar un formato para ceder los derechos a favor de la Universidad Autónoma de Nuevo León, en particular para la revista InnOvaciOnes de NegOciOs.
Para mayor información favor de comunicar a la Secretaria de Investigación de Facpya de la Universidad Autónoma de Nuevo León, o bien consultar alguno de las siguientes páginas Web:
Universidad Autónoma de Nuevo León/ Dirección de Investigación:
Página web: http://www.uanl.mx/universidad/investigacion/investigacion.html
