The Multiple Flying Sidekicks Traveling Salesman Problem (mFSTSP)

This repository provides a collection of mFSTSP test problems, as well as the source code to solve mFSTSP instances. The mFSTSP is a variant of the classical TSP, in which one or more UAVs coordinate with a truck to deliver parcels in the minimum possible time. The code provided here consists of both the mixed integer linear programming (MILP) implementation and a heuristic to solve larger problems.

The repository accompanies the following paper, which is currently undergoing a second round of reviews:

C. Murray and R. Raj, The Multiple Flying Sidekicks Traveling Salesman Problem: Parcel Delivery with Multiple Drones (July 27, 2019). Available at SSRN: https://ssrn.com/abstract=3338436 or http://dx.doi.org/10.2139/ssrn.3338436

The paper provides details on the mFSTSP definition, a corresponding MILP formulation, and the heuristic.

mFSTSP Repository Contents

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

A collection of test problems (and solutions) that were used in the analysis described in the mFSTSP paper.
1. problems_info.csv contains a summary of all 100 "base" test problems, including:
  - numCust: Total number of customers.
  - city: Geographic region (Buffalo, NY or Seattle, WA).
  - 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 rectangel.
  - 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, or problems in Seattle).
2. performance_summary_archive.csv provides information about solutions generated for each test problem in the mFSTSP paper. See the "Archived Problem Solutions" section below for details on the contents of this file.
  - NOTE: performance_summary.csv is an empty/placeholder file. It will be populated only if/when you run the solver code. This file currently exists solely to initialize the column headings.
3. The Problems directory contains 100 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 either the MILP model or 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 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 file that was created by our "problem generator":
    - 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 (MILP, heuristic, or both) when we were preparing the mFSTSP 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>_<solutionMethod>.csv, where
      - <UAVtype> indicates the speed and range 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 paper considered 1-4 UAVs.
      - <solutionMethod> will be either IP (if Gurobi was used to solve the MILP) or Heuristic (if the heuristic was employed).
      Each of these files contains details about solutions corresponding to a specified combination of <UAVtype>, <# of UAVs>, and <solutionMethod>.
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: High speed, low range;
  - ID 102: High speed, high range;
  - ID 103: Low speed, low range; and
  - ID 104: Low speed, high range.
  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.
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 two mFSTSP solvers (either an exact MILP or a heuristic).

Compatability

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

Prerequisites

Both the exact and heuristic methods require 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.

Download a .zip archive of the repository by either:
- Clicking this link, or
- Clicking the green "Clone or download" button above and choosing "Download ZIP".
In either case, unzip the archive on your computer to the location of your choice.
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>   
```
1. Clone the repository. This will create a directory named mFSTSP. Within that directory will be the entire contents of this repository.
```
git clone https://github.com/optimatorlab/mFSTSP.git
```

Running the Solvers

Open a terminal (command prompt) window.
Change directories to the location where the mFSTSP directory is saved.
- For Linux/Mac: We will assume that you have downloaded the repository to a directory named mFSTSP within your Downloads directory. If you saved the mFSTSP directory elsewhere, you'll need to modify the paths below accordingly.
```
cd ~/Downloads/mFSTSP
```
  (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 on the "D:" drive. If you saved the mFSTSP directory elsewhere, you'll need to modify the paths below accordingly.
```
D:
cd mFSTSP
```
  (Your path will differ if you saved the repository contents to a different directory.)
The mFSTSP solvers are invoked by running the main.py Python script with 10 arguments. This will have the following structure:
```
python main.py <problemName> <vehicleFileID> <cutoffTime> <problemType> <numUAVs> <numTrucks> <requireTruckAtDepot> <requireDriver> <Etype> <ITER>
```
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 speed and range of the UAVs. See the note above, which describes the definitions of 101, 102, 103, and 104.
- cutoffTime - The maximum allowable runtime, in [seconds]. If the problem is to be solved via heuristic, this value represents the maximum runtime of Phase 3. A cutoff time of -1 indicates that the solver should ignore any runtime limits.
- problemType - Indicates if the problem is to be solved via the exact MILP formulation (1) or via the heuristic (2).
- numUAVs - Number of UAVs available in the problem (e.g., 3).
- `numTr

MFSTSP

Install / Use

README