CONICET | Buscador de Institutos y Recursos Humanos

Logistics and especially the physical transportation of goods, lie at the heart of nowadays business activities. The importance of pick-up/distribution management has motivated intense theoretical work and the development of a variety of models and algorithms. In particular, vehicle routing problems have received much attention in recent years due to the increased importance of determining efficient strategies to reduce the operational costs associated with the supply chain. One of the typical routing problems consists of a fleet of vehicles, located at a central depot or warehouse, that must be scheduled to provide some type of service to customers which are geographically dispersed in a service region. In particular, the vehicle routing problem with time windows (VRPTW) has as objective to serve a number of customers within predefined time windows at minimum cost, without violating the capacity and total trip time constraints for each vehicle. VRPTW has recently become an area of intensive research since time windows naturally arise from realistic considerations and their impact on the optimal solution must be taken into account. Combinatorial optimization problems of this kind are non-polynomial-hard (NP-hard); therefore, known approaches for solving them to optimality suffer from an exponential growth in computational load with problem size. This work presents a constraint programming (CP) model for the VRPTW, as well as a heuristic search procedure which has been designed to tackle large instances of the problem. The specially designed search procedure successfully reduces the effort required to explore the search space. The proposed approach was tested on some standard benchmarks (Solomon´s problem instances) and computational results are presented and discussed.

enviar mensaje