Examining the Online Food Delivery Problem on K-Ary Trees

This paper explores the Online Food Delivery Problem (OFDP) on the K-ary graph structure by analyzing six heuristic algorithms: First-In-First-Out (FIFO), Earliest Return First (ERF), Highest Density First (HDF), Simulated Annealing (SA), Genetic Algorithm (GA), and Ant Colony Optimization (ACO). We evaluate their effectiveness in minimizing key performance metrics such as maximum flow time, extra wait time, and relative wait time increase across dynamic request scenarios modeled on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>-ary tree. Using systematically generated test-cases, we simulate delivery workloads under both normal and stress conditions. Our findings show that GA offers the best averagecase performance in minimizing overall flow time, while ERF demonstrates robust worst-case behavior, particularly in highpressure environments. Simple heuristics like FIFO and ERF prove effective under online constraints, leveraging structural properties such as immediate service of singleton requests. Additionally, theoretical properties are derived to support heuristic behavior, including decision rules for serving temporally newer versus spatially closer requests.