Restrict NearestNeighbors version; remove debug statement

CHANGELOG.md

@@ -11,6 +11,13 @@ All notable changes to this project will be documented in this file.
 [semver]: https://semver.org/spec/v2.0.0.html
 [pkjjl]: https://pkgdocs.julialang.org/v1/compatibility/#compat-pre-1.0
 
+# [0.6.0] -- 2022-12-15
+### Added
+- Allow RELOG to calculate approximate driving distances, instead of just straight-line distances between points.
+
+### Fixed
+- Fix bug that caused building period parameter to be ignored
+
 ## [0.5.2] -- 2022-08-26
 ### Changed
 - Update to JuMP 1.x

Makefile

@@ -1,4 +1,4 @@
-VERSION := 0.5
+VERSION := 0.6
 
 clean:
 	rm -rfv build Manifest.toml test/Manifest.toml deps/formatter/build deps/formatter/Manifest.toml

Project.toml

@@ -1,7 +1,7 @@
 name = "RELOG"
 uuid = "a2afcdf7-cf04-4913-85f9-c0d81ddf2008"
 authors = ["Alinson S Xavier <axavier@anl.gov>"]
-version = "0.5.2"
+version = "0.6.0"
 
 [deps]
 CRC = "44b605c4-b955-5f2b-9b6d-d2bd01d3d205"
@@ -18,6 +18,7 @@ JSONSchema = "7d188eb4-7ad8-530c-ae41-71a32a6d4692"
 JuMP = "4076af6c-e467-56ae-b986-b466b2749572"
 LinearAlgebra = "37e2e46d-f89d-539d-b4ee-838fcccc9c8e"
 MathOptInterface = "b8f27783-ece8-5eb3-8dc8-9495eed66fee"
+NearestNeighbors = "b8a86587-4115-5ab1-83bc-aa920d37bbce"
 OrderedCollections = "bac558e1-5e72-5ebc-8fee-abe8a469f55d"
 Printf = "de0858da-6303-5e67-8744-51eddeeeb8d7"
 ProgressBars = "49802e3a-d2f1-5c88-81d8-b72133a6f568"
@@ -44,3 +45,4 @@ ProgressBars = "1"
 Shapefile = "0.8"
 ZipFile = "0.10"
 julia = "1"
+NearestNeighbors = "0.4"

README.md

@@ -15,14 +15,14 @@
 
 
 
-<img src="https://anl-ceeesa.github.io/RELOG/0.5/assets/ex_transportation.png" width="1000px"/>
+<img src="https://anl-ceeesa.github.io/RELOG/0.6/assets/ex_transportation.png" width="1000px"/>
 
 ### Documentation
 
