An ant colony optimisation approach to scheduling truck and drone delivery systems
Date
2022-04
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH SUMMARY: ‘Last mile’ logistic scheduling is a complex problem businesses are facing today.
Competitive pressure has increased with technological growth. The speed of delivering
parcels to customers can be an excellent source of competitive advantage,
since businesses are facing the challenge of efficiently delivering parcels to customers
on a daily basis. The use of delivery drones in conjunction with traditional
delivery vehicles is a new highly promising research direction explored in this thesis.
This dissertation proposes various truck and drone delivery system optimisation
problems where a delivery drone is launched from a purpose-built truck, completes
additional deliveries while the truck is en route between two customer locations,
and intercepts the truck after completing the additional delivery. The dissertation
describes the development of an ant colony optimisation algorithm used to solve
the problem. More specifically, an ant colony system with k-means clustering was
used in this research. Adaptive algorithm control parameters were also used to
ensure an acceptable balance between exploration and exploitation throughout
the search process.
The algorithm was tested on drone scheduling benchmark problems, optimal
solution and other population based metaheuristics and compared against a truckonly delivery system. It was shown that the truck and drone delivery system has
a significant positive impact on delivery time performance.
AFRIKAANS OPSOMMING: ‘Last mile’ skedulering is ’n ingewikkelde probleem wat ondernemings vandag moet kan hanteer. Mededingende druk het toegeneem met tegnologiese groei. Die spoed van die aflewering van pakkies aan kliënte kan ’n uitstekende bron van mededingende voordeel wees, aangesien ondernemings daagliks die uitdaging ondervind om pakkies doeltreffend aan kliënte te lewer. Die gebruik van onbemande lugvoertuie saam met tradisionele afleweringsvoertuie is ’n nuwe, baie belowende navorsingsrigting wat in hierdie tesis ondersoek word. Hierdie verhandeling beskryf ’n vragmotor-lugvoertuig afleweringstelsel waar ’n onbemande lugvoertuig vanaf ’n doelgemaakte vragmotor gelanseer word, addisionele aflewerings voltooi terwyl die vragmotor tussen twee kliënte beweeg, en die vragmotor onderskep nadat die addisionele aflewering voltooi is. Die verhandeling beskryf die ontwikkeling van ’n mierkolonieoptimeringsalgoritme wat gebruik word om die probleem op te los. Meer spesifiek, is ’n mierkoloniestelsel in hierdie navorsing gebruik. Aanpasbare algoritme beheerparameters is ook gebruik om ’n aanvaarbare balans tussen eksplorasie en ontginning gedurende die soekproses te verseker. Die algoritme is getoets op standaard probleme vir aflewerings lugvoertuig skedulering en vergelyk met ’n afleweringstelsel wat slegs uit tradisionele voertuie bestaan. Daar word gewys dat die vragmotor-lugvoertuig afleweringstelsel ’n beduidende positiewe invloed op die afleweringstydprestasie het.
AFRIKAANS OPSOMMING: ‘Last mile’ skedulering is ’n ingewikkelde probleem wat ondernemings vandag moet kan hanteer. Mededingende druk het toegeneem met tegnologiese groei. Die spoed van die aflewering van pakkies aan kliënte kan ’n uitstekende bron van mededingende voordeel wees, aangesien ondernemings daagliks die uitdaging ondervind om pakkies doeltreffend aan kliënte te lewer. Die gebruik van onbemande lugvoertuie saam met tradisionele afleweringsvoertuie is ’n nuwe, baie belowende navorsingsrigting wat in hierdie tesis ondersoek word. Hierdie verhandeling beskryf ’n vragmotor-lugvoertuig afleweringstelsel waar ’n onbemande lugvoertuig vanaf ’n doelgemaakte vragmotor gelanseer word, addisionele aflewerings voltooi terwyl die vragmotor tussen twee kliënte beweeg, en die vragmotor onderskep nadat die addisionele aflewering voltooi is. Die verhandeling beskryf die ontwikkeling van ’n mierkolonieoptimeringsalgoritme wat gebruik word om die probleem op te los. Meer spesifiek, is ’n mierkoloniestelsel in hierdie navorsing gebruik. Aanpasbare algoritme beheerparameters is ook gebruik om ’n aanvaarbare balans tussen eksplorasie en ontginning gedurende die soekproses te verseker. Die algoritme is getoets op standaard probleme vir aflewerings lugvoertuig skedulering en vergelyk met ’n afleweringstelsel wat slegs uit tradisionele voertuie bestaan. Daar word gewys dat die vragmotor-lugvoertuig afleweringstelsel ’n beduidende positiewe invloed op die afleweringstydprestasie het.
Description
Thesis (PhD)--Stellenbosch University, 2022
Keywords
Ant algorithms, Ant colony -- Optimization, Vehicle Routing Problem and Drones (VRPD), Vehicle Routing Problem and Drones Time Window (VRPDTW), Mathematical optimization, Transportation -- Planning, Delivery systems – Optimization, Business logistics