heumilkr

heumilkr provides an implementation of the Clarke-Wright algorithm (Clarke and Wright 1964) to find a quasi-optimal solution to the Capacitated Vehicle Routing Problem. It is available as an R package and as a Python package, which share the same C++ core.

Besides deliveries, it also supports “backhaul”: sites with negative demand have goods picked up and brought back to the depot, in any order within a run as long as the load stays within the vehicle capacity.

For a fixed number of vehicle types, the run time grows at best quadratically and at worst cubically with the number of sites $n$. On the problems we tested with randomly placed sites and up to 4000 sites, it grew roughly like $n^{2}$ to $n^{2.1}$, and roughly like $n^{3}$ if a limited vehicle type repeatedly runs out (see Runtime Benchmarks).

Installation

R

You can install the latest CRAN release of heumilkr with:

install.packages("heumilkr")

Alternatively, you can install the development version of heumilkr from GitHub with:

# install.packages("devtools")
# devtools::install_github("lschneiderbauer/heumilkr")
install.packages("heumilkr", repos = c('https://lschneiderbauer.r-universe.dev', 'https://cloud.r-project.org'))

Python

You can install the latest PyPI release of heumilkr with:

pip install heumilkr

Alternatively, you can install the development version of heumilkr from GitHub, which requires a C++ compiler, with:

pip install git+https://github.com/lschneiderbauer/heumilkr

The only dependency is NumPy. Install heumilkr[pandas] to also get pandas for Solution.to_pandas().

Example

R

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.

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)
#> $runs
#>   run vehicle max_load  distance
#> 1   0       0 25.78821 16.929475
#> 2   1       0 31.75943 29.029139
#> 3   2       1 34.12677 20.601801
#> 4   3       1 41.60558 30.176394
#> 5   4       0 22.65398 14.329082
#> 6   5       0 21.76854 14.231704
#> 7   6       0 14.34672  6.043174
#> 8   7       0 30.58007 36.895550
#> 
#> $sites
#>    site    demand
#> 1     0 14.148060
#> 2     1 14.370754
#> 3     2  7.861395
#> 4     3 13.304476
#> 5     4 11.417455
#> 6     5 10.190959
#> 7     6 12.365883
#> 8     7  6.346666
#> 9     8 11.569923
#> 10    9 12.050648
#> 11   10  9.577418
#> 12   11 12.191123
#> 13   12 14.346722
#> 14   13  7.554288
#> 15   14  9.622928
#> 16   15 14.400145
#> 17   16 14.782264
#> 18   17  6.174874
#> 19   18  9.749971
#> 20   19 10.603327
#> 
#> $visits
#>    run site order      load
#> 1    1    0     2  0.000000
#> 2    0    1     0 11.417455
#> 3    1    2     0 23.898031
#> 4    3    3     1 21.954433
#> 5    0    4     1  0.000000
#> 6    2    5     0 23.935806
#> 7    2    6     2  0.000000
#> 8    3    7     0 35.258910
#> 9    2    8     1 12.365883
#> 10   4    9     0 10.603327
#> 11   5   10     0 12.191123
#> 12   5   11     1  0.000000
#> 13   6   12     0  0.000000
#> 14   3   13     3  0.000000
#> 15   7   14     1  6.174874
#> 16   3   15     2  7.554288
#> 17   7   16     0 15.797802
#> 18   7   17     2  0.000000
#> 19   1   18     1 14.148060
#> 20   4   19     1  0.000000

# returns the total cost / distance
# (the quantity that is minimized by CVRP)
print(milkr_cost(solution))
#> [1] 168.2363

# returns the savings resulting from the heuristic optimization procedure
print(milkr_saving(solution))
#> [1] 168.7352

The R package has a built-in plotting function (using ggplot) for the result. The individual runs are distinguished by color. The site locations are marked with round circles while the depot is depicted as a square. The line types (solid/dashed/…) are associated to different vehicle types.

plot(solution)

Python

The following example solves a small problem with a fixed set of demands and distances, applies the Clarke-Wright algorithm to generate quasi-optimal vehicle runs, and shows the resulting vehicle run solution.

import heumilkr as hm

solution = hm.clarke_wright(
    demand=[3, 2, 4, 2],
    # distances between all locations, the first one is the depot
    distances=[
        [0, 1, 1, 2, 3],
        [1, 0, 2, 1, 2],
        [1, 2, 0, 3, 4],
        [2, 1, 3, 0, 1],
        [3, 2, 4, 1, 0],
    ],
    # one vehicle with capacity 6, and an unlimited number with capacity 9
    vehicles=[hm.Vehicle(capacity=6, count=1), hm.Vehicle(capacity=9)],
)

for run in solution.runs:
    print(run)
#> Run(id=0, vehicle=1, sites=(0, 2, 3), loads=(6.0, 2.0, 0.0), distance=6.0, max_load=9.0)
#> Run(id=1, vehicle=0, sites=(1,), loads=(0.0,), distance=2.0, max_load=2.0)

# returns the total cost / distance
# (the quantity that is minimized by CVRP)
print(solution.cost())
#> 8.0

# returns the savings resulting from the heuristic optimization procedure
print(solution.saving())
#> 6.0

How the Algorithm Works

The following animation, made with the R package, shows how the Clarke-Wright algorithm iterates to arrive at its final solution:

Runtime Benchmarks

The benchmarks were taken on an Intel® Xeon® CPU E3-1231 v3 @ 3.40GHz CPU, through the R package using bench. The solver itself is the same C++ code in Python, but converting inputs and results adds some overhead that differs between the two packages.

The following graph shows the run time on one kind of problem: uniformly distributed random sites, demands between 5 and 15 and a vehicle capacity of 33. It amounts to $\sim 764µs$ for $n = 110$, $\sim 26.9ms$ for $n = 1010$, and $\sim 110ms$ for $n = 1910$. Run times can differ for other problems.

Documentation

The two packages have separate documentation sites:

Feature Differences

Both packages include the solver with all its options (backhaul, vehicle types and restrictions) and calculate the cost and savings of a solution. The following is only part of the R package:

References

Clarke, G., and J. W. Wright. 1964. “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points.” Operations Research 12 (4): 568–81. https://doi.org/10.1287/opre.12.4.568.