A metaheuristic approach to crowdsourced package delivery

Abstract

Increased demand on the package delivery industry is prompting companies to make use of crowdsourced delivery drivers. In this industry, when crowdsourced drivers are used the drivers need to be quickly provided with an optimal delivery route. This thesis addresses a new, real-world, crowdsourcing variant of the Vehicle Routing Problem, with deviation constraints and both heterogeneous and homogeneous capacity constraints using ad-hoc drivers. Previously, the problem has only been solved with exact techniques. Although exact techniques guarantee exact optimal solutions, they can have very long running times making them impractical in a fast paced, real-world situation. For this reason, this thesis explores a metaheuristic approach to solving the crowdsourced VRP, where solutions are not guaranteed to be exact, but can be close to exact and the running times are much shorter, thus practical in a real-world setting. In this thesis, we develop two Memetic Algorithms (HA1 and HA2) by combining a Genetic Algorithm with a Randomized Hill Climbing Local Search. The algorithms aim is the problem’s objective of minimizing total deviations of all the drivers while satisfying the problem's constraints. Problem-specific crossover and mutation operations are developed, and two variants of the crossover operation are explored. The results of the algorithms are empirically evaluated. The algorithms best fitness values and running times are compared to results of a Constraint Programming solver and the algorithms are compared against each other.One Memetic Algorithm in particular, HA1, provided positive results when evaluated. This algorithm is able to provide feasible solutions to instances with up to 135 packages with average running times of only a few minutes. On small instances the Memetic and Genetic Algorithms found feasible, but not exact, solutions, compared to the exact solutions of the Constraint Programming solver. Both Memetic Algorithms found more feasible and better results than the Genetic Algorithm, with HA1 performing the best in this area. The results found with a Memetic approach are practical for real-world problems since results that are both feasible and practical are provided within very short running times.