Application of Graph Theory in Grain and Oil Deployment

Guangshu Xu, Zilong Song

School of Logistics, Beijing Wuzi University, Beijing, China.

DOI: 10.4236/jssm.2015.84051                

Abstract

The deployment of grain and oil is related to the daily needs of people and the stability of society. In this paper, we take the shortest path problem and the minimum cost maximum flow problem in graph theory as the theoretical basis. Through the establishment of distance matrix between the reserves station and the deployment warehouse or between reserve station and reserve station, we use the Floyd algorithm to calculate the shortest path between any two points in the matrix to determine the optimal deployment of the emergency plan. Through the establishment of mathematical model of the reserve station and deployment warehouse, we use the minimum cost maximum flow theory to solve the model and to obtain the deployment programs of grain and oil under normal circumstances. Through the combination of shortest path and minimum cost and maximum flow, we give the deployment plan under the general emergency situation and provide a new way for the deployment of the supply of grain and oil in each case.

Keywords

Short-Path, Min-Cost Max-Flow, Grain and Oil Deployment

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Mao, Y.J. (2013) Floyd Algorithm and MATLAB Program Realization of Shortest Path Problem. Journal of Hebei North University (Natural Science Edition), 29, 13-18.
[2]	Li, L. (2006) The Application of Shortest Path Problem in Transportation Network. Journal of Changchun Normal University (Natural Science), 25, 58-61.
[3]	Cao, X. and Zhang Z. (2012) Application of the Shortest Path Problem in the Tourist Route Optimization. Science Mosaic, 2, 115-118.
[4]	Feillet, D., Dejax, P., Gendreau, M. and Gueguen, C. (2004) An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints: Application to Some Vehicle Routing Problems. Networks, 44, 216-229. http://onlinelibrary.wiley.com/doi/10.1002/net.20033/abstract http://dx.doi.org/10.1002/net.20033
[5]	Klunder, G.A. and Post, H.N. (2006) The Shortest Path Problem on Large-Scale Real-Road Networks. Networks, 48, 182-194. http://dblp.uni-trier.de/search?q=The+shortest+path+problem+on+large-scale+real-road+networks http://dx.doi.org/10.1002/net.20131
[6]	Olivia, J.S. and Martin, W.P. (2014) A Note on Shortest Path Problems with Forbidden Paths. Networks, 63, 239-242. http://onlinelibrary.wiley.com/doi/10.1002/net.21541/abstract http://dx.doi.org/10.1002/net.21541
[7]	Chen, B.Y., Lam, W.H.K., Sumalee, A., Li, Q.Q. and Tam, M.L. (2014) Reliable Shortest Path Problems in Stochastic Time-Dependent Networks. Journal of Intelligent Transportation Systems, 18, 177-189. http://www.tandfonline.com/action/doSearch?quickLinkJournal=&journalText=&AllField=Reliable+Shortest+Path+Problems+in+Stochastic+Time-Dependent+Networks&publication=40000540 http://dx.doi.org/10.1080/15472450.2013.806851
[8]	Zhu, J.S., Zhu, Q., Wang, J., Li, J. and Liu, Z.P. (2002) Application of the Minimum Cost Maximum Flow Algorithm in Path Planning. Journal of Wuhan University of Technology (Transportation Science & Engineering), 26, 293-295.
[9]	Yang, J.H. and Gai, Y.X. (2005) Research on Making of Railway Transport Price Using Theory of Minimum Cost Maximum Amount. Journal of Lanzhou Jiaotong University (Natural Sciences), 24, 139-142.
[10]	Sun, H.D. and Wen, X.J. (2001) The Application of The Minimum Cost Maximum Flow Model in The Connecting Cargo Flights. Journal of Nanjing University of Aeronautics & Astronautics, 33, 478-481.
[11]	Ji, L. and Chi, H. (2005) Fire Resource Distribution Model Base on Multistage Process of Eliminating Fire. Systems Engineering, 23, 12-15.
[12]	An, N. and Zhuang, D.H. (2005) Optimization of Refined Oil Distribution System. China Petroleum Enterprise, 7, 60-61.
[13]	Wang, L. and Cao, D. (2009) The Optimization Model of Refined Oil Distribution System. Petrochemical Technology & Application, 27, 571-575.
[14]	Ahmed, N., Das, S. and Purusotham, S. (2013) The Problem of Maximum Flow with Minimum Attainable Cost in a Network. OPSEARCH, 50, 197-214. http://link.springer.com/article/10.1007/s12597-012-0106-1 http://dx.doi.org/10.1007/s12597-012-0106-1
[15]	Vaidyanathan, B. and Ahuja, R.K. (2013) Fast Algorithms for Specially Structured Minimum Cost Flow Problems with Applications. Operations Research, 58, 1681-1696. http://www.ncbi.nlm.nih.gov/nlmcatalog?term=%22Oper+Res%22%5Bta%5D http://dx.doi.org/10.1287/opre.1100.0846
[16]	Ou, Z.W. and Wang, J.Y. (2003) Emergency Logistics. Journal of Chongqing University, 27, 164-167.
[17]	He, M.K. (2003) The Loss of Emergency Logistics Costs Is Everywhere. China Logistics & Purchasing, 23, 18-19.
[18]	Sun, L.H. and Wang, X.Q. (2010) The Analysis of Emergency Logistics Situation and Development. China Safety Science Journal, 10, 165-169.
[19]	Ying, S.H. and Li, Y.X. (2009) Application of Dynamic Programming and Integer Programming in Emergency Materials Distribution Optimization. Logistics Technology, 28, 80-83.
[20]	Tang, W.Q. and Zhang, M. (2009) The Process Model of Large-Scale Emergency Supplies Scheduling. China Safety Science Journal, 9, 33-37.
[21]	Liu, C.L. and He, J.M. (2001) Optimization Model of a Kind of Emergency Materials Urgent Transportation Problem. Chinese Journal of Management Science, 9, 29-35.
[22]	Yuan, Y. and Wang, D.W. (2009) Path Selection Model and Algorithm for Emergency Logistics Management. Computers & Industrial Engineering, 56, 1081-1094. http://www.sciencedirect.com/science/article/pii/S0360835208002234 http://dx.doi.org/10.1016/j.cie.2008.09.033
[23]	Han, B.T. (2010) Shortest Path Problem. Operations Research, Academic Press, Beijing, 65-82.
[24]	National Bureau of Statistics of the People’s Republic of China. http://www.stats.gov.cn/tjsj/ndsj/2014/indexch.htm
[25]	Shandong Statistical Information Net. http://www.stats-sd.gov.cn/tjnj/nj2014/indexch.htm
[26]	Hebei Provincial Bureau of Statistics. http://www.hetj.gov.cn/hetj/tjsj/