Within the Traveling Salesman Problem there is a specific number of nodes to be distributed on the shortest possible path, where no capacities are to be considered. If one, however, would include the demands of all the single nodes there would have to be assumed that the capacity of the vehicle used is greater than or equal to the sum of the demands of all nodes.
However, if the entire amount to be delivered or picked up is exceeding the capacity of one single vehicle the nodes need to be supplied via multiple routes. This sort of problems belongs to the group of Vehicle Routing Problems.
In Vehicle Routing Problems a number of demand nodes is to be delivered from a depot. The demand of each node need is known and it is less than or equal to the capacity of the type of vehicle used. The demands of the destinations are to be distributed in accordance with the capacity of the vehicles on individual tours. For the single tours the routes from the depot to the assigned demand node and back to the depot need to be found. Therewith the total costs or the entire length of run of all tours shall be minimized.
To solve the Symmetric Vehicle Routing Problem LogisticsLab/VRP
can be used. As a construction algorithm, the Savings/P-, the
Savings/PM- and the Sweep Method are implemented, which can also
be combined with an improvement approach based on the 3-opt algorithm.