Differential Evolution for Permutation-Based Combinatorial Problems - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 24

The formulation of this problem shows that DPP model is a function of i th placement
in a sequence b ( i ),and i th component in a pick sequence, m ( i ). This is obviously a
permutative-based combinatorial optimization problem which is challenging to solve.

2.2.5 Vehicle Routing Problem

Vehicle routing problem is delivery of goods to customers by a vehicle from a depot
(see Fig 2.7). The goal here is to minimize the travelling distance and hence save cost.
Here too an objective function would be created and inserted into the optimizer in order
to obtain the best travelling path for which the cost is minimized. The application of
vehicle routing problem can be applied in many places. One example is bin picking

problem. In some countries, the City Council bears a lot of extra costs on bin-picking
vehicle by not following shortest path.

−

routes

Depot customer

Fig. 2.7. DPP model

The CVRP is described as follows: n customers must be served from a unique depot.
Each customer asks for a quantity for quantity q i (where i = 1 , 2 , 3 ,..., n ) of goods and
a vehicle of capacity Q is available for delivery. Since the vehicle capacity is limited,
the vehicle has to periodically return to the depot for reloading. Total tour demand is at
most Q (which is vehicle capacity) and a customer should be visited only once [5].

2.2.6 Facility Location Problem

In facility location problem, we are given n potential facility location and m customers
that must be served from these locations. There is a fixed cost c j of opening facility j .
There is a cost d ij associated with serving customer i from facility j .Wethenhavetwo
sets of binary variables which are y j is 1 if facility j is opened, 0 otherwise x ij is 1 if
customer i is served by facility j , 0 otherwise.