This paper proposes a combined tactical and operational two stage food grain transportation model with linear formulation in the first stage and a mixed-integer non-linear problem (MINLP) in the second stage taking the case of India. Transportation cost is minimized in both stages to fulfil a deterministic demand. First and the second stages correspond to the movement of food grains in between state and central level warehouses respectively. A novel k-parameter based method of constraint handling has been proposed. Further, the two stage MINLP formulation newly incorporates vehicle capacity constraints and proposes a generic metric for measuring vehicle utilization. First stage is solved by CPLEX and for the second stage, two population based random search techniques: Particle swarm optimization-composite particle (PSOCP) and PSO, have been employed. Experimentations on 10 different problem sets reveal that PSOCP performs marginally better than PSO with lesser standard deviation of global fitness and better solution quality with slightly higher CPU time. Later, sensitivity analysis is conducted on all ten problem sets and a decision support framework is proposed to assist potential stakeholders. © 2017 Elsevier Ltd