The multiple flying sidekicks traveling salesman problem with variable drone speeds (mFSTSP-VDS)

This repository provides a collection of mFSTSP-VDS test problems, as well as the soucre code of the heuristic to solve mFSTSP-VDS instances. The mFSTSP-VDS is a variant of the TSP in which multiple UAVs coordinate with a truck to deliver parcels in the minimum time, and UAVs can fly at any speeds below their maximum speeds.

The repository accompanies the following paper, which is currently under its second round of reviews:

R. Raj and C. Murray. Fly slower, deliver faster: The multiple flying sidekicks traveling salesman problem with variable drone speeds. Available at SSRN: https://ssrn.com/abstract=3549622

The paper provides details on the mFSTSP-VDS definition, and a heuristic as a solution approach. The figure below is the visual representation of the solution of an mFSTSP-VDS instance:

---

This paper is an extension of:

C. C. Murray and R. Raj (2020), The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones, Transportation Research Part C: Emerging Technologies, Volume 110, Pages 368-398.

• The mFSTSP paper is available at:

  • https://ssrn.com/abstract=3338436 (free download from SSRN), or
  • https://www.sciencedirect.com/science/article/pii/S0968090X19302505 (published paper)

• Visit https://github.com/optimatorlab/mFSTSP for test problems, solutions, and heuristic source code for the mFSTSP.

---

mFSTSP-VDS Repository Contents

This repository contains test problems (and solutions), and the source code required to run the mFSTSP-VDS solver. These elements are described in detail below.

1. A collection of test problems (and solutions) that were used in the analysis described in the mFSTSP-VDS paper.

   1. problems_info.csv contains a summary of all 80 "base" test problems, including:

      • numCust: Total number of customers.
      • LeftLon, LowerLat, RightLon, UpperLat: Latitude/Longitude coordinates of the bounding region from which customer locations were generated. These coordinates specify the SW and NE corners of a rectangle.
      • widthOfRegion and heightOfRegion: Sizes of the geographic region, available in both miles and meters.
      • numCust5milesDepot: Number of customers located within 5 miles (Euclidean distance) of the depot.
      • numCust10milesDepot: Number of customers located within 10 miles (Euclidean distance) of the depot.

      This file may be useful if you are looking for problems with certain properties (e.g., 50-customer problems).

   2. performance_summary_archive.csv provides information about solutions generated for each test problem in the mFSTSP-VDS paper. See the "Archived Problem Solutions" section below for details on the contents of this file.

   3. The Problems directory contains 80 sub-directories (one for each "base" problem). Each sub-directory contains the following groups of files:

      • There are 2 files that are required by the solver. These 2 files must be present in order to run the solver, as they are inputs to the heuristic:
        • tbl_locations.csv describes all nodes in the problem. nodeType 0 represents the depot, nodeType 1 represents a customer. The depot is always assigned to nodeID 0. Each node has a corresponding latitude and longitude (specified in degrees). The altitude is always 0. Customer nodes have a corresponding non-zero parcel weight (in [pounds]). There is no parcel associated with the depot.
        • tbl_truck_travel_data_PG.csv contains the directed truck travel time and distance information from one node to another. All time and distance values were obtained by pgRouting, using OpenStreetMaps data.
      • There is one map file:
        • map.html is a webpage showing the locations of all nodes (one depot and multiple customers) associated with this problem. This is for informational purposes only; it is neither an input to, nor an output from, the solvers.
      • Finally, there are multiple files that were generated by the solvers when we were preparing the mFSTSP-VDS paper. These are outputs from the solver (and are, therefore, not required before solving a problem).

        • Numerous files of the form tbl_solutions_<UAVtype>_<# of UAVs>_<UAVSpeedType>.csv, where

          • <UAVtype> indicates the maximum allowable speeds of the UAVs. This will be 101, 102, 103, or 104. See below for more information.
          • <# of UAVs> indicates the number of available UAVs. The mFSTSP-VDS paper considered 1-4 UAVs.
          • <UAVSpeedType> will be either maximum (if UAV speeds were fixed to their maximum allowable values, as in mFSTSP), or maximum-range (if UAV speeds were fixed to their maximum-range values), or variable (if UAV speeds were variable, as in mFSTSP-VDS).

          Each of these files contains details about solutions corresponding to a specified combination of <UAVtype>, <# of UAVs>, and <UAVSpeedType>.

   4. The Problems directory also contains four CSV files, of the form tbl_vehicles_<ID>.csv that provide information on UAV specifications, where:

      • ID 101: Maximum UAV speed is 10 m/s;
      • ID 102: Maximum UAV speed is 20 m/s;
      • ID 103: Maximum UAV speed is 30 m/s; and
      • ID 104: Maximum UAV speed is 40 m/s.

      Each test problem can be solved with any of these UAV specifications by specifying the appropriate command-line argument. This is described in the "Running the Solvers" section below.

