-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathREADME.Rmd
128 lines (98 loc) · 4.14 KB
/
README.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
---
output: github_document
bibliography: references.bib
link-citations: true
---
<!-- README.md is generated from README.Rmd. Please edit that file -->
```{r, include = FALSE}
knitr::opts_chunk$set(
collapse = TRUE,
comment = "#>",
fig.path = "man/figures/README-",
out.width = "100%",
dpi = 300
)
```
# heumilkr
<!-- badges: start -->
[](https://github.com/lschneiderbauer/heumilkr/actions/workflows/R-CMD-check.yaml) [](https://app.codecov.io/gh/lschneiderbauer/heumilkr?branch=master) [](https://lifecycle.r-lib.org/articles/stages.html#experimental) [](https://CRAN.R-project.org/package=heumilkr)
<!-- badges: end -->
This R package provides an implementation of the Clarke-Wright algorithm [@clarke1964] to find a quasi-optimal solution to the [Capacitated Vehicle Routing Problem](https://en.wikipedia.org/wiki/Vehicle_routing_problem).
## Installation
You can install the latest CRAN release of heumilkr with:
``` r
install.packages("heumilkr")
```
Alternatively, you can install the development version of heumilkr from [GitHub](https://github.com/) with:
``` r
# install.packages("devtools")
devtools::install_github("lschneiderbauer/heumilkr")
```
## Example
The following example generates random demands at random locations, defines two vehicle types, applies the Clarke-Wright algorithm to generate quasi-optimal vehicle runs, and shows the resulting vehicle run solution.
```{r example}
library(heumilkr)
set.seed(42)
# generating random demand
demand <- runif(20, 5, 15)
# generating random site positions
positions <-
data.frame(
pos_x = c(0, runif(length(demand), -10, 10)),
pos_y = c(0, runif(length(demand), -10, 10))
)
solution <-
clarke_wright(
demand,
dist(positions),
# We have an infinite number of vehicles with capacity 33 available,
# and two vehicles with capacity 44.
data.frame(n = c(NA_integer_, 2L), caps = c(33, 44))
)
print(solution)
# returns the total cost / distance
# (the quantity that is minimized by CVRP)
print(milkr_cost(solution))
# returns the savings resulting from the heuristic optimization procedure
print(milkr_saving(solution))
```
A plotting function (using [ggplot](https://ggplot2.tidyverse.org/)) for the result is built in. The individual runs are distinguished by color. The demanding site locations are marked with round circles while the (single) supplying site is depicted as a square. The line types (solid/dashed/...) are associated to different vehicle types.
```{r example_plot}
plot(solution)
```
## Runtime Benchmarks
```{r benchmark_calc, echo=FALSE, message=FALSE, warning=FALSE}
library(bench) # we load that so that the below gets correctly formatted
result <- readRDS(paste0("./benchmark/", readLines("./benchmark/last_result.txt")))
time <- \(n) format(result$median[result$n == n])
library(ggplot2)
library(dplyr)
```
The benchmarks were taken on an Intel® Xeon® CPU E3-1231 v3 \@ 3.40GHz CPU, using the R package [bench](https://bench.r-lib.org/).
The following graph shows the run time behavior as the number of sites $n$ increase. The curve exhibits near-cubic behavior in $n$. For $n = 110$ the performance is still relatively reasonable with a run time of $\sim `r time(110)`$.
```{r benchmark_runtime, echo = FALSE}
result |>
mutate(
ymin = as.numeric(mean - std),
ymax = as.numeric(mean + std),
median = as.numeric(median)
) |>
ggplot(aes(x = n, y = median, ymin = ymin, ymax = ymax)) +
scale_x_continuous(
name = "Number of demanding sites",
labels = scales::label_number(
scale_cut = scales::cut_long_scale()
)
) +
scale_y_continuous(
name = "Runtime (in seconds)",
labels = scales::label_number(
suffix = "s",
scale_cut = scales::cut_long_scale()
)
) +
geom_ribbon(alpha = 0.3, linewidth = 0) +
geom_point() +
geom_line() +
theme_bw()
```