Skip to main content

CVRPTW Optimization Models

Project description

Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) Optimization Models

Repo for CVRPTW optimization models.

Prerequisites

Install requirements.txt for prerequisites.

conda create --name cvrptw_optimization --file requirements.txt

Install environment.yml for prerequisites.

conda env create -f environment.yml

To recreate environment.yml

conda env export > environment.yml

To create requirements.txt from environment.yml

pip freeze > requirements.txt

Installation

pip install cimren-cvrptw-optimization

Tips

Convert pandas data frame to dictionary.

df.set_index("ID", drop=True, inplace=True)
dictionary = df.to_dict(orient="index")

Models

Descrochers et al.1988

Desrochers, M., Lenstra, J.K., Savelsbergh, M.W.P., Soumis, F. (1988).
Vehicle routing with time windows: Optimization and approximation.
In: Golden, B.L., Assad, A.A. (Eds.), Vehicle Routing: Methods and Studies. North-Holland, Amsterdam, pp. 65–84.

Inputs

Depot

Data frame for inputs.

LOCATION_NAME LATITUDE LONGITUDE
Depot 36.1627 -86.7816

Locations

Data frame of locations for routing.

LOCATION_NAME LATITUDE LONGITUDE TW_START_MINUTES TW_END_MINUTES STOP_TIME_WH_HELPER STOP_TIME_W_HELPER DEMAND
Loc 1 35.9021 -84.1508 960 1950 27 21 1
Loc 2 35.7498 -83.9922 960 1950 27 21 1
Loc 3 35.9077 -83.8392 960 1950 27 21 1
Loc 4 35.9077 -83.8392 960 1950 27 21 1
Loc 5 35.8625 -84.0666 960 1950 27 21 1

Transportation Matrix

Data frame of drive minutes.

FROM_LOCATION_NAME TO_LOCATION_NAME FROM_LATITUDE FROM_LONGITUDE TO_LATITUDE TO_LONGITUDE DRIVE_MINUTES
Depot Depot 36.1627 -86.7816 36.1627 -86.7816 0
Depot Loc 1 36.1627 -86.7816 35.9021 -84.1508 163.85
Depot Loc 2 36.1627 -86.7816 35.7498 -83.9922 206.06
Depot Loc 3 36.1627 -86.7816 35.9077 -83.8392 210.03
Depot Loc 4 36.1627 -86.7816 35.9077 -83.8392 210.03

Vehicles

Data frame for vehicles.

TEAM='assign' if route uses a team truck. TEAM='not assign' if route does not use a team truck. TEAM='select' if model decides using a team truck or not.

HELPER='assign' if route uses a team truck. HELPER='not assign' if route does not use a team truck. HELPER='select' if model decides using a team truck or not.

Note that if TEAM='assign', then HELPER='assign' automatically.

VEHICLE_NAME CAPACITY HELPER_COST_PER_HELPER_PER_ROUTE MAXIMUM_SOLO_TRAVEL_HOURS MAXIMUM_TEAM_TRAVEL_HOURS TEAM HELPER TEAM_COST_PER_TEAM_PER_ROUTE TRANS_COST_PER_MINUTE TYPE
Vehicle 1 20 1200 12 20 assign assign 2000 5 48 FOOTER TRUCK

Sample Data

Package has a sample data set

from cvrptw_optimization.src import data
data.depot
data.locations
data.transportation_matrix
data.vehicles

How to use

To be able run an Or Tools model:

from cvrptw_optimization.src import data
from cvrptw_optimization import desrochers_et_all_1988 as d
d.run_desrochers_et_all_1988(data.depot,
                             data.locations,
                             data.transportation_matrix,
                             data.vehicles,
                             solver_time_limit_mins=1,
                             mip_gap = 0,
                             solver='or tools')

To be able run a Gurobi model:

from cvrptw_optimization.src import data
from cvrptw_optimization import desrochers_et_all_1988 as d
d.run_desrochers_et_all_1988(data.depot,
                             data.locations,
                             data.transportation_matrix,
                             data.vehicles,
                             solver_time_limit_mins=1,
                             mip_gap = 0,
                             solver='gurobi')

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for cimren-cvrptw-optimization, version 1.1.3
Filename, size File type Python version Upload date Hashes
Filename, size cimren_cvrptw_optimization-1.1.3-py3-none-any.whl (29.3 kB) File type Wheel Python version py3 Upload date Hashes View
Filename, size cimren-cvrptw-optimization-1.1.3.tar.gz (25.0 kB) File type Source Python version None Upload date Hashes View

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page