A reactive GRASP with path relinking for the pick-up and delivery problem with cross-docks

The pick-up and delivery problem with cross-docks is the problem of serving a number of transportation requests using a limited heterogeneous vehicle fleet. Each request has to be picked-up from and delivered to a specific location. Cross-docks can be used to temporarily store a product, such that another vehicle can deliver the product to its final destination. Our task is to construct routes against the lowest cost such that all requests are handled and time, capacity and capability constraints are met. Very liberal routing policies are allowed, which makes that this thesis is as far as we know the first in literature that studies this problem. This thesis mathematically defines this problem and presents a heuristic for it that combines a Greedy Randomized Adaptive Search Procedure with a ruin and recreate method for local search and Path Relinking, Furthermore, this heuristic is embedded in an Ant Colony Optimization framework. The heuristic is tested on 21 instances with up to 25 requests. The results indicate that sizable cost decrease can be obtained by applying more liberal routing policies and a dynamic assignment of requests to cross-docks.