Polynomial approximate dynamic programming scheme for theweight constrained two-echelon routing problem with a drone
C. Lorenza , A. Ottoa,∗ and D. Vigob
Chair of Management Science / Operations and Supply Chain Management, University ofPassau, Passau, Germany
catherine.lorenz@uni-passau.de, alena.otto@uni-passau.deb Department of Electrical, Electronic and Information Engineering and CIRI-ICT, Universityof Bologna, Bologna, Italy
daniele.vigo@unibo.it∗ Corresponding authoraExtended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

January 11, 2022
Keywords: Dynamic Programming, Two-echelon routing, Multi-visit drone routing

1Introduction

In this abstract, we investigate a generic variant of a 2-echelon routing problem, in which thetravel range of the primal vehicle (2nd echelon vehicle) is constrained by one or several capacitated resources. By meeting at the same place and the same time with the supporting vehicle(1st echelon vehicle) for a service in one of possible meeting points (MPs), those resources canbe replenished. The arising problem is characterized by particularly strong synchronization constraints for the two vehicles compared to the well-studied 2-echelon problem formulations. The
described problem setting emerges in many robot routing applications, notably, those including
a drone. In the latter case, the supporting vehicle may be a truck (Poikonen & Golden, 2020)
or an autonomous mobile replenishment station (Barrett et al., 2018). In possible applications,the drone, constrained by its data storage capacity, collects data from scattered sensors (Jawharet al., 2014); or it delivers packages, the total weight of which can not exceed its payload (Poikonen & Golden, 2020); or it visits several locations for monitoring in a long mission that surpasses
its flight range (Baik & Valenzuela, 2021). The current pandemics gave a further boost to thedeployment of drones, which now spray disinfectants in public spaces, pick up lab samples, anddeliver tests and medical supplies (UNICEF, 2021).
This paper reports on selected results of a larger research project on the described 2-echelon
routing problem, which we dubbed as the Drone Routing Problem with Energy replenishment(DRP-E). The project is conducted by the authors and Nicola Mimmo (University of Bologna).
DRP-E is a generalization of several routing problems, such as the asymmetric travelingsalesman problem with replenishment arcs (Boland et al., 2000), the traveling salesperson problem
with hotel selection (Castro et al., 2015), and drone routing with stationary service stations(Mathew et al., 2015). Contrary to the available literature on drone routing applications, suchas traveling salesman problems with drone (Agatz et al., 2018), DRP-E allows the drone tovisit multiple destinations between consecutive meetings for a service and permits both vehicles
to revisit arcs and MP’s. Furthermore, most studied drone routing scenarios consider simplified
energy consumption which is linear in the flight time. To the best of our knowledge, only Poikonen
TRISTAN XI Symposium

Original abstract submittal

C.Lorenz, A. Otto and D.Vigo

2Figure 1 – An instance of DRP-E with one resource Figure 2 – Solutions for the instance of(energy) and load-dependent energy consumption Figure 1Instance with |V d | = 3 and |V m | = 3. The tour must start in wsand end in wt . The edge weights mark the distances, the (boxed)node weights denote the package weight. The drone’s energy
consumption depends on the flight time t and the current loadp: E(t, p) = t·(p+1). The drone’s energy capacity is cmax = 55.

Top: Solution of the route-first-cluster-second approach
RTS based on TSP path (ws , v1 , v2 , v3 , wt ). The tour
consists of 3 operations (ws , v1 , wt ), (wt , v2 , w1 ) and(w1 , v3 , wt ) of duration 12, 5 and 4 respectively. Thetotal makespan is 21.
Bottom:Optimal solution with 2 operations(ws , v2 , v1 , wt ), (wt , v3 , wt ) of duration 16 and 4,respectively. The total makespan is 20, or 5% less thanin the solution above.

& Golden (2020) consider the problem setting described by DRP-E; the authors propose a routefirst-cluster-second construction heuristic, which they dub RTS. This state-of-the-art approachfirst fixes the visiting order of the required destinations by the primal vehicle as a TSP-path,then optimally selects and inserts MPs into this fixed sequence of destinations.
Similarly to RTS, many state-of-the art approaches for 2-echelon routing problems exploit theseparability of the routing decisions for both echelons. Those provide good starting solutions, but
are hard to improve by standard local search operators such as k-exchanges, swaps or randomized
neighbourhood searches, and usually show a large gap to optimality. This gap generally grows
with the addition of realistic problem features that strengthen the interdependence of bothvehicles. In our project, we propose a (polynomial approximate) dynamic programming scheme(PADP) that considers routing on both echelons simultaneously and is able to significantly
improve the initial solution, such as that of RTS, in reasonable running time. By dropping theaggregation of the states in the state graph, PADP can be straightforwardly transformed into a
powerful exact dynamic programming approach.

