Vehicle Routing Problems with Time Windows and
Multiple Service Workers
Combined Learning for Clustering and Routing
Gerald Senarclens de Grancy <gerald@senarclens.eu>,
EULOG, November 2014, Vienna
Delivery of soft drinks to small and medium sized retailers in São Paulo:
{ "name": "presentation 3", "description": "This instance is for presentation/ demo purposes. It can also be used to test the efficiency of algorithms as it is designed with an optimal solution in mind. It can be solved with three trucks - one with one, the second with two and the third with three service workers. Parking at the customer sites is forbidden by an extremely high penalty.", "truckCapacity": 100.0, "costTruck": 1.0, "costWorker": 0.1, "costDistance": 0.0001, "bestKnownTrucks": 3, "bestKnownWorkers": 6, "bestKnownDistance": 410.9302842022, "bestKnownCost": 3.6410930284, "bestKnownSolution": "3;0;1,6,10;2,5;3,8,12,11,14;4,9,13,7;0 2;0;15,21,27,23,30;18,28,25,24;16,20,26;19,22;17,29;0 1;0;31,47,43;35,40;32,45,49;36,41;31,48;33,46,42,44;0", "optimumKnown": true, "depot": { "id": 0, "x": 0.0, "y": 0.0, "est": 0.0, "lst": 480.0}, "parkings": [ { "id": 1, "x": -29, "y": -31 }, ... { "id": 39, "x": -1, "y": 36 } ], "clients": [ { "id": 5, "x": -39, "y": -9, "demand": 10, "est": 0, "lst": 240, "st": 5 }, ... { "id": 49, "x": 53, "y": -9, "demand": 10, "est": 0, "lst": 480, "st": 5 } ] }
num_ants
iterations, a memory data structure is updated to allow learning from the best known solutioncluster.attractiveness() * trail(cluster.parking, cluster.client)
cluster.evaluate_addition(client) * trail(cluster, client)
cost clusters trucks workers distance average before: 41.24 89.46 32.80 81.06 3424.06 average after: 36.81 47.13 28.81 77.26 2730.73 average delta: 4.43 (-10.74%) 3.99 (-12.15%) 3.80 ( -4.68%) 693.33 (-20.25%) best after: 34.98 46.74 27.33 73.83 2611.35 best delta: 6.26 (-15.19%) 5.47 (-16.67%) 7.23 (-8.91%) 812.71 (-23.74%)