2. Although there are numerous Python scripts in this repository, main.py is the only one you will directly interact with. This script makes use of the other Python scripts. See "Running the Solvers" below for instructions on generating solutions.

---

Installation and Setup

This section provides instructions for running the mFSTSP-VDS solver.

Compatability

The mFSTSP-VDS source code is compatible with both Python 2 and Python 3.
It has been tested on Windows, Linux, and Mac.

Prerequisites

• The heuristic requires Gurobi as the MILP solver.

• The pandas Python package is also required.

• For Linux/Mac, issue the following terminal command to install pandas:

  pip install pandas
  

  If you receive errors related to "access denied", try running sudo pip install pandas.

• For Windows, there are two options:

  1. If you installed Python through Anaconda, pandas is already included.
  2. Otherwise, enter the following at a command prompt:

     py -m pip install pandas
     

Download Problems and Source Code

There are two options for importing this repository's contents to your computer.

1. Download a .zip archive of the repository by either:

   • Clicking this link, or
   • Clicking the green "Code" button above and choosing "Download ZIP".

   In either case, unzip the archive on your computer to the location of your choice.

2. Use git from the command-line.

   1. Change directories to your preferred download location, replacing <the directory of your choice> with a path to that location:

   cd <the directory of your choice>   
   

   2. Clone the repository. This will create a directory named mFSTSP-VDS. Within that directory will be the entire contents of this repository.

   git clone https://github.com/optimatorlab/mFSTSP-VDS.git
   

Running the Solver

1. Open a terminal (command prompt) window.

2. Change directories to the location where the mFSTSP-VDS directory is saved.

   • For Linux/Mac: We will assume that you have downloaded the repository to a directory named mFSTSP-VDS within your Downloads directory. If you saved the mFSTSP-VDS directory elsewhere, you'll need to modify the paths below accordingly.

     cd ~/Downloads/mFSTSP-VDS
     

     (Your path will differ if you saved the repository contents to a different directory.)

   • For Windows: We will assume that you have downloaded the repository to a folder named mFSTSP-VDS on the "D:" drive. If you saved the mFSTSP-VDS directory elsewhere, you'll need to modify the paths below accordingly.

     D:
     cd mFSTSP-VDS
     

     (Your path will differ if you saved the repository contents to a different directory.)

