# Drone-Based Parcel Delivery Using the Rooftops of City Buildings: Model and Solution
## 4 Heuristic-Based Solution  
As mentioned in Section 1, commercial optimization software has difficulty in providing optimized planning for large MILP problems in a reasonable time. This problem also occurred in our case, which will be summarized in a later section. Thus, to address the computational tractability of the proposed problem, we developed an efficient heuristic that can quickly generate optimal or near-optimal solutions in terms of the objective value of the DROP-Model for various problem instances. The proposed heuristic is based on two basic steps: 1) building a solution by stacking blocks and 2) improving the solution by making space and inserting blocks. Each step can be explained as follows. * **Step 1**: Building a solution by stacking blocks. First, we need to define a block. A block is assigned to each destination (e.g., rooftop) and includes the time information (i.e., block time) for delivery and charging. For example, block '1' has 0.68 h, 0.29 h for any drone to deliver a parcel to destination '1' and 0.39 h for any drone to charge the battery for this delivery only. Once the blocks for all destinations are defined, we can start to stack the blocks for each drone to generate a solution (i.e., schedule). **Step 1.1**: Initially, adopt a simple assignment rule for block stacking. Shorter deliveries and charging times are assigned first. Among the blocks, the shorter blocks are assigned to the drones first, as shown in Figure 1(a). Each line represents a schedule or delivery work allocation for each drone. However, since our schedule should not exceed the operating hours (i.e., 9 h), we cannot assign blocks that go over the given operating hours. Thus, we need to rearrange the blocks to avoid violating the operating hours. **Step 1.2**: Whenever trying to stack any block to a line, create a power set from the line to pick up the blocks with summed charging times that are most similar to the time for a battery to be fully charged. For example, if the summed charging time from blocks '2', '2', and '4' is 1.47, then there is only a 0.03 gap to the battery charging time (from zero to full) of 1.5. This grouping can be easily made by checking the summed charging time of each combination in the power set. The reason why we pick up those blocks as a group is that we want to allocate them at the end of the line. Because charging is no longer required after operating hours (i.e., zero battery will be okay at the end of operating hours), those blocks need to be allocated at the end of the line, as shown in Figure 1(b). However, if the allocation of such a block group for any drone exceeds the operating hours, we cancel the allocation of the block group for that drone. * **Step 2**: Improving the solution by making space and inserting blocks. After Step 1, we can obtain the lines of blocks for the drones that do not exceed the operating hours. Next, we have to improve the current solution (i.e., lines) by inserting more blocks because the objective function of the DROP-Model maximizes the number of delivered parcels. **Step 2.1**: Try to make a space to add a new block that has a shorter block time among the remaining blocks (not inserted in the lines yet). To do this, the lines for the drones need be sorted in descending order of their remaining time. If any line's length (i.e., the sum of the block times of the line) is 8.26, the remaining time of this line would be 0.74 (= 9.0-8.26). **Step 2.2:** Choose the first and the second lines from the sorted list and then find the common destinations (i.e., intersection) that exist among both lines. From those common destinations, we need to generate combinations whose elements are two destinations only. For example, if there are three destinations 1, 2, and 3 that compose the intersections of the two lines, we can generate three combinations: {1, 2}, {1, 3}, and {2, 3}. **Step 2.3:** From the combinations, choose the one that has the largest gap of block time between two elements, as shown in Figure 3a.