AAE5301 Chap.5 Vehicle Routing for Drone Operations
Vehicle Routing for Drone Operations
Connected service sequences
TSP creates one depot-returning tour, while VRP extends the structure to multiple vehicles, capacities, time windows, pickups, depots, transfers and batteries. Arc and flow constraints preserve local movement, but subtour elimination is needed to prevent disconnected customer cycles.
The chapter also compares pure-drone, unsynchronised and synchronised truck-drone systems and shows why a complete route total must include every depot leg.
Local rules do not guarantee a route
One arrival and one departure at each customer can produce several closed cycles. Connectivity or subtour-elimination constraints are what attach every served customer to a depot route.
Capacity, time and battery states must also propagate along selected arcs so that a route cannot reset its load or energy between customers. Trace the selected arcs from each depot; any customer cycle that cannot be reached is infeasible even if its travel cost is attractive.
Hybrid routing adds coordination
A truck can act as carrier, mobile depot or rendezvous platform.
If drone flights are independent, the model may compare separate route totals. If a drone launches from and returns to a moving truck, truck arrival, launch, service and recovery times must align. Report the complete system cost, including depot legs, waiting and recovery. Test the returned route against payload, usable energy and time windows rather than trusting a short geometric path.
What this chapter covers
- 01
TSP and depot-returning tours
- 02
Arc variables and flow conservation
- 03
Subtour elimination
- 04
CVRP and cumulative load
- 05
VRP variants
- 06
Pure and truck-drone delivery modes
Worked example · free
Compare two complete routes
- 2List all arcs including return to depot.
- 3Sum kilometres for each route.
- 3Price the routes and interpret the tie.
Key terms
- Travelling Salesman Problem
- A shortest-tour problem visiting each required node once and returning to origin.
- Vehicle Routing Problem
- A multi-vehicle extension of a tour problem with capacity, time or other service constraints.
- Arc Variable
- A binary decision recording whether a vehicle travels directly from one node to another.
- MTZ Constraint
- An order-based inequality used to exclude customer-only subtours.
- Synchronised Delivery
- A multimodal service in which truck and drone movements meet at coordinated launch or recovery events.
Vehicle Routing for Drone Operations FAQ
Why are degree constraints not enough?
One arrival and one departure at every customer can still create a closed cycle disconnected from the depot. Connectivity or subtour-elimination constraints are needed so selected arcs form valid service routes.
What turns TSP into CVRP?
CVRP introduces multiple vehicles and payload capacity. Customer demand, per-vehicle flow and load propagation must ensure each route stays within capacity while every customer is served as required.
When is truck-drone synchronisation necessary?
Synchronisation is necessary when a drone launches from a moving truck and must rejoin it later. The model must coordinate truck arrival, launch, flight, service and recovery times at the rendezvous.
How should battery feasibility be checked on a route?
Propagate usable energy from launch through every flown leg and service action to the permitted recovery point, including the required reserve. Energy cannot reset at a customer unless charging or battery exchange is explicitly available there. A distance-feasible path can still fail because payload, wind or waiting changes consumption.
Why must every depot leg appear in the route total?
Comparing only customer-to-customer arcs favours fragmented or distant routes by omitting launch and return travel. List each sequence from depot departure to depot return, then sum every selected arc once. For multiple vehicles, keep separate route totals before aggregating so that the longest duty and capacity use remain visible.
How can a returned route be validated quickly?
Trace every selected arc from a depot until it returns, marking each customer exactly once unless split service is explicitly allowed. Along the trace, update load, time and usable energy after every leg and service event. Check that all time windows, recovery points and duty limits hold. Finally recompute the objective from the traced arcs.
This independent ledger exposes subtours, omitted depot legs and state variables that reset without a permitted action.
Exam move
Trace every proposed solution from a depot and write the visited nodes in order. Maintain a second line for cumulative load or energy. If a customer cycle cannot be reached from a depot, label it as a subtour before inspecting cost. Add arrival, service and departure time columns when time windows matter. For a truck-drone case, draw parallel timelines and connect each launch to its recovery event.
Recalculate the objective from the listed arcs, including every depot leg and any waiting term, before accepting the reported total. Flag every state reset and justify its physical cause.
