A logic-based Benders decomposition method for the multi-trip traveling repairman problem with drones. (September 2022)

• Record Type: Journal Article
• Authors: Bruni, M.E.; Khodaparasti, S.; Moshref-Javadi, M.
• Is Part Of: Computers & operations research. Volume 145(2022)
• Publication Date: 2022-09
• Subjects: Multi-trip truck and drone routing problem -- Traveling repairman problem -- Latency -- Logic-based Benders decomposition; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105845
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: This paper considers the problem of delivering a certain number of packages to a set of customers using multiple drones dispatched from a single truck. Once a drone delivers a package, it returns to the truck to pick up another package while the truck waits at the launch location. The aim is to determine the truck route and the sequence of drone trips from the truck such that all the customer demands are served, either by the truck or drones, to minimize the sum of customer waiting times. We propose a new formulation of this problem based on an extended graph network representation. A new logic-based Benders decomposition method enhanced with relaxations is also developed and evaluated on several benchmark instances. The numerical results show that the proposed exact method obtains optimal solutions to the majority of the problem instances within the time limit of one hour. Highlights: We introduce a novel formulation of the multi-trip truck and drone delivery routing problem. We provide an exact method based on the logic-based Benders decomposition method. We present extensive computational experiments, comparing the proposed formulation and exact method.