Capacitated Vehicle Routing Problem with Categories

Question

My problem resembles the capacitated vehicle routing problem but there is an aspect to it to which I've been unable to find a solution in tools like ESRI's Network Analyst.

The problem is to find the optimal route(s) in a network to visit target locations belonging to different categories, all of which have a given number of locations that must be visited. The issue is selecting the set of targets from a much larger group of target candidates resulting in the optimal route. Starting location is fixed.

Here's another way to describe the problem. A vehicle has items belonging to different categories and all of the items must be delivered. There are many destination candidates each having demand for one item from one of the categories. The vehicle has relatively few items, hence all the demand can't be satisfied and we need to find the destinations to which all of the items can be delivered with minimal cost.

How would you esteemed GIS folks approach this task?

Many thanks!

Answer 1

A working solution was found with ESRI's Network Analyst Vehicle Routing Problem tool. Here is a simple explanation, note that the tool also works in much more complex setting with dozens of capacity dimensions.

Say we have categories A, B, C & D from which we have to visit 10, 20, 30 & 40 locations, respectively. There are hundreds of candidate locations in each category.

The number of locations to visit in each category is given in a route's "Capacities" parameter delimited by space: '10 20 30 40'. In the same manner, for each target location candidate (called orders in the Network Analyst) a quantity of 1 corresponding to its class is given in the "DeliveryQuantities" parameter and zero for other classes, e.g. for a location in the class B one would insert '0 1 0 0'. Additionally, a matching Capacity Count (4) must be given in the Network Analyst's Analysis Settings.

Solving the VRP exhausts the route's capacities in each category and finds the optimal set of locations to visit from the much larger set. :)