A Swarm Intelligence Solution for the Multi-Vehicle Profitable Pickup and Delivery Problem

Abstract

Delivery apps are experiencing significant growth, requiring efficient algorithms to coordinate transportation and generate profits. One problem that considers the goals of delivery apps is the multi-vehicle profitable pickup and delivery problem (MVPPDP). In this paper, we propose eight new metaheuristics to improve the initial solutions for the MVPPDP based on the well-known swarm intelligence algorithm, Artificial Bee Colony (ABC): K-means-GRASP-ABC(C)S1, K-means-GRASP-ABC(C)S2, Modified K-means-GRASP-ABC(C)S1, Modified K-means-GRASP-ABC(C)S2, ACO-GRASP-ABC(C)S1, ACO-GRASP-ABC(C)S2, ABC(S1), and ABC(S2). All methods achieved superior performance in most instances in terms of processing time. For example, for 250 customers, the average times of the algorithms was 75.9, 72.86, 79.17, 73.85, 76.60, 66.29, 177.07, and 196.09, which were faster than those of the state-of-the-art methods that took 300 s. Moreover, all proposed algorithms performed well on small-size instances in terms of profit by achieving thirteen new best solutions and five equal solutions to the best-known solutions. However, the algorithms slightly lag behind in medium- and large-sized instances due to the greedy randomised strategy and GRASP that have been used in the scout bee phase. Moreover, our algorithms prioritise minimal solutions and iterations for rapid processing time in daily m-commerce apps, while reducing iteration counts and population sizes reduces the likelihood of obtaining good solution quality.

Keywords

• multi-vehicle profitable pickup and delivery problem
• Artificial Bee Colony
• swarm intelligence
• metaheuristic algorithms