capacitated vrp with time windows about scikit-opt HOT 9 CLOSED

Yes, it can do, but with a little complex, because I didn't attempt to cover CVRP.

As an example, we want to minimize the total distance, with max capacity.

Define the problem

import numpy as np
from scipy import spatial
import matplotlib.pyplot as plt

num_customers = 15
num_vehicle = 5
num_points = 1 + num_customers
max_capacity = 5

customers_coordinate = np.random.rand(num_points, 2)  # generate coordinate of points
depot_coordinate = np.array([[0.5, 0.5]])
points_coordinate = np.concatenate([depot_coordinate, customers_coordinate], axis=0)


distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')


def cal_total_distance(routine):
    '''The objective function. input routine, return total distance.
    cal_total_distance(np.arange(num_points))
    '''
    num_points, = routine.shape
    return distance_matrix[0, routine[0]] \
           + sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)]) \
           + distance_matrix[routine[-1], 0]


def constraint_capacity(routine):
    capacity = 0
    c = 0
    for i in routine:
        if i != 0:
            c += 1
        else:
            capacity = max(capacity, c + 1)
            c = 0
    capacity = max(capacity, c + 1)
    return capacity - max_capacity

Run GA

from sko.GA import GA_TSP

ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=500, prob_mut=1, )

ga_tsp.Chrom = np.concatenate([np.zeros(shape=(ga_tsp.size_pop, num_vehicle - 1), dtype=np.int), ga_tsp.Chrom], axis=1)
ga_tsp.has_constraint = True
ga_tsp.constraint_ueq = [constraint_capacity]
best_points, best_distance = ga_tsp.run()

Plot

fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([[0], best_points, [0]])
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
ax[1].plot(ga_tsp.generation_best_Y)
plt.show()

Looking good

You may want to use constraint_eq and constraint_ueq to deal with time window or other constraint, see https://scikit-opt.github.io/scikit-opt/#/en/README?id=_1-differential-evolution

from scikit-opt.

Thanks a lot!

from scikit-opt.

@guofei9987 dalao能稍微解释一下def constraint_capacity(routine):这个函数吗，routine 传入的这个参数是什么？我没看懂这个不等式是怎么表达的。。。。
总距离矩阵为什么加上了distance_matrix[0, routine[0]]与distance_matrix[routine[-1], 0]？

from scikit-opt.

@guofei9987 dalao能稍微解释一下def constraint_capacity(routine):这个函数吗，routine 传入的这个参数是什么？我没看懂这个不等式是怎么表达的。。。。
总距离矩阵为什么加上了distance_matrix[0, routine[0]]与distance_matrix[routine[-1], 0]？

这是 vrp 问题，多辆货车去送货，constraint_capacity 计算的是每辆车的最大载重（约束为每次最多过max_capacity个点）。
cal_total_distance 这个函数是计算总路径，不过这个路径比较特殊，预先限定了多辆车，每辆车回到原点。

你的 #58 问题比这个问题简单很多，只需要改变一下目标函数 cal_total_distance ，只把中间n-2个点作为自变量即可。

from scikit-opt.

ga_tsp.Chrom = np.concatenate([np.zeros(shape=(ga_tsp.size_pop, num_vehicle - 1), dtype=np.int), ga_tsp.Chrom], axis=1)

Maybe there are some mistakes?
New Chrom includes point zero 5 times (1 zero in original Chrom and 4 zeros in np.zeros).
However, there are 4 zeros at most excluding the starting and ending.
It seems that this doesn't change the result. Adding 4 or 6 np.zeros will only add something like [0 0 0] to best_points.

from scikit-opt.

ga_tsp.Chrom = np.concatenate([np.zeros(shape=(ga_tsp.size_pop, num_vehicle - 1), dtype=np.int), ga_tsp.Chrom], axis=1)

Maybe there are some mistakes?
New Chrom includes point zero 5 times (1 zero in original Chrom and 4 zeros in np.zeros).
However, there are 4 zeros at most excluding the starting and ending.
It seems that this doesn't change the result. Adding 4 or 6 np.zeros will only add something like [0 0 0] to best_points.

Thanks for pointing out the mistake. I wrote this code in too hurriedly to check again.

(Besides, the parameter was not good, either)

import numpy as np
from scipy import spatial
import matplotlib.pyplot as plt

num_customers = 17
num_vehicle = 5
num_points = 1 + num_customers
max_capacity = 5

customers_coordinate = np.random.rand(num_points, 2)  # generate coordinate of points
depot_coordinate = np.array([[0.5, 0.5]])
points_coordinate = np.concatenate([depot_coordinate, customers_coordinate], axis=0)

distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')


def cal_total_distance(routine):
    '''The objective function. input routine, return total distance.
    cal_total_distance(np.arange(num_points))
    '''
    num_points, = routine.shape
    return distance_matrix[0, routine[0]] \
           + sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)]) \
           + distance_matrix[routine[-1], 0]


def constraint_capacity(routine):
    capacity = 0
    c = 0
    for i in routine:
        if i != 0:
            c += 1
        else:
            capacity = max(capacity, c + 1)
            c = 0
    capacity = max(capacity, c + 1)
    return capacity - max_capacity

Let the index of customers range from 1 to num_customers, and add num_vehicle - 1 zeros in the middle. We already hav start point and end point in function constraint_capacity.

from sko.GA import GA_TSP

ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_customers, size_pop=50, max_iter=500, prob_mut=1, )

ga_tsp.Chrom = np.concatenate([np.zeros(shape=(ga_tsp.size_pop, num_vehicle - 1), dtype=np.int), ga_tsp.Chrom+1], axis=1)
ga_tsp.has_constraint = True
ga_tsp.constraint_ueq = [constraint_capacity]
best_points, best_distance = ga_tsp.run()

Plot it

fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([[0], best_points, [0]])
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
ax[1].plot(ga_tsp.generation_best_Y)
plt.show()

This code seems to be terrible to read. I will work out another one later.

from scikit-opt.

how can I change this vrp code to simulates annealing and ant colony optimization?

from scikit-opt.

how can I change this vrp code to simulates annealing and ant colony optimization?

Reuse the objective function, some changes might be needed.

from scikit-opt.

sa用法一样嘛？

from scikit-opt.