Finds a quasi-optimal solution to the Capacitated Vehicle Routing Problem (CVRP). It is assumed that all demands will be satisfied by a single source.
clarke_wright(demand, distances, vehicles, restrictions = NULL)Returns a "heumilkr_solution" object, a data.frame() with one row per
site-run combination bestowed with additional attributes. Its columns
consist of:
site - The site index (i.e. the index of the demand vector) associated
to the run.
run - Identifies the run the site is assigned to.
order - Integer values providing the visiting order within each run.
vehicle - The vehicle type index (as provided in vehicles) associated
to the run.
load - The actual load in units of demand on the particular run.
distance - The travel distance of the particular run.
Unless a site demand exceeds the vehicle capacities it is always assigned to only a single run.
A numeric vector consisting of "demands" indexed by sites.
The ith entry refers to the demand of site i (and the length
of the vector equals the number of sites N with demands). The
units of demand values need to match the units of vehicle capacity values.
NA values are not allowed.
An object of class dist, created by stats::dist(), with
(N + 1) locations describing the distances between individual
sites. The first index refers to the source site. The (i+1)th
index refers to site i (as defined by demand).
A data.frame() describing available vehicle types and their respective
capacities. One row per vehicle type. The data frame is expected to have
two columns:
n - Number of available vehicles. This can be set to NA if the
number is "infinite" (i.e. effectively the maximal integer value
on your machine.).
It is recommended to keep at least one vehicle type as "infinite",
otherwise the solver might raise a run time error due to initially
not having enough vehicles available (even though the final
solution might satisfy the availability restrictions).
caps - The vehicle capacity in same units as demand.
The order of the data.frame() is relevant and determines the prioritization
of vehicle assignments to runs (in case two or more vehicle types are
eligible for assignment the "first" vehicle is chosen). In a typical scenario
"more expensive" vehicles should be further down in the list (so the cheaper
one is chosen in case there is doubt). Since higher capacity vehicles
usually involve higher costs sorting the data frame by capacity is usually
a good rule of thumb.
An optional data.frame() that allows to define vehicle type restrictions for
particular sites in the form of a blacklist.
The data frame is expected to have two columns:
vehicle - The vehicle type index.
site - The site index (i.e. the index of the demand vector)
Each row defines a restriction: vehicle type vehicle can not approach site
site. Defaults to NULL, i.e. no restrictions are enforced.
See the original paper, Clarke, G. and Wright, J.R. (1964) tools:::Rd_expr_doi("10.1287/opre.12.4.568"), for a detailed explanation of the Clarke-Wright algorithm.
demand <- c(3, 2, 4, 2)
positions <-
data.frame(
pos_x = c(0, 1, -1, 2, 3),
pos_y = c(0, 1, 1, 2, 3)
)
clarke_wright(
demand,
dist(positions),
data.frame(n = NA_integer_, caps = 6)
)
Run the code above in your browser using DataLab