A TWO-PHASE DECOMPOSITION HEURISTIC VERSUS A HYBRID GENETIC ALGORITHM FOR SOLVING A MULTI-PRODUCT, MULTI-COMPARTMENT VEHICLE ROUTING PROBLEM WITH SIMULTANEOUS PICKUP AND DELIVERY AND TIME WINDOWS FOR THE TRANSPORT OF PERISHABLE PRODUCTS

We compare two approximate methods for solving the MPMC-VRPSPDTW, a vehicle routing problem for the transport of perishable products. The problem combines the following features: multiple products, multiple compartments, simultaneous pickup and delivery, time windows and a product degradation that depends on the road category. A single objective function minimizes the transport cost and the opportunity cost due to the loss of economic value of the products. The first solution method is a two-phase decomposition heuristic (TPDH) that works as follows: nearest-neighbour clustering of customers, then inter-route local search. The second is a hybrid genetic algorithm (GA) whose initial population is built from a feasible solution provided by an insertion heuristic inspired by Solomons I1. On 45 configurations derived from Solomons instances C101, R104 and RC107, the hybrid GA obtains a lower cost in 34 configurations and reduces the mean cost by 5.1% and the mean number of vehicles by 25.8%. Its mean run time is 1.5 times that of the TPDH (497 s vs 339 s).