Engineering & Technologyarticle2026-10-28

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

Open access0 citations

Abstract

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).

// Source

View paper (DOI)Open access versionOpenAlexInternational Journal of Advanced ResearchPublished 2026-10-28

Authors: Gueu Ounsé Éric-Noël, Kaye Bi Kouai Bertin, Coulibaly Kpinna Tiekoura, Oumtanaga Souleymane

Institutions: Université Félix Houphouët-Boigny, Institut National Polytechnique Félix Houphouët-Boigny, École Supérieure Africaine des TIC