Skip to content

jmarca/initial-solution

master
Switch branches/tags
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
 
 
src
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Open Solver Initial Solution

Build Status Maintainability Test Coverage

This solver generates an initial solution to the problem of routing freight vehicles between cities while still respecting Hours of Service (HOS) regulations. The vehicles are fully loaded, meaning it is a Truck Load Routing problem, with trucks having only one delivery point for their full load.

The python code here reads in the CSV input file, sets up a call to Google's OR-Tools routing solver, and then writes out that solution as a CSV file. While hopefully this initial solution is pretty good, it is the job of downstream solvers to read in this initial solution and improve it.

Docker setup

This project is easiest to run from within the Docker container that can be build based on the Dockerfile. To do this, change into the Docker directory and execute the build command:

docker build -t jmarca/initial_solution .

This will build an image based on the official Python Docker image that includes the latest version of OR Tools version 7.0 at this time.

To use the solver in this image, you have to create a container and tell it how to find your data and code. From the root of this project, you can do this:

docker run -it \
           --rm \
	       -v /etc/localtime:/etc/localtime:ro \
           --name routing_initial_solution \
           -v ${PWD}:/work \
           -w /work \
           jmarca/initial_solution bash

This will create a container and link the current working directory (${PWD}) to the /work directory inside of the container. From within the container, you can then run all the commands you would expect from the bash command line prompt.

If you want to run code in the container but not spawn a bash prompt, you can do something like this, assuming you have code in src and data in data directories:

docker run -it \
           --rm \
	       -v /etc/localtime:/etc/localtime:ro \
           --name routing_initial_solution \
           -v ${PWD}:/work \
           -w /work \
           jmarca/initial_solution python src/run.py -i data/input.csv -o solution.csv

Non-Docker setup

If you do not have Docker, then you can install all of the dependencies globally using pip.

sudo python -m pip install -U ortools

Or install locally for just your user:

python -m pip install -U --user ortools

For non-linux platforms, the approach is the same. See https://developers.google.com/optimization/install/python/ for details. For example, on windows assuming you have python 3.7 installed, from a command line prompt you can run:

python -m pip install --user ortools

Just guessing here, but if you're running conda, you'll need to install pip first. See https://docs.conda.io/projects/conda/en/latest/user-guide/tasks/manage-pkgs.html?highlight=pip#installing-non-conda-packages

For example, something like (untested)

conda install pip
pip install ortools

Run solver

master branch

There are two executables that can be run: src/run_initial_routes.py and src/run_without_constraints.py.

python src/run_initial_routes.py -h
usage: run_initial_routes.py [-h] [-m,--matrixfile MATRIXFILE]
                             [-d,--demandfile DEMAND]
                             [-o,--vehicleoutput VEHICLE_OUTPUT]
                             [--demandoutput DEMAND_OUTPUT]
                             [--summaryoutput SUMMARY_OUTPUT] [--speed SPEED]
                             [--maxtime HORIZON] [-v,--vehicles NUMVEHICLES]
                             [--pickup_time PICKUP_TIME]
                             [--dropoff_time DROPOFF_TIME]
                             [-t, --timelimit TIMELIMIT]
                             [--narrow_destination_timewindows DESTINATION_TIME_WINDOWS]
                             [--drive_dim_start_value DRIVE_DIMENSION_START_VALUE]
                             [--debug DEBUG]

Solve assignment of truck load routing problem, give hours of service rules
and a specified list of origins and destinations

optional arguments:
  -h, --help            show this help message and exit
  -m,--matrixfile MATRIXFILE
                        CSV file for travel matrix (distances)
  -d,--demandfile DEMAND
                        CSV file for demand pairs (origin, dest, time windows)
  -o,--vehicleoutput VEHICLE_OUTPUT
                        CSV file for dumping output
  --demandoutput DEMAND_OUTPUT
                        CSV file for dumping output for demand details
                        (including invalid demands, etc)
  --summaryoutput SUMMARY_OUTPUT
                        A file for dumping the human-readable summary output
                        for the assignment
  --speed SPEED         Average speed, miles per hour. Default is 55 (miles
                        per hour). Distance unit should match that of the
                        matrix of distances. The time part should be per hours
  --maxtime HORIZON     Max time in minutes. Default is 10080 minutes, which
                        is 7 days.
  -v,--vehicles NUMVEHICLES
                        Number of vehicles to create. Default is 100.
  --pickup_time PICKUP_TIME
                        Pick up time in minutes. Default is 15 minutes.
  --dropoff_time DROPOFF_TIME
                        Drop off time in minutes. Default is 15 minutes.
  -t, --timelimit TIMELIMIT
                        Maximum run time for solver, in minutes. Default is 5
                        minutes.
  --narrow_destination_timewindows DESTINATION_TIME_WINDOWS
                        If true, limit destination node time windows based on
                        travel time from corresponding origin. If false,
                        destination nodes time windows are 0 to args.horizon.
                        Default true (limit the time window).
  --drive_dim_start_value DRIVE_DIMENSION_START_VALUE
                        Due to internal solver mechanics, the drive dimension
                        can't go below zero (it gets truncated at zero). So to
                        get around this, the starting point for the drive time
                        dimension has to be greater than zero. The default is
                        1000. Change it with this variable
  --debug DEBUG         Turn on some print statements.

