Evolutionary algorithms for routing problems with drones with interceptions
Date
2024-02
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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.
AFRIKAANSE OPSOMMING: Die proses om die finale stap van die aflewering van mense of goedere vanaf ’n vaste verspreidingsfasiliteit te voltooi, staan bekend as laaste myl vervoer. Studies toon dat die grootste deel van die koste verbonde aan logistiek verband hou met die verspreiding in die ‘laaste myl’. Die grootste verlies in doeltreffendheid word in die finale stap van die afleweringsproses waargeneem. Die groeiende e-handelbesigheid het die beweging van goedere drasties verhoog. Onlangse vooruitgang in tegnologie lei daartoe dat hommeltuie of ‘drones’ gebruik word om die laaste myl aflewerings te maak. Die verhandeling dra by om die voordele van die gebruik van ‘drones’ in kombinasie met vragmotors vir aflewerings te beklemtoon. ’n ‘Particle swarm optimization’-gebaseerde algoritme, ’n ‘differential evolution’-gebaseerde algoritme, en ’n ‘covariance matrix adaptation evolution strategy’ (CMA-ES) algoritme word ontwikkel en ge¨ımplementeer op die ‘travelling salesman problem with drone with interceptions’ (TSPDi). Die metaheuristieke word ge¨ımplementeer op 23 datastelle wat wissel in grootte en verspreiding van nodusse. Twee herstelmeganismes word ge¨ımplementeer om onuitvoerbare oplossings te hanteer, ’n algemene probleem wat waargeneem word wanneer metaheuristieke wat gebruik maak van kontinue besluitveranderlike waardes, gebruik word om NP-harde kombinatoriese optimeringsprobleme op te los. Die studie het getoon dat die ‘self-adaptive neighbourhood search differential evolution’ (SaNSDE) algoritme die beste presteerder op kleiner datastelle is, terwyl die CMA-ES die beste algoritme vir groter datastelle is. Verdere analise word gedoen om die prestasie van verskeie metaheuristieke op die kombinatoriese optimeringsprobleem te verstaan soos die metaheuristieke poog om op die beste oplossing te verbeter deur die soekruimte te navigeer. Die ontleding oorweeg duplikaatoplossings, onuitvoerbare nodusse, en onuitvoerbare oplossings, sowel as die doeltreffendheid van die metaheuristieke wanneer dit op die TSPDi ge¨ımplementeer word. Die studie beklemtoon die probleme wat ondervind word wanneer metaheuristieke gebruik word om die kombinatoriese TSPDi op te los. Vier nuwe SaNSDE-algoritmes is ontwikkel vir die TSPDi, wat fokus op die gebruik van probleemspesifieke operateurs en heuristieke om prestasie te verbeter. Die vier nuwe algoritmes het die oplossings wat vir die TSPDi verkry is drasties verbeter en die oorspronklike metaheuristieke met tot 80% op groter datastelle oortref. Die nuut-ontwikkelde SaNSDE-algoritmes presteer ook beter as die bekendste resultate verkry deur Moremi [169] met tot 77%. Die resultate het getoon dat die ‘nearest neighbour for initial solutions’ (NNHis) SaNSDE die beste algoritme vir die TSPDi is. Die NNHis SaNSDE is aangepas om toegepas te word op ’n meervoudige vragmotor en ‘drone’ logistieke probleem. Eerste word ’n groepeer-eerste, roete-tweede benadering gevolg om ’n veelvuldige TSPDi (mTSPDi) op te los. ’n ‘Vehicle routing problem with drones with interceptions’ (VRPDi) word ook opgelos, waar nodusse nie groepeer word nie. Die NNHis SaNSDE word uitgebrei deur probleemspesifieke operateurs te ontwikkel om werkverrigting te verbeter, en die nuut ontwikkelde NNHis EXDSH SaNSDE-algoritme word op die VRPDi toegepas. Die NNHis SaNSDE mTSPDi-benadering vertoon die beste, terwyl die NNHis EXDSH SaNSDE verbeter op die oplossings wat deur die NNHis SaNSDE op die VRPDi verkry is.
AFRIKAANSE OPSOMMING: Die proses om die finale stap van die aflewering van mense of goedere vanaf ’n vaste verspreidingsfasiliteit te voltooi, staan bekend as laaste myl vervoer. Studies toon dat die grootste deel van die koste verbonde aan logistiek verband hou met die verspreiding in die ‘laaste myl’. Die grootste verlies in doeltreffendheid word in die finale stap van die afleweringsproses waargeneem. Die groeiende e-handelbesigheid het die beweging van goedere drasties verhoog. Onlangse vooruitgang in tegnologie lei daartoe dat hommeltuie of ‘drones’ gebruik word om die laaste myl aflewerings te maak. Die verhandeling dra by om die voordele van die gebruik van ‘drones’ in kombinasie met vragmotors vir aflewerings te beklemtoon. ’n ‘Particle swarm optimization’-gebaseerde algoritme, ’n ‘differential evolution’-gebaseerde algoritme, en ’n ‘covariance matrix adaptation evolution strategy’ (CMA-ES) algoritme word ontwikkel en ge¨ımplementeer op die ‘travelling salesman problem with drone with interceptions’ (TSPDi). Die metaheuristieke word ge¨ımplementeer op 23 datastelle wat wissel in grootte en verspreiding van nodusse. Twee herstelmeganismes word ge¨ımplementeer om onuitvoerbare oplossings te hanteer, ’n algemene probleem wat waargeneem word wanneer metaheuristieke wat gebruik maak van kontinue besluitveranderlike waardes, gebruik word om NP-harde kombinatoriese optimeringsprobleme op te los. Die studie het getoon dat die ‘self-adaptive neighbourhood search differential evolution’ (SaNSDE) algoritme die beste presteerder op kleiner datastelle is, terwyl die CMA-ES die beste algoritme vir groter datastelle is. Verdere analise word gedoen om die prestasie van verskeie metaheuristieke op die kombinatoriese optimeringsprobleem te verstaan soos die metaheuristieke poog om op die beste oplossing te verbeter deur die soekruimte te navigeer. Die ontleding oorweeg duplikaatoplossings, onuitvoerbare nodusse, en onuitvoerbare oplossings, sowel as die doeltreffendheid van die metaheuristieke wanneer dit op die TSPDi ge¨ımplementeer word. Die studie beklemtoon die probleme wat ondervind word wanneer metaheuristieke gebruik word om die kombinatoriese TSPDi op te los. Vier nuwe SaNSDE-algoritmes is ontwikkel vir die TSPDi, wat fokus op die gebruik van probleemspesifieke operateurs en heuristieke om prestasie te verbeter. Die vier nuwe algoritmes het die oplossings wat vir die TSPDi verkry is drasties verbeter en die oorspronklike metaheuristieke met tot 80% op groter datastelle oortref. Die nuut-ontwikkelde SaNSDE-algoritmes presteer ook beter as die bekendste resultate verkry deur Moremi [169] met tot 77%. Die resultate het getoon dat die ‘nearest neighbour for initial solutions’ (NNHis) SaNSDE die beste algoritme vir die TSPDi is. Die NNHis SaNSDE is aangepas om toegepas te word op ’n meervoudige vragmotor en ‘drone’ logistieke probleem. Eerste word ’n groepeer-eerste, roete-tweede benadering gevolg om ’n veelvuldige TSPDi (mTSPDi) op te los. ’n ‘Vehicle routing problem with drones with interceptions’ (VRPDi) word ook opgelos, waar nodusse nie groepeer word nie. Die NNHis SaNSDE word uitgebrei deur probleemspesifieke operateurs te ontwikkel om werkverrigting te verbeter, en die nuut ontwikkelde NNHis EXDSH SaNSDE-algoritme word op die VRPDi toegepas. Die NNHis SaNSDE mTSPDi-benadering vertoon die beste, terwyl die NNHis EXDSH SaNSDE verbeter op die oplossings wat deur die NNHis SaNSDE op die VRPDi verkry is.
Description
Thesis (PhD)--Stellenbosch University, 2024.