Dynamic pickup and delivery problem for autonomous delivery robots in an airport terminal

• Published in: Computers & industrial engineering 2024-10, Vol.196, p.110476, Article 110476
• Main Authors: Jeong, Joonhwa, Moon, Ilkyeong
• Format: Article
• Language: English
• Subjects: Autonomous delivery robot; Battery recharging strategy; Dynamic pickup and delivery problem; Peak period management
• ISSN: 0360-8352
• DOI: 10.1016/j.cie.2024.110476

Autonomous delivery robot (ADR) operation for short-range delivery purposes is becoming an increasingly popular mode of service. Assigning orders to robots is critical in ensuring high quality in these automated delivery operations. This paper considers a dynamic pickup and delivery problem using autonomous robots (DPDP-AR), where a fleet of ADRs picks up desired items from stores and delivers them to customers. The arrival time of orders is uncertain, with a hard delivery deadline for each order. This study considered the battery consumption of ADRs, which has been less extensively covered in previous research, and devised a battery recharging strategy for the operation. To handle this stochasticity and dynamism in the problem, we developed a reassignment algorithm that reschedules previously assigned orders at the arrival of a new order. Additionally, as periods of high demand can be estimated, peak time management of the battery is proposed to enhance ADR utilization at peak periods. Computational experiments were performed on real-world ADR food delivery service instances in an airport terminal. Test instances on various demand scenarios demonstrated improvement in service quality when devised policies were used compared to current practice. We substantiated that the proposed algorithms found efficient solutions within short computation times, validating their applicability to real-world operations. •Dynamic pickup and delivery problem using autonomous delivery robots is introduced.•We developed a novel reassignment algorithm for operational flexibility.•We considered battery constraints and suggested a distinct recharging strategy.•Peak time management method was developed to manage demand during peak periods.