2Problem description

In DRP-E, the primary vehicle, which we call drone, has to visit a given set of destinations V d .
Because of the limited capacity of one or several resources, the drone has to meet regularly withthe supporting vehicle (SV) in a set of potential meeting points (MP), denoted as V m , which
are safe spots on the SV’s road network for servicing the drone. A service usually implies abattery swap, but may also refer to data transmissions to the data storage, package pick-ups, orpackage deliveries. Both vehicles depart from the source ws ∈ V m and terminate their trip in thetarget wt ∈ V m . We call the walks of both vehicles in between two consecutive meetings for aservice at MP’s w and w′ as operation (OP) o = wsw′ , where s is the corresponding sequence ofdestinations visited by the drone. The duration of an OP wsw′ is determined by the latest arrivalof the two vehicles at w′ (synchronization) and possibly involves waiting times. An OP is feasible
if the consumption of each resource r ∈ R in the corresponding drone walk does not exceed its
respective capacity crmax ∈ R. The resource consumption functions are generally complex andTRISTAN XI Symposium

Original abstract submittal

C.Lorenz, A. Otto and D.Vigo3

do not solely depend on the flight time. Each mission can be considered as a sequence of feasible
operations.
The objective of DRP-E is to minimize the makespan of the drone’s mission, by:• sequencing the destination visits of the drone (2nd echelon)• scheduling the services, which requires routing the SV through selected MP’s (1st echelon)
Figure 1 illustrates an instance of DRP-E with one resource (energy), in which the energy
drain depends on the load carried by the drone.

3

Contributions and computational results

The developed solution scheme PADP stands out from conventional heuristics in a number ofaspects which will be elaborated in detail during the presentation:• The proposed PADP explores an exponential number of promising solutions in polynomialtime. This is due to a novel state-space aggregation procedure and an efficient encoding of
the states. The path exploration in the aggregated state graphs optimizes simultaneously
two polynomial subproblems of DRP-E. Given an input sequence of destinations, the first
subproblem compares similar missions, in which the visiting order of destinations verifies
the precedence constraints defined by Balas & Simonetti (2001). The second polynomial
subproblem takes the visiting order of destinations as given and optimizes, when and where
the services take place. The simultaneous solution of the mentioned subproblems by PADP
exploits synergies and significantly boosters the efficiency of the solution procedure.
• PADP can be straightforwardly adapted to many 2-echelon routing problem variants. This
flexibility arises from the design of PADP as a two-phase approach: The first phase constitutes of |V m | weight-constrained one-to-many shortest path problems, which identify
feasible operations and eliminate dominated ones. The associated aggregated state-graph,dubbed operations graph, accommodates all drone-related features and is searched by a label
setting algorithm. In the second phase, these pre-selected feasible operations are sequenced
to a best possible complete mission. The second phase accommodates the specificity of thedrone service and the characteristics of the SV. Note that the two-phase approach does notseparate the routing decisions for different echelons.
• The intensity of the aggregation in the state graphs of PADP is flexibly scaled by only
one parameter p, which controls the trade-off between the computational complexity andaccuracy. By dropping the aggregation, PADP – which is exponential in p, but polynomialin the parameters of DRP-E – can be straightforwardly transformed to an exact dynamic
programming approach, which is the first exact solution approach for DRP-E so far.
We analytically estimate the size of the explored solution space and the time complexity ofPADP. Then, we evaluate the performance of PADP in extensive computational tests on various
structured artificial benchmark data sets. On the basis of different application scenarios, weidentify which factors reinforce or deteriorate the benefits of PADP compared to the stateof-the-art heuristics. Table 1 shows an extract from the conducted experiments. Benchmark
instances are generated as described in Poikonen & Golden (2020) for a quadcopter operating ina square area of length l (km) with zero package weights (NoPack) and package weights between
0 and 2.3 kg (Pack). PADP outperformed the state-of-the-art procedure RTS in almost all theinstances. In several cases the observed improvement exceeded 10%. Observe that RTS-solutions
cannot be easily improved even after hundreds of iterations with standard local search operators
neither applied to the route-first part of the solution, nor to the resulting mission, as we show in
our extensive experiments. Each instance with |V d | = 16 destinations and |V m | = 16 MPs was
TRISTAN XI Symposium

