Análisis comparativo de una metaheurística en base a algoritmo genético vs un método de ramificación y corte para un caso de entrega y recolección con restricciones de ventana de horario

Jesús Fabián López Pérez

doi:10.29105/rinn1.2-4

Authors

Jesús Fabián López Pérez Autonomous University of Nuevo León

DOI:

https://doi.org/10.29105/rinn1.2-4

Keywords:

Genetic Algorithms, Routing Logistics, Metaheuristics, Scheduling

Abstract

In an attempt to sovle the combinatorics problems, it is important to evaluate the costbenefit ratio between obtaining solutions of high quality and the loss of the computational resources required. The problem presented is for the routing of a vehicle with pickup and delivery of products with time window constraints. This problem requires instances of great scale (nodes≥100). A strong active time window percentage exists (≥90%) with factors of amplitude ≥75%. The problem is NP-hard and hence, the application of an exact method of solution, is limited by the time frame required for routing activity. A specialized genetic algorithm is proposed, which offers solutions of high precision and in computational times that makes its practical application useful. An experimental design is developed with good results that makes use of optimum solutions obtained by means of branch and cut algorithm without time limit.

Downloads

Download data is not yet available.

References

Applegate, D., R. Bixby & V. Chvátal. 1998. On the solution of traveling salesman problems. Documenta Mathematica Extr. jrositasm@yahoo.com Vol. ICM III”: 45-56.

Ascheuer, N., M. Fischetti & M. Grotschel. 2001. Solving ATSP With Time Windows by Branchand-Cut. Springer-Verlag, Alemania.

Ascheuer, N., M. Jünger & G. Reinelt. 2000. A branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints. Computational Optimization and

Applications, 17(1): 2-7.

Cook, W. & J. Rich. 1999. A parallel cutting-plane algorithm for the vehicle routing problem with time windows, Computational and Applied Mathematics, p: 5.

Dumas, Y., J. Desrosiers & M. Solomon. 1995. An algorithm for the traveling salesman problem with time windows. Operations Research, 43(2): 23-25.

Eijl Van, C. 1995. A polyhedral approach to the delivery man problem, Technical Report 95–19.

Department of Mathematics and Computer Science, Eindhoven University of Technology, The Neatherlands, pp. 12-14.

Fisher, R. 1971. The Design of Experiments, Hafner Press & Macmillan Publishers, London.

Goldberg, D. 1995. Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley Pub Co, University of Massachusetts.

Lenstra, K. 1990. A Variable Depth Approach for the Single-Vehicle Pickup and Delivery Problem with Time Windows, “COSOR No. 90-48”, Eindhoven University of Technology.

López, F. 2004. Aplicación de un AG para un problema de logística de ruteo. Tesis Doctoral. FAPYA, UANL.

Mitrovic, S. 1998. Pickup and Delivery Problem with Time Windows. Technical Report SFU CMPT TR 1998-12. Toronto.

Palmgren, M. 2001. A Column Generation Algorithm for the Log Truck Scheduling Problem. Department of Science and Technology (ITN), Linköping University. Norrköping.

Savelsberg, M. 1995. Local Search in Routing Problem with Time Windows. Annals of Operations Research. Rotherdam.

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, Colombus.

Tsitsiklis, J. 1992. Special cases of traveling salesman and repairman problems with time windows. Networks No. 22. Detroit.