search

iRB-Lab / py-ga-VRPTW

A Python Implementation of a Genetic Algorithm-based Solution to Vehicle Routing Problem with Time Windows
MIT License
560 stars 170 forks source link

About the performance #4

Closed AlgorithmFan closed 6 years ago

AlgorithmFan commented 6 years ago

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. image

  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.

figure_1

AlgorithmFan commented 6 years ago

In my view, the cross over function might have some errors. Please reference the method of the deap libariry. https://github.com/DEAP/deap/blob/master/deap/tools/crossover.py

iROCKBUNNY commented 6 years ago

@AlgorithmFan Thank you and your nice work. It looks like your results were not yet converged. The parameters of the GA have to be tuned to get the best results.

I implemented my own cross over function which in a certain case was suitable for my solution. You can try other cross over functions (either from the DEAP library or written by yourself) as well.