irb-lab / py-ga-vrptw Goto Github PK

学长您好，偶然学习到您的程序，算法实现非常严谨。但有一个问题，观察您上传的result，感觉fitness随generation收敛速度有些慢，甚至感觉没有得到实质性的收敛，我初学可能理解不是很深刻，希望能得到您的指教。
BYR

Most of the things in this code follow python2 and their results are not as intended in Python 3. Users should take caution in using functions in this code.

The selection function in this code is making the length of population to converge to zero in few generations, which can not be a feature of genetic algorithms.

First of all thanks for your great code! It's very well written and documented.

I plotted the fitness values (min, max: blue; avg: green) for the solution process of the provided R101 example. I am wondering, if the algorithm performs well, because the max value doesn't increase and even dicreases after a view generations.

I'm not sure, if I'm right, but in my point of view that means that the best individual is already being created with the initialization of the problem. Furthermore the optimal solution (max) seems to be getting worser during the solution procedure. I guess it should be the other way round, so that the optimal solution (max value) gets better over time. I observed this behavior for other examples, too.

Do you have an idea what the problem could be here? Maybe something with the operators? Or am I totally wrong with my understanding of the plot?

Thanks a lot for your support!

Very thanks for your code. I'm very interested in applying genetic algorithm in vehicle route problem (VRP).

In the code, I turned this code for VRPTW into a general VRP problem by doing the following modifications:

1. Calculate the distance matrix with Euclidean distance between any two coordinates.
   

2. Set the waitCost to zero, and the delayCost to zero.

3. Remove the code related with dueTime as follows:
   line 28: updatedElapsedTime = elapsedTime + instance['distance_matrix'][lastCustomerID][customerID]
   line 30: if (updatedVehicleLoad <= vehicleCapacity):
   line 34: elapsedTime = updatedElapsedTime
   line 41: elapsedTime = instance['distance_matrix'][0][customerID]

At last, I get the results of routes:
Vehicle 1's route: 0 - 48 - 44 - 34 - 9 - 19 - 41 - 40 - 2 - 33 - 35 - 70 - 76 - 64 - 59 - 96 - 88 - 3 - 5 - 69 - 82 - 29 - 26 - 92 - 75 - 71 - 16 - 52 - 45 - 21 - 23 - 27 - 58 - 60 - 6 - 7 - 31 - 67 - 25 - 13 - 77 - 10 - 0
Vehicle 2's route: 0 - 54 - 24 - 94 - 18 - 50 - 53 - 56 - 38 - 14 - 81 - 79 - 63 - 61 - 73 - 66 - 86 - 55 - 20 - 100 - 8 - 95 - 89 - 22 - 74 - 4 - 90 - 91 - 12 - 85 - 93 - 65 - 87 - 49 - 72 - 84 - 39 - 47 - 0
Vehicle 3's route: 0 - 15 - 68 - 46 - 37 - 83 - 97 - 32 - 43 - 57 - 42 - 80 - 51 - 1 - 98 - 30 - 11 - 36 - 17 - 28 - 99 - 62 - 78 - 0

And I plot the route as follow. From the figure, we can observe the cost of generated routes is very expensive. I don't know what problems exist in the code. Can you provide some explanations for these problems.

The core code of mutation and cross doesn't work.
The new individual doesn't return normally.
This is the cross and mutation code.

def cx_partialy_matched(ind1, ind2):
    '''gavrptw.core.cx_partialy_matched(ind1, ind2)'''
    size = min(len(ind1), len(ind2))
    cxpoint1, cxpoint2 = sorted(random.sample(range(size), 2))
    temp1 = ind1[cxpoint1:cxpoint2+1] + ind2
    temp2 = ind1[cxpoint1:cxpoint2+1] + ind1
    ind1 = []
    for gene in temp1:
        if gene not in ind1:
            ind1.append(gene)
    ind2 = []
    for gene in temp2:
        if gene not in ind2:
            ind2.append(gene)
    return ind1, ind2


def mut_inverse_indexes(individual):
    '''gavrptw.core.mut_inverse_indexes(individual)'''
    start, stop = sorted(random.sample(range(len(individual)), 2))
    individual = individual[:start] + individual[stop:start-1:-1] + individual[stop+1:]
    return (individual, )

In the run_gavrptw, you don't catch the return value.

for child1, child2 in zip(offspring[::2], offspring[1::2]):
            if random.random() < cx_pb:
                toolbox.mate(child1, child2)
                del child1.fitness.values
                del child2.fitness.values
        for mutant in offspring:
            if random.random() < mut_pb:
                toolbox.mutate(mutant)
                del mutant.fitness.values

You can change this bug by in-place update the individual in the cross and mutation code like

individual[start:stop+1] = individual[stop:start-1:-1]

Hi. what is the unit of time windows? is it second or hour? and why we need service time? can we ignore it?

我看了一下实现代码，好像没有找到关于车辆限制的的约束处理，我把R101.json的最大车辆数量改成了3，运行sample_R101.py的结果仍然有5个车辆路线。sub_route的分割逻辑是顺序分割，并没有对sub_route的数量进行约束？

Hi，
我刚看了你的代码，很漂亮。但是有一点问题想请教一下。
你的初始解，只考虑了车辆的capacity和due_time，但是并没有考虑到每个custom的时间窗，如果你要是比当前站点的ready_time还要早，那应该需要等到ready_time，然后再加上服务时间。但是在ind2route中，并没有考虑到这点，是有什么trick么？

谢谢！

Hi, first of all thank you for the well documented code - it has helped me a lot with my research project. I wanted to ask - in the run_gavrptw() function , why do we evaluate the individuals with invalid fitness?

It seems like you're trying to save the individuals with really bad fitness scores but I'm wondering why you're doing that. Thanks!

关于你这个项目 有些问题想请教 能给个联系方式嘛

Hello, first of all thank you for the repo as it provided a great starting point for me to adapt the GA procedure to solve VRP with movement synchronizations. From my experience, I find that using an elite selection process will help improve your code performance. So I used the built-in elite selection function from deap - selBest() and keep that individual to the next generation. You can elite select x% of the percentage as you see fit.

Another thing is I found there was a small error with your implementation of the PMX function, I suggest use the built in one from deap but make a small modification to the indexing to account for the depot number convention. This will make the PMX function work as intended and create better offsprings. With these two changes implmented, it can converge VRP solutions very quickly.

Sorry that I am writing this as an issue as opposed to making a pull request. I am fairly new to git and I didn't know which is the more efficient way when I already made a fork but committed too many changes that are not relevant to your repo anymore.

Let me know if I can still make a pull-request and help you improve this awesome repo.

Hi. How I can run the code for 1 vehicle and d customers and without any time constraints. (assuming that 1 vehicle has the capacity to deliver all orders). I want a single rout answer.

Does the paremater max_vechicle_number has an effect on the result?

Hey, I have been trying the code and I discovered that max_fitness is not changing within number of generations. It makes the result always the same, even if there is only 1 generation. Firstly I was convinced that it can be library versioning or something connected to that, but the issue is also visible in the result csv's (max_fitness column does't seem to change).

Hello,

I am trying to run the algorithm on all of Solomon's data sets to analyse the performance of the library.

1. Are there existing benchmarks where I could find such results ?

2. I am unable to find feasible solutions. In particular, the routes that are computed violate the time windows (the arrival time is after the upper time window). I have tried setting a very high delay_cost, but this does not prevent the algorithm from violating the time windows (the due time).

Thanks for your help!