The travelling salesmen problem is a pretty old problem, it was studied back in 1930 and continues to play a key role in operational research for things such as vehicle routing. The problem is as follows:
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
Swapping cities for various alternatives means this type of problem fits many different scenarios and the modern day continues to add further complexities. One of which I think is pretty interesting is the addition of a drone to a vehicle routing scenario. Rather than replacing the vehicle with the drone, the drone acts as sort of a sidekick (some papers even refer to it as so).
A drone alone can only carry lighter packages and has a finite battery life that determines maximum flight time and distance. Therefore instead of having the drone only deliver light packages that are close to the depot, the drone will keep meeting up with the delivery van en-route to collect more packages (one package at a time) and replace batteries. This not only increases the range the drone can reach but means you can continue to have the drone delivering while the van is also and therefore greatly reduce the total delivery time.
The idea was first proposed in 2015 and there are currently various methods optimally planning this. One such method, proposed by El-Adle et al. uses Mixed Integer Programming.
What is Mixed Integer Programming?
Mixed Integer Programming is a type of Linear Programming. It is used to find the “best” solution for a particular objective given a set of limitations known as constraints.
The goal is usually find a solution which either minimises or maximises some linear objective function subject to the set of given linear constraints. The constraints can be a mixture of equalities and inequalities.
A common form of a linear equation is: $$ \begin{align*} \max \,\,\, & c^T x \\ \text{subject to} \,\,\, & A x \leq b \\ & x\geq0 \end{align*} $$ where \(x\) is a vector of variables which vary to find the best solution (known as the decision variables), \(c\) is the vector of coefficents of the decision variables within the objective function, \(A\) is the matrix of coefficents of the decision variables within the constraints and \(b\) is the vector of bounds on the constraints.
The mixed integer element comes from adding constraints to the problem which ensures some (but not all) of the variables in the solution much be integers.
The usual method for solving Mixed Integer Programs is called Branch and Bound.
Branch and Bound
Finding the solution to a Linear Program where all the decision variables don’t necessarily need to be integers is much simpler than when some or all do. There is well known algorithm known as the revised simplex method which can be used do this. The Branch and Bound method uses relaxed versions of Integer or Mixed Integer Programs where variables that are constrained to be integers are allowed to be non-integer and iteratively the method moves towards integer solutions, eventually finding the optimal option. For a Mixed Integer Program (MIP), the steps are as follows:
- Start at node 1. Find the optimal solution to the relaxation of the MIP and calculate the objective function value at this optimal. If the variables which are constrained to be integers are in your found optimal then you can stop here.
- Choose a variable which you want to be integer in the final solution but currently isn’t and branch on this. This means resolving for the optimal twice but keeping this variable fixed in both instances. In one instance (node 2), the chosen variable is fixed at the “floor” of its value in the current optimal solution (i.e rounded down to the nearest integer). In the other instance (node 3), the chosen variable is fixed at the “ceiling” of its value in the current optimal solution (i.e rounded up to the nearest integer).
- Choose the solution with the highest objective value for the optimal solution at that node to branch a second time on. This keeps the variable which was set in step 2 fixed to the value at the node you branched on but repeats the process for another non-integer value in your current optimal at that node which you wish to be integer.
- Continue branching on the node which has the highest objective function value until you have a solution which fulfils the mixed integer constraints and all nodes have a objective function value which is less than or equal.
Here is an example of the Branch and Bound algorithm being used. Slide mouse over image to pause the slideshow. The \(x\) and OV stated at each node is the optimal solution and objective function value respectively at that stage in the Branch and Bound.
While for simple problems you may want to solve these by hand, in reality and especially for the travelling salesmen problem with drone an optimization solver such as Gurobi can do this much more efficiently for you.
How can the Travelling Salesmen Problem with Drone be formulated?
A paper recently published in the Journal of the Operational Research Society by El-Adle et al formulated the problem as a MIP with elements as described in this section .
Objective
Minimize the return time of both drone and vehicle to the depot.
Decision variables
Integer variables
For each of the following points below a set of binary decision variables are created to indicate:
- If the vehicle travels from a location i to a location j.
- If the vehicle travels from a location i to a location j.
- If the vehicle flies from a location i to a location j.
- If the vehicle visits a location j.
These are set to 1 if the event occurs and 0 if not. Here you’ll see that the second and third set of decision variables appear to be the same however the drone may be transported from one location to another aboard the vehicle. In this case, for that pair of location, the “travelling” variable would be set to 1 however the “flying” variable would be set to 0.
Non-integer variables
For each of the following points below a set of decision variables are created to indicate:
- The arrival time of the delivery carrier at location j.
- The departure time of the delivery carrier at location j.
- The time spent by the vehicle waiting for the drone at location j.
Constraints
One or more constraints is used to ensure the following hold:
- The vehicle departs the depot for exactly one location.
- The drone departs the depot for exactly one location.
- If the vehicle does not visit a location then the drone does.
- If the drone travels from one location to another, then the vehicle must visit at least one of those.
- If the drone travels from one location i to another location j and the vehicle also visits both those locations on its full journey then it must travel from i to j.
- The drone cannot be transported aboard the vehicle at the same time that it flies.
- If the drone “flies” then it also “travels”.
- The drone cannot fly for a duration more than it’s capacity before meeting with the vehicle.
- If a carrier travels from one location to the next than it cannot arrive before the departure time from the last location plus the travel time to the new location.
- A carrier cannot depart before it arrives.
- Whenever the drone departs a location later than the vehicle, the vehicle’s waiting time is equal to the difference.
This makes up a much long lists of constraints and decision variables than the traditional Travelling Salesmen Problem as it is much more complex. However with the way technology is moving forward, it definitely has its place. There are a number of other approaches to solve the Travelling Salesmen Problem with Drone and further adaptations too. For instance, adding multiple drones futher complicates the problem but can speed delivery times up considerably.
For the paper where they detail the full Mixed Integer Program in mathematical terms and give a number of further model enhancements see the reference below.
References
Amro M. El-Adle, Ahmed Ghoniem & Mohamed Haouari (2021) Parcel delivery by vehicle and drone, Journal of the Operational Research Society, 72:2, 398-416, DOI: 10.1080/01605682.2019.1671156
Wikipedia: Travelling salesman problem, https://en.wikipedia.org/w/index.php?title=Travelling_salesman_problem&oldid=1014002267