A Lagrangian Decomposition Algorithm for Robust Green Transportation Location Problem


Department of Industrial Engineering, Shahed University, Teheran, Iran


In this paper, a green transportation location problem is considered with uncertain demand parameter. Increasing robustness influences the number of trucks for sending goods and products, caused consequently, increase the air pollution. In this paper, two green approaches are introduced which demand is the main uncertain parameter in both. These approaches are addressed to provide a trade-off between using available trucks and buying new hybrid trucks for evaluating total costs beside air pollution. Due to growing complexity, a Lagrangian decomposition algorithm is applied to find a tight lower bound for each approach. In this propounded algorithm, the main model is decomposed into master and subproblems to speed up convergence with a tight gap. Finally, the suggested algorithm is compared with commercial solver regarding total cost and computational time. Due to computational results for the proposed approach, the Lagrangian decomposition algorithm is provided a close lower bound in less time against commercial solver.


1.     Soyster, A.L., “Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming”, Operations Research,  Vol. 21, No. 5, (1973), 1154–1157.
2.     Ben-Tal, A., and Nemirovski, A., “Robust solutions of Linear Programming problems contaminated with uncertain data”, Mathematical Programming,  Vol. 3, No. 88, (2000), 411–424.
3.     Bertsimas, D., and Sim, M., “The Price of Robustness”, Operations Research,  Vol. 52, No. 1, (2004), 35–53.
4.     Hamidieh, A., Arshadikhamseh, A., and Fazli-Khalaf, M., “A Robust Reliable Closed Loop Supply Chain Network Design under Uncertainty: A Case Study in Equipment Training Centers”, International Journal of Engineering - Transactions A: Basics ,  Vol. 31, No. 4, (2018), 648–658.
5.     Fazli-Khalaf, M., and Hamidieh, A., “A Robust Reliable Forward-reverse Supply Chain Network Design Model under Parameter and Disruption Uncertainties”, International Journal of Engineering - Transactions B: Applications,  Vol. 30, No. 8, (2017), 1160–1169.
6.     Javadian, N., Modarres, S., and Bozorgi, A., “A Bi-objective Stochastic Optimization Model for Humanitarian Relief Chain by using Evolutionary Algorithms”, International Journal of Engineering - Transactions A: Basics,  Vol. 30, No. 10, (2017), 1526–1537.
7.     Gabrel, V., Lacroix, M., Murat, C., and Remli, N., “Robust location transportation problems under uncertain demands”, Discrete Applied Mathematics,  Vol. 164, (2014), 100–111.
8.     Hinojosa, Y., Puerto, J., and Saldanha-da-Gama, F., “A two-stage stochastic transportation problem with fixed handling costs and a priori selection of the distribution channels”, TOP,  Vol. 22, No. 3, (2014), 1123–1147.
9.     Carlo, H.J., David, V., and Salvat-Dávila, G.S., “Transportation-location problem with unknown number of facilities”, Computers & Industrial Engineering,  Vol. 112, , (2017), 212–220.
10.   Shen, Y., Wang, Q., Yan, W., and Wang, J., “A transportation-location problem model for pedestrian evacuation in chemical industrial parks disasters”, Journal of Loss Prevention in the Process Industries,  Vol. 33, , (2015), 29–38.
11.   Yilmaz, O., Kara, B.Y., and Yetis, U., “Hazardous waste management system design under population and environmental impact considerations”, Journal of Environmental Management,  Vol. 203, No. P2, (2017), 720–731.
12.   Geoffrion, A.M., “Lagrangean relaxation for integer programming”, In Springer, Berlin, Heidelberg, (1974), 82–114.
13.   Chen, W.-A., Zhu, Z., and Kong, N., “A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs”, Optimization Letters,  Vol. 12, No. 1, (2018), 155–169.
14.   Keyvanshokooh, E., Ryan, S.M., and Kabir, E., “Hybrid robust and stochastic optimization for closed-loop supply chain network design using accelerated Benders decomposition”, European Journal of Operational Research,  Vol. 249, No. 1, (2016), 76–92.
15.   Gupta, V., and Grossmann, I.E., “Offshore oilfield development planning under uncertainty and fiscal considerations”, Optimization and Engineering,  Vol. 18, No. 1, (2017), 3–33.