Capacitated Vehicle route optimization in real world using Artificial bee colony optimization and open street map in python

4 min readJul 21, 2020

Figure 1: A Street Map of Cologne, Germany showing the position of depot and positions of the customers

The capacitated vehicle routing problem (CVRP) is a Vehicle route problem in which vehicles with limited carrying capacity need to pick up or deliver items at various locations. The items have a quantity, such as weight or volume, and the vehicles have a maximum capacity that they can carry. The problem is to pick up or deliver the items for the least cost, while never exceeding the capacity of the vehicles.

The Capacitated Vehicle Routing Problem (CVRP) (i.e., the classical vehicle routing problem) is defined on a complete undirected graph G = (V,E) , where V = {1,…., n} is the vertex set and E = {(i, j ): i, j is in V, i < j} is the edge set. Vertices 1,…., n represent customers; each customer i is associated with a non-negative demand di and a non-negative service time Si. Vertex 0 represents the depot at which a fleet of m homogeneous vehicles of capacity Q is based. The fleet size is treated as a decision variable. Each edge (i, j) is associated a non-negative traveling cost or travel time cij.

The CVRP is to determine m vehicle routes such that:

(a) every route starts and ends at the depot;

(b) every customer is visited exactly once;

(c.) the total demand of any vehicle route does not exceed Q; and

(d) the total cost of all vehicle routes is minimized.

The real world CVRP is more complex than the solving CVRP theoretically assuming a straight line between the nodes. In the real world problem, we need to determine the shortest distance between the nodes by using a complex structure of Road and street network, which may looks like a spider web. I have used the example of cologne, Germany as an example to show how CVRP can be solved. There are 30 customers whose positions are shown in Figure-1. The location of depot is also marked in the map shown in Figure-1. I have used 5 vehicles with equal capacities for simplicity but the case can be generalized. To solve CVRP, I have used artificial bee colony optimization.

About Artificial bee optimization

The ABC algorithm belongs to a class of evolutionary algorithms that are inspired by the intelligent behavior of the honey bees in finding nectar sources around their hives. This class of meta-heuristics has only started to receive attention recently. Different variations of bee algorithms under various names have been proposed to solve combinatorial problems. But in all of them, some common search strategies are applied; that is, complete or partial solutions are considered as food sources and the groups of bees try to exploit the food sources in the hope of finding good quality nectar (i.e., high quality solutions) for the hive. In addition, bees communicate between themselves about the search space and the food sources by performing a waggle dance.

In the ABC algorithm, the bees are divided into three types; employed bees, onlookers and scouts. Employed bees are responsible for exploiting available food sources and gathering required information. They also share the information with the onlookers, and the onlookers select existing food sources to be further explored. When the food source is abandoned by its employed bee, the employed bee becomes a scout and starts to search for a new food source in the vicinity of the hive. The abandonment happens when the quality of the food source is not improved after performing a maximum allowable number of iterations.

Implementation

I have used total distance traveled by the vehicles as cost function to be minimized, however the cost function can be modified depending upon the problem. To calculate the distance between the nodes, I have used the road network of Cologne, Germany extracted by osmnx. The road network of cologne, Germany is shown in Figure-2.