Browsing by Author "Ernst, Rudolf Heinrich"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Evolutionary algorithms for routing problems with drones with interceptions
    (Stellenbosch : Stellenbosch University, 2024-02) Ernst, Rudolf Heinrich; Groblem, Jacomine; Kaminsky, Phil; Stellenbosch University. Faculty of Engineering. Dept. of Industrial Engineering.
    ENGLISH ABSTRACT: The process of fulfilling the final step of the delivery of people or goods from a fixed distribution facility is known as last-mile freight. Studies have shown that the bulk of costs related to logistics are related to ‘last mile’ distribution. The biggest loss in efficiency is observed in the final step of the delivery process. The ever-growing e-commerce business-to-customer industry has drastically increased the movement of goods in pursuit of satisfying the increased demand of individuals and retailers. Recent advances in technology have led to drones being used to make last-mile deliveries. The research in this dissertation contributes to showing the advantages of using drones in combination with trucks for deliveries. In this dissertation, a particle swarm optimization-based algorithm, a differential evolution-based algorithm, and a covariance matrix adaptation evolution strategy (CMA-ES) algorithm are developed and implemented on the travelling salesman problem with drone with interceptions (TSPDi). The metaheuristics are implemented on 23 benchmark datasets, varying in size and distribution of nodes. Two repair mechanisms are implemented to deal with infeasible solutions, a common problem observed when metaheuristics making use of continuous decision variable values are used to solve NP-hard combinatorial optimisation problems. The study showed that the self-adaptive neighbourhood search differential evolution (SaNSDE) algorithm is the best performer on smaller datasets, while the CMA-ES algorithm is the best algorithm for larger datasets. Further analysis is done to understand the performance of various metaheuristics on the combinatorial optimisation problem as the metaheuristics attempt to improve on their best solution by navigating through the search space. The analysis considers duplicate solutions, infeasible nodes, and infeasible solutions, as well as the efficiency of the metaheuristics when implemented on the TSPDi. The study highlights the problems encountered when metaheuristics are used to solve the combinatorial TSPDi. Four new SaNSDE algorithms are also developed for the TSPDi, focusing on utilising problem specific operators and heuristics to improve performance. The four new algorithms drastically improved the solutions obtained for the TSPDi, outperforming the originally developed metaheuristics by up to 80% on larger datasets. The newly developed SaNSDE algorithms also outperform the best-known results obtained by Moremi [169], by up to 77%. The results showed that the nearest neighbour for initial solutions (NNHis) SaNSDE is the best algorithm for the TSPDi. The NNHis SaNSDE is adapted to be applied to a multiple truck and drone logistical problem. In the first instance, a cluster-first, route second approach is implemented to solve a multiple travelling salesman problem with drone with interceptions (mTSPDi). A vehicle routing problem with drones with interceptions (VRPDi) is also solved where nodes are not clustered. The NNHis SaNSDE is expanded on by developing problem-specific operators to improve performance, and the newly developed NNHis EXDSH SaNSDE algorithm is applied to the VRPDi. Overall, the NNHis aNSDE mTSPDi approach performs the best, while the NNHis EXDSH SaNSDE improves upon the solutions obtained by the NNHis SaNSDE on the VRPDi.