The run_without_constraints.py options are similar. The main difference between the two is that run_without_constraints.py will solve the assignment problem without including any breaks at all. The below text refers to the run_initial_routes.py program, but aside from break-specific aspects, the same comments apply to the without constraints program.

Many of these options tweak things that influence the travel times, such as the speed and the pickup and drop off times. Others are related to the internals of the solver (--narrow_destination_timewindows and --drive_dim_start_value) and probably should not be changed.

A typical solver run allowing the solver 10 minutes to think is as follows:

 python src/run_initial_routes.py -m data/distance_matrix.csv --speed 65 -d data/demand.csv -t 10 -v 75  --maxtime 20000  --summaryoutput out.txt

In this case only 75 vehicles are used, because many of the trips are difficult to serve with a speed of 65mph, because the arrival time at the pickup node is after the closing of the pickup time window.

The human-readable output in this case is also very long, and will probably scroll past the screen. In that case, you can pass a file to "--summaryoutput", as was done here.

The program will always dump two csv files. The first is a per vehicle file that shows the vehicle usage. For example:

demand,distance,location,order,time,veh
0,0,0,0,2107,0
0,357,-1,1,2437,0
0,357,-1,2,2797,0
0,357,-1,3,3727,0
0,357,-1,4,4087,0
1,187,29,5,4860,0
0,357,-1,6,5205,0
0,357,-1,7,5565,0
0,357,-1,8,6495,0
0,357,-1,9,6855,0
0,164,-1,10,7607,0
0,165,-1,11,7790,0
-1,331,33,12,8696,0
0,357,-1,13,9041,0
0,357,-1,14,9401,0
0,357,-1,15,10331,0
0,357,-1,16,10691,0
0,194,0,17,11471,0

The second is a file showing the output from the perspective of the demand items. For example:

dropoff_distance,dropoff_node,dropoff_order,dropoff_time,pickup_distance,pickup_node,pickup_order,pickup_time,veh
331,33,12,8696,187,29,5,4860,0

The names of these files default to demand_output{_N}.csv and vehicle_output{_N}.csv. If there are collisions with previously written files, the N part will be incremented by one.

Tests

The tests are woefully out of date. When they weren't out of date, coverage was pretty good, but at this point the tests most likely won't even run properly.

Tests are run with pytest.

pytest --cov=src
==================== test session starts ============================
platform linux -- Python 3.7.3, pytest-4.5.0, py-1.8.0, pluggy-0.11.0
rootdir: /work, inifile: setup.cfg
plugins: cov-2.7.1
collected 13 items

test/test_breaks.py ......                                     [ 46%]
test/test_demand.py .                                          [ 53%]
test/test_evaluators.py .                                      [ 61%]
test/test_output.py .                                          [ 69%]
test/test_read_csv.py ...                                      [ 92%]
test/test_vehicles.py .                                        [100%]

----------- coverage: platform linux, python 3.7.3-final-0 -----------
Name                             Stmts   Miss  Cover
----------------------------------------------------
src/break_node.py                   18      2    89%
src/breaks.py                      120      5    96%
src/demand.py                      260     35    87%
src/evaluators.py                  192     79    59%
src/initial_routes.py              205     90    56%
src/model_run.py                   191     34    82%
src/read_csv.py                     11      0   100%
src/run_initial_routes.py           60     44    27%
src/run_without_constraints.py      62     46    26%
src/solution_output.py             303    165    46%
src/vehicles.py                     11      0   100%
----------------------------------------------------
TOTAL                             1433    500    65%

=================== 13 passed in 22.88 seconds =======================

The coverage isn't great, but at least they're passing.

About

Open Solver Initial Solution

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published