Original abstract submittal

C.Lorenz, A. Otto and D.Vigo

4solved by the exact algorithm based on PADP on a standard laptop with Intel i7-8565U, 1.80
GHz, 32GB RAM within a 10-minute time limit with an average runtime of 193 seconds.
We also examine real-life case studies, such as a search-and-rescue operation by a drone andan autonomous robotic charging platform in the mountainous areas around lake Occhito, inSouthern Italy. In the mentioned case study, PADP outperformed the state-of-the-art solution
in disaster relief by 20%.
Table 1 – Performance of PADPSetting(|V d |–|V m |–l–P)
16-16-20-noPacks
16-16-20-Packs
25-25-25-noPacks
25-25-25-Packs
50-25-25-noPacks
50-25-25-Packs
25-50-25-noPacks
25-50-25-Packs
Total

4Avg. (worst) gap
to optimality (%)
2.1 (6.7)
3.6 (9.7)
– (–)
– (–)
– (–)
– (–)
– (–)
– (–)
– (–)

Avg. (best) improve- ment over RTS (%)
1.4 0(5.4)
3.9 0(7.5)
2.7 0(7.6)
5.5 (13.8)
3.7 0(8.6)
5.8 0(9.7)
2.1 0(7.6)
4.5 0(8.4)
3.7 (13.8)# improvements
over RTS
5 (out of 10)
10 (out of 10)
10 (out of 10)
10 (out of 10)
10 (out of 10)
10 (out of 10)
10 (out of 10)
10 (out of 10)
75 (out of 80)

Conclusion

We currently examine PADP in a number of further real-world case studies. As next steps, theinitial problem formulation as well as our analysis and the developed solution scheme PADP
should be extended to further cases relevant for practice. These include problem formulations
with uncertain flight times and multiple drones.

References
Agatz, N., Bouman, P., & Schmidt, M. 2018. Optimization approaches for the traveling salesman problem
with drone. Transportation Science, 52(4), 965–981.
Baik, H., & Valenzuela, J. 2021. An optimization drone routing model for inspecting wind farms. Soft
Computing, 25(3), 2483–2498.
Balas, E., & Simonetti, N. 2001. Linear time dynamic-programming algorithms for new classes of restricted TSPs: A computational study. INFORMS Journal on Computing, 13(1), 56–75.
Barrett, É., Reiling, M., Mirhassani, S., Meijering, R., Jager, J., Mimmo, N., Callegati, F., Marconi, L.,
Carloni, R., & Stramigioli, S. 2018. Autonomous battery exchange of UAVs with a mobile ground base.
Pages 699–705 of: 2018 IEEE International Conference on Robotics and Automation (ICRA).
Boland, N., Clarke, L., & Nemhauser, G. 2000. The asymmetric traveling salesman problem with replenishment arcs. European Journal of Operational Research, 123(06), 408–427.
Castro, M., Sörensen, K., Vansteenwegen, P., & Goos, P. 2015. A fast metaheuristic for the travelling
salesperson problem with hotel selection. 4OR quarterly journal of the Belgian, French and ItalianOperations Research Societies, 13, 15–34.
Jawhar, I., Mohamed, N., Al-Jaroodi, J., & Zhang, S. 2014. A framework for using unmanned aerialvehicles for data collection in linear wireless sensor networks. Journal of Intelligent Robotic Systems,74(1–2), 437–453.
Mathew, N., Smith, S., & Waslander, S. 2015. Planning paths for package delivery in heterogeneous
multirobot teams. IEEE Transactions on Automation Science and Engineering, 12(4), 1298–1308.
Poikonen, S., & Golden, B. 2020. Multi-visit drone routing problem. Computers & Operations Research,113, 104802.
UNICEF. 2021. Rapid Guidance: How Drones Can Be Used to combat COVID-19. Tech. rept. Downloaded on Jan 2022. https://www.unicef.org/supply/media/5286/file/

TRISTAN XI Symposium

Original abstract submittal