VRP	Previous  Top  Next

The VRP functions can help solving the basic multiple vehicle TSP problem, known as VRP. Problem is there are more customers to visit than a single vehicle can handle, so multiple routes has to be calculated. Below is listed the options available in this algorithm:

1.	It is possible to define 2 load values for all customers. This can be number of passengers and weight for instance.

2.	The maximum load is the same for all vehicles.

3.	It is possible to define a service time for all customers (it takes X minutes to make a stop).

4.	The maximum length (km or miles) and / or duration of the routes can be defined. This is the same for all vehicles.

5.	It can be defined if the routes should be round-trips, in-bound or out-bound.

There are 3 algorithms available to choose between. Each of them may perform best for different kind of problems.

The map below show an example of the Sweep algorithm in out-bound mode. The red marker shows the depot:



This sample code is based on the standard demo data and generates the map seen above:

rwnetbase1.NWLoad
rwcalc1.ExtraVarCreate
rwcalc1.SetFastest

// 40 km/h on all links
for i = 1 to rwnetbase1.LinkMax
  rwnetbase1.SetLinkSpeed(i,40)

centernode = 1  // Node 1 = the depot
N = 100         // 100 customers, we use node 21-120 for ease
tripmode = 1    // tripmode 1 (out-bound)

rwcalc1.VRPcreate(N)

// setup coordinates
rwcalc1.VRPcoordinate(0,rwnetbase1.NodeCoordX(centernode),rwnetbase1.NodeCoordY(centernode))
for i = 1 to N 
  rwcalc1.VRPcoordinate(i,rwnetbase1.NodeCoordX(i+20),rwnetbase1.NodeCoordY(i+20))

// demand1 = 1 person
// servicecost = 2 minutes to pick up each person
for i = 1 to N
  rwcalc1.VRPcustomer(i,1,0,2,0)

// maxload1 = 12 persons in each vehicle, max time = 35 minutes
rwcalc1.VRPvars(12,0,35,0)

// determine cost matrix
for i = 0 to N
begin
  if i=0 then startnode = centernode else startnode = i+20
  rwcalc1.IsoCost(startnode,0)
  for j = 0 to N
  begin
    if j=0 then endnode = centernode else endnode = j+20
    rwcalc1.VRPmatrix(i,j,rwcalc1.GetNodeCost(endnode),0)
  end
end

// Run model
rwcalc1.VRPrunSweep(tripmode)

// Get main results back
rwcalc1.VRPresults(routecount,cost,extra)

// create a GIS file showing all routes
RWcalc1.RouteFileCreate("route2",1)
RWcalc1.RouteFileFieldAdd("routeID",2,0,0)

for i = 1 to routecount
begin
  // get route-specific results back
  rwcalc1.VRPresultsRoute(i,customercount,cost,extra,load1,load2)
  for j = 1 to CustomerCount
  begin
    index1 = j
    index2 = j+1
    if j=CustomerCount then index2 = 1
    if index1=1 then
      node1 = centernode else
      node1 = rwcalc1.VRPresultsRouteIndex(i,index1)+20
    if index2=1 then
      node2 = centernode else
      node2 = rwcalc1.VRPresultsRouteIndex(i,index2)+20
    if  (tripmode=0) or
       ((tripmode=1) and (j<>CustomerCount)) or
       ((tripmode=2) and (j<>1)) then
    begin
      rwcalc1.Route(node1,node2)
      length = RWcalc1.RouteFind(node2)-1
      RWcalc1.RouteFileRecordAdd(length,inttostr(i))
      for k = 1 to length
        rwcalc1.RouteFileRecordAddSection(abs(rwcalc1.RouteGetLink(k)),0,1)
    end
  end
end
rwcalc1.RouteFileClose
rwcalc1.VRPdrop