An ant colony optimisation approach to scheduling truck and drone delivery systems

Tsietsi John, Moremi. (2022-04)

Thesis (PhD)--Stellenbosch University, 2022

Thesis

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.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/124509
This item appears in the following collections: