PGP ’11 student, Kapil Vaish, An Operations enthusiast shares his insight on MILP Model for Clark Algorithm
MILP Model for Clark Algorithm: Vehicle routing Algorithm
In a vehicle routing algorithm you would have come across Clark’s algorithm at some point of time. It is a very effective tool to decide the vehicle routing when fleet size is infinite for us but carrier carrying the load is fixed. Algorithm uses the saving method to decide the optimal no of carriers and best possible combination of nodes to get the minimum cost (Distance traveled).
I have attempt a mix integer linear programming model on vehicle routing algorithm. Let’s see how I formulated the model to get the optimal solution. I took help of the research paper by Francois Cote and Yves Potvin on “A tabu search heuristic for the vehicle routing problem with private fleet and common carrier” published in May 2007.
Problem Formulation:
The problem can be formulated as a directed graph having n vertex (nodes) where 0 is the depot from where the carrier starts and end, and others are customers to be visited. Distance (Cost) associated between the pair of vertices are given by Cij where i,j are vertex and i≠j. Every vertex has a defined demand Di. Also every carrier has a limited capacity of Q units to carry, fleet size is infinite. The goal of the routing problem is to design at most m routes for the fleet such that:
- Carrier serves single route that starts and end at the depot,
- Every customer is visited exactly once,
- Total demand on each route should not exceed the capacity Q of carrier,
Such that total distance (cost) is minimized
Subject To:
A formulated model is given in the link below. Model is developed on a small problem with 6 nodes only. But it has a great potential to be applied on day to day companies vehicle routing decision.
Hope excel attached would be very helpful for you. Sheet clark algo is the formulated model and sheet Practice is a practice exercise for you.
Download Excel : Clark
The IIM Kashipur Blog 