Avicena is an application that solves the patient pickup and dropoff problem. Below is a rough description of the problem's attributes:
- There are some number of patients that must be transported from one location to one or more other locations through out the day, and there are some number of drivers available to complete the trips.
- For each leg of their trip a patient must be picked up from their starting location within a time window of the scheduled pickup time, and they must be dropped off no later than a short time interval after the scheduled dropoff time.
- Some trips known as "merge" trips mean that a patient has two back to back trips. These trips often indicate short visits to the pharmacy to pick up prescriptions. Therefore, the same driver must complete both legs.
- Some patients require wheelchair support in their vehicles, which only a subset of the drivers can provide. Drivers can only transport patients for which their vehicle is equipped.
- All drivers should receive approximately the same compensation, and all wheelchair drivers should receive a approximately the same number of wheelchair bound trips.
- Drivers are split into two groups. A group that begins before a designated "early day time" on Mondays, Wednesdays, and Fridays and another group that begins before the "early day time" on Tuesdays, Thursdays, and Saturdays. If there is a day where all drivers are from the same group, a part of the drivers will be randomly selected to temporarily be part of the second group.
- The goal is to minimize the total amount of time spent traveling on the road while ensuring to meet all of driver fairness requirements and trip scheduling requirements.
In general, the patient pickup and dropoff problem is a special case of the Vehicle Routing with Time Windows problem. However, here we have additional constraints that take into account the preferences and fairness attributes for the drivers.
Make sure IBM CPLEX Solver is installed. Use the following link: CPLEX Follow the instructions on the website to prepare the CPLEX Installation with usage for Python. Make sure you do not re-install CPLEX using PIP or it will overwrite the licensed version from IBM. However, if you are unable to obtain a CPLEX license, PIP will install a community version of CPLEX. (Warning: the community version will likely only support on the order of 2 drivers and 7-10 trips)
Setup prerequisites
cd ~/Downloads
chmod 755 cplex_studio1210.linux-x86-64.bin
./cplex_studio1210.linux-x86-64.bin
sudo apt-get install postgresql postgresql-server-dev-all
sudo -u postgres createuser -P -d -r -s pickup
sudo -u postgres createdb -O pickup pickup
Setup python app
git clone https://github.com/ribsthakkar/RiderPickup
cd RiderPickup/
python3 -m virtualenv ~/.riderpickup
source ~/.riderpickup/bin/activate
python3 -m pip install -r requirements.txt
python setup.py develop
python /opt/ibm/ILOG/CPLEX_Studio1210/python/setup.py install
config/sample_app_config.yaml provides an example configuration YAML.
A configuration file of this format must be placed at the path
config/app_config.yaml to run the application. Below is a glossary of
the application configuration parameters.
Note the "." syntax below just indicates that the field after the "."
is a child parameter of the field before the "." See the
config/sample_app_config.yaml for proper format.
| Parameter | Type | Details |
|---|---|---|
| database.enabled | Boolean | True if input data such as revenue table, merge addresses, driver table will come from database. Otherwise it uses CSVs with paths below |
| database.url | String | URL to PostgreSQL database. Ignored if database.enabled is False |
| geocoder_key | String | API Key for geocoding. Currently only support OpenCage Geocoder |
| trips_parser | String | Parser used to read the incoming trips file. See more here |
| optimizer | String | Model used to calculate and assign trips. See more details below. |
| seed | Integer | Sets the Python random seed. |
| merge_address_table_path | String | Path to CSV representation of merge_address_table. Ignored if database.enabled is True. |
| revenue_table_path | String | Path to CSV representation of revenue rate. Ignored if database.enabled is True. |
| driver_table_path | String | Path to CSV representation of drivers table. Ignored if database.enabled is True. |
| output_directory | String | Path to directory where the generated files are stored. These include the one or more parsed trips file (depending on parser), the resulting CSV with the solution, and an HTML page that provides a visualization of the solution. |
In addition to the app_config.yaml, you will need to provide a
config/optimizer_config.yaml. This configuration file provides the
configuration for optimizer model (specified in the app_config.yaml)
used to solve the problem. Below is a list of supported optimizers and
their configuration definitions. Samples are also provided in the
config/ folder.
| Optimizer | Configuration Details | Comments |
|---|---|---|
| GeneralOptimizer | Glossary | Self Developed Formulation to Solve Problem |
| PDWTWOptimizer | Glossary | (Not working in non-experimental mode yet) Formulation from following paper with additional fairness constraints integrated here |
Finally, the app will need a log_config.yaml with details about how
and what kind of logging we expect from the application. Information
about how to setup the log config can be found at Python's logging
module documentation.
For simplicity, a copy of the sample_log_config.yaml will suffice.
The command-line application supports interfacing with a PostgreSQL
database. We assume you have a PostgreSQL server hosted somewhere with a
configured username and login. If in the database section in your
config/app_config.yaml the "enabled" flag is set to True, Avicena will
poll inputs such as the merge address table, the revenue rates table,
and the drivers table from the database. Therefore it is assumed that
the data is already in your database. Follow the instructions below to
setup the database
The database is versioned by alembic. In order to generate the initial
tables in your database, make a copy of sample_alembic.ini in the same
directory and name it alembic.ini. Modify the line in the file
starting with sqlalchemy.url = <fake_url> and replace <fake_url> the
URL to connect to your database. Be sure that the URL of the database
will be the same one used in the app_config.yaml.
Run the command:
alembic upgrade head
After that, the database tables should be created.
Once the tables are created, the revenue_rate, merge_details, and
driver tables must be populated with data. In order to help populate
your database with the required inputs, a script
avi-import is provided. It can be run as follows:
usage: avi-import [-h] -r REVENUE_TABLE_FILE -m MERGE_DETAILS_FILE -d
DRIVER_DETAILS_FILE
Populate Database with Base Information needed including Revenue Table, Merge
Address Details, and Driver Details.
optional arguments:
-h, --help show this help message and exit
required arguments:
-r REVENUE_TABLE_FILE, --revenue-table-csv REVENUE_TABLE_FILE
Path to revenue table CSV
-m MERGE_DETAILS_FILE, --merge-details-csv MERGE_DETAILS_FILE
Path to merge details CSV
-d DRIVER_DETAILS_FILE, --driver-details-csv DRIVER_DETAILS_FILE
Path to driver details CSV
The three input CSV files must follow the same format and header as
shown by sample_data/sample_rev_table.csv,
sample_data/sample_merge_details.csv, and
sample_data/sample_drivers.csv.
Avicena is run through the command line by simply following the format
below. If the database is enabled in the application configuration, then
the resulting dispatch "Assignment" and its driver specific solutions
"DriverAssignment", will be stored in the database. In the output
directory you will find any files generated during the model's running.
At the least, they include parsed_trips.csv with the basic trip
details standarized and parsed from the original trips file,
solution.csv with the final dispatch assignments, visualization.html
which provides a visual representation of the final solution.
usage: avi-cli [-h] [-n NAME] [-s SPEED] [-d DATE] [-t TRIPS_FILE]
[-i DRIVER_IDS [DRIVER_IDS ...]]
Run the Patient Dispatch Model
optional arguments:
-h, --help show this help message and exit
required arguments:
-n NAME, --name NAME Name of Model
-s SPEED, --speed SPEED
Assumed Traveling Speed in MPH
-d DATE, --date DATE Date in MM-DD-YYYY format
-t TRIPS_FILE, --trips-file TRIPS_FILE
Path to Trips File
-i DRIVER_IDS [DRIVER_IDS ...], --driver-ids DRIVER_IDS [DRIVER_IDS ...]
List of driver IDs separated by spaces