Decomposição de Benders para o problema da entrega compartilhada (crowdshipping)

Abstract

The growth of e-commerce has intensified the demand for efficient last-mile delivery solutions, driving interest in logistics models based on the sharing economy. Among these approaches, employee-based crowdshipping stands out, in which employees perform deliveries along their commute home after work. This study addresses the demand–supply matching problem within this context, considering operational constraints such as vehicle capacity, maximum allowable deviation, and minimum expected compensation for employees. To solve the problem, an exact algorithm from the literature based on Benders Decomposition is implemented. Additionally, a GRASP (Greedy Randomized Adaptive Search Procedure) metaheuristic is developed to generate high-quality initial solutions, replacing the Greedy Heuristic originally proposed. Computational experiments are conducted using benchmark instances from the literature to compare the performance of both approaches. The results show that the GRASP metaheuristic consistently produces superior initial solutions, establishing it as a more robust and effective alternative for the employee-based crowdshipping problem.