Un método de programación mixta entera para un problema de transportación de movimiento continuo con restricciones de servicio

J. Fabián López

doi:10.29105/rinn7.13-2

Autores/as

J. Fabián López Universidad Autónoma de Nuevo León

DOI:

https://doi.org/10.29105/rinn7.13-2

Palabras clave:

Algoritmos Genéticos, Logística de Ruteo, Metahurística, Programación, Ventana de Horario

Resumen

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

Los datos de descargas todavía no están disponibles.

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