heumilkr

R package implementing the Clarke-Wright algorithm to find a quasi-optimal solution to the Capacitated Vehicle Routing Problem.

https://github.com/lschneiderbauer/heumilkr

Keywords

Repository

R package implementing the Clarke-Wright algorithm to find a quasi-optimal solution to the Capacitated Vehicle Routing Problem.

README.Rmd

---
output: github_document
bibliography: references.bib
link-citations: true
---



```{r, include = FALSE}
knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>",
  fig.path = "man/figures/README-",
  out.width = "100%",
  dpi = 300
)
```

# heumilkr



[![R-CMD-check](https://github.com/lschneiderbauer/heumilkr/actions/workflows/R-CMD-check.yaml/badge.svg)](https://github.com/lschneiderbauer/heumilkr/actions/workflows/R-CMD-check.yaml) [![Codecov test coverage](https://codecov.io/gh/lschneiderbauer/heumilkr/branch/master/graph/badge.svg)](https://app.codecov.io/gh/lschneiderbauer/heumilkr?branch=master) [![Lifecycle: experimental](https://img.shields.io/badge/lifecycle-experimental-orange.svg)](https://lifecycle.r-lib.org/articles/stages.html#experimental) [![CRAN status](https://www.r-pkg.org/badges/version/heumilkr)](https://CRAN.R-project.org/package=heumilkr)



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()
```

Owner

GitHub Events

Issues and Pull Requests

Last synced: 10 months ago

Packages