A Mixed-Integer Linear Programming (MILP) solution for the Flying Sidekick Traveling Salesman Problem (FSTSP). This project optimizes last-mile delivery routes by coordinating a truck and a drone to minimize total operation time.
In modern logistics, combining traditional trucks with drones can significantly reduce delivery times. The truck acts as a moving launchpad, performing deliveries while launching a drone to serve customers within a radius
Key Constraints:
- Each customer is visited exactly once (by truck OR drone).
- The drone has a limited flight range (
$R$ ) and capacity (1 package). - Subtour elimination constraints ensure valid routing.
- The objective is to minimize the total time (
$Z$ ) required to serve all$N$ customers and return to the depot.
The problem is modeled using Gurobi Optimizer.
Objective Function:
Where:
-
$x_{ij} \in {0,1}$ : Truck travels from$i$ to$j$ . -
$y_{ij} \in {0,1}$ : Drone delivers to$j$ launching from$i$ . -
$d_{ij}$ : Euclidean distance. -
$K$ : Speed factor (Truck/Drone ratio).
We tested the model on random instances (15 to 35 nodes). The hybrid approach demonstrated significant efficiency gains compared to the traditional Truck-Only TSP.
| Instance | Nodes | Truck Only Cost | Hybrid Cost | Improvement |
|---|---|---|---|---|
inst_35_0 |
35 | 3736.83 | 3324.46 | ~11% |
inst_20_1 |
20 | 2870.62 | 2677.91 | ~6.7% |
Blue lines: Truck Path | Red dashed lines: Drone Flight
-
Clone the repository:
git clone [https://github.com/Dev-Toledo/tsp-drone-solver.git](https://github.com/Dev-Toledo/tsp-drone-solver.git)
-
Install dependencies
pip install -r requirements.txt
-
Run the solver: (Note: A valid Gurobi License is required. Academic licenses are free.)
python src/solver.py
Language: Python
Solver: Gurobi Optimizer (gurobipy)
Visualization: Matplotlib & Folium
This project is licensed under the MIT License.
Caio Toledo - Github / LinkedIn