Article
Construction of an Optimal Solution for a Real-World Routing-Scheduling-Loading Problem
Fecha
2010-04-14Registro en:
Revista Computación y Sistemas; Vol. 13 No.4
1405-5546
Autor
González Barbosa, Juan Javier
Delgado Orta, José Francisco
Fraire Huacuja, Héctor Joaquín
Martínez Flores, José Antonio
Morales Rodríguez, María Lucila
Institución
Resumen
Abstract. This work presents an exact method for the Routing-Loading-Scheduling Problem (RoSLoP). The objective of RoSLoP consists of optimizing the delivery process of bottled products in a company study case. RoSLoP, formulated through the well-known Vehicle Routing Problem (VRP), has been solved as a rich VRP variant through approximate methods. The exact method uses a linear transformation function, which allows the reduction of the complexity of the problem to an integer programming problem. The optimal solution to this method establishes metrics of performance for approximate methods, which reach an efficiency of 100% in distance traveled and 75% in vehicles used, objectives of VRP. The transformation function reduces the computation time from 55 to four seconds. These results demonstrate the advantages of the modeling mathematical to reduce the dimensionality of problems NP-hard, which permits to obtain an optimal solution of RoSLoP. This modeling can be applied to get optimal solutions for real-world problems.