3. The mFSTSP solvers are invoked by running the main.py Python script with 5 arguments. This will have the following structure:

   python main.py <problemName> <vehicleFileID> <UAVSpeedType> <numUAVs> <numTrucks>
   

   The command-line arguments, which must be specified in this order, are:

   • problemName - The name of the directory containing the data for a particular problem instance. This directory is in the format of a timestamp, and must exist within the Problems directory.
   • vehicleFileID - Indicates the maximum allowable speed of the UAVs. See the note above, which describes the definitions of 101, 102, 103, and 104.
   • UAVSpeedType - Indicates the type of UAV speed being considered in the problem. 1 indicates that the problem is being solved by considering variable UAV speeds, 2 indicates that the problem is being solved by considering UAV speeds equal to the maximum allowable speed, and 3 indicates that the problem is being solved by considering UAV speeds equal to the maximum-range speeds.
   • numUAVs - Number of UAVs available in the problem (e.g., 3).
   • numTrucks - Number of trucks available in the problem. The code currently only supports 1 truck. Assigning -1 to this argument ignores its value and considers 1 truck.

   Example 1 -- Solving the problem with variable UAV speeds (mFSTSP-VDS):

   python main.py 20191118T124843195400 101 1 3 -1
   

   Example 2 -- Solving the problem with maximum UAV speeds (mFSTSP):

   python main.py 20191118T124843195400 101 2 3 -1
   

4. The solver is finished when you receive a message like this in the terminal:

   See 'performance_summary.csv' for statistics.
   
   See 'Problems/20191118T124843195400/tbl_solutions_101_3_variable.csv' for solution summary.
   

   • The solver appends a row to the end of performance_summary.csv. This row contains the objective function value, total run time, number of customers assigned to the truck, number of customers assigned to UAVs, etc.

   • The solver also generates a file of the form tbl_solutions_<UAVtype>_<# of UAVs>_<UAVSpeedType>.csv. This file will appear within the subdirectory corresponding to the problemName within the Problems directory (e.g., Problems/20191118T124843195400) in the above example. The solutions file contains the objective function value and a detailed schedule for the truck and UAV(s).

     • NOTE: If you re-run the solver, solution details will be appended to the bottom of the applicable tbl_solutions_<UAVtype>_<# of UAVs>_<UAVSpeedType>.csv file.

---

Archived Problem Solutions

This repository contains solutions to the problem instances, as discussed in the analysis section of the mFSTSP-VDS paper.

performance_summary_archive.csv provides summary information about these solutions. This file contains the following columns:

• problemName - The name of the problem instance (written in the form of a timestamp). This is a subdirectory name within the Problems directory.
• vehicleFileID - Indicates the maximum speed of the UAVs (or the tbl_vehicles_<ID>.csv file that was used)
• numUAVs - # of UAVs available (1, 2, 3, or 4).
• UAVSpeedType - Indicates whether the problem was solved using maximum, maximum-range or variable UAV speeds.
• numTrucks - This can be ignored; it will always have a value of -1. However, in each problem there is actually exactly 1 truck.
• numCustomers - The total number of customers.
• timestamp - The time at which the problem was solved.
• ofv - The objective function value, as obtained by the given solution approach.
• totalTime - The total runtime of the heuristic.
• numUAVcust - The number of customers assigned to the UAV(s).
• numTruckCust - The number of customers assigned to the truck.
• waitingTruck - The amount of time, in [seconds], that the truck spends waiting on UAVs.
• waitingUAV - The amount of time, in [seconds], that the UAVs spend waiting on the truck.

performance_summary_archive.csv contains records for the following classes of problems: Each problem (there are 80 total) was run using four different settings of vehicleFileID (101, 102, 103, and 104) and four different settings of numUAVs (1, 2, 3, and 4). Each problem was solved using the maximum, the maximum-range, and the variable UAV speeds. This resulted in a total of 3840 problem solutions (80 * 4 * 4 * 3).

Details of each solution may be found in the applicable tbl_solutions_<UAVtype>_<# of UAVs>_<UAVSpeedType>.csv file contained within the problemName subdirectory of the Problems directory (e.g., Problems/20191118T124843195400).

When a problem is run again, using the same settings (e.g., the same vehicleFileID, numUAVs and UAVSpeedType), the solution details are appended to the applicable tbl_solutions_<UAVtype>_<# of UAVs>_<UAVSpeedType>.csv file.

---

Contact Info

For any queries, please send an email to [email protected].