-  * [Usage](https://anl-ceeesa.github.io/RELOG/0.5/usage)
-  * [Input and Output Data Formats](https://anl-ceeesa.github.io/RELOG/0.5/format)
-  * [Simplified Solution Reports](https://anl-ceeesa.github.io/RELOG/0.5/reports)
-  * [Optimization Model](https://anl-ceeesa.github.io/RELOG/0.5/model)
+  * [Usage](https://anl-ceeesa.github.io/RELOG/0.6/usage)
+  * [Input and Output Data Formats](https://anl-ceeesa.github.io/RELOG/0.6/format)
+  * [Simplified Solution Reports](https://anl-ceeesa.github.io/RELOG/0.6/reports)
+  * [Optimization Model](https://anl-ceeesa.github.io/RELOG/0.6/model)
 
 ### Authors
 
@@ -30,6 +30,7 @@
 * **Nwike Iloeje** <<ciloeje@anl.gov>>
 * **John Atkins**
 * **Kyle Sun**
+* **Audrey Gallier**
 
 ### License
 

docs/src/format.md

@@ -14,6 +14,7 @@ The **parameters** section describes details about the simulation itself.
 |:--------------------------|:---------------|
 |`time horizon (years)`     | Number of years in the simulation.
 |`building period (years)`  | List of years in which we are allowed to open new plants. For example, if this parameter is set to `[1,2,3]`, we can only open plants during the first three years. By default, this equals `[1]`; that is, plants can only be opened during the first year. |
+|`distance metric` | Metric used to compute distances between pairs of locations. Valid options are: `"Euclidean"`, for the straight-line distance between points; or `"driving"` for an approximated driving distance. If not specified, defaults to `"Euclidean"`.
 
 
 #### Example
@@ -21,7 +22,8 @@ The **parameters** section describes details about the simulation itself.
 {
     "parameters": {
         "time horizon (years)": 2,
-        "building period (years)": [1]
+        "building period (years)": [1],
+        "distance metric": "driving",
     }
 }
 ```
@@ -220,6 +222,7 @@ Database | Description | Examples
 * Plants can be expanded at any time, even long after they are open.
 * All material available at the beginning of a time period must be entirely processed by the end of that time period. It is not possible to store unprocessed materials from one time period to the next.
 * Up to two plant sizes are currently supported. Variable operating costs must be the same for all plant sizes.
+* Accurate driving distances are only available for the continental United States.
 
 ## Output Data Format (JSON)
 

docs/src/usage.md

@@ -7,7 +7,7 @@ To use RELOG, the first step is to install the [Julia programming language](http
 
 ```julia
 using Pkg
-Pkg.add(name="RELOG", version="0.5")
+Pkg.add(name="RELOG", version="0.6")
 ```
 
 After the package and all its dependencies have been installed, please run the RELOG test suite, as shown below, to make sure that the package has been correctly installed:

instances/s1.json

@@ -1,6 +1,7 @@
 {
     "parameters": {
-        "time horizon (years)": 2
+        "time horizon (years)": 2,
+        "distance metric": "driving"
     },
     "products": {
         "P1": {

src/RELOG.jl

@@ -5,19 +5,19 @@
 module RELOG
 
 include("instance/structs.jl")
-
 include("graph/structs.jl")
 
+include("instance/geodb.jl")
+include("graph/dist.jl")
 include("graph/build.jl")
 include("graph/csv.jl")
 include("instance/compress.jl")
-include("instance/geodb.jl")
 include("instance/parse.jl")
 include("instance/validate.jl")
 include("model/build.jl")
 include("model/getsol.jl")
-include("model/solve.jl")
 include("model/resolve.jl")
+include("model/solve.jl")
 include("reports/plant_emissions.jl")
 include("reports/plant_outputs.jl")
 include("reports/plants.jl")

src/graph/build.jl

@@ -2,14 +2,6 @@
 # Copyright (C) 2020, UChicago Argonne, LLC. All rights reserved.
 # Released under the modified BSD license. See COPYING.md for more details.
 
-using Geodesy
-
-function calculate_distance(source_lat, source_lon, dest_lat, dest_lon)::Float64
-    x = LLA(source_lat, source_lon, 0.0)
-    y = LLA(dest_lat, dest_lon, 0.0)
-    return round(euclidean_distance(x, y) / 1000.0, digits = 2)
-end
-
 function build_graph(instance::Instance)::Graph
     arcs = []
     next_index = 0
@@ -50,11 +42,12 @@ function build_graph(instance::Instance)::Graph
     # Build arcs from collection centers to plants, and from one plant to another
     for source in [collection_shipping_nodes; plant_shipping_nodes]
         for dest in process_nodes_by_input_product[source.product]
-            distance = calculate_distance(
+            distance = _calculate_distance(
                 source.location.latitude,
                 source.location.longitude,
                 dest.location.latitude,
                 dest.location.longitude,
+                instance.distance_metric,
             )
             values = Dict("distance" => distance)
             arc = Arc(source, dest, values)

src/graph/dist.jl

@@ -0,0 +1,57 @@
+# RELOG: Reverse Logistics Optimization
+# Copyright (C) 2020, UChicago Argonne, LLC. All rights reserved.
+# Released under the modified BSD license. See COPYING.md for more details.
+
+using Geodesy
+using NearestNeighbors
+using DataFrames
+
+function _calculate_distance(
+    source_lat,
+    source_lon,
+    dest_lat,
+    dest_lon,
+    ::EuclideanDistance,
+)::Float64
+    x = LLA(source_lat, source_lon, 0.0)
+    y = LLA(dest_lat, dest_lon, 0.0)
+    return round(euclidean_distance(x, y) / 1000.0, digits = 3)
+end
+
+function _calculate_distance(
+    source_lat,
+    source_lon,
+    dest_lat,
+    dest_lon,
+    metric::KnnDrivingDistance,
+)::Float64
+    if metric.tree === nothing
+        basedir = joinpath(dirname(@__FILE__), "..", "..", "data")
+        csv_filename = joinpath(basedir, "dist_driving.csv")
+
+        # Download pre-computed driving data
+        if !isfile(csv_filename)
+            _download_zip(
+                "https://axavier.org/RELOG/0.6/data/dist_driving_0b9a6ad6.zip",
+                basedir,
+                csv_filename,
+                0x0b9a6ad6,
+            )
+        end
+
+        # Fit kNN model
+        df = DataFrame(CSV.File(csv_filename))
+        coords = Matrix(df[!, [:source_lat, :source_lon, :dest_lat, :dest_lon]])'
+        metric.ratios = Matrix(df[!, [:ratio]])
+        metric.tree = KDTree(coords)
+    end
+
+    # Compute Euclidean distance
+    dist_euclidean =
+        _calculate_distance(source_lat, source_lon, dest_lat, dest_lon, EuclideanDistance())
+
+    # Predict ratio
+    idxs, _ = knn(metric.tree, [source_lat, source_lon, dest_lat, dest_lon], 5)
+    ratio_pred = mean(metric.ratios[idxs])
+    return round(dist_euclidean * ratio_pred, digits = 3)
+end

src/instance/parse.jl

@@ -23,8 +23,20 @@ function parse(json)::Instance
     validate(json, Schema(json_schema))
 
     building_period = [1]
-    if "building period (years)" in keys(json)
-        building_period = json["building period (years)"]
+    if "building period (years)" in keys(json["parameters"])
+        building_period = json["parameters"]["building period (years)"]
+    end
+
+    distance_metric = EuclideanDistance()
+    if "distance metric" in keys(json["parameters"])
+        metric_name = json["parameters"]["distance metric"]
+        if metric_name == "driving"
+            distance_metric = KnnDrivingDistance()
+        elseif metric_name == "Euclidean"
+            # nop
+        else
+            error("Unknown distance metric: $metric_name")
+        end
     end
 
     plants = Plant[]
@@ -176,5 +188,12 @@ function parse(json)::Instance
     @info @sprintf("%12d collection centers", length(collection_centers))
     @info @sprintf("%12d candidate plant locations", length(plants))
 
-    return Instance(T, products, collection_centers, plants, building_period)
+    return Instance(
+        T,
+        products,
+        collection_centers,
+        plants,
+        building_period,
+        distance_metric,
+    )
 end

src/instance/structs.jl

@@ -48,10 +48,21 @@ mutable struct Plant
     storage_cost::Vector{Float64}
 end
 
+
+abstract type DistanceMetric end
+
+Base.@kwdef mutable struct KnnDrivingDistance <: DistanceMetric
+    tree = nothing
+    ratios = nothing
+end
+
+mutable struct EuclideanDistance <: DistanceMetric end
+
 mutable struct Instance
     time::Int64
     products::Vector{Product}
     collection_centers::Vector{CollectionCenter}
     plants::Vector{Plant}
     building_period::Vector{Int64}
+    distance_metric::DistanceMetric
 end

src/schemas/input.json

@@ -14,6 +14,9 @@
             "properties": {
                 "time horizon (years)": {
                     "type": "number"
+                },
+                "distance metric": {
+                    "type": "string"
                 }
             },
             "required": [

test/graph/build_test.jl

@@ -21,7 +21,7 @@ using RELOG
     @test node.outgoing_arcs[1].source.location.name == "C1"
     @test node.outgoing_arcs[1].dest.location.plant_name == "F1"
     @test node.outgoing_arcs[1].dest.location.location_name == "L1"
-    @test node.outgoing_arcs[1].values["distance"] == 1095.62
+    @test node.outgoing_arcs[1].values["distance"] == 1695.364
 
     node = process_node_by_location_name["L1"]
     @test node.location.plant_name == "F1"

test/graph/dist_test.jl

@@ -0,0 +1,25 @@
+# RELOG: Reverse Logistics Optimization
+# Copyright (C) 2020, UChicago Argonne, LLC. All rights reserved.
+# Released under the modified BSD license. See COPYING.md for more details.
+
+using RELOG
+
+@testset "KnnDrivingDistance" begin
+    # Euclidean distance between Chicago and Indianapolis
+    @test RELOG._calculate_distance(
+        41.866,
+        -87.656,
+        39.764,
+        -86.148,
+        RELOG.EuclideanDistance(),
+    ) == 265.818
+
+    # Approximate driving distance between Chicago and Indianapolis
+    @test RELOG._calculate_distance(
+        41.866,
+        -87.656,
+        39.764,
+        -86.148,
+        RELOG.KnnDrivingDistance(),
+    ) == 316.43
+end

test/runtests.jl

@@ -11,6 +11,7 @@ using Test
     end
     @testset "Graph" begin
         include("graph/build_test.jl")
+        include("graph/dist_test.jl")
     end
     @testset "Model" begin
         include("model/build_test.jl")