I want to modify Clarke and wright saving algorithm so i can afford heterogeneous fleet. In my current project I implement the saving algorithm in c# to solve asymmetric capacitated vehicle routing problem and GMap.NET to visualize the route. But the saving algorithm only afford homogeneous fleet so I search in many literature. After many hours searching, I can't find suitable information. So is there any reference that explain about heterogeneous fleet in Clarke and Wright saving algorithm ?.
Note : this is my first question and I'm interested in vrp problem but I don't know where to ask. Sory about my english grammar.
Hi, the paper that introduced the Fleet Size and Mix VRP problem Golden et Al 1984 http://www.sciencedirect.com/science/article/pii/0305054884900078 in this work a variant of this constructive heuristics is used.
http://gujs.gazi.edu.tr/article/viewFile/1060001519/1060000877
http://www4.ncsu.edu/~kay/matlog/Matlog%20-%20Logistics%20Engineering%20using%20Matlab.pdf
http://www4.ncsu.edu/~kay/matlog/
I hope so, these links illuminate your mind.
Thank's for the references. I'l try to combine the algorithm for the heterogeneous fleet.
after some hour of code. I try two option for assign heterogeneous fleet. option 1 : explicit and early assignment for the route and option 2 : using saving algorithm sequentially and iterate all generate route so fulfill capacity constrain. But i have a problem , is it necessary to ordering the fleet according to the fleet capacity ?. I'm still unsure this problem will affect the route . Thank's
Hi, You should try the Successive Approximations Algorithm. This is a multi-round algorithm in which the number of rounds is limited by the number of vehicle types. Randomly you select a vehicle type assuming unlimited vehicles and solve the CVRP with the savings algorithm, then you remove the exceeding routes (if the number of routes is higher than the number of vehicles of that type). Non-removed routes are saved as partial solution. With the nodes belonging to the discarded routes are extracted so they can be routed in the next round. In successive rounds, another type of vehicle is selected and a new VRP (considering unrouted nodes) is solved following the previous steps.
Thank's for the answer. I'll try the suggestion also I found paper related to my question although I can't implement it in my program. https://www.researchgate.net/publication/265778994_A_savings_based_method_for_real-life_vehicle_routing_problems
Article A savings based method for real-life vehicle routing problems
- Badges